A129531 Triangle read by rows: T(n,k) is the number of 4-ary words of length n on {0,1,2,3} having k inversions (n >= 0, k >= 0).

1, 4, 10, 6, 20, 20, 20, 4, 35, 45, 65, 60, 35, 15, 1, 56, 84, 144, 180, 200, 152, 120, 60, 24, 4, 84, 140, 266, 386, 526, 584, 590, 524, 424, 290, 164, 86, 26, 6, 120, 216, 440, 700, 1064, 1384, 1720, 1844, 1940, 1820, 1616, 1272, 956, 620, 380, 184, 80, 24, 4

Offset

0,2

Comments

Row n has (apparently) ceiling((3n^2+4)/8) terms.

Row sums are equal to 4^n = A000302(n).

Alternating row sums are 4^(ceiling(n/2)).

T(n,0) = (n+1)*(n+2)(n+3)/6 = A000292(n+1).

Sum_{k>=0} k*T(n,k) = 3*n*(n-1)*4^(n-2) = A129532(n).

This sequence is mentioned in the Andrews-Savage-Wilf paper. - Omar E. Pol, Jan 30 2012

References

G. E. Andrews, The Theory of Partitions, Addison-Wesley, 1976.

M. Bona, Combinatorics of Permutations, Chapman & Hall/CRC, Boca Raton, FL, 2004, pp. 57-61.

Links

Table of n, a(n) for n=0..57.

G. E. Andrews, C. D. Savage and H. S. Wilf, Hypergeometric identities associated with statistics on words

Mark A. Shattuck and Carl G. Wagner, Parity Theorems for Statistics on Lattice Paths and Laguerre Configurations, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.1.

Formula

Generating polynomial of row n is Sum_{a=0..n} Sum_{b=0..n-a} Sum_{c=0..n-a-b} binomial[n; a,b,c,n-a-b-c], where binomial[n;a,b,c,d] (a+b+c+d=n) is a q-multinomial coefficient.

Example

T(2,1)=6 because we have 10, 20, 30, 21, 31 and 32.
Triangle starts:
   1;
   4;
  10,   6;
  20,  20,  20,   4;
  35,  45,  65,  60,  35,  15,   1;
  56,  84, 144, 180, 200, 152, 120,  60,  24,   4;

Maple

for n from 0 to 12 do br[n]:=sum(q^i, i=0..n-1) od: for n from 0 to 12 do f[n]:=simplify(product(br[j], j=1..n)) od: mbr:=(n, a, b, c, d)->simplify(f[n]/f[a]/f[b]/f[c]/f[d]): for n from 0 to 8 do G[n]:=sort(simplify(sum(sum(sum(mbr(n, a, b, c, n-a-b-c), c=0..n-a-b), b=0..n-a), a=0..n))) od: for n from 0 to 8 do seq(coeff(G[n], q, j), j=0..ceil((3*n^2-4)/8)) od; # yields sequence in triangular form

Crossrefs

Cf. A000302, A000292, A129532, A083906.

Sequence in context: A347116 A205016 A241619 * A298264 A014476 A080362

Adjacent sequences: A129528 A129529 A129530 * A129532 A129533 A129534

Keyword

nonn,tabf

Author

Emeric Deutsch, Apr 22 2007

Status

approved