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

Sean A. Irvine sairvin at xtra.co.nz
Wed May 2 22:37:12 CEST 2012


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.



More information about the SeqFan mailing list