Author |
Topic: Ascents in Permutations (Read 4975 times) |
|
Johno-G
Newbie
Could God create a wall that he could not jump?
Gender: 
Posts: 31
|
 |
Ascents in Permutations
« on: Jan 15th, 2003, 7:42am » |
 Quote  Modify
|
K, I've only rescently started learning how to program using Maple, and I especially liked this following problem we got set:
Create a program to count the number of permutations of n distinct numbers with exactly r ascents in it.
(if anyone is unclear The number of ascents in a permutation is the number of times when one number is greater than the one directly preceding it. eg. [1,2,3,4,5] has 4 ascents in it, (2>1, 3>2, 4>3, 5>4), [1,4,3,2,5] has 2 ascents in it, (4>1, 5>2), and [5,4,3,2,1] has none.
I only know how to use Maple, so that's the only language I can give you my solution in, I'm afraid!
Give the numbers for r=2, 0<n<7.
|
| « Last Edit: Jan 15th, 2003, 9:50am by Johno-G » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Ascents in Permutations
« Reply #1 on: Jan 15th, 2003, 9:10am » |
Quote Modify
|
the easy way would be just to generated all permutations, then filter out anything with the wrong number of ascends..
There's probably a better way, one that isn't exponential in time (and space)..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Ascents in Permutations
« Reply #2 on: Jan 15th, 2003, 11:43am » |
Quote Modify
|
If you put the permutations in reverse lexical order, and print out the string S that is formed by counting the number of ascents in those permutations, you get the following recursion formula to determine the string for the strings of length n:
S1 = 0
Sn+1 = Sn,0, Sn,1, Sn,2, ..., Sn,n
where Sn,i is Sn with the first (i/n) of the numbers incremented by one.
That is to say:
S3 = S3,0 = 0, 1, 1, 1, 1, 2
S3,1 = 1, 2, 1, 1, 1, 2
S3,2 = 1, 2, 2, 2, 1, 2
S3,3 = 1, 2, 2, 2, 2, 3
Therefore, S4 = 0, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 2, 1, 2, 2, 2, 1, 2, 1, 2, 2, 2, 2, 3
Now we just need to count the number of 1's, 2's, etc. in these strings...
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Ascents in Permutations
« Reply #3 on: Jan 15th, 2003, 12:39pm » |
Quote Modify
|
I can't readily see why that recursion formula would hold true.. Do you have a simple intuitive proof?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Ascents in Permutations
« Reply #4 on: Jan 15th, 2003, 1:22pm » |
Quote Modify
|
well, assuming it's correct, so far I have these results:
1
1 1
1 4 1
1 11 11 1
1 26 66 26 1
1 57 302 302 57 1
1 120 1191 2416 1191 120 1
1 247 4293 15619 15619 4293 247 1 look at the second column..
1 *2 + 2 = 4
4 *2 + 3 = 11
11 *2 + 4 = 26
26 *2 + 5 = 57
57 *2 + 6 = 120
120 *2 +7 = 247
there's definitely a pattern.. So a closed formula should exist..
|
| « Last Edit: Jan 15th, 2003, 1:26pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Ascents in Permutations
« Reply #5 on: Jan 15th, 2003, 1:32pm » |
Quote Modify
|
Well, I just made up all the permutations for n=3, n=4, and n=5, and saw how the numbers went. Here's an attempt at a justification:
1) Consider creating length-5 permutations from length-4 permutations by adding a number to the front of the permutation. There are 5 cases that are important, corresponding to how the value of the first number compares to the values of the numbers in the length-4 permutation.
2) In the first case, the first number is larger than all the numbers of the length-4 permutation. In this case, we add zero ascents. Here are some examples:
3142 -> 53142 (haven't added any ascents)
1234 -> 51234 (haven't added any ascents)
3) In the second case, the first number is larger than 3 of the remaining numbers. In this case, we add an ascent only when the second number is the largest of the original four. Examples:
5213 -> 45213 (we have added one ascent)
1235 -> 41235 (haven't added any ascents)
We add a single ascent to the first 1/4 of the permutations (in reverse lexical order).
4) Similarly, the first number could be larger than 2, 1, or none of the existing 4 numbers. In these cases, we add a single ascent to the first 2/4, 3/4, and 4/4 of the permutations (in reverse lexical order).
5) Each of these 5 cases contributes to the string we generate. The first case contributes a string which is the same as the string from the length-4 permutations. The second case contributes a string which is the same as the string from the length-4 permutations, but with the first 1/4 of the numbers incremented. The third case contributes a string with the first 1/2 incremented, etc. This also happens to put the strings in reverse lexical order.
By the way, I have come up with a method to calculate these numbers, and with one optimization, it should take O(n3) time, and O(n2) space.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Ascents in Permutations
« Reply #6 on: Jan 16th, 2003, 6:24am » |
Quote Modify
|
towr,
Based on your initial guess at a relation to generate the triangle, I have found this method:
1) On a spreadsheet, create the following grid:
X 0 1 2 3 4 5
0 0 0 0 0 0 0
1 0 1 . . . .
2 0 . . . . .
3 0 . . . . .
4 0 . . . . .
5 0 . . . . .
In the spaces I've filled with '.', enter the following formula: "(r,-1)*(r,c-1)+(-1,c)*(r-1,c)", where r is the row number, and c is the column number. (r,-1) is the heading at the beginning of the row, and (-1,c) is the heading at the top of the column. The '1' entered inside the zero-padded space is the generator for the triangle.
This makes a skewed version of the triangle, like this:
X
0
1
2
3
4
5 | 0
0
0
0
0
0
0 | 1
0
1
1
1
1
1 | 2
0
1
4
11
26
47 | 3
0
1
11
66
302
1191 | 4
0
1
26
302
2416
15619 | 5
0
1
57
1191
15619
156190 |
The rows that go across in your version are diagonals from bottom-left to top-right. I still don't have an explicit formula yet, although I'm sure there is one. This method does better than my O(n3) method from before, taking only O(n2).
|
| « Last Edit: Jan 16th, 2003, 6:33am by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Ascents in Permutations
« Reply #7 on: Jan 16th, 2003, 6:56am » |
Quote Modify
|
for the second row (and second column) there's the formula 2^(n+1) - (n+2)
perhaps the others are a similar exponential function..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Ascents in Permutations
« Reply #8 on: Jan 16th, 2003, 7:24am » |
Quote Modify
|
a[i,j] = j*a[i-1,j] + i*a[i, j-1]
a[2, n] = 2n+1 - (n+2)
a[n, 2] = 2n+1 - (n+2)
a[3, n]
= n*a[2, n] + 3* a[3, n-1]
= n*2n+1 - n*(n+2) + 3* a[3, n-1]
= sum(3n-x *(x*2x+1 - x*(x+2)), x, 0, n)
= 3n + 2 - 2n + 2*(n + 3) + (n+2)*(n+3)/2
a few more, and I'm sure we'll get a general formula..
|
| « Last Edit: Jan 16th, 2003, 7:27am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Ascents in Permutations
« Reply #9 on: Jan 16th, 2003, 7:35am » |
Quote Modify
|
a[4,n] = 4(n + 3) - 3(n + 3)·(n + 4) + 2^(n + 3)·(n + 3)·(n + 4)/2 - (n + 2)·(n + 3)·(n + 4)/6
a[5,n] = 5^(n + 4)/0! - 4^(n + 4)·(n + 5)/1! + 3^(n + 4)·(n + 4)·(n + 5)/2! - 2^(n + 4)·(n + 3)·(n + 4)·(n + 5)/3! + (n + 2)·(n + 3)·(n + 4)·(n + 5)/4!
|
| « Last Edit: Jan 16th, 2003, 7:48am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Ascents in Permutations
« Reply #10 on: Jan 16th, 2003, 7:59am » |
Quote Modify
|
I think this is it..
It would still take O(n) to calculate it..
|
| « Last Edit: Jan 16th, 2003, 8:16am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Ascents in Permutations
« Reply #11 on: Jan 16th, 2003, 8:43am » |
Quote Modify
|
we actually still need to transform back from the skewed triangle to the original..
so cnt_asc(r, n) = a[r+1, n-r]
(And no I'll go clean up all the malformed formulas from my formula-generator  )
|
| « Last Edit: Jan 16th, 2003, 9:01am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Ascents in Permutations
« Reply #12 on: Jan 16th, 2003, 9:18am » |
Quote Modify
|
towr,
Very nice! I was guessing that column 3 was dominated by 3n+2, but I didn't know what the smaller terms were. It's really quite a clean-looking formula ... now all we have to do is come up with some simple explanation for it, and make ourselves look silly for finding it this way 
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Ascents in Permutations
« Reply #13 on: Jan 16th, 2003, 9:53am » |
Quote Modify
|
Well, the realization that
a[r, n] = sum(rn-x *(x*a[r-1,x]), x, 0, n)
was really helpful too me.. Which means if you know the formula for the row above you're done.. And for some row at the top it is always 1.
There's probably some usefull theorem somewhere that gives a formula for repeating it r times..
There's f.i. also a closed formula for the sequence
m a[n]
0 n
1 sum(i, i, 0, n)
2 sum(sum(i, i, 0, j), j, 0, n)
3 sum(sum(sum(i, i, 0, j), j, 0, k), k, 0, n)
namely a[n] = (n + m)!/((n - 1)!*(m + 1)!)
in a way it's similar.. (again with factorials..)
|
| « Last Edit: Jan 16th, 2003, 10:09am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Ascents in Permutations
« Reply #14 on: Jan 16th, 2003, 1:28pm » |
Quote Modify
|
Apparently these are called Eulerian numbers..
http://mathworld.wolfram.com/EulerianNumber.html
http://mathworld.wolfram.com/PermutationAscent.html
he beat us to it again..
For some reason though the formula they give is slightly different from mine (they end the sum at k+1, where I end at r, while the rest is equivalent..)..
huh.. that difference only changes the outcome in the case of n=0 and r=0.. I say there's 1, they say there's none..
They're right I guess (I mean, an empty set has count 0)..
|
| « Last Edit: Jan 16th, 2003, 1:39pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Ascents in Permutations
« Reply #15 on: Jan 16th, 2003, 1:43pm » |
Quote Modify
|
towr,
Don't feel bad. He may have beat us to the punch, but look who's not dead!
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Ascents in Permutations
« Reply #16 on: Jan 16th, 2003, 2:00pm » |
Quote Modify
|
hehe..
Well, I don't feel bad.. I'm still tremendously satisfied we figured this out on our own.. (Which is a lot more fun when you don't yet know someone has beaten you to the punch).
Still it'd be cool if we would have found something no one else had..
Overall this has been a good week for me for feeling smug.. (on several occasions this week I also 'outsmarted' my university teachers)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Ascents in Permutations
« Reply #17 on: Jan 17th, 2003, 1:55pm » |
Quote Modify
|
One interesting fact about this triangle is that the rows sum to the factorial numbers (compare to Pascal's triangle, in which the rows sum to the powers of 2). Let's see if we can come up with a justification for this triangle. First of all, let's consider how you make a permutation with zero ascents. There is only ever one way: You choose all of the elements, and put them in reverse order.
How do you make a permutation with one ascent? You divide the elements into two groups, then put each group in reverse order. How many ways are there to do this?
With three elements, there are three ways we can pick the first group to have two elements, and there are three ways we can pick the second group to have two elements. However, you will notice that this sums to 6, not the answer we want. The reason is that some of these groups will give you zero ascents (picking the first group to be {2,3}, or picking the second group to be {1,2}). It turns out that for every different number of elements in the first group, there is exactly one way to make zero ascents. Therefore, our answer for three with one ascent is:
(3 choose 2) - 1 + (3 choose 1) - 1 = 4
Now let us consider the four case with one ascent. We can have zero, one, two, three, or four elements in the first group (I'm generalizing here. The zero and four cases go away), and in each case, there is one way to make a zero-ascent permutation.
(4 choose 0)-1 + (4 choose 1)-1 + (4 choose 2)-1 + (4 choose 3)-1 + (4 choose 4)-1 = 24 - (4+1)
cnt_asc(1,n) = 2n - (n+1)
And this explains why the second column has that particular form.
I'm currently working on the the cnt_asc(2,4) column, from the same direction. Soon I may have a justification for the formula from first principles
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Ascents in Permutations
« Reply #18 on: Jan 20th, 2003, 9:39am » |
Quote Modify
|
Here's another way to get a formula:
Consider creating a length n permutation from a length n-1 permutation. WLOG, we can consider that we add the number n to all the permutations of the numbers 1 to n-1. There are n places in which we can add the new number in each permutation. For instance, with n=5:
1 4 2 3
51 4 2 3 (2 ascents)
154 2 3 (2 ascents)
1 452 3 (3 ascents)
1 4 253 (2 ascents)
1 4 2 35 (3 ascents)
For this reason, the sum of each row of our triangle is n!. It is not too difficult to show that all possible permutations are created this way, and that all permutations created this way are unique.
It is fairly easy to see that adding the number n sometimes adds a single permutation, and sometimes doesn't. After a little examination, it becomes clear that the new number adds an ascent only when:
1) We put it where there was a descent before, or
2) We put it at the end of the permutation.
So out of the n places to put the number, there are d+1 ways to add an ascent, and a+1 ways to not add an ascent, where a is the number of ascents in the length n-1 permutation, and d is the number of descents (d+a = n-2).
So when we consider making all the length n permutations with exactly r ascents, we do this by considering all the ways to take a length n-1 permutation with r ascents and add no ascents, plus all the ways to take a length n-1 permutation with r-1 ascents and add a single ascent. This leads us to the following sum:
cnt_asc(r,n) = cnt_asc(r-1, n-1)*(d+1) + cnt_asc(r, n-1)*(a+1)
cnt_asc(r,n) = cnt_asc(r-1, n-1)*(n-2 - (r-1) + 1) + cnt_asc(r, n-1)*(r+1)
cnt_asc(r,n) = cnt_asc(r-1, n-1)*(n-r) + cnt_asc(r, n-1)*(r+1)
This is exactly the relation I used before to specify the skewed triangle. If we do a little math, we will get the towr-Euler relation.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Ascents in Permutations
« Reply #19 on: Jan 20th, 2003, 10:55am » |
Quote Modify
|
*nods*
neat.. It all makes perfect sense now..
on Jan 20th, 2003, 9:39am, James Fingas wrote:| If we do a little math, we will get the towr-Euler relation. |
|
Nice to be named with Euler like that 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Johno-G
Newbie
Could God create a wall that he could not jump?
Gender:
Posts: 31
|
|
Re: Ascents in Permutations
« Reply #20 on: Jan 23rd, 2003, 5:11am » |
Quote Modify
|
James: I can see that the sum of the rows are the factoral numbers, but I don't follow your logic in trying to justify that, could you explain how you reason this?
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Ascents in Permutations
« Reply #21 on: Jan 23rd, 2003, 9:11am » |
Quote Modify
|
For each permutation of length 4, there are 5 permutations of length five. Since there is one permutation of length 1, we get this:
length 1: 1 permutation
length 2: 2 * 1 permutations
length 3: 3 * 2 * 1 permutations
etc.
You can also just notice that for five elements, you have five ways to pick the first, then four ways to pick the second, etc. (it's a given the all the elements are distinct).
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Johno-G
Newbie
Could God create a wall that he could not jump?
Gender:
Posts: 31
|
|
Re: Ascents in Permutations
« Reply #22 on: Jan 24th, 2003, 1:01am » |
Quote Modify
|
Yes, sorry James, I was being a bit of a muppet with that n! thing you pointed out - I was barking up the wrong tree completeley!!
Anyway, here's my solution for the problem, done in Maple, for anyone who's interested.
This program will give you E(n,r) for any n, r, but it takes a while for Maple to compute past n = 8.
E:=proc(n,r) local C1,C2,L,P,x,y;
with(combinat,permute):
C1:=0;
P:=permute(n);
for x from 1 to nops(P) do
C2:=0;
L:=P[x];
for y from 2 to n do
if L[y-1]<L[y] then
C2:=C2+1
end if
end do;
if C2=r then
C1:=C1+1;
end if;
end do;
return C1;
end:
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
