A240085 Number of compositions of n in which no part is unique (every part appears at least twice).

1, 0, 1, 1, 2, 1, 9, 11, 34, 53, 108, 169, 400, 680, 1530, 2984, 6362, 12498, 25766, 50093, 102126, 199309, 400288, 788227, 1581584, 3135117, 6286310, 12532861, 25121292, 50184582, 100627207, 201208477, 403170900, 806534560, 1615151111, 3231224804, 6467909442

Offset

0,5

References

S. Heubach and T. Mansour, Combinatorics of Compositions and Words, Chapman and Hall, 2009.

Links

Alois P. Heinz and Vaclav Kotesovec, Table of n, a(n) for n = 0..2100 (first 500 terms from Alois P. Heinz)

Vaclav Kotesovec, Graph a(n)/2^n

Example

a(6) = 9 because we have: 3+3, 2+2+2, 2+2+1+1, 2+1+2+1, 2+1+1+2, 1+2+2+1, 1+2+1+2, 1+1+2+2, 1+1+1+1+1+1.

Maple

b:= proc(n, i, t) option remember; `if`(n=0, t!, `if`(i<1, 0,
      b(n, i-1, t) +add(b(n-i*j, i-1, t+j)/j!, j=2..n/i)))
    end:
a:= n-> b(n$2, 0):
seq(a(n), n=0..40);  # Alois P. Heinz, Mar 31 2014

Mathematica

Table[Length[Level[Map[Permutations, Select[IntegerPartitions[n], Apply[And, Table[Count[#, #[[i]]]>1, {i, 1, Length[#]}]]&]], {2}]], {n, 0, 20}]
(* Second program: *)
b[n_, i_, t_] := b[n, i, t] = If[n == 0, t!, If[i < 1, 0, b[n, i - 1, t] + Sum[b[n - i*j, i - 1, t + j]/j!, {j, 2, n/i}]]]; a[n_] := b[n, n, 0]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Aug 29 2016, after Alois P. Heinz *)

Crossrefs

Cf. A007690.

Sequence in context: A368375 A192324 A063579 * A078623 A198204 A099599

Adjacent sequences: A240082 A240083 A240084 * A240086 A240087 A240088

Keyword

nonn

Author

Geoffrey Critzer, Mar 31 2014

Extensions

More terms from Alois P. Heinz, Mar 31 2014

Status

approved