login
Triangle T(n,k) read by rows: T(n,k) is the number of compositions of n with k descents, n>=0, 0<=k<=n.
116

%I #22 Mar 25 2020 06:54:03

%S 1,1,0,2,0,0,3,1,0,0,5,3,0,0,0,7,9,0,0,0,0,11,19,2,0,0,0,0,15,41,8,0,

%T 0,0,0,0,22,77,29,0,0,0,0,0,0,30,142,81,3,0,0,0,0,0,0,42,247,205,18,0,

%U 0,0,0,0,0,0,56,421,469,78,0,0,0,0,0,0,0,0,77,689,1013,264,5,0,0,0,0,0,0,0,0,101,1113,2059,786,37,0,0,0,0,0,0,0,0,0

%N Triangle T(n,k) read by rows: T(n,k) is the number of compositions of n with k descents, n>=0, 0<=k<=n.

%C Counting ascents gives the same triangle.

%C For n > 0, also the number of compositions of n with k + 1 maximal weakly increasing runs. - _Gus Wiseman_, Mar 23 2020

%H Joerg Arndt and Alois P. Heinz, <a href="/A238343/b238343.txt">Rows n = 0..140, flattened</a>

%e Triangle starts:

%e 00: 1;

%e 01: 1, 0;

%e 02: 2, 0, 0;

%e 03: 3, 1, 0, 0;

%e 04: 5, 3, 0, 0, 0;

%e 05: 7, 9, 0, 0, 0, 0;

%e 06: 11, 19, 2, 0, 0, 0, 0;

%e 07: 15, 41, 8, 0, 0, 0, 0, 0;

%e 08: 22, 77, 29, 0, 0, 0, 0, 0, 0;

%e 09: 30, 142, 81, 3, 0, 0, 0, 0, 0, 0;

%e 10: 42, 247, 205, 18, 0, 0, 0, 0, 0, 0, 0;

%e 11: 56, 421, 469, 78, 0, 0, 0, 0, 0, 0, 0, 0;

%e 12: 77, 689, 1013, 264, 5, 0, 0, 0, 0, 0, 0, 0, 0;

%e 13: 101, 1113, 2059, 786, 37, 0, 0, 0, 0, 0, 0, 0, 0, 0;

%e 14: 135, 1750, 4021, 2097, 189, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0;

%e 15: 176, 2712, 7558, 5179, 751, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0;

%e ...

%e From _Gus Wiseman_, Mar 23 2020: (Start)

%e Row n = 5 counts the following compositions:

%e (5) (3,2)

%e (1,4) (4,1)

%e (2,3) (1,3,1)

%e (1,1,3) (2,1,2)

%e (1,2,2) (2,2,1)

%e (1,1,1,2) (3,1,1)

%e (1,1,1,1,1) (1,1,2,1)

%e (1,2,1,1)

%e (2,1,1,1)

%e (End)

%p b:= proc(n, i) option remember; `if`(n=0, 1, expand(

%p add(b(n-j, j)*`if`(j<i, x, 1), j=1..n)))

%p end:

%p T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n, 0)):

%p seq(T(n), n=0..20);

%t b[n_, i_] := b[n, i] = If[n == 0, 1, Sum[b[n-j, j]*If[j<i, x, 1], {j, 1, n}]]; T[n_] := Function[{p}, Table[Coefficient[p, x, i], {i, 0, n}]][b[n, 0]]; Table[T[n], {n, 0, 20}] // Flatten (* _Jean-François Alcover_, Jan 08 2015, translated from Maple *)

%t Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],n==0||Length[Split[#,LessEqual]]==k+1&]],{n,0,9},{k,0,n}] (* _Gus Wiseman_, Mar 23 2020 *)

%Y Columns k=0-10 give: A000041, A241626, A241627, A241628, A241629, A241630, A241631, A241632, A241633, A241634, A241635.

%Y T(3n,n) gives A000045(n+1).

%Y T(3n+1,n) = A136376(n+1).

%Y Row sums are A011782.

%Y Compositions by length are A007318.

%Y The version for co-runs or levels is A106356.

%Y The case of partitions (instead of compositions) is A133121.

%Y The version for runs is A238279.

%Y The version without zeros is A238344.

%Y The version for weak ascents is A333213.

%Y Cf. A008284, A124765, A124766, A332875, A333215.

%K nonn,tabl

%O 0,4

%A _Joerg Arndt_ and _Alois P. Heinz_, Feb 25 2014