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

[Sean A. Irvine]

I have sent Max the relevant pages off list.

Sean.

On Sun, May 20, 2012 at 11:37 AM, Sean A. Irvine <sairvin at gmail.com> wrote:
> Hi Max,
>
> I have attached scans of the most relevant pages. Please be aware that the
> DKB book consists primarily of tables. In addition to A001250 it deals with
> many other kinds of permutation counts, such as pairs of runs, and those
> that are just ascents or descents.
>
> I apologize for the quality of my scanner, but hopefully they are legible.,
>
> Sean.
>
> On Sun, May 20, 2012 at 4:13 AM, Max Alekseyev <maxale at gmail.com> wrote:
>> I'm preparing a paper on these sequences and would like to double
>> check the related information given in David, Kendall, and Barton.
>> Could somebody please tell me what exactly is listed in this book (or
>> maybe even scan the relevant pages)?
>> Thanks,
>> Max
>>
>> On Thu, May 3, 2012 at 12:37 AM, Sean A. Irvine <sairvin at xtra.co.nz> wrote:
>>> 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/
>>
>> _______________________________________________
>>
>> Seqfan Mailing list - http://list.seqfan.eu/