Sean,
I took a liberty to correct and edit the sequences A001251, A001252,
A001253 as you suggested.
I also provided b-files with first 100 terms for them.
Regards,
Max
On Fri, May 4, 2012 at 12:00 AM, Sean A. Irvine <sairvin at xtra.co.nz> wrote:
> 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/