login
This site is supported by donations to The OEIS Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing.
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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.

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

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.

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

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

// 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 5 10:45 EST 2019. Contains 329751 sequences. (Running on oeis4.)