A129529 Triangle read by rows: T(n,k) is the number of ternary words of length n on {0,1,2} that have k inversions (n >= 0, k >= 0).

1, 3, 6, 3, 10, 8, 8, 1, 15, 15, 21, 18, 9, 3, 21, 24, 39, 45, 48, 30, 24, 9, 3, 28, 35, 62, 82, 107, 108, 101, 81, 62, 37, 17, 8, 1, 36, 48, 90, 129, 186, 222, 264, 252, 255, 219, 183, 126, 90, 48, 27, 9, 3, 45, 63, 123, 186, 285, 372, 492, 561, 624, 648, 651, 597, 537, 435, 336, 249, 165, 99, 54, 27, 9, 3

Offset: 0

Author

Emeric Deutsch, Apr 22 2007

Keywords

• nonn
• tabf

Comments

Row n has 1 + floor(n^2/3) terms.

Row sums are equal to 3^n = A000244(n).

Alternating row sums are 3^(ceiling(n/2)) = A108411(n+1).

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

Examples

			T(3,2) = 8 because we have 100, 110, 120, 200, 201, 211, 220 and 221.
Triangle starts:
   1;
   3;
   6,  3;
  10,  8,  8,  1;
  15, 15, 21, 18,  9,  3;
  21, 24, 39, 45, 48, 30, 24,  9,  3;
  ...
		

References

• M. Bona, Combinatorics of Permutations, Chapman & Hall/CRC, Boca Raton, FL, 2004, pp. 57-61.
• G. E. Andrews, The Theory of Partitions, Addison-Wesley, 1976.

Links

• Alois P. Heinz, Rows n = 0..50, flattened
• 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. A000244, A056449, A083906, A108411, A000217, A129530, A129531, A129532.

Programs

Maple

for n from 0 to 40 do br[n]:=sum(q^i,i=0..n-1) od: for n from 0 to 40 do f[n]:=simplify(product(br[j],j=1..n)) od: mbr:=(n,a,b,c)->simplify(f[n]/f[a]/f[b]/f[c]): for n from 0 to 9 do G[n]:=sort(simplify(sum(sum(mbr(n,a,b,n-a-b),b=0..n-a),a=0..n))) od: for n from 0 to 9 do seq(coeff(G[n],q,j),j=0..floor(n^2/3)) od; # yields sequence in triangular form
# second Maple program:
b:= proc(n, l) option remember; `if`(n=0, 1, add(expand(b(n-1, `if`(j<3,
      subsop(j=l[j]+1, l), l)))*x^([0, l[1], l[1]+l[2]][j]), j=1..3))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, [0$2])):
seq(T(n), n=0..10);  # Alois P. Heinz, Feb 12 2025

Mathematica

b[n_, l_] := b[n, l] =
   If[n == 0, 1, Sum[Expand[b[n-1, If[j < 3, ReplacePart[l, j -> l[[j]]+1], l]]]*x^({0, l[[1]], l[[1]]+l[[2]]}[[j]]), {j, 1, 3}]];
T[n_] := With[{p = b[n, {0, 0}]}, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]];
Table[T[n], {n, 0, 10}] // Flatten (* Jean-François Alcover, Apr 13 2025, after Alois P. Heinz *)

Formula

T(n,0) = (n+1)*(n+2)/2 = A000217(n+1).

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

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

Sum_{k=0..floor(n^2/3)} (-1)^k * T(n,k) = A056449(n). - Alois P. Heinz, Feb 12 2025