# This recurrance relationship seems too easy any ideas?

• mr_coffee
In summary, the conversation discusses finding the recurrence relation for the number of permutations of a set of numbers where each number is at most one place away from its "natural" position. The recurrence relation is a_n = a_{n-1} + a_{n-2} with base cases a_1 = 1
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?

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 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?

$$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!

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

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!

Last edited:
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 an-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?

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

Last edited:
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?

Last edited:
mr_coffee said:
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 an-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?

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?

mr_coffee said:
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?

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.

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?)

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

mr_coffee said:
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.

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.

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

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.

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

You know that an = an-1 + something. I think you understand where the an-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:
x1x2...xn-2(n)(n-1)
for some xi's drawn from {1 ... n-2}. So how many legal permutations are there of this form, and why?

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}$$

## 1. How can I determine the general formula for this recurrence relationship?

The general formula for a recurrence relationship can be found using various techniques such as substitution, iteration method, or characteristic equation method. It is important to understand the pattern and behavior of the recurrence relationship in order to determine the appropriate method.

## 2. Can I solve this recurrence relationship using a closed-form solution?

It depends on the complexity and type of the recurrence relationship. Some recurrence relationships have closed-form solutions, while others may not. In some cases, an asymptotic approximation may be used to estimate the solution.

## 3. How can I prove that the recurrence relationship is correct?

There are various techniques to prove the correctness of a recurrence relationship. One approach is to use mathematical induction, where you prove that the relationship holds for a base case and then show that if it holds for a certain value, it also holds for the next value. Another approach is to use a direct proof, where you use algebraic manipulations to show that the recurrence relationship holds.

## 4. Is there a way to optimize this recurrence relationship?

Yes, there are various techniques to optimize a recurrence relationship. One approach is to use memoization, where you store previously calculated values to avoid repeating calculations. Another approach is to use dynamic programming, where you break down the problem into smaller subproblems and store the solutions to those subproblems. Additionally, you can also try to simplify the recurrence relationship by finding a closed-form solution.

## 5. How can I apply this recurrence relationship in real-world problems?

Recurrence relationships are commonly used in various fields such as mathematics, computer science, and engineering. They can be used to model and solve real-world problems such as population growth, financial investments, and algorithm analysis. It is important to understand the problem and the underlying pattern before applying a recurrence relationship to a real-world scenario.

• Set Theory, Logic, Probability, Statistics
Replies
2
Views
3K
• Calculus and Beyond Homework Help
Replies
1
Views
2K
• Calculus and Beyond Homework Help
Replies
12
Views
2K
• General Math
Replies
11
Views
1K
• Math POTW for University Students
Replies
1
Views
2K
• Calculus and Beyond Homework Help
Replies
3
Views
2K
• Math Proof Training and Practice
Replies
175
Views
20K
• Set Theory, Logic, Probability, Statistics
Replies
1
Views
2K
• Introductory Physics Homework Help
Replies
16
Views
13K
• MATLAB, Maple, Mathematica, LaTeX
Replies
2
Views
2K