[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