A334778 Triangle read by rows: T(n,k) is the number of permutations of 2 indistinguishable copies of 1..n arranged in a circle with exactly k local maxima.
1, 0, 1, 0, 4, 2, 0, 18, 66, 6, 0, 72, 1168, 1192, 88, 0, 270, 16220, 61830, 33600, 1480, 0, 972, 202416, 2150688, 3821760, 1268292, 40272, 0, 3402, 2395540, 62178928, 272509552, 279561086, 62954948, 1476944, 0, 11664, 27517568, 1629254640, 15313310208, 36381368048, 24342647424, 3963672720, 71865728
Offset: 0
Examples
Triangle begins: 1; 0, 1; 0, 4, 2; 0, 18, 66, 6; 0, 72, 1168, 1192, 88; 0, 270, 16220, 61830, 33600, 1480; 0, 972, 202416, 2150688, 3821760, 1268292, 40272; 0, 3402, 2395540, 62178928, 272509552, 279561086, 62954948, 1476944; ... The T(2,1) = 4 permutations of 1122 with 1 local maximum are 1122, 1221, 2112, 2211. The T(2,2) = 2 permutations of 1122 with 2 local maxima are 1212, 2121.
Links
- Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)
Crossrefs
Programs
-
PARI
CircPeaksBySig(sig, D)={ my(F(lev,p,q) = my(key=[lev,p,q], z); if(!mapisdefined(FC, key, &z), my(m=sig[lev]); z = if(lev==1, if(p==0, binomial(m-1, q), 0), sum(i=0, p, sum(j=0, min(m-i, q), self()(lev-1, p-i, q-j+i) * binomial(m+2*(q-j)+1, 2*q+i-j+1) * binomial(q-j+i, i) * binomial(q+1, j) ))); mapput(FC, key, z)); z); local(FC=Map()); vector(#D, i, my(k=D[i], lev=#sig); if(lev==1, k==1, my(m=sig[lev]); lev*sum(j=1, min(m,k), m*binomial(m-1,j-1)*F(lev-1,k-j,j-1)/j))); } Row(n)={ if(n==0, [1], CircPeaksBySig(vector(n,i,2), [0..n])) } { for(n=0, 8, print(Row(n))) }
Formula
T(n,k) = n*(2*F(2,n-1,k-1,0) + F(2,n-1,k-2,1)) for n > 1 where F(m,n,p,q) = Sum_{i=0..p} Sum_{j=0..min(m-i, q)} F(m, n-1, p-i, q-j+i) * binomial(m+2*(q-j)+1, 2*q+i-j+1) * binomial(q-j+i, i) * binomial(q+1, j) for n > 1 with F(m,1,0,q) = binomial(m-1, q), F(m,1,p,q) = 0 for p > 0.
A334780(n) = Sum_{k=1..n} k*T(n,k).
Comments