OFFSET
0,3
COMMENTS
Number of compositions of n into parts where there are phi(k) sorts of part k. - Joerg Arndt, Sep 30 2012
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..1000
FORMULA
INVERT transform of A000010.
G.f.: 1/( 1 - Sum_{k>=1} phi(k) * x^k ) where phi = A000010. Joerg Arndt, Sep 30 2012
a(n) ~ c * d^n, where d = 2.26371672715382105671101924573765243871241560288177676216035633730282369149... is the root of the equation Sum_{k>=1} phi(k)/d^k = 1 and c = 0.42880036544961338799475947921442516792321060146527623589359809145075482942... - Vaclav Kotesovec, Aug 18 2021
EXAMPLE
a(6) = 57 = (1, 1, 2, 2, 4, 2) dot (26, 11, 5, 2, 1, 1) = (26 + 11 + 10 + 4 + 4 + 2).
MAPLE
a:= proc(n) option remember; `if`(n=0, 1,
add(a(n-i)*numtheory[phi](i), i=1..n))
end:
seq(a(n), n=0..35); # Alois P. Heinz, Sep 22 2017
MATHEMATICA
a[n_] := a[n] = If[n == 0, 1, Sum[a[n-i] EulerPhi[i], {i, 1, n}]];
a /@ Range[0, 35] (* Jean-François Alcover, Oct 31 2020, after Maple *)
PROG
(PARI)
N=66; x='x+O('x^N);
Vec( 1/( 1 - sum(k=1, N, eulerphi(k)*x^k ) ) - 1 )
/* Joerg Arndt, Sep 30 2012 */
CROSSREFS
KEYWORD
nonn
AUTHOR
Gary W. Adamson, Apr 26 2009
EXTENSIONS
a(0)=1 prepended by Alois P. Heinz, Sep 22 2017
STATUS
approved