A335455 Number of compositions of n with some part appearing more than twice.

0, 0, 0, 1, 1, 5, 11, 30, 69, 142, 334, 740, 1526, 3273, 6840, 14251, 29029, 59729, 122009, 248070, 500649, 1012570, 2040238, 4107008, 8257466, 16562283, 33229788, 66621205, 133478437, 267326999, 535146239, 1071183438, 2143604313, 4289194948, 8581463248

Offset

0,6

Comments

Also the number of compositions of n matching the pattern (1,1,1).

A composition of n is a finite sequence of positive integers summing to n.

Links

Table of n, a(n) for n=0..34.

Wikipedia, Permutation pattern

Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

Formula

a(n > 0) = 2^(n - 1) - A232432(n).

Example

The a(3) = 1 through a(6) = 11 compositions:
  (111)  (1111)  (1112)   (222)
                 (1121)   (1113)
                 (1211)   (1131)
                 (2111)   (1311)
                 (11111)  (3111)
                          (11112)
                          (11121)
                          (11211)
                          (12111)
                          (21111)
                          (111111)

Mathematica

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], Max@@Length/@Split[Sort[#]]>=3&]], {n, 0, 10}]

Crossrefs

The case of partitions is A000726.

The avoiding version is A232432.

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

The version for patterns is A335508.

The version for prime indices is A335510.

These compositions are ranked by A335512.

Compositions are counted by A011782.

Combinatory separations are counted by A269134.

Normal patterns matched by compositions are counted by A335456.

Cf. A000740, A034691, A056986, A080599, A106356, A181796, A232464, A238279, A333755.

Sequence in context: A179256 A209659 A266820 * A114688 A257717 A192194

Adjacent sequences: A335452 A335453 A335454 * A335456 A335457 A335458

Keyword

nonn

Author

Gus Wiseman, Jun 15 2020

Status

approved