[seqfan] Re: A001250, A001251, A001252, A001253 counting permutations

Ron Hardin rhhardin at att.net
Thu May 3 01:33:20 CEST 2012


A fast calculation of the 2nd and 3rd columns agrees with you out to 15
(as row)
0 2 4 10 32 122 544 2770 15872 101042 707584 5405530 44736512 398721962 
3807514624
and
0 0 2 12 70 442 3108 24216 208586 1972904 20373338 228346522 2763212980 
35926266244 499676669254

the 4th agrees out to 14, which is as far as I wanted it to churn, things not 
speeding up any as the column number goes up
0 0 0 2 16 134 1164 10982 112354 1245676 14909340 191916532 2646100822 
38932850396

I haven't checked the code very thoroughly, thinking that agreement with either 
side would most probably prove correctness.
A loop limit mistake wouldn't agree with the existing sequences, presumably, 
which would be the most likely shared error.

 rhhardin at mindspring.com
rhhardin at att.net (either)



----- Original Message ----
> From: Sean A. Irvine <sairvin at xtra.co.nz>
> To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
> Sent: Wed, May 2, 2012 4:37:20 PM
> Subject: [seqfan] A001250, A001251, A001252, A001253 counting permutations
> 
> The sequences A001250, A001251, A001252, A001253 (and possibly a few others)  
>count runs in permutations. Their current values appear to be taken from Table  
>7.4.2 in "Symmetric Function and Allied Tables" by David, Kendall, and Barton.  
>For example, A001251, gives the number of permutations of 1,2,...,n such that  
>the longest run (either ascending or descending) is precisely 3.
> 
> I would  like to give these sequences more precise titles and extend them in 
>the OEIS.  But, I have run into a problem. My computed values for these 
>sequences differ  from those in the original reference for n>=13. I computed my 
>values by brute  force so I am inclined to believe them, but it is always 
>possible I have  overlooked something. Given the book was published in 1966, it 
>seems unlikely  that the entire original table (which goes up to n=14) was 
>computed by brute  force, but I could find no obvious generating function or 
>recurrence in the book  or other explanation as to how they produced their 
>table. It seems likely that  such a recurrence should exist, but it eludes me.
> 
> Here are my brute force  numbers for permutations of length n. Each row sums to 
>n! as expected. For the  case l=2 (A001250) my numbers agree with the formula 
>and entries in the OEIS,  but for A001251, A001252, A001253 they do not.
> 
> n l=0, l=1, l=2, l=3,  etc...
> 1 [0, 1]
> 2 [0, 0, 2]
> 3 [0, 0, 4, 2]
> 4 [0, 0, 10, 12, 2]
> 5  [0, 0, 32, 70, 16, 2]
> 6 [0, 0, 122, 442, 134, 20, 2]
> 7 [0, 0, 544, 3108,  1164, 198, 24, 2]
> 8 [0, 0, 2770, 24216, 10982, 2048, 274, 28, 2]
> 9 [0, 0,  15872, 208586, 112354, 22468, 3204, 362, 32, 2]
> 10 [0, 0, 101042, 1972904,  1245676, 264538, 39420, 4720, 462, 36, 2]
> 11 [0, 0, 707584, 20373338,  14909340, 3340962, 514296, 64020, 6644, 574, 40, 
>2]
> 12 [0, 0, 5405530,  228346522, 191916532, 45173518, 7137818, 913440, 98472, 
>9024, 698, 44, 2]
> 13  [0, 0, 44736512, 2763212980, 2646100822, 652209564, 105318770, 13760472,  
>1523808, 145080, 11908, 834, 48, 2]
> 14 [0, 0, 398721962, 35926266244,  38932850396, 10024669626, 1649355338, 
>219040274, 24744720, 2419872, 206388,  15344, 982, 52, 2]
> 15 [0, 0, 3807514624, 499676669254, 609137502242,  163546399460, 27356466626, 
>3681354658, 422335056, 42129360, 3690960, 285180,  19380, 1142, 56, 2]
> 
> I would appreciate either an independent verification  of my numbers or some 
>insight into a way of computing these numbers without  recourse to brute  force.
> 
> Sean.
> 
> _______________________________________________
> 
> Seqfan  Mailing list - http://list.seqfan.eu/
> 



More information about the SeqFan mailing list