|
|
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.
|
|
26
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
|
The version for permutations of 1..n is A008303(n,k-1).
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|