A189073 Triangle read by rows: T(n,k) is the number of inversions in k-compositions of n for n >= 3, 2 <= k <= n-1.

1, 1, 3, 2, 6, 6, 2, 12, 18, 10, 3, 18, 42, 40, 15, 3, 27, 78, 110, 75, 21, 4, 36, 132, 240, 240, 126, 28, 4, 48, 204, 460, 600, 462, 196, 36, 5, 60, 300, 800, 1290, 1302, 812, 288, 45, 5, 75, 420, 1300, 2490, 3108, 2548, 1332, 405, 55, 6, 90, 570, 2000, 4440, 6594, 6692, 4608, 2070, 550, 66

Offset

3,3

Comments

The Heibach et al. reference has a table for n <= 14.

Links

Alois P. Heinz, Rows n = 3..143, flattened

S. Heubach, A. Knopfmacher, M. E. Mays and A. Munagi, Inversions in Compositions of Integers, to appear in Quaestiones Mathematicae.

Formula

G.f.: (1-x)*x^3/((1+x)*(1-x-y*x)^3). - Geoffrey Critzer, Mar 19 2014

Example

Triangle begins:
1;
1,  3;
2,  6,   6;
2, 12,  18,   10;
3, 18,  42,   40,   15;
3, 27,  78,  110,   75,   21;
4, 36, 132,  240,  240,  126,   28;
4, 48, 204,  460,  600,  462,  196,   36;
5, 60, 300,  800, 1290, 1302,  812,  288,   45;
5, 75, 420, 1300, 2490, 3108, 2548, 1332,  405,  55;
6, 90, 570, 2000, 4440, 6594, 6692, 4608, 2070, 550, 66;
...
T(5,3) = 6 because we have: 3+1+1, 1+3+1, 1+1+3, 2+2+1, 2+1+2, 1+2+2 having 2,1,0,2,1,0 inversions respectively. - Geoffrey Critzer, Mar 19 2014

Maple

T:= proc(n, k) option remember;
      if k=2 then floor((n-1)/2)
    elif k>=n then 0
    else T(n-1, k) +k/(k-2) *T(n-1, k-1)
      fi
    end:
seq(seq(T(n, k), k=2..n-1), n=3..13);  # Alois P. Heinz, Apr 17 2011

Mathematica

T[n_, k_] := T[n, k] = Which[k == 2, Floor[(n-1)/2], k >= n, 0, True, T[n-1, k] + k/(k-2)*T[n-1, k-1]]; Table[Table[T[n, k], {k, 2, n-1}], {n, 3, 13}] // Flatten (* Jean-François Alcover, Jan 14 2014, after Alois P. Heinz *)

Crossrefs

Row sums are A189052. The first column is A004526(n-1). Diagonal is A000217(n-2). Lower diagonal is A002411(n-3). 2nd lower diagonal is A001621(n-4).

Sequence in context: A370377 A306443 A336518 * A107271 A196565 A104633

Adjacent sequences: A189070 A189071 A189072 * A189074 A189075 A189076

Keyword

nonn,tabl

Author

N. J. A. Sloane, Apr 16 2011

Status

approved