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

[Max Alekseyev]

Sean, thank you!
These pages helped helped me to identify errors in some other
sequences copied from DKB book.
In particular, I've found and corrected errors in A000402 and A000434.
Regards,
Max

On Sun, May 20, 2012 at 11:21 AM, Sean A. Irvine <sairvin at gmail.com> wrote:
> 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/
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/