• We’re currently investigating an issue related to the forum theme and styling that is impacting page layout and visual formatting. The problem has been identified, and we are actively working on a resolution. There is no impact to user data or functionality, this is strictly a front-end display issue. We’ll post an update once the fix has been deployed. Thanks for your patience while we get this sorted.

Discrete Math help

T

tfinch2

Lifer
Derive a formula to calculate the combinations if you have n integers (1 to n) to where the nth digit can't be in the nth spot of the combination.

Example: {2 3 1} is good but but {3 2 1} is bad because 2 is in the second spot.
Example 2: {2 3 1 5 4} is good but {1 5 2 3 4} is bad because 1 is in the first spot.

Help please?
 
2 possibilities for the middle digit, leaving two other possible combinations each for the remaining digits (the 2 is either first or last)?

I dunno, haven't taken discrete math yet.
 
it's basically the Mississippi problem: you have so many combinations, but have to divide out the ones that are bad.
 
If I did it right

1 number = 0 options
2 numbers = 1 option
3 numbers = 2 options
4 numbers = 6 options
5 numbers = 64 options

Thats as far as I could get with it. Dunno of what formula could work though. Sorry.
 
so if you have 5 digits, then the 5 can be in for different places....so if you have n digits, any n can only be in n-1 different places....

thats my contribution for today
 
Originally posted by: Semidevil
so if you have 5 digits, then the 5 can be in for different places....so if you have n digits, any n can only be in n-1 different places....

thats my contribution for today
Click to expand...

So if you are using the set {1 2 3} 3 can be in 2 spots, but 2 can only be in 1 spot depending on 3, and the same with 1. Not quite that easy.
 
Originally posted by: tfinch2
Originally posted by: Semidevil
so if you have 5 digits, then the 5 can be in for different places....so if you have n digits, any n can only be in n-1 different places....

thats my contribution for today
Click to expand...

So if you are using the set {1 2 3} 3 can be in 2 spots, but 2 can only be in 1 spot depending on 3, and the same with 1. Not quite that easy.
Click to expand...

*head explodes*


hm....so if n is a subset of N. then n has n-1 choices. give another m...then m has (m-1) + (n - 1) choices...and you can go until you reach 0...


p.s. just so you know. I really dont know what im doing here...i'm just trying to give you an idea, so maybe you can get something going...

*heads explodes again*
 
Originally posted by: MartyMcFly3
If I did it right

1 number = 0 options
2 numbers = 1 option
3 numbers = 2 options
4 numbers = 6 options
5 numbers = 64 options

Thats as far as I could get with it. Dunno of what formula could work though. Sorry.
Click to expand...

3421
3412
3142
2413
2143
2341
4321
4123
4312

it looks like (n-1)^(n-2)
 
Originally posted by: JetBlack69
Originally posted by: MartyMcFly3
If I did it right

1 number = 0 options
2 numbers = 1 option
3 numbers = 2 options
4 numbers = 6 options
5 numbers = 64 options

Thats as far as I could get with it. Dunno of what formula could work though. Sorry.
Click to expand...

3421
3412
3142
2413
2143
2341
4321
4123
4312

it looks like (n-1)^(n-2)
Click to expand...

I knew that number seemed low. 😛
 
Originally posted by: JetBlack69
Originally posted by: MartyMcFly3
If I did it right

1 number = 0 options
2 numbers = 1 option
3 numbers = 2 options
4 numbers = 6 options
5 numbers = 64 options

Thats as far as I could get with it. Dunno of what formula could work though. Sorry.
Click to expand...

3421
3412
3142
2413
2143
2341
4321
4123
4312

it looks like (n-1)^(n-2)
Click to expand...


Ding Ding Ding! We have a winner.

Thanks for the help!
 
Originally posted by: chuckywang
Set up a recurrence relation:

for n numbers, define P(n) to be the number of ways to arrange them such that n is not in the nth spot.

Then,

P(n) = (n-1)*P(n-1) and we know that P(2) = 1.

With a little thinking, it is easily determined that P(n) = (n-1)!
Click to expand...


So for {1 2 3 4 5} P(n) = 4! but 4 x 3 x 2 x 1 = 24 when there are 64 options
 
First, I think you're using the word "combination" incorrectly since order matters in the answer. So we're looking at permutations. I think the answer is n! - (n - 1)!

The reasoning is that you start with all possible n-digit permutations. Then you ask yourself, how many ways can I fvck this up? The answer is, you fix the nth digit in the nth spot, and then come up with all the permutations of the remaining digits around it. There are (n - 1)! different permutations if one of the digits is fixed.
 
Originally posted by: KingNothing
First, I think you're using the word "combination" incorrectly since order matters in the answer. So we're looking at permutations. I think the answer is n! - (n - 1)!

The reasoning is that you start with all possible n-digit permutations. Then you ask yourself, how many ways can I fvck this up? The answer is, you fix the nth digit in the nth spot, and then come up with all the permutations of the remaining digits around it. There are (n - 1)! different permutations if one of the digits is fixed.
Click to expand...


But take { 1 2 3}

3! - 2! = 4 but there are only 2 ways to arrange the numbers.
 
Ok, I got this wrong the first time I did it. As of now, I only saw the answer, not the solution. Anybody have a solution? I'm working on it.
 
so you got the formula for it, how are you gonna prove it works for all cases? i.e. do you know how to derive it to (n-1)^(n-2) ?
 
Originally posted by: Bacardi151
so you got the formula for it, how are you gonna prove it works for all cases? i.e. do you know how to derive it to (n-1)^(n-2) ?
Click to expand...

I am gonna work on that. If you turn in an answer only you'll get laughed at by the professor. Even if I didn't get the answer but I filled up my paper with thoughts and effort I would get atleast a 70, maybe higher if I came close.
 
The recurrence relation that I got was almost correct. The correct relation is:

P(n) = (n-1)*P(n-1)+(n-1)*P(n-2).

Hmm...try to get an explicit formula for P(n).
 
You must log in or register to reply here.

TRENDING THREADS

Back
Top