[seqfan] Re: A001250, A001251, A001252, A001253 counting permutations
Max Alekseyev
maxale at gmail.com
Tue May 22 06:54:26 CEST 2012
SeqFans,
I've made my paper available at http://arxiv.org/abs/1205.4581
Comments or questions are welcome.
Regards,
Max
On Sun, May 20, 2012 at 10:27 PM, Max Alekseyev <maxale at gmail.com> wrote:
> 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/
More information about the SeqFan
mailing list