A225085 -id:A225085 - cp's OEIS frontend

A225084 Triangle read by rows: T(n,k) is the number of compositions of n with maximal up-step k; n>=1, 0<=k

1, 2, 0, 3, 1, 0, 5, 2, 1, 0, 7, 6, 2, 1, 0, 11, 12, 6, 2, 1, 0, 15, 26, 14, 6, 2, 1, 0, 22, 50, 33, 14, 6, 2, 1, 0, 30, 97, 72, 34, 14, 6, 2, 1, 0, 42, 180, 156, 77, 34, 14, 6, 2, 1, 0, 56, 332, 328, 173, 78, 34, 14, 6, 2, 1, 0, 77, 600, 681, 378, 177, 78, 34, 14, 6, 2, 1, 0, 101, 1078, 1393, 818, 393, 178, 78, 34, 14, 6, 2, 1, 0

Offset: 1

Joerg Arndt, Apr 27 2013

T(n,k) is the number of compositions [p(1), p(2), ..., p(k)] of n such that max(p(j) - p(j-1)) == k.
The first column is A000041 (partition numbers).
Sum of first and second column is A003116.
Sum of the first three columns is A224959.
The second columns deviates from A054454 after the term 600.
Row sums are A011782.

			Triangle starts:
01: 1,
02: 2, 0,
03: 3, 1, 0,
04: 5, 2, 1, 0,
05: 7, 6, 2, 1, 0,
06: 11, 12, 6, 2, 1, 0,
07: 15, 26, 14, 6, 2, 1, 0,
08: 22, 50, 33, 14, 6, 2, 1, 0,
09: 30, 97, 72, 34, 14, 6, 2, 1, 0,
10: 42, 180, 156, 77, 34, 14, 6, 2, 1, 0,
11: 56, 332, 328, 173, 78, 34, 14, 6, 2, 1, 0,
12: 77, 600, 681, 378, 177, 78, 34, 14, 6, 2, 1, 0,
13: 101, 1078, 1393, 818, 393, 178, 78, 34, 14, 6, 2, 1, 0,
14: 135, 1917, 2821, 1746, 863, 397, 178, 78, 34, 14, 6, 2, 1, 0,
15: 176, 3393, 5660, 3695, 1872, 877, 398, 178, 78, 34, 14, 6, 2, 1, 0,
...
The fifth row corresponds to the following statistics:
#:  M   composition
01:  0  [ 1 1 1 1 1 ]
02:  1  [ 1 1 1 2 ]
03:  1  [ 1 1 2 1 ]
04:  2  [ 1 1 3 ]
05:  1  [ 1 2 1 1 ]
06:  1  [ 1 2 2 ]
07:  2  [ 1 3 1 ]
08:  3  [ 1 4 ]
09:  0  [ 2 1 1 1 ]
10:  1  [ 2 1 2 ]
11:  0  [ 2 2 1 ]
12:  1  [ 2 3 ]
13:  0  [ 3 1 1 ]
14:  0  [ 3 2 ]
15:  0  [ 4 1 ]
16:  0  [ 5 ]
There are 7 compositions with no up-step (M=0), 6 with M=1, 2 with M=2, and 1 with M=3.

Joerg Arndt and Alois P. Heinz, Rows n = 1..141, flattened

Cf. A225085 (partial sums of rows).

T(2n,n) gives A059570.

b:= proc(n, v) option remember; `if`(n=0, 1, add((p->
      `if`(i seq(coeff(b(n, 0), x, i), i=0..n-1):
seq(T(n), n=1..14);  # Alois P. Heinz, Feb 22 2014

b[n_, v_] := b[n, v] = If[n == 0, 1, Sum[Function[{p}, If[iJean-François Alcover, Feb 18 2015, after Alois P. Heinz *)

A224959 Number of compositions [p(1), p(2), ..., p(k)] of n such that p(j) - p(j-1) <= 2.

Original entry on oeis.org

1, 1, 2, 4, 8, 15, 29, 55, 105, 199, 378, 716, 1358, 2572, 4873, 9229, 17480, 33102, 62688, 118709, 224795, 425676, 806068, 1526371, 2890338, 5473125, 10363871, 19624925, 37161558, 70368705, 133249369, 252319408, 477788980, 904735349, 1713195705, 3244086145

Offset: 0

Joerg Arndt, Apr 21 2013

nonn

			There are a(5) = 15 such compositions of 5:
01:  [ 1 1 1 1 1 ]
02:  [ 1 1 1 2 ]
03:  [ 1 1 2 1 ]
04:  [ 1 1 3 ]
05:  [ 1 2 1 1 ]
06:  [ 1 2 2 ]
07:  [ 1 3 1 ]
08:  [ 2 1 1 1 ]
09:  [ 2 1 2 ]
10:  [ 2 2 1 ]
11:  [ 2 3 ]
12:  [ 3 1 1 ]
13:  [ 3 2 ]
14:  [ 4 1 ]
15:  [ 5 ]
(the single forbidden composition is [ 1 4 ]).

Alois P. Heinz, Table of n, a(n) for n = 0..3607

Cf. A003116 (compositions such that p(j) - p(j-1) <= 1).
Cf. A225084 (triangle: compositions of n such that max(p(j) - p(j-1)) = k).
Cf. A225085 (triangle: compositions of n such that max(p(j) - p(j-1)) <= k).

b:= proc(n, i) option remember;
      `if`(n=0, 1, add(b(n-j, max(1, j-2)), j=i..n))
    end:
a:= n-> b(n, 1):
seq(a(n), n=0..40);  # Alois P. Heinz, May 02 2013

b[n_, i_] := b[n, i] = If[n==0, 1, Sum[b[n-j, Max[1, j-2]], {j, i, n}]];
a[n_] := b[n, 1];
a /@ Range[0, 40] (* Jean-François Alcover, Dec 19 2020, after Alois P. Heinz *)

a(n) ~ c * d^n, where d=1.893587506319686491635881459546948770530553555112342985931092896452453511... and c=0.6398882559654423774981963082429746674258714212085034829366885993226... - Vaclav Kotesovec, May 01 2014

cp's OEIS Frontend

A225084 Triangle read by rows: T(n,k) is the number of compositions of n with maximal up-step k; n>=1, 0<=k

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica