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

Wouter Meeussen wouter.meeussen at telenet.be
Thu May 3 00:26:17 CEST 2012


Sean,

there is an alternative to do it by brute force: 'use the combinatorics 
force'  ;-))

the permutations can be generated by compositions of Standard Young 
tableaux.
These are counted by the partitions of n, and the tend to increase slightly 
less steep than n-factorial.
So, you only need to generate and classify the *involutions* , not the 
permutations.

---- proof left to the reader 'cause it seems to work out like that, an' I 
can't do it  ----

Do you speak mathematica?

<<DiscreteMath`Combinatorica`;
binDescents[perm_List]:=FromDigits[Sign[  Rest[perm]-Drop[perm,-1]  ] 
/2+1/2,2 ];

n = 5;
mm2 = Outer[
          1 + RankPermutation@
                TableauxToPermutation[#1, #2] &, \
{FirstLexicographicTableau[#]}, Tableaux[#], 1] & /@ Partitions[n];

it = Map[(binDescents[NthPermutation[# - 1, Range[n]]]) &, mm2, {3}]

        {{{15}}, {{7, 11, 13, 14}}, {{5, 11, 6, 10, 13}}, {{3, 5, 9, 6, 10, 
12}}, {{2,
          5, 9, 4, 10}}, {{1, 2, 4, 8}}, {{0}}}

Flatten[it, 1] /. i_Integer :> Max[Length /@ Split[IntegerDigits[i, 2, 4]]]

        {{4}, {3, 2, 2, 3}, {1, 2, 2, 1, 2}, {2, 1, 2, 2, 1, 2}, {2, 1, 2, 
2, 1}, {3,
           2, 2, 3}, {4}}

Tr at Flatten[(# Length[#]) & /@ Map[z, %, {-1}]]

        32 z[1] + 70 z[2] + 16 z[3] + 2 z[4]

and there you got line  5 [0, 0, 32, 70, 16, 2]  on the cheap.

My programming is "post-a-few-glasses-of-red-claret" here,
and should be cleaned up a bit,
but the gist is there. Go for n=24 !  (not factorial, just exclamation mark)

past midnight over here, tired, got to go to bed,

Wouter.


-----Original Message----- 
From: Sean A. Irvine
Sent: Wednesday, May 02, 2012 10:37 PM
To: Sequence Fanatics Discussion list
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