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

Author

Gus Wiseman, Jun 15 2020

Keywords

• nonn

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.

Examples

			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)
		

Links

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

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.

Programs

Mathematica

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

Formula

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