wu :: forums
« wu :: forums - Ascents in Permutations »

Welcome, Guest. Please Login or Register.
Mar 28th, 2024, 1:12pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: Eigenray, william wu, SMQ, towr, Grimbal, ThudnBlunder, Icarus)
   Ascents in Permutations
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Ascents in Permutations  (Read 4893 times)
Johno-G
Newbie
*




Could God create a wall that he could not jump?

   
Email

Gender: male
Posts: 31
Ascents in Permutations  
« on: Jan 15th, 2003, 7:42am »
Quote Quote Modify 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 unclearSmiley 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: male
Posts: 13730
Re: Ascents in Permutations  
« Reply #1 on: Jan 15th, 2003, 9:10am »
Quote Quote Modify 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
*****





   
Email

Gender: male
Posts: 949
Re: Ascents in Permutations  
« Reply #2 on: Jan 15th, 2003, 11:43am »
Quote Quote Modify 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: male
Posts: 13730
Re: Ascents in Permutations  
« Reply #3 on: Jan 15th, 2003, 12:39pm »
Quote Quote Modify 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: male
Posts: 13730
Re: Ascents in Permutations  
« Reply #4 on: Jan 15th, 2003, 1:22pm »
Quote Quote Modify 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
*****





   
Email

Gender: male
Posts: 949
Re: Ascents in Permutations  
« Reply #5 on: Jan 15th, 2003, 1:32pm »
Quote Quote Modify 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
*****





   
Email

Gender: male
Posts: 949
Re: Ascents in Permutations  
« Reply #6 on: Jan 16th, 2003, 6:24am »
Quote Quote Modify 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: male
Posts: 13730
Re: Ascents in Permutations  
« Reply #7 on: Jan 16th, 2003, 6:56am »
Quote Quote Modify 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: male
Posts: 13730
Re: Ascents in Permutations  
« Reply #8 on: Jan 16th, 2003, 7:24am »
Quote Quote Modify 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: male
Posts: 13730
Re: Ascents in Permutations  
« Reply #9 on: Jan 16th, 2003, 7:35am »
Quote Quote Modify 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: male
Posts: 13730
Re: Ascents in Permutations  
« Reply #10 on: Jan 16th, 2003, 7:59am »
Quote Quote Modify 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: male
Posts: 13730
Re: Ascents in Permutations  
« Reply #11 on: Jan 16th, 2003, 8:43am »
Quote Quote Modify 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 Tongue )
« Last Edit: Jan 16th, 2003, 9:01am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Re: Ascents in Permutations  
« Reply #12 on: Jan 16th, 2003, 9:18am »
Quote Quote Modify 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 Wink
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: male
Posts: 13730
Re: Ascents in Permutations  
« Reply #13 on: Jan 16th, 2003, 9:53am »
Quote Quote Modify 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: male
Posts: 13730
Re: Ascents in Permutations  
« Reply #14 on: Jan 16th, 2003, 1:28pm »
Quote Quote Modify 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
*****





   
Email

Gender: male
Posts: 949
Re: Ascents in Permutations  
« Reply #15 on: Jan 16th, 2003, 1:43pm »
Quote Quote Modify 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: male
Posts: 13730
Re: Ascents in Permutations  
« Reply #16 on: Jan 16th, 2003, 2:00pm »
Quote Quote Modify 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
*****





   
Email

Gender: male
Posts: 949
Re: Ascents in Permutations  
« Reply #17 on: Jan 17th, 2003, 1:55pm »
Quote Quote Modify 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  Smiley
IP Logged

Doc, I'm addicted to advice! What should I do?
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Re: Ascents in Permutations  
« Reply #18 on: Jan 20th, 2003, 9:39am »
Quote Quote Modify 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: male
Posts: 13730
Re: Ascents in Permutations  
« Reply #19 on: Jan 20th, 2003, 10:55am »
Quote Quote Modify 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 Grin
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Johno-G
Newbie
*




Could God create a wall that he could not jump?

   
Email

Gender: male
Posts: 31
Re: Ascents in Permutations  
« Reply #20 on: Jan 23rd, 2003, 5:11am »
Quote Quote Modify 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
*****





   
Email

Gender: male
Posts: 949
Re: Ascents in Permutations  
« Reply #21 on: Jan 23rd, 2003, 9:11am »
Quote Quote Modify 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?

   
Email

Gender: male
Posts: 31
Re: Ascents in Permutations  
« Reply #22 on: Jan 24th, 2003, 1:01am »
Quote Quote Modify 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
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Re: Ascents in Permutations  
« Reply #23 on: Feb 5th, 2003, 4:16am »
Quote Quote Modify Modify

Decided to move this problem out of the cs section because it doesn't really require a computer science background.
IP Logged


[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board