login
A335443
Number of compositions of n where neighboring runs have different lengths.
1
1, 1, 2, 2, 5, 8, 13, 24, 42, 68, 122, 210, 360, 622, 1077, 1858, 3198, 5519, 9549, 16460, 28386, 49031, 84595, 145988, 251956, 434805, 750418, 1294998, 2234971, 3857106, 6656383, 11487641, 19825318, 34214136, 59046458, 101901743, 175860875, 303498779
OFFSET
0,3
LINKS
EXAMPLE
a(0) = 1: the empty composition.
a(1) = 1: 1.
a(2) = 2: 2, 11.
a(3) = 2: 3, 111.
a(4) = 5: 4, 22, 112, 211, 1111.
a(5) = 8: 5, 113, 122, 221, 311, 1112, 2111, 11111.
a(6) = 13: 6, 33, 114, 222, 411, 1113, 1221, 2112, 3111, 11112, 11211, 21111, 111111.
a(7) = 24: 7, 115, 133, 223, 322, 331, 511, 1114, 1222, 2113, 2221, 3112, 4111, 11113, 11122, 11311, 21112, 22111, 31111, 111112, 111211, 112111, 211111, 1111111.
a(8) = 42: 8, 44, 116, 224, 233, 332, 422, 611, 1115, 1223, 1331, 2114, 2222, 3113, 3221, 4112, 5111, 11114, 11222, 11411, 12221, 21113, 22211, 31112, 41111, 111113, 111122, 111221, 111311, 112112, 113111, 122111, 211112, 211211, 221111, 311111, 1111112, 1111211, 1112111, 1121111, 2111111, 11111111.
MAPLE
b:= proc(n, l, t) option remember; `if`(n=0, 1, add(add(
`if`(j=t, 0, b(n-i*j, i, j)), j=1..n/i), i={$1..n} minus {l}))
end:
a:= n-> b(n, 0$2):
seq(a(n), n=0..40);
MATHEMATICA
b[n_, l_, t_] := b[n, l, t] = If[n == 0, 1, Sum[Sum[If[j == t, 0,
b[n-i*j, i, j]], {j, 1, n/i}], {i, Range[n]~Complement~{l}}]];
a[n_] := b[n, 0, 0];
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Apr 13 2022, after Alois P. Heinz *)
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Jul 06 2020
STATUS
approved