A304969 Expansion of 1/(1 - Sum_{k>=1} q(k)*x^k), where q(k) = number of partitions of k into distinct parts (A000009).

1, 1, 2, 5, 11, 25, 57, 129, 292, 662, 1500, 3398, 7699, 17443, 39519, 89536, 202855, 459593, 1041267, 2359122, 5344889, 12109524, 27435660, 62158961, 140828999, 319065932, 722884274, 1637785870, 3710611298, 8406859805, 19046805534, 43152950024, 97768473163

Offset

0,3

Comments

Invert transform of A000009.

From Gus Wiseman, Jul 31 2022: (Start)

Also the number of ways to choose a multiset partition into distinct constant multisets of a multiset of length n that covers an initial interval of positive integers. This interpretation involves only multisets, not sequences. For example, the a(1) = 1 through a(4) = 11 multiset partitions are:

{{1}} {{1,1}} {{1,1,1}} {{1,1,1,1}}

{{1},{2}} {{1},{1,1}} {{1},{1,1,1}}

{{1},{2,2}} {{1,1},{2,2}}

{{2},{1,1}} {{1},{2,2,2}}

{{1},{2},{3}} {{2},{1,1,1}}

{{1},{2},{1,1}}

{{1},{2},{2,2}}

{{1},{2},{3,3}}

{{1},{3},{2,2}}

{{2},{3},{1,1}}

{{1},{2},{3},{4}}

The non-strict version is A055887.

The strongly normal non-strict version is A063834.

The strongly normal version is A270995.

(End)

Links

Alois P. Heinz, Table of n, a(n) for n = 0..2816

N. J. A. Sloane, Transforms

Eric Weisstein's World of Mathematics, Partition Function Q

Index entries for sequences related to partitions

Index entries for sequences related to compositions

Formula

G.f.: 1/(1 - Sum_{k>=1} A000009(k)*x^k).

G.f.: 1/(2 - Product_{k>=1} (1 + x^k)).

G.f.: 1/(2 - Product_{k>=1} 1/(1 - x^(2*k-1))).

G.f.: 1/(2 - exp(Sum_{k>=1} (-1)^(k+1)*x^k/(k*(1 - x^k)))).

a(n) ~ c / r^n, where r = 0.441378990861652015438479635503868737167721352874... is the root of the equation QPochhammer[-1, r] = 4 and c = 0.4208931614610039677452560636348863586180784719323982664940444607322... - Vaclav Kotesovec, May 23 2018

Example

From Gus Wiseman, Jul 31 2022: (Start)
a(n) is the number of ways to choose a strict integer partition of each part of an integer composition of n. The a(1) = 1 through a(4) = 11 choices are:
  ((1))  ((2))     ((3))        ((4))
         ((1)(1))  ((21))       ((31))
                   ((1)(2))     ((1)(3))
                   ((2)(1))     ((2)(2))
                   ((1)(1)(1))  ((3)(1))
                                ((1)(21))
                                ((21)(1))
                                ((1)(1)(2))
                                ((1)(2)(1))
                                ((2)(1)(1))
                                ((1)(1)(1)(1))
(End)

Maple

b:= proc(n) option remember; `if`(n=0, 1, add(b(n-j)*add(
     `if`(d::odd, d, 0), d=numtheory[divisors](j)), j=1..n)/n)
    end:
a:= proc(n) option remember; `if`(n=0, 1,
      add(b(j)*a(n-j), j=1..n))
    end:
seq(a(n), n=0..40);  # Alois P. Heinz, May 22 2018

Mathematica

nmax = 32; CoefficientList[Series[1/(1 - Sum[PartitionsQ[k] x^k, {k, 1, nmax}]), {x, 0, nmax}], x]
nmax = 32; CoefficientList[Series[1/(2 - Product[1 + x^k, {k, 1, nmax}]), {x, 0, nmax}], x]
nmax = 32; CoefficientList[Series[1/(2 - 1/QPochhammer[x, x^2]), {x, 0, nmax}], x]
a[0] = 1; a[n_] := a[n] = Sum[PartitionsQ[k] a[n - k], {k, 1, n}]; Table[a[n], {n, 0, 32}]

Crossrefs

Cf. A050342, A055887, A067687, A081362, A279785, A299106.

Row sums of A308680.

The unordered version is A089259, non-strict A001970 (row-sums of A061260).

For partitions instead of compositions we have A270995, non-strict A063834.

A000041 counts integer partitions, strict A000009.

A072233 counts partitions by sum and length.

Cf. A279784.

Sequence in context: A106805 A356846 A094981 * A239812 A097779 A319768

Adjacent sequences: A304966 A304967 A304968 * A304970 A304971 A304972

Keyword

nonn

Author

Ilya Gutkovskiy, May 22 2018

Status

approved