A334774 Triangle read by rows: T(n,k) is the number of permutations of 2 indistinguishable copies of 1..n with exactly k local maxima.

1, 3, 3, 9, 57, 24, 27, 705, 1449, 339, 81, 7617, 48615, 49695, 7392, 243, 78357, 1290234, 3650706, 2234643, 230217, 729, 791589, 30630618, 197457468, 314306943, 128203119, 9689934, 2187, 7944321, 686779323, 9080961729, 30829608729, 31435152267, 9159564513, 529634931

Offset

1,2

Comments

Also the number of permutations of 2 indistinguishable copies of 1..n with exactly k-1 peaks. A peak is an interior maximum.

Links

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50)

Formula

T(n,k) = F(2,n,k-1,0) 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.

A334776(n) = Sum_{k=1..n} (k-1)*T(n,k).

A334777(n) = Sum_{k=1..n} k*T(n,k).

Example

Triangle begins:
    1;
    3,      3;
    9,     57,       24;
   27,    705,     1449,       339;
   81,   7617,    48615,     49695,      7392;
  243,  78357,  1290234,   3650706,   2234643,    230217;
  729, 791589, 30630618, 197457468, 314306943, 128203119, 9689934;
  ...
The T(2,1) = 3 permutations of 1122 with 1 local maxima are 1122, 1221, 2211.
The T(2,2) = 3 permutations of 1122 with 2 local maxima are 1212, 2112, 2121.
The T(2,1) = 3 permutations of 1122 with 0 peaks are 2211, 2112, 1122.
The T(2,2) = 3 permutations of 1122 with 1 peak are 2121, 1221, 1212.

Prog

(PARI)
PeaksBySig(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, F(#sig, D[i], 0));
}
Row(n)={ PeaksBySig(vector(n, i, 2), [0..n-1]) }
{ for(n=1, 8, print(Row(n))) }

Crossrefs

Columns k=1..6 are A000244(n-1), 3*A152494, 3*A152495, 3*A152496, 3*A152497, 3*A152498.

Row sums are A000680.

Main diagonal is A334775.

The version for permutations of 1..n is A008303(n,k-1).

Cf. A154283, A334773, A334776, A334777, A334778.

Sequence in context: A257623 A257625 A216147 * A257627 A115564 A122961

Adjacent sequences: A334771 A334772 A334773 * A334775 A334776 A334777

Keyword

nonn,tabl

Author

Andrew Howroyd, May 11 2020

Status

approved