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,3

Comments

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

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.

Example

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

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

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.

Sequence in context: A014529 A095015 A024367 * A037078 A034431 A339610

Adjacent sequences: A232429 A232430 A232431 * A232433 A232434 A232435

Keyword

nonn

Author

Alois P. Heinz, Nov 23 2013

Status

approved