

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 2011202110122 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^(n1) = 3*A081038(n1) for n >= 1.
T(n,k) = A120987(n,nk).


REFERENCES

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. AddisonWesley, Reading, MA, 2nd. ed., 1994, p. 24, p. 154.


LINKS

G. C. Greubel, Table of n, a(n) for n = 0..11475
Giuliano Cabrele, Words Partitioned according to Number of Strictly Increasing Runs
MathPages, Balls In Bins With Limited Capacity.


FORMULA

T(n,k) = trinomial(n+1,3n3k+2) = trinomial(n+1,3kn) (conjecture).
G.f.: 1/(13tz3t(1t)z^2t(1t)^2*z^3).
Can anyone prove the conjecture (either from the g.f. or combinatorially from the definition)?
From Giuliano Cabrele, Mar 02 2008: (Start)
The conjecture is compatible with the g.f., which can be rewritten as (1t)/(1t(1+(1t)z)^3) and expanded to give T(n,k) = Sum_{j=0..k} (1)^(kj)*C(3j, n)*C(n+1, kj) = Sum_{j=0..k} (1)^j*C(n+1,j)*C(3k3j,n) = trinomial(n+1,3kn) = A027907(n+1,3kn).
Also (1t)/(1t(1+(1t)z)^2) equals the g.f. for the case of binary words, A119900, where Sum_{j=0..k} (1)^(kj)*C(2j,n)*C(n+1,kj) = C(n+1,2kn). Changing the exponent to 1 gives 1/(1zt), the g.f. for the case of unary words, the expansion coefficients of which can be written as Kronecker delta(kn)^(n+1) = Sum_{j=0..k} (1)^(kj)*C(j, n)*C(n+1,kj).
So the conjecture shifts to that the g.f. is (1t)/(1t(1+(1t)z)^m) and coefficients T(m,n,k) = Sum_{j=0..k} (1)^(kj)*C(mj,n)*C(n+1, kj) may apply to the general case of mary words. (End)
Sum_{k=0..n} T(n,k) *(1)^(nk) = A157241(n+1).  Philippe Deléham, Oct 25 2011
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 01201, 01202, 01212, 01012, 02012 and 12012 (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/(13*t*z3*t*(1t)*z^2t*(1t)^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)^(kj)*Cb(n+1, kj)*Cb(3*j, n)$j=0..k):
// Giuliano Cabrele, Dec 11 2015


CROSSREFS

Cf. A000244, A008287, A081038, A099464, A119900, A120987, A265644.
Nb(s,2,q) = A027907(q,s).  Giuliano Cabrele, Dec 11 2015
Sequence in context: A194136 A194480 A194485 * A281293 A258108 A282610
Adjacent sequences: A120984 A120985 A120986 * A120988 A120989 A120990


KEYWORD

nonn,tabl


AUTHOR

Emeric Deutsch, Jul 23 2006


STATUS

approved



