login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
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

%I #58 Jul 16 2019 03:24:50

%S 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,

%T 28,0,0,0,36,504,1107,504,36,0,0,0,9,414,2304,2907,882,45,0,0,0,1,210,

%U 2850,8350,6765,1452,55,0,0,0,0,66,2277,14355,25653,14355,2277,66,0,0,0,0,12

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

%C Sum of entries in row n is 3^n (A000244).

%C Sum of entries in column k is A099464(k+1) (a trisection of the tribonacci numbers).

%C Row n contains 1 + floor(2n/3) nonzero terms.

%C T(n,n) = (n+1)*(n+2)/2 (the triangular numbers (A000217)).

%C Sum_{k=0..n} k*T(n,k) = (2n+1)*3^(n-1) = 3*A081038(n-1) for n >= 1.

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

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

%H G. C. Greubel, <a href="/A120987/b120987.txt">Table of n, a(n) for n = 0..11475</a>

%H Giuliano Cabrele, <a href="/A120987/a120987.pdf">Words Partitioned according to Number of Strictly Increasing Runs</a>

%H MathPages, <a href="https://web.archive.org/web/20160309185520/https://www.mathpages.com/home/kmath337.htm">Balls In Bins With Limited Capacity</a>.

%F T(n,k) = trinomial(n+1,3n-3k+2) = trinomial(n+1,3k-n) (conjecture).

%F G.f.: 1/(1-3tz-3t(1-t)z^2-t(1-t)^2*z^3).

%F Can anyone prove the conjecture (either from the g.f. or combinatorially from the definition)?

%F From _Giuliano Cabrele_, Mar 02 2008: (Start)

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

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

%F 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)

%F Sum_{k=0..n} T(n,k) *(-1)^(n-k) = A157241(n+1). - _Philippe Deléham_, Oct 25 2011

%F 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

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

%e Triangle starts:

%e 1;

%e 0, 3;

%e 0, 3, 6;

%e 0, 1, 16, 10;

%e 0, 0, 15, 51, 15;

%e 0, 0, 6, 90, 126, 21;

%p 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

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

%o (MuPAD)

%o // binomial c. defined as in linked document

%o Cb:=(x,m)->_if(0<=m and is(m in Z_), binomial(x,m), 0):

%o // closed formula derived and proved in the linked document

%o // Qsc(r,q,m) with r=2

%o T(n,k):=(n,k)->_plus((-1)^(k-j)*Cb(n+1,k-j)*Cb(3*j, n)$j=0..k):

%o // _Giuliano Cabrele_, Dec 11 2015

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

%Y Nb(s,2,q) = A027907(q,s). - _Giuliano Cabrele_, Dec 11 2015

%K nonn,tabl

%O 0,3

%A _Emeric Deutsch_, Jul 23 2006

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 04:23 EDT 2024. Contains 371264 sequences. (Running on oeis4.)