cp's OEIS Frontend

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

%I A265644 #26 Dec 18 2017 03:10:02
%S A265644 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,
%T A265644 2128,1128,84,0,0,8,728,5328,7728,2472,120,0,0,1,486,8451,27876,23607,
%U A265644 4950,165
%N 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).
%C A265644 In the following description the alphabet {0..r} is taken as a basis, with r = 3 in this case.
%C A265644 For example, the quaternary word 2|03|123|3 of length n=7, has m=4 strictly increasing runs.
%C A265644 The empty word has n = 0 and m = 0, and T(0, 0) = 1.
%C A265644 T(n, 0) = 0 for n >= 1.
%C A265644 T(n, m) <> 0 for m <= n <= m*(r+1). T(m*(r+1), m) = 1.
%C A265644 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.
%D A265644 R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 2nd. ed., 1994, p. 24, p. 154.
%H A265644 MathPages, <a href="http://www.mathpages.com/home/kmath337.htm">Balls In Bins With Limited Capacity</a>
%F A265644 Refer to comment to A120987 concerning formulas for general values of r and considerations.
%F A265644 Therefrom we get
%F A265644 T(n, m) = Qsc(3, n, m) =
%F A265644 Nb(4*m-n, 3, n+1) = Nb(4*(n-m)+3, 3, n+1) =
%F A265644 Sum_{j=0..n+1} (-1)^j*Cb(n+1, j)*Cb(4*(m-j), 4*(m-j)-n) =
%F A265644 Sum_{j=0..m} (-1)^(m-j)*Cb(n+1, m-j)*Cb(4*j, n) =
%F A265644 (in this last version Cb(n,m) can be replaced by binomial(n,m))
%F A265644 Sum_{j=0..m} (-1)^(m-j)*binomial(n+1, m-j)*binomial(4*j, n) = [z^n, t^m](1-t)/(1-t(1+(1-t)z)^4) where [x^n]F(x) denotes the coefficient of x^n in the formal power series expansion of F(x),
%F A265644 Nb(s,r,n) denotes the (r+1)-nomial coefficient [x^s](1+x+..+x^r)^n,(Nb(s,3,n) = A008287(n,s)).
%F A265644 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.
%F A265644 The diagonal T(n, n) = Nb(3, 3, n+1) = Sum_{j=0..n} (-1)^(n-j)*Cb(n+1, n-j)*Cb(4*j, n) = Cb(n+3, 3) = binomial(n+3, 3) = A000292(n+1).
%e A265644 Triangle starts:
%e A265644 1;
%e A265644 0, 4;
%e A265644 0, 6, 10;
%e A265644 0, 4, 40,  20;
%e A265644 0, 1, 65, 155,  35;
%e A265644 0, 0, 56, 456, 456, 56;
%e A265644 .
%e A265644 T(3,2) = 40, which accounts for the following words:
%e A265644 [0 <= a <= 0, 1 |    0 <= b <= 1]  =   2
%e A265644 [0 <= a <= 1, 2 |    0 <= b <= 2]  =   6
%e A265644 [0 <= a <= 2, 3 |    0 <= b <= 3]  =  12
%e A265644 [0 <= a <= 3    | 0, 1 <= b <= 3]  =  12
%e A265644 [1 <= a <= 3    | 1, 2 <= b <= 3]  =   6
%e A265644 [2 <= a <= 3    | 2, 3 <= b <= 3]  =   2
%o A265644 (MuPAD) T:=(n,m)->_plus((-1)^(m-j)*binomial(n+1, m-j)*binomial(4*j, n)$j=0..m):
%o A265644 (PARI) T(n, k) = sum(j=0, k, (-1)^(k-j)*binomial(n+1, k-j)*binomial(4*j, n));
%o A265644 tabl(nn) = for (n=0, nn, for (k=0, n, print1(T(n, k), ", ")); print()); \\ _Michel Marcus_, Feb 09 2016
%Y A265644 Cf. A119900 (r=1, binary words), A120987 (r=2, ternary words), A008287 (quadrinomial coefficients).
%Y A265644 Row sums give A000302.
%Y A265644 Cf. A000292.
%K A265644 tabl,nonn
%O A265644 0,3
%A A265644 _Giuliano Cabrele_, Dec 13 2015