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

Author

Emeric Deutsch, Apr 22 2007

Keywords

• nonn
• tabf

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

Examples

			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;
		

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

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

Crossrefs

Cf. A000302, A000292, A129532, A083906.

Programs

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

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.