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

Author

Alois P. Heinz, Nov 24 2013

Keywords

• nonn

Comments

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

Examples

			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].
		

Links

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

Crossrefs

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

Column k=3 of A243081.

Programs

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 *)