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

Comments

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

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.

Formula

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

Example

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.

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

Crossrefs

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

Sequence in context: A146935 A360756 A133730 * A112031 A146285 A146059

Adjacent sequences: A330770 A330771 A330772 * A330774 A330775 A330776

Keyword

nonn,easy

Author

Augustine O. Munagi, Dec 30 2019

Status

approved