A330773 Number of perfect compositions of n.

1, 1, 1, 3, 1, 5, 1, 11, 3, 5, 1, 27, 1, 5, 5, 49, 1, 27, 1, 27, 5, 5, 1, 163, 3, 5, 11, 27, 1, 49, 1, 261, 5, 5, 5, 231, 1, 5, 5, 163, 1, 49, 1, 27, 27, 5, 1, 1109, 3, 27, 5, 27, 1, 163, 5, 163, 5, 5, 1, 435, 1, 5, 27, 1631, 5, 49, 1, 27, 5, 49, 1, 2055, 1, 5, 27, 27, 5, 49, 1

Offset: 0

Author

Augustine O. Munagi, Dec 30 2019

Keywords

• nonn
• easy

Comments

A perfect composition of n is one whose sequence of parts contains one composition of every positive integer less than n.

Examples

			a(7) = 11 because the perfect compositions are 1111111, 1222, 2221, 1114, 4111, 124, 142, 214, 241, 412, 421.
For example, 241 generates the compositions of 1,...,6: 1,2,21,4,41,24.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..20000
• A. O. Munagi, Perfect Compositions of Numbers, J. Integer Seq. 23 (2020), art. 20.5.1.

Crossrefs

Cf. A001222, A002033, A074206, A251683, A330774.

Programs

Maple

b:= proc(n) option remember; expand(x*(1+add(b(n/d),
       d=numtheory[divisors](n) minus {1, n})))
    end:
a:= n-> (p-> add(coeff(p, x, i)*i!, i=1..degree(p)))(b(n+1)):
seq(a(n), n=0..100);  # Alois P. Heinz, Jan 15 2020

Mathematica

b[n_] := b[n] = x(1+Sum[b[n/d], {d, Divisors[n]~Complement~{1, n}}]);
a[n_] := With[{p = b[n+1]}, Sum[Coefficient[p, x, i] i!, {i, Exponent[p, x]}]];
a /@ Range[0, 100] (* Jean-François Alcover, Nov 17 2020, after Alois P. Heinz *)

Formula

a(1)=1, a(n) = Sum_{k=1..Omega(n+1)} k! * A251683(n+1,k), n>1.