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).

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

Offset: 0

Author

Emeric Deutsch, Jul 23 2006

Keywords

• nonn
• tabl

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.

T(n,k) = A120987(n,n-k).

Examples

			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;
		

References

• R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, 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.

Crossrefs

Cf. A000244, A008287, A081038, A099464, A119900, A120987, A265644.

Nb(s,2,q) = A027907(q,s). - Giuliano Cabrele, Dec 11 2015

Programs

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 *)

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):
// Giuliano Cabrele, Dec 11 2015

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)?

From Giuliano Cabrele, Mar 02 2008: (Start)

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)

Sum_{k=0..n} T(n,k) *(-1)^(n-k) = 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