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

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,2

Comments

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

Links

Table of n, a(n) for n=1..41.

Example

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

Prog

(PARI) 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

Crossrefs

Cf. A034297, A003116, A000041.

Sequence in context: A266650 A205183 A233759 * A051058 A332578 A026625

Adjacent sequences: A090749 A090750 A090751 * A090753 A090754 A090755

Keyword

nonn

Author

Jon Perry, Feb 06 2004

Extensions

More terms from Vladeta Jovovic, Feb 13 2004

More terms from David Wasserman, Feb 02 2006

Status

approved