A261982 Number of compositions of n with some part repeated.

0, 0, 1, 1, 5, 11, 21, 51, 109, 229, 455, 959, 1947, 3963, 7999, 16033, 32333, 64919, 130221, 260967, 522733, 1045825, 2093855, 4189547, 8382315, 16768455, 33543127, 67093261, 134193413, 268404995, 536829045, 1073686083, 2147408773, 4294869253, 8589803783

Offset: 0

Author

Alois P. Heinz, Sep 07 2015

Keywords

• nonn

Comments

Also compositions matching the pattern (1,1). - Gus Wiseman, Jun 23 2020

Examples

			a(2) = 1: 11.
a(3) = 1: 111.
a(4) = 5: 22, 211, 121, 112, 1111.
		

Links

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

Crossrefs

Row sums of A261981 and of A262191.

Cf. A262047.

The version for patterns is A019472.

The (1,1)-avoiding version is A032020.

The case of partitions is A047967.

(1,1,1)-matching compositions are counted by A335455.

Patterns matched by compositions are counted by A335456.

(1,1)-matching compositions are ranked by A335488.

Cf. A011782, A056986, A106356, A181796, A238279, A269134, A333755.

Programs

Maple

b:= proc(n, k) option remember; `if`(k<0 or n<0, 0,
      `if`(k=0, `if`(n=0, 1, 0), b(n-k, k) +k*b(n-k, k-1)))
    end:
a:= n-> ceil(2^(n-1))-add(b(n, k), k=0..floor((sqrt(8*n+1)-1)/2)):
seq(a(n), n=0..40);

Mathematica

b[n_, k_] := b[n, k] = If[k<0 || n<0, 0, If[k==0, If[n==0, 1, 0], b[n-k, k] + k*b[n-k, k-1]]]; a[n_] := Ceiling[2^(n-1)]-Sum[b[n, k], {k, 0, Floor[ (Sqrt[8n+1]-1)/2]}]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Feb 08 2017, translated from Maple *)
Table[Length[Join@@Permutations/@Select[IntegerPartitions[n],Length[#]>Length[Split[#]]&]],{n,0,10}] (* Gus Wiseman, Jun 24 2020 *)

Formula

a(n) = A011782(n) - A032020(n).

G.f.: (1 - x) / (1 - 2*x) - Sum_{k>=0} k! * x^(k*(k + 1)/2) / Product_{j=1..k} (1 - x^j). - Ilya Gutkovskiy, Jan 30 2020