

A265644


Triangle read by rows: T(n,m) is the number of quaternary words of length n with m strictly increasing runs (0 <= m <= n).


1



1, 0, 4, 0, 6, 10, 0, 4, 40, 20, 0, 1, 65, 155, 35, 0, 0, 56, 456, 456, 56, 0, 0, 28, 728, 2128, 1128, 84, 0, 0, 8, 728, 5328, 7728, 2472, 120, 0, 0, 1, 486, 8451, 27876, 23607, 4950, 165
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

In the following description the alphabet {0..r} is taken as a basis, with r = 3 in this case.
For example, the quaternary word 2031233 of length n=7, has m=4 strictly increasing runs.
The empty word has n = 0 and m = 0, and T(0, 0) = 1.
T(n, 0) = 0 for n >= 1.
T(n, m) <> 0 for m <= n <= m*(r+1). T(m*(r+1), m) = 1.
T(n,m) is a partition, based on m, of all the words of length n, so Sum_{k=0..n} T(n,k) = (r+1)^n.


REFERENCES

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


LINKS



FORMULA

Refer to comment to A120987 concerning formulas for general values of r and considerations.
Therefrom we get
T(n, m) = Qsc(3, n, m) =
Nb(4*mn, 3, n+1) = Nb(4*(nm)+3, 3, n+1) =
Sum_{j=0..n+1} (1)^j*Cb(n+1, j)*Cb(4*(mj), 4*(mj)n) =
Sum_{j=0..m} (1)^(mj)*Cb(n+1, mj)*Cb(4*j, n) =
(in this last version Cb(n,m) can be replaced by binomial(n,m))
Sum_{j=0..m} (1)^(mj)*binomial(n+1, mj)*binomial(4*j, n) = [z^n, t^m](1t)/(1t(1+(1t)z)^4) where [x^n]F(x) denotes the coefficient of x^n in the formal power series expansion of F(x),
Nb(s,r,n) denotes the (r+1)nomial coefficient [x^s](1+x+..+x^r)^n,(Nb(s,3,n) = A008287(n,s)).
Cb(x,m) denotes the binomial coefficient in its extended falling factorial notation (Cb(x,m)= x^_m/m! iff m is a nonnegative integer, 0 otherwise), as defined in the Graham et al. reference.
The diagonal T(n, n) = Nb(3, 3, n+1) = Sum_{j=0..n} (1)^(nj)*Cb(n+1, nj)*Cb(4*j, n) = Cb(n+3, 3) = binomial(n+3, 3) = A000292(n+1).


EXAMPLE

Triangle starts:
1;
0, 4;
0, 6, 10;
0, 4, 40, 20;
0, 1, 65, 155, 35;
0, 0, 56, 456, 456, 56;
.
T(3,2) = 40, which accounts for the following words:
[0 <= a <= 0, 1  0 <= b <= 1] = 2
[0 <= a <= 1, 2  0 <= b <= 2] = 6
[0 <= a <= 2, 3  0 <= b <= 3] = 12
[0 <= a <= 3  0, 1 <= b <= 3] = 12
[1 <= a <= 3  1, 2 <= b <= 3] = 6
[2 <= a <= 3  2, 3 <= b <= 3] = 2


PROG

(MuPAD) T:=(n, m)>_plus((1)^(mj)*binomial(n+1, mj)*binomial(4*j, n)$j=0..m):
(PARI) T(n, k) = sum(j=0, k, (1)^(kj)*binomial(n+1, kj)*binomial(4*j, n));
tabl(nn) = for (n=0, nn, for (k=0, n, print1(T(n, k), ", ")); print()); \\ Michel Marcus, Feb 09 2016


CROSSREFS



KEYWORD



AUTHOR



STATUS

approved



