cp's OEIS Frontend

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

%I A304969 #21 Feb 16 2025 08:33:54
%S A304969 1,1,2,5,11,25,57,129,292,662,1500,3398,7699,17443,39519,89536,202855,
%T A304969 459593,1041267,2359122,5344889,12109524,27435660,62158961,140828999,
%U A304969 319065932,722884274,1637785870,3710611298,8406859805,19046805534,43152950024,97768473163
%N A304969 Expansion of 1/(1 - Sum_{k>=1} q(k)*x^k), where q(k) = number of partitions of k into distinct parts (A000009).
%C A304969 Invert transform of A000009.
%C A304969 From _Gus Wiseman_, Jul 31 2022: (Start)
%C A304969 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:
%C A304969   {{1}}  {{1,1}}    {{1,1,1}}      {{1,1,1,1}}
%C A304969          {{1},{2}}  {{1},{1,1}}    {{1},{1,1,1}}
%C A304969                     {{1},{2,2}}    {{1,1},{2,2}}
%C A304969                     {{2},{1,1}}    {{1},{2,2,2}}
%C A304969                     {{1},{2},{3}}  {{2},{1,1,1}}
%C A304969                                    {{1},{2},{1,1}}
%C A304969                                    {{1},{2},{2,2}}
%C A304969                                    {{1},{2},{3,3}}
%C A304969                                    {{1},{3},{2,2}}
%C A304969                                    {{2},{3},{1,1}}
%C A304969                                    {{1},{2},{3},{4}}
%C A304969 The non-strict version is A055887.
%C A304969 The strongly normal non-strict version is A063834.
%C A304969 The strongly normal version is A270995.
%C A304969 (End)
%H A304969 Alois P. Heinz, <a href="/A304969/b304969.txt">Table of n, a(n) for n = 0..2816</a>
%H A304969 N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>
%H A304969 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PartitionFunctionQ.html">Partition Function Q</a>
%H A304969 <a href="/index/Par#part">Index entries for sequences related to partitions</a>
%H A304969 <a href="/index/Com#comp">Index entries for sequences related to compositions</a>
%F A304969 G.f.: 1/(1 - Sum_{k>=1} A000009(k)*x^k).
%F A304969 G.f.: 1/(2 - Product_{k>=1} (1 + x^k)).
%F A304969 G.f.: 1/(2 - Product_{k>=1} 1/(1 - x^(2*k-1))).
%F A304969 G.f.: 1/(2 - exp(Sum_{k>=1} (-1)^(k+1)*x^k/(k*(1 - x^k)))).
%F A304969 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
%e A304969 From _Gus Wiseman_, Jul 31 2022: (Start)
%e A304969 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:
%e A304969   ((1))  ((2))     ((3))        ((4))
%e A304969          ((1)(1))  ((21))       ((31))
%e A304969                    ((1)(2))     ((1)(3))
%e A304969                    ((2)(1))     ((2)(2))
%e A304969                    ((1)(1)(1))  ((3)(1))
%e A304969                                 ((1)(21))
%e A304969                                 ((21)(1))
%e A304969                                 ((1)(1)(2))
%e A304969                                 ((1)(2)(1))
%e A304969                                 ((2)(1)(1))
%e A304969                                 ((1)(1)(1)(1))
%e A304969 (End)
%p A304969 b:= proc(n) option remember; `if`(n=0, 1, add(b(n-j)*add(
%p A304969      `if`(d::odd, d, 0), d=numtheory[divisors](j)), j=1..n)/n)
%p A304969     end:
%p A304969 a:= proc(n) option remember; `if`(n=0, 1,
%p A304969       add(b(j)*a(n-j), j=1..n))
%p A304969     end:
%p A304969 seq(a(n), n=0..40);  # _Alois P. Heinz_, May 22 2018
%t A304969 nmax = 32; CoefficientList[Series[1/(1 - Sum[PartitionsQ[k] x^k, {k, 1, nmax}]), {x, 0, nmax}], x]
%t A304969 nmax = 32; CoefficientList[Series[1/(2 - Product[1 + x^k, {k, 1, nmax}]), {x, 0, nmax}], x]
%t A304969 nmax = 32; CoefficientList[Series[1/(2 - 1/QPochhammer[x, x^2]), {x, 0, nmax}], x]
%t A304969 a[0] = 1; a[n_] := a[n] = Sum[PartitionsQ[k] a[n - k], {k, 1, n}]; Table[a[n], {n, 0, 32}]
%Y A304969 Cf. A050342, A055887, A067687, A081362, A279785, A299106.
%Y A304969 Row sums of A308680.
%Y A304969 The unordered version is A089259, non-strict A001970 (row-sums of A061260).
%Y A304969 For partitions instead of compositions we have A270995, non-strict A063834.
%Y A304969 A000041 counts integer partitions, strict A000009.
%Y A304969 A072233 counts partitions by sum and length.
%Y A304969 Cf. A279784.
%K A304969 nonn
%O A304969 0,3
%A A304969 _Ilya Gutkovskiy_, May 22 2018