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

Comments

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

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.

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

Example

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

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

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.

Sequence in context: A168642 A357750 A234597 * A296033 A296968 A184552

Adjacent sequences: A261979 A261980 A261981 * A261983 A261984 A261985

Keyword

nonn

Author

Alois P. Heinz, Sep 07 2015

Status

approved