|
Search: id:A120987
|
|
|
| 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). |
|
+0
1
|
|
| 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; listen)
|
|
|
OFFSET
|
0,3
|
|
|
COMMENT
|
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*T(n,k),k=0..n)=(2n+1)*3^(n-1)=3*A081038(n-1) for n>=1. T(n,k)=A120987(n,n-k).
|
|
FORMULA
|
T(n,k)=trinom(n+1,3n-3k+2)=trinom(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)?
Comment from Giuliano Cabrele (giulianocabrele(AT)tin.it), 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.=(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)
|
|
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
|
|
CROSSREFS
|
Cf. A000244, A099464, A081038, A120987, A119900.
Sequence in context: A138188 A014715 A131656 this_sequence A011076 A010599 A038517
Adjacent sequences: A120984 A120985 A120986 this_sequence A120988 A120989 A120990
|
|
KEYWORD
|
nonn,tabl
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Jul 23 2006
|
|
|
Search completed in 0.003 seconds
|
