A232464 Number of compositions of n avoiding the pattern 1111.

1, 1, 2, 4, 7, 15, 26, 52, 93, 173, 310, 556, 1041, 1789, 3098, 5620, 9725, 16377, 28764, 48518, 82889, 137161, 237502, 390084, 646347, 1055975, 1774036, 2907822, 4698733, 7581093, 12381660, 19891026, 32113631, 51110319, 80777888, 130175410, 204813395

Offset

0,3

Comments

Number of compositions of n into parts with multiplicity <= 3.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..3000

Example

a(5) = 15: [5], [4,1], [3,2], [2,3], [1,4], [1,2,2], [2,1,2], [1,1,3], [3,1,1], [2,2,1], [1,3,1], [1,2,1,1], [2,1,1,1], [1,1,2,1], [1,1,1,2].
a(6) = 26: [6], [3,3], [5,1], [4,2], [2,4], [1,5], [4,1,1], [3,2,1], [2,3,1], [1,4,1], [3,1,2], [2,2,2], [1,3,2], [1,2,3], [2,1,3], [1,1,4], [1,2,2,1], [2,1,2,1], [1,1,3,1], [3,1,1,1], [2,2,1,1], [1,3,1,1], [1,2,1,2], [2,1,1,2], [1,1,2,2], [1,1,1,3].

Maple

b:= proc(n, i, p) option remember; `if`(n=0, p!, `if`(i<1, 0,
      add(b(n-i*j, i-1, p+j)/j!, j=0..min(n/i, 3))))
    end:
a:= n-> b(n$2, 0):
seq(a(n), n=0..50);

Mathematica

f[list_]:=Apply[And, Table[Count[list, i]<4, {i, 1, Max[list]}]];
g[list_]:=Length[list]!/Apply[Times, Table[Count[list, i]!, {i, 1, Max[list]}]];
a[n_] := If[n == 0, 1, Total[Map[g, Select[IntegerPartitions[n], f]]]];
Table[a[n], {n, 0, 40}] (* Geoffrey Critzer, Nov 25 2013, updated by Jean-François Alcover, Nov 20 2023 *)

Crossrefs

Cf. A001935 (partitions avoiding 1111), A032020 (pattern 11), A232432 (pattern 111), A232394 (consecutive pattern 1111).

Column k=3 of A243081.

Sequence in context: A027167 A259090 A358832 * A264292 A259592 A291220

Adjacent sequences: A232461 A232462 A232463 * A232465 A232466 A232467

Keyword

nonn

Author

Alois P. Heinz, Nov 24 2013

Status

approved