login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A129921
Number of generalized compositions of n: words b_1^{i_1}b_2^{i_2}...b_k^{i_k} such that b_j's and j_i's are positive integers and sum b_j*i_j = n.
22
1, 1, 3, 7, 18, 43, 108, 263, 651, 1599, 3942, 9698, 23890, 58805, 144806, 356512, 877820, 2161285, 5321485, 13102246, 32259890, 79428762, 195566238, 481514453, 1185564348, 2919044646, 7187145712, 17695877607, 43570023304, 107276219947, 264130857268, 650331536681, 1601218102939
OFFSET
0,3
COMMENTS
If the additional constraint was added that b_j does not equal to b_{j+1}, the sequence generated would be the compositions (ordered partitions) of integers.
This is a variant of compositions of compositions: for each composition of n, write it in value^repetition form, and then choose a composition for each repetition factor. - Franklin T. Adams-Watters, May 27 2010
INVERT transform of tau (A000005). - Alois P. Heinz, Feb 11 2021
LINKS
Sylvie Corteel and Paweł Hitczenko, Generalizations of Carlitz Compositions, Journal of Integer Sequences, Vol. 10 (2007), Article 07.8.8.
FORMULA
G.f.: 1/(1 - Sum_{k>0} z^k/(1-z^k)).
G.f.: 1/(1 - Sum_{k>0} tau(k) x^k), where tau(k) is the number of divisors of k. - Franklin T. Adams-Watters, May 27 2010
G.f.: 1/(1 + x * (d/dx) log(Product_{k>=1} (1 - x^k)^(1/k))). - Ilya Gutkovskiy, Oct 18 2018
a(n) = Sum_{k=0..n-1} tau(n-k)*a(k) for n>0 with a(0) = 1. - Ridouane Oudra, Mar 13 2020
EXAMPLE
a(3)=7 because we can write
3^{1},
1^{2} 2^{1},
2^{1} 1^{1},
1^{3},
1^{2} 1^{1},
1^{1} 1^{2},
1^{1} 1^{1} 1^{1}.
MAPLE
a:= proc(n) option remember; `if`(n=0, 1,
add(add(a(n-i*j), j=1..n/i), i=1..n))
end:
seq(a(n), n=0..40); # Alois P. Heinz, Jul 22 2017
# second Maple program:
a:= proc(n) option remember; `if`(n=0, 1,
add(a(n-i)*numtheory[tau](i), i=1..n))
end:
seq(a(n), n=0..40); # Alois P. Heinz, Feb 11 2021
MATHEMATICA
nmax = 50; CoefficientList[Series[1/(1 - Sum[DivisorSigma[0, k]*x^k, {k, 1, nmax}]), {x, 0, nmax}], x] (* Vaclav Kotesovec, Jan 06 2017 *)
PROG
(PARI) N=66; A=vector(66); A[0+1]=1;
for (n=1, N-1, A[n+1] = sum(k=0, n-1, A[k+1]*sigma(n-k, 0)) );
A /* Joerg Arndt, Apr 28 2013 */
(PARI) N = 66; x = 'x + O('x^N);
gf = 1/(1-sum(k=1, N, x^k/(1-x^k)) );
Vec(gf) /* Joerg Arndt, Apr 28 2013 */
CROSSREFS
KEYWORD
nonn
AUTHOR
Pawel Hitczenko (phitczenko(AT)math.drexel.edu), Jun 05 2007
EXTENSIONS
Edited by Franklin T. Adams-Watters, May 27 2010
More terms from Joerg Arndt, Apr 28 2013
STATUS
approved