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

%I #15 Nov 15 2019 23:24:34

%S 1,4,10,6,20,20,20,4,35,45,65,60,35,15,1,56,84,144,180,200,152,120,60,

%T 24,4,84,140,266,386,526,584,590,524,424,290,164,86,26,6,120,216,440,

%U 700,1064,1384,1720,1844,1940,1820,1616,1272,956,620,380,184,80,24,4

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

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

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

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

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

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

%C This sequence is mentioned in the Andrews-Savage-Wilf paper. - _Omar E. Pol_, Jan 30 2012

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

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

%H G. E. Andrews, C. D. Savage and H. S. Wilf, <a href="http://www.math.psu.edu/andrews/pdf/286.pdf">Hypergeometric identities associated with statistics on words</a>

%H Mark A. Shattuck and Carl G. Wagner, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL8/Shattuck2/shattuck44.html">Parity Theorems for Statistics on Lattice Paths and Laguerre Configurations</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.1.

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

%e T(2,1)=6 because we have 10, 20, 30, 21, 31 and 32.

%e Triangle starts:

%e 1;

%e 4;

%e 10, 6;

%e 20, 20, 20, 4;

%e 35, 45, 65, 60, 35, 15, 1;

%e 56, 84, 144, 180, 200, 152, 120, 60, 24, 4;

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

%Y Cf. A000302, A000292, A129532, A083906.

%K nonn,tabf

%O 0,2

%A _Emeric Deutsch_, Apr 22 2007