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

[Neil Sloane]

Sean, I checked the DKB book, and you are right on all counts
(except I did not check your numbers).

This is indeed where the numbers came from, DKB do not explain how they
found them
(by hand, is my guess, knowing the authors), and there is a discrepancy
with your counts.

If someone can confirm your numbers, the sequences should be corrected.

By the way, the triangle itself forms sequence A010026 (read up the
columns),
and later today I will add the other version - reading the columns
downwards -
which will be A211318.

Thanks for catching these (presumed) errors.

I'll copy this to Colin Mallows, maybe he remembers how the tables
were computed. Colin, would David, Kendall and Barton have used a computer
to enumerate permutations on <= 14 letters? I would have thought
they would have worked by hand!

Neil

On Wed, May 2, 2012 at 4:37 PM, 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/
>



-- 
Dear Friends, I will soon be retiring from AT&T. New coordinates:

Neil J. A. Sloane, President, OEIS Foundation
11 South Adelaide Avenue, Highland Park, NJ 08904, USA
Phone: 732 828 6098; home page: http://NeilSloane.com
Email: njasloane at gmail.com