|
| |
|
|
A120987
|
|
Triangle read by rows: T(n,k) is the number of ternary words of length n with k strictly increasing runs (0 <= k <= n; for example, the ternary word 2|01|12|02|1|1|012|2 has 8 strictly increasing runs).
|
|
4
|
|
|
|
1, 0, 3, 0, 3, 6, 0, 1, 16, 10, 0, 0, 15, 51, 15, 0, 0, 6, 90, 126, 21, 0, 0, 1, 77, 357, 266, 28, 0, 0, 0, 36, 504, 1107, 504, 36, 0, 0, 0, 9, 414, 2304, 2907, 882, 45, 0, 0, 0, 1, 210, 2850, 8350, 6765, 1452, 55, 0, 0, 0, 0, 66, 2277, 14355, 25653, 14355, 2277, 66, 0, 0, 0, 0, 12
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
Sum of entries in row n is 3^n (A000244).
Sum of entries in column k is A099464(k+1) (a trisection of the tribonacci numbers).
Row n contains 1 + floor(2n/3) nonzero terms.
T(n,n) = (n+1)*(n+2)/2 (the triangular numbers (A000217)).
Sum_{k=0..n} k*T(n,k) = (2n+1)*3^(n-1) = 3*A081038(n-1) for n >= 1.
|
|
|
REFERENCES
|
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 2nd. ed., 1994, p. 24, p. 154.
|
|
|
LINKS
|
|
|
|
FORMULA
|
T(n,k) = trinomial(n+1,3n-3k+2) = trinomial(n+1,3k-n) (conjecture).
G.f.: 1/(1-3tz-3t(1-t)z^2-t(1-t)^2*z^3).
Can anyone prove the conjecture (either from the g.f. or combinatorially from the definition)?
The conjecture is compatible with the g.f., which can be rewritten as (1-t)/(1-t(1+(1-t)z)^3) and expanded to give T(n,k) = Sum_{j=0..k} (-1)^(k-j)*C(3j, n)*C(n+1, k-j) = Sum_{j=0..k} (-1)^j*C(n+1,j)*C(3k-3j,n) = trinomial(n+1,3k-n) = A027907(n+1,3k-n).
Also (1-t)/(1-t(1+(1-t)z)^2) equals the g.f. for the case of binary words, A119900, where Sum_{j=0..k} (-1)^(k-j)*C(2j,n)*C(n+1,k-j) = C(n+1,2k-n). Changing the exponent to 1 gives 1/(1-zt), the g.f. for the case of unary words, the expansion coefficients of which can be written as Kronecker delta(k-n)^(n+1) = Sum_{j=0..k} (-1)^(k-j)*C(j, n)*C(n+1,k-j).
So the conjecture shifts to that the g.f. is (1-t)/(1-t(1+(1-t)z)^m) and coefficients T(m,n,k) = Sum_{j=0..k} (-1)^(k-j)*C(mj,n)*C(n+1, k-j) may apply to the general case of m-ary words. (End)
The generalized conjecture above can in fact be proved, as described in the file "Words Partitioned according to Number of Strictly Increasing Runs" linked above. - Giuliano Cabrele, Dec 11 2015
|
|
|
EXAMPLE
|
T(5,2) = 6 because we have 012|01, 012|02, 012|12, 01|012, 02|012 and 12|012 (the runs are separated by |).
Triangle starts:
1;
0, 3;
0, 3, 6;
0, 1, 16, 10;
0, 0, 15, 51, 15;
0, 0, 6, 90, 126, 21;
|
|
|
MAPLE
|
G:=1/(1-3*t*z-3*t*(1-t)*z^2-t*(1-t)^2*z^3): Gser:=simplify(series(G, z=0, 33)): P[0]:=1: for n from 1 to 13 do P[n]:=sort(coeff(Gser, z^n)) od: for n from 0 to 12 do seq(coeff(P[n], t, j), j=0..n) od; # yields sequence in triangular form
|
|
|
MATHEMATICA
|
Flatten[Table[Sum[(-1)^j*Binomial[n + 1, j]*Binomial[3 k - 3 j, n], {j, 0, k}], {n, 0, 10}, {k, 0, n}]] (* G. C. Greubel, Dec 20 2015 *)
|
|
|
PROG
|
(MuPAD)
// binomial c. defined as in linked document
Cb:=(x, m)->_if(0<=m and is(m in Z_), binomial(x, m), 0):
// closed formula derived and proved in the linked document
// Qsc(r, q, m) with r=2
T(n, k):=(n, k)->_plus((-1)^(k-j)*Cb(n+1, k-j)*Cb(3*j, n)$j=0..k):
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
