A189074 Irregular triangle read by rows: T(n,k) = number of compositions of n with k inversions (n >= 0, 0 <= k <= floor(n^2/8)).

1, 1, 2, 3, 1, 5, 2, 1, 7, 5, 3, 1, 11, 8, 7, 4, 2, 15, 15, 14, 10, 6, 3, 1, 22, 23, 26, 21, 17, 10, 6, 2, 1, 30, 37, 44, 42, 36, 27, 19, 11, 6, 3, 1, 42, 55, 73, 74, 73, 60, 50, 34, 24, 13, 8, 4, 2, 56, 83, 115, 128, 133, 123, 109, 87, 68, 48, 32, 20, 12, 6, 3, 1, 77, 118, 177, 209, 235, 230, 223, 192, 166, 129, 100, 70, 51, 31, 20, 11, 6, 2, 1

Offset

0,3

Comments

Row sums are powers of 2.

The Heubach et al. reference has a table for n <= 12.

Links

Alois P. Heinz, Rows n = 0..25, flattened

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

Example

T(4,0) = 5: [4], [1,3], [2,2], [1,1,2], [1,1,1,1] - all partitions of 4.
T(5,2) = 3: [2,2,1], [3,1,1], [1,2,1,1].
T(6,4) = 2: [2,2,1,1], [2,1,1,1,1].
Triangle begins:
1
1
2
3   1
5   2  1
7   5  3  1
11  8  7  4  2
15 15 14 10  6  3 1
22 23 26 21 17 10 6 2 1
...

Maple

T:= proc(n) option remember; local b, p;
      b:=proc(m, i, l)
           if m=0 then p(i):= p(i)+1
         else seq(b(m-h, i+nops(select(j->j<h, l)), [h, l[]]), h=1..m)
           fi
         end;
      p:= proc() 0 end; forget(p);
      b(n, 0, []); seq(p(i), i=0..floor(n^2/8))
    end:
seq(T(n), n=0..12);  # Alois P. Heinz, Apr 17 2011

Mathematica

T[n_] := T[n] = Module[{b, p}, b[m_, i_, l_List] := If[m == 0, p[i] = p[i] + 1, Table[b[m-h, i+Length[Select[ l, #<h&]], Join[{h}, l]], {h, 1, m}]]; Clear[p]; p[_]=0; b[n, 0, {}]; Table[p[i], {i, 0, Floor[n^2/8]}]]; Table[ T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, Jan 17 2016, after Alois P. Heinz *)

Crossrefs

The first two columns are A000041 and A058884 (for n>0). Lengths of rows are given by 1+A001972(n-3). Row sums are A011782.

Sequence in context: A066909 A095195 A229961 * A255973 A169615 A076791

Adjacent sequences: A189071 A189072 A189073 * A189075 A189076 A189077

Keyword

nonn,tabf

Author

N. J. A. Sloane, Apr 16 2011

Status

approved