A232432 Number of compositions of n avoiding the pattern 111.

1, 1, 2, 3, 7, 11, 21, 34, 59, 114, 178, 284, 522, 823, 1352, 2133, 3739, 5807, 9063, 14074, 23639, 36006, 56914, 87296, 131142, 214933, 324644, 487659, 739291, 1108457, 1724673, 2558386, 3879335, 5772348, 8471344, 12413666, 19109304, 27886339, 40816496

Offset: 0

Author

Alois P. Heinz, Nov 23 2013

Keywords

• nonn

Comments

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

Examples

			a(4) = 7: [4], [3,1], [2,2], [1,3], [2,1,1], [1,2,1], [1,1,2].
a(5) = 11: [5], [4,1], [3,2], [2,3], [1,4], [3,1,1], [2,2,1], [1,3,1], [2,1,2], [1,2,2], [1,1,3].
a(6) = 21: [6], [4,2], [3,3], [5,1], [2,4], [1,5], [2,1,3], [1,2,3], [1,1,4], [4,1,1], [3,2,1], [2,3,1], [1,4,1], [3,1,2], [1,3,2], [1,2,2,1], [2,1,1,2], [1,2,1,2], [1,1,2,2], [2,2,1,1], [2,1,2,1].
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• Wikipedia, Permutation pattern
• Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

Crossrefs

Cf. A000726 (partitions avoiding 111), A032020 (pattern 11), A128695 (adjacent pattern 111).

Column k=2 of A243081.

The case of partitions is ranked by A004709.

The version for patterns is A080599.

(1,1,1,1)-avoiding partitions are counted by A232464.

The (1,1,1)-matching version is A335455.

Patterns matched by compositions are counted by A335456.

The version for prime indices is A335511.

(1,1,1)-avoiding compositions are ranked by A335513.

Cf. A011782, A006918, A102726, A106356, A238279, A333755.

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, 2))))
    end:
a:= n-> b(n$2, 0):
seq(a(n), n=0..50);

Mathematica

f[list_]:=Apply[And,Table[Count[list,i]<3,{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, 35}] (* Geoffrey Critzer, Nov 25 2013, updated by Jean-François Alcover, Nov 20 2023 *)