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

Author

Jon Perry, Feb 06 2004

Keywords

• nonn

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

Examples

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

Crossrefs

Cf. A034297, A003116, A000041.

Programs

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

Extensions

More terms from Vladeta Jovovic, Feb 13 2004

More terms from David Wasserman, Feb 02 2006