A003116 -id:A003116 - cp's OEIS frontend

A168443 Triangle, T(n,k) = number of compositions a(1),...,a(k) of n, such that a(i+1) <= a(i) + 1 for 1 <= i < k.

1, 1, 1, 1, 2, 1, 1, 2, 3, 1, 1, 3, 4, 4, 1, 1, 3, 6, 7, 5, 1, 1, 4, 7, 11, 11, 6, 1, 1, 4, 9, 15, 19, 16, 7, 1, 1, 5, 11, 19, 29, 31, 22, 8, 1, 1, 5, 13, 25, 39, 52, 48, 29, 9, 1, 1, 6, 15, 30, 53, 76, 88, 71, 37, 10, 1, 1, 6, 18, 37, 67, 107, 140, 142, 101, 46, 11, 1, 1, 7, 20, 44, 84, 143, 207, 245, 220, 139, 56, 12, 1

Offset: 1

Vladeta Jovovic, Nov 25 2009

			Triangle T(n,k) begins:
  1;
  1, 1;
  1, 2, 1;
  1, 2, 3,  1;
  1, 3, 4,  4,  1;
  1, 3, 6,  7,  5,  1;
  1, 4, 7, 11, 11,  6, 1;
  1, 4, 9, 15, 19, 16, 7, 1;
  ...

Alois P. Heinz, Rows n = 1..200, flattened

Cf. A003116 (row sums), A168396.

b:= proc(n, k) option remember; expand(`if`(n=0, 1,
      x*add(b(n-j, j), j=1..min(n, k+1))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n$2)):
seq(T(n), n=1..14);  # Alois P. Heinz, Jan 21 2022

b[n_, k_] := b[n, k] = Expand[If[n == 0, 1,
     x*Sum[b[n - j, j], {j, 1, Min[n, k + 1]}]]];
T[n_] := Rest@CoefficientList[b[n, n], x];
Table[T[n], {n, 1, 14}] // Flatten (* Jean-François Alcover, Apr 14 2022, after Alois P. Heinz *)

A168445 Number of compositions a(1),...,a(k) of n, for some k, such that a(i+1) <= a(i) + 1 for 1 <= i < k and a(1) <= a(k) + 1.

Original entry on oeis.org

1, 2, 4, 6, 11, 18, 31, 52, 91, 155, 268, 464, 802, 1390, 2411, 4178, 7249, 12578, 21823, 37870, 65724, 114061, 197960, 343578, 596317, 1034983, 1796359, 3117837, 5411478, 9392460, 16302081, 28294850, 49110242, 85238716, 147945552, 256783448, 445689300

Offset: 1

Vladeta Jovovic, Nov 25 2009

nonn

Steven R. Finch, Mathematical Constants, Cambridge, 2003, p. 381.

Alois P. Heinz, Table of n, a(n) for n = 1..400

Cf. A003116, A005169.

b:= proc(n,r,f) option remember; `if`(n=0, `if`(f-1<=r, 1, 0),
      add(b(n-i, i, f), i=1..min(r+1, n)))
    end:
a:= n-> add(b(n-i, i, i), i=1..n):
seq(a(n), n=1..40);  # Alois P. Heinz, Dec 15 2009

b[n_, r_, f_] := b[n, r, f] = If[n == 0, If[f - 1 <= r, 1, 0], Sum[b[n - i, i, f], {i, 1, Min [r + 1, n]}]];
a[n_] := Sum[b[n - i, i, i], {i, 1, n}];
Array[a, 40] (* Jean-François Alcover, Nov 10 2020, after Alois P. Heinz *)

a(n) ~ c / r^n, where r = A347901 = 0.576148769142756602297868573719938782354724663118974... is the lowest root of the equation Sum_{k>=0} (-1)^k * r^(k^2) / QPochhammer(r, r, k) = 0 and c = 0.6149126319329581124890112676009720339906790088212712130894... - Vaclav Kotesovec, May 01 2014, updated Sep 09 2020

More terms from Alois P. Heinz, Dec 15 2009

A090752 Number of compositions (ordered partitions) of n whereby at most 1 increase is allowed and this increase must be by 1.

Original entry on oeis.org

1, 2, 4, 7, 13, 21, 36, 56, 89, 134, 204, 296, 435, 618, 879, 1223, 1702, 2323, 3171, 4263, 5720, 7589, 10043, 13158, 17202, 22305, 28839, 37038, 47437, 60391, 76686, 96872, 122047, 153081, 191513, 238625, 296620, 367379, 453948, 559112, 687107

Offset: 1

Jon Perry, Feb 06 2004

nonn

The number of compositions of n in which exactly 1 increase is allowed and this increase must be by 1, is a(n)-A000041(n). - Vladeta Jovovic, Feb 09 2004

			a(5)=13, as we have 5, 41, 32, 23, 311, 221, 212, 122, 2111, 1211, 1121, 1112 and 11111.

Cf. A034297, A003116, A000041.

Ta = matrix(70, 70, i, j, -1); Tn = Ta;
doAllowed(last, left) = local(c); c = Ta[last, left]; if (c == -1, c = 0; for (i = 1, min(last, left), c += b(i, left - i, 1)); c += b(last + 1, left - last - 1, 0); Ta[last, left] = c); c;
doNot(last, left) = local(c); c = Tn[last, left]; if (c == -1, c = 0; for (i = 1, min(last, left), c += b(i, left - i, 0)); Tn[last, left] = c); c;
b(last, left, allowed) = if (left == 0, return(1)); if (left < 0, return(0)); if (allowed, doAllowed(last, left), doNot(last, left));
a(n) = sum (i = 1, n, b(i, n - i, 1)); \\ David Wasserman, Feb 02 2006

More terms from Vladeta Jovovic, Feb 13 2004

More terms from David Wasserman, Feb 02 2006

cp's OEIS Frontend

A168443 Triangle, T(n,k) = number of compositions a(1),...,a(k) of n, such that a(i+1) <= a(i) + 1 for 1 <= i < k.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A168445 Number of compositions a(1),...,a(k) of n, for some k, such that a(i+1) <= a(i) + 1 for 1 <= i < k and a(1) <= a(k) + 1.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A090752 Number of compositions (ordered partitions) of n whereby at most 1 increase is allowed and this increase must be by 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Extensions