login
A090752
Number of compositions (ordered partitions) of n whereby at most 1 increase is allowed and this increase must be by 1.
0
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
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
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