This recurrance relationship seems too easy any ideas?

[mr_coffee]

Hello everyone. I'm not sure what the recurance relationship of this would be becuase, it doesn't seem liek the answer you want requires calculation of any of the previous terms...here it is:

For each integer n >= 2, let a_n be the number of permutations of {1,2,3,...n} in which no number is more than one palce removed from its "natural" position. Thus a_1 = 1; since the on permutation of {1}, namely 1, does not move 1 from its natural postion. Also a_2 = 2 since neither of the two permutations of {1,2}, namely, 12 and 21, moves either number more than one place from its natural positon.

a. find a_3 = 3
THe 3 permutations that do not move more than one place from their natural postions are 213, 132, and 123.

Find the recurrance relation for a_1, a_2, a_3...

Okay so I started to figure out more terms...but it said n >= 2, so why would they say find a_1 if they siad, n must be 2 or greater?

well anyways
a_4 = 4 because
1234, 2134, 1324 1243

a_5 = 5 because
12345, 21345, 13245, 12435, 12354


so as you see, if i go to
a_n, would a_n just be n?

 

[0rthodontist]

I don't know why they said for n >= 2. It doesn't seem necessary or relevant to the problem.

You missed a permutation contributing to a_4, namely 2143, and also a few contributing to a_5.

They are asking for a recurrence relation for a_n. Let's say that you have a permutation of length n-1 x₁x₂...x_n-1 to which you append the number n, giving you x₁x₂...x_n-1n. So it should be clear that a_n = a_n-1 + something, because those first x₁...x_n-1 can be arranged in any legal way for permutations of length n-1, and then you append n. There is another set of legal permutations of length n you can generate though. What is that set?

 

[mr_coffee]

$$x_{n-1}$$
So it would be:
$$a_n = a_{n-1} + a_{n-2}$$ with base cases: $$a_0 = 1 a_1 = 1$$

i think...

thanks again!

 

[0rthodontist]

Well, what do you mean "you think"? Do you know why you also add a_n-2?

 

[mr_coffee]

i'm not exactly sure, I could break down the easier of the recurrances, but what is your thought process when dealing with these?
it all seems these hit a pattern of $$a_{n-1}$$ but I don't see the reason behind it.

When you say:

Let's say that you have a permutation of length n-1 x1x2...xn-1 to which you append the number n, giving you x1x2...xn-1n. So it should be clear that a_n = a_n-1 + something, because those first x1...xn-1 can be arranged in any legal way for permutations of length n-1, and then you append n. There is another set of legal permutations of length n you can generate though. What is that set?

Is the a_{n-1} because you are allowed to move the digit 1 position from the "natural" position?

if so I don't see what the a_{n-2} is doing, unless its because n >= 2? but i saw in the above post it shouldn't matter. But if u say, n = 1, then u would have
a_1 = a_0 + a_-1 and a_{-1} isn't defined so maybe that's why they have it? if n is at least 2, then you will have:
a_2 = a_1 + a_0 and we know both of those, 1! = 1, and 0! = 1, but -1! = ?

thanks!

 

[0rthodontist]

Let's say that I have some legal permutations of length n-1, in this case n-1 = 4:
1234, 2134, 1324, 1243, 2143
Now to generate some legal permutations of length n, I can stick an n at the end of each of these, to get
12345, 21345, 13245, 12435, 21435
Do you agree that all of these permutations are legal? Do you see where the a_n-1 term comes from?

But these are not ALL the legal permutations of length 5. In fact, they are exactly the legal permutations of length 5 where the number 5 is not moved. Can you count the legal permutations of length 5 where the number 5 is moved?

 

[mr_coffee]

ortho,

i'm getting:
12345, 21345, 13245, 12435, 21435
12354, 21354, 13254, 12454, 21453

so for permutations of length n = 5, you have 10.

but by using the above recurrance relation, you get
a_5 = a_4 + a_3 = 5 + 3 = 8.

I do understand your reasoning, but when you say you append an n at the end, why wouldn't the recurrance relation be:
a_n = n*(a_{n-1} + a_{n-2}) ?
I don't see how a_{n-1} + a_{n-2} satisfys that appending n at the end.

say i have a string of length n = 5
[12345]

then length n-1 would be 4, which would look like
[1234]

now length n-2 would be 3, which would be
[123]

if you add n-2 + n-1 you would get the whole n i believe.
[12345]

but I don't see how n-2 is catching the permutations of the last digit, n, it looks like its going to take care of switching [123] and [1234] all around, so u would get different permutations of those numbers but leaving out the 5 or am i totally looking at this wrong?

for example:
n-2, with n = 5
123 213 132

n-1 with n = 5
1234, 2134, 1324, 1243, 2143

 

[rocketturtle]

hi mr coffee,

first of all, please excuse my less-than-perfect-mathematical notations. =)

i don't have strong formal math background. I'm using the notation "[somestring]" to mean all the legal permutations allowed by a given string.

it looks to me that what ortho is trying to get at is the following.

so you are given,

a_1 = 1 -> [1]

and a_2 = 2 -> [12]

then you solved for n = 3 -> [123]

a_3 = 3

but for n = 3, it can be broken down like

[123] -> [[12]3]
a_3 = a_2 + something

to find the "something", we use the constraint of the number only able to be at most one away from its natural position, but the 3 also has an additional constraint due to its natural position.

[123] -> 132
try looking at the leftover numbers that haven't moved and use that to find where to put the [...] pairs for permutations that you already know.

using the pattern that you've derived above by example, you can try extending it to some arbitrary n using similar notation.

does that make sense to you?

 

[0rthodontist]

ortho,

i'm getting:
12345, 21345, 13245, 12435, 21435
12354, 21354, 13254, 12454, 21453

12454 and 21453 are not legal.

Let me try to explain the a_n-1 a little more. You have all the legal permutations of length 4, namely 1234, 2134, 1324, 1243, 2143. There are 5 of these strings. To each of these you add a 5, getting 12345, 21345, 13245, 12435, 21435. The 5 legal permutations of length 4 are transformed into 5 legal permutations of length 5--more precisely there is a one-to-one correspondence between the legal permutations of length n where the last digit is n, and the legal permutations of length n-1, where in this case n = 5.

Now you know that the set of all legal permutations of length n consists of {the set of all legal permutations of length n where the last digit is n} union {the set of all legal permutations of length n where the last digit is not n}, and that the number of legal permutations of length n is {the number of legal permutations of length n where the last digit is n} + {the number of legal permutations of length n where the last digit is not n}.

I've already showed you (hopefully) how to count the number of legal permutations of length n where the last digit is n: this is the same as the total number of legal permutations of length n-1. Now can you count the number of legal permutations of length n where the last digit is not n? Hint: if the last digit of the permutation is not n, what is the last digit?

 

[mr_coffee]

thanks for the responces guys, I do get the n-1 case after that explanation, thank you.

12454 and 21453 are not legal.

whoops i don't know why i wrote thatWhen you said,

...how to count the number of legal permutations of length n where the last digit is n: this is the same as the total number of legal permutations of length n-1. Now can you count the number of legal permutations of length n where the last digit is not n? Hint: if the last digit of the permutation is not n, what is the last digit?

If the last digit is not n, and n is the same as the total number of legal permutations of length n-1, then wouldn't it have to be the next digit which would be n-2?

 

[0rthodontist]

If the last digit is not n, and n is the same as the total number of legal permutations of length n-1, then wouldn't it have to be the next digit which would be n-2?

No, n is not the same as the total number of legal permutations of length n-1. n is the highest number that is being permuted.

Returning to the example of n = 5, let's say that you have the legal permutation
abcde
Where a, b, c, d, and e are drawn from 1, 2, 3, 4, 5, and e is not 5.
Can you tell me what e must be?

 

[mr_coffee]

wow I'm slow hah hm..

well if we are talking about permutations, that means rearranging a, b, c,d, and e around by only by 1 from its natural position, so the only thing e must be if its not 5 would be 4 or d.
abcde
12345

so if e is not 5, can u see why i think its 4? because
abced
12354

d is now in place of e
so if this is the case then the above when u said:

Hint: if the last digit of the permutation is not n, what is the last digit?

then n would be n-1.

 

[0rthodontist]

Right, so you know the last digit is n-1, and the second to last digit is n. So what are the first n-2 digits? (How can you count the permutations where the last digit is not n?)

 

[mr_coffee]

ahh finally, okay so the last digit is n-1 and the second to last digit is n
for example:
abcde, e is n-1 and n is d, so n-2 or c would be
{the number of legal permutations of length n where the last digit is n-1} + {the number of legal permutations of length n where the last digit is n}.

but n + n-1 doesn't equal n-2 so i don't think this is correct but its all i could come up with

 

[0rthodontist]

ahh finally, okay so the last digit is n-1 and the second to last digit is n
for example:
abcde, e is n-1 and n is d, so n-2 or c would be
{the number of legal permutations of length n where the last digit is n-1} + {the number of legal permutations of length n where the last digit is n}.

c is 2 or 3, which is either n-3 or n-2 where n = 5. I think you have some confusion between the number of permutations of length n and the various digits of one such permutation.

 

[mr_coffee]

ooo well that makes sense then because if the last digit is n, then its n or n-1, if the last digit is not n, meaning its n-1, then its either n-1 or n-2 and if you add those together you will hit all the cases, and it would give you the recurrance relation.

 

[0rthodontist]

If the last digit is not n, could it be n-2?

 

[mr_coffee]

if the last digit is, not n, then we knwo it could be n-1
if the last digit is n-1, then i don't see how it could be n-2
[abcdef] <-- f is n
[abcdfe] <-- e is n-1
but i don't see how if the last digit is not, n, that it be n-2, because your only allowed moving 1 spot from its "natural" postion, so d would be n-2, and for d to be the last digit it wouold have to move 2 spots from its "natural" position.

 

[0rthodontist]

Right, just that you seemed to be saying that it could be n-2 before, unless I have misread you.

You know that a_n = a_n-1 + something. I think you understand where the a_n-1 comes from--the number of legal permutations where the last digit is n. The "something" counts the number of legal permutations where the last digit is not n. If the last digit is not n, you know that the last digit must be n-1, and the second to last digit must be n. That is, your permutation is like:
x₁x₂...x_n-2(n)(n-1)
for some x_i's drawn from {1 ... n-2}. So how many legal permutations are there of this form, and why?

 

[mr_coffee]

Well the total number of legal permutations would be the union of the 2 sets because it will cover all the cases which is
$$a_n = a_{n-1} + a_{n-2}$$