[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