cp's OEIS Frontend

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

%I A189074 #43 Dec 26 2023 10:03:11
%S A189074 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,
%T A189074 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,
%U A189074 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
%N 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)).
%C A189074 Row sums are powers of 2.
%C A189074 The Heubach et al. reference has a table for n <= 12.
%H A189074 Alois P. Heinz, <a href="/A189074/b189074.txt">Rows n = 0..25, flattened</a>
%H A189074 S. Heubach, A. Knopfmacher, M. E. Mays and A. Munagi, <a href="http://www.calstatela.edu/faculty/sheubac/papers/inversns_in_composns.pdf ">Inversions in Compositions of Integers</a>, to appear in Quaestiones Mathematicae.
%e A189074 T(4,0) = 5: [4], [1,3], [2,2], [1,1,2], [1,1,1,1] - all partitions of 4.
%e A189074 T(5,2) = 3: [2,2,1], [3,1,1], [1,2,1,1].
%e A189074 T(6,4) = 2: [2,2,1,1], [2,1,1,1,1].
%e A189074 Triangle begins:
%e A189074 1
%e A189074 1
%e A189074 2
%e A189074 3   1
%e A189074 5   2  1
%e A189074 7   5  3  1
%e A189074 11  8  7  4  2
%e A189074 15 15 14 10  6  3 1
%e A189074 22 23 26 21 17 10 6 2 1
%e A189074 ...
%p A189074 T:= proc(n) option remember; local b, p;
%p A189074       b:=proc(m, i, l)
%p A189074            if m=0 then p(i):= p(i)+1
%p A189074          else seq(b(m-h, i+nops(select(j->j<h, l)), [h, l[]]), h=1..m)
%p A189074            fi
%p A189074          end;
%p A189074       p:= proc() 0 end; forget(p);
%p A189074       b(n, 0, []); seq(p(i), i=0..floor(n^2/8))
%p A189074     end:
%p A189074 seq(T(n), n=0..12);  # _Alois P. Heinz_, Apr 17 2011
%t A189074 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_ *)
%Y A189074 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.
%K A189074 nonn,tabf
%O A189074 0,3
%A A189074 _N. J. A. Sloane_, Apr 16 2011