[seqfan] Re: A001250, A001251, A001252, A001253 counting permutations
Meeussen Wouter (bkarnd)
wouter.meeussen at vandemoortele.com
Fri May 4 09:44:22 CEST 2012
Sean,
your table is verified up to n=2 .. 14.
{2 z[1]},
{4 z[1] + 2 z[2]},
{10 z[1] + 12 z[2] + 2 z[3]},
{32 z[1] + 70 z[2] + 16 z[3] + 2 z[4]},
{122 z[1] + 442 z[2] + 134 z[3] + 20 z[4] + 2 z[5]},
{544 z[1] + 3108 z[2] + 1164 z[3] + 198 z[4] + 24 z[5] + 2 z[6]}
{2770 z[1] + 24216 z[2] + 10982 z[3] + 2048 z[4] + 274 z[5] + 28 z[6] + 2 z[7]},
{15872 z[1] + 208586 z[2] + 112354 z[3] + 22468 z[4] + 3204 z[5] + 362 z[6] + 32 z[7] + 2 z[8]}
10 {60.156 Second, Null}
101042 z[1] + 1972904 z[2] +
1245676 z[3] + 264538 z[4] + 39420 z[5] + 4720 z[6] + 462 z[7] +
36 z[8] + 2 z[9]
11 {382.812 Second, Null}
707584 z[1] + 20373338 z[2] +
14909340 z[3] + 3340962 z[4] + 514296 z[5] + 64020 z[6] + 6644 z[7] +
574 z[8] + 40 z[9] + 2 z[10]
12 {1658.11 Second, Null}
5405530 z[1] + 228346522 z[2] +
191916532 z[3] + 45173518 z[4] + 7137818 z[5] + 913440 z[6] +
98472 z[7] + 9024 z[8] + 698 z[9] + 44 z[10] + 2 z[11]
13 {7358.3 Second, Null}
44736512 z[1] +
2763212980 z[2] + 2646100822 z[3] + 652209564 z[4] + 105318770 z[5] +
13760472 z[6] + 1523808 z[7] + 145080 z[8] + 11908 z[9] + 834 z[10] +
48 z[11] + 2 z[12]
14 {22329.6 Second, Null}
398721962 z[1] +
35926266244 z[2] + 38932850396 z[3] + 10024669626 z[4] +
1649355338 z[5] + 219040274 z[6] + 24744720 z[7] + 2419872 z[8] +
206388 z[9] + 15344 z[10] + 982 z[11] + 52 z[12] + 2 z[13]
I'll try and get beyond by using the 'transpose' symmetry of the partitions
(they have same descent lengths, just generated in reverse order).
Wouter.
-----Original Message-----
From: seqfan-bounces at list.seqfan.eu [mailto:seqfan-bounces at list.seqfan.eu] On Behalf Of Sean A. Irvine
Sent: vrijdag 4 mei 2012 6:00
To: Sequence Fanatics Discussion list
Subject: [seqfan] Re: A001250, A001251, A001252, A001253 counting permutations
Thanks Max, Ron, Wouter, and Neil for taking the time to give confirmations, various programs, and extra clues. It seems fairly clear now, that the later terms of these sequences in the DKB are wrong. I'll update the corresponding OEIS entries within the next few days (bit busy right now).
Sean.
On 05/04/12 10:27, Ron Hardin wrote:
> You can do a cached recurrence, anyway this bc(1) program seems to
> work $ bc -q formula.b
> grand(10,6)
> 10 6 39420 [= row, col, and result]
> 0
> quit
> $ bc -q formula.b
> grand(15,3)
> 15 3 499676669254
> 0
> quit
>
> formula.b is
> define count(curseqlen,nleft,nabove,hasmaxseq) {
> auto sum,h,k,hash;
> if(nleft==0) {
> if(hasmaxseq)return 1;
> return 0;
> }
>
> hash=curseqlen+(maxseq+1)*(nleft+(permlength+1)*(nabove+(permlength+1)
> *hasmaxseq));
>
> if(sv[hash])return sv[hash];
> sum=0;
> if(curseqlen<maxseq) {
> for(k=1; k<=nabove; k++) {
> h=hasmaxseq;
> if(curseqlen+1==maxseq)h=1;
> sum+=count(curseqlen+1,nleft-1,nabove-k,h);
> }
> }
> for(k=1; k<=nleft-nabove; k++) {
> sum+=count(1,nleft-1,nleft-nabove-k,hasmaxseq);
> }
> sv[hash]=sum;
> return sum;
> }
> define grand(row,col) {
> auto sum,i;
> maxseq=col-1;
> permlength=row-1;
> sum=0;
> for(i=0; i<=permlength; i++)sum+=count(0,permlength,i,0);
> print row," ",col," ",sum,"\n";
> }
>
> You have to run it anew when you change row and col because it caches
> old values of count() in sv[].
>
> Matching row and col to maxseq and permlength was done empirically.
> Too hard to figure out.
>
> The idea is that all that matters when adding the rest of a
> permutation is 1. the current run length (direction doesn't matter) 2.
> the number of elements left to be added 3. the number of these that
> would extend the current sequence 4. a flag indicating whether the
> permutation already contains a maximal run
>
> and the result has to be cached so it's not recomputed.
>
> bc(1) limits arrays to around 10,000.
>
> Maybe somebody can do it in a better language!
>
> Program may not work for small row and col, I haven't tried it.
>
> rhhardin at mindspring.com
> rhhardin at att.net (either)
>
>
>
>
>> -----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/
>
_______________________________________________
Seqfan Mailing list - http://list.seqfan.eu/
===============================
This email is confidential and intended solely for the use of the individual to whom it is addressed.
If you are not the intended recipient, be advised that you have received this email in error and that any use, dissemination, forwarding, printing, or copying of this email is strictly prohibited.
You are explicitly requested to notify the sender of this email that the intended recipient was not reached.
More information about the SeqFan
mailing list