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

Ron Hardin rhhardin at att.net
Fri May 4 00:27:32 CEST 2012

```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.

```