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

Author

Geoffrey Critzer, Mar 31 2014

Keywords

• nonn

Examples

			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.
		

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

Crossrefs

Cf. A007690.

Programs

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

Formula

G.f.: 1 + Sum_{m>1} C(m,x)/(1-x^m) where C(m,x) = x^m + Sum_{i=2..m-2} m! * x^m * C(m-i,x)/(i! * (m-i)! * (1 - x^(m-i))). - John Tyler Rascoe, Jan 09 2025

Extensions

More terms from Alois P. Heinz, Mar 31 2014