A000712 Generating function = Product_{m>=1} 1/(1 - x^m)^2; a(n) = number of partitions of n into parts of 2 kinds.

1, 2, 5, 10, 20, 36, 65, 110, 185, 300, 481, 752, 1165, 1770, 2665, 3956, 5822, 8470, 12230, 17490, 24842, 35002, 49010, 68150, 94235, 129512, 177087, 240840, 326015, 439190, 589128, 786814, 1046705, 1386930, 1831065, 2408658, 3157789, 4126070, 5374390

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

For n >= 1, a(n) is also the number of conjugacy classes in the automorphism group of the n-dimensional hypercube. This automorphism group is the wreath product of the cyclic group C_2 and the symmetric group S_n, its order is in sequence A000165. - Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Nov 04 2001

Also, number of noncongruent matrices in GL_n(Z): each Jordan block can only have +1 or -1 on the diagonal. - Michele Dondi (blazar(AT)lcm.mi.infn.it), Jun 15 2004

a(n) = Sum (k(1)+1)*(k(2)+1)*...*(k(n)+1), where the sum is taken over all (k(1),k(2),...,k(n)) such that k(1)+2*k(2)+...+n*k(n) = n, k(i)>=0, i=1..n, cf. A104510, A077285. - Vladeta Jovovic, Apr 21 2005

Convolution of partition numbers (A000041) with itself. - Graeme McRae, Jun 07 2006

Number of one-to-one partial endofunctions on n unlabeled points. Connected components are either cycles or "lines", hence two for each size. - Franklin T. Adams-Watters, Dec 28 2006

Equals A000716: (1, 3, 9, 22, 561, 108, ...) convolved with A010815. A000716 = the number of partitions of n into parts of 3 kinds = the Euler transform of [3,3,3,...]. - Gary W. Adamson, Oct 26 2008

Paraphrasing the g.f.: 1 + 2x + 5x^2 + ... = s(x) * s(x^2) * s(x^3) * s(x^4) * ...; where s(x) = 1 + 2x + 3x^2 + 4x^3 + ... is (up to a factor x) the g.f. of A000027. - Gary W. Adamson, Apr 01 2010

Also equals number of partitions of 2n in which the odd parts appear as many times in even as in odd positions. - Wouter Meeussen, Apr 17 2013

Also number of ordered pairs (R,S) with R a partition of r, S a partition of s, and r+s=n; see example. This corresponds to the formula a(n) = sum(r+s==n, p(r)*p(s) ) = Sum_{k=0..n} p(k)*p(n-k). - Joerg Arndt, Apr 29 2013

Also the number of all multi-graphs with exactly n-edges and with vertex degrees 1 or 2. - Ebrahim Ghorbani, Dec 02 2013

If one decomposes k-permutations into cycles and so-called paths, the number of different type of decompositions equals to a(k); see the paper by Chen, Ghorbani, and Wong. - Ebrahim Ghorbani, Dec 02 2013

Let T(n,k) be the number of partitions of n having parts 1 through k of two kinds, with T(n,0) = A000041(n), the number of partitions of n. Then a(n) = T(n,0) + T(n-1,1) + T(n-2,2) + T(n-3,3) + ... - Gregory L. Simay, May 18 2019

Also the number of orbits of projections in the partition monoid P_n under conjugation by permutations. - James East, Jul 21 2020

Examples

			Assume there are integers of two kinds: k and k'; then a(3) = 10 since 3 has the following partitions into parts of two kinds: 111, 111', 11'1', 1'1'1', 12, 1'2, 12', 1'2', 3, and 3'. - _W. Edwin Clark_, Jun 24 2011
There are a(4)=20 partitions of 4 into 2 sorts of parts. Here p:s stands for "part p of sort s":
01:  [ 1:0  1:0  1:0  1:0  ]
02:  [ 1:0  1:0  1:0  1:1  ]
03:  [ 1:0  1:0  1:1  1:1  ]
04:  [ 1:0  1:1  1:1  1:1  ]
05:  [ 1:1  1:1  1:1  1:1  ]
06:  [ 2:0  1:0  1:0  ]
07:  [ 2:0  1:0  1:1  ]
08:  [ 2:0  1:1  1:1  ]
09:  [ 2:0  2:0  ]
10:  [ 2:0  2:1  ]
11:  [ 2:1  1:0  1:0  ]
12:  [ 2:1  1:0  1:1  ]
13:  [ 2:1  1:1  1:1  ]
14:  [ 2:1  2:1  ]
15:  [ 3:0  1:0  ]
16:  [ 3:0  1:1  ]
17:  [ 3:1  1:0  ]
18:  [ 3:1  1:1  ]
19:  [ 4:0  ]
20:  [ 4:1  ]
- _Joerg Arndt_, Apr 28 2013
The a(4)=20 ordered pairs (R,S) of partitions for n=4 are
  ([4], [])
  ([3, 1], [])
  ([2, 2], [])
  ([2, 1, 1], [])
  ([1, 1, 1, 1], [])
  ([3], [1])
  ([2, 1], [1])
  ([1, 1, 1], [1])
  ([2], [2])
  ([2], [1, 1])
  ([1, 1], [2])
  ([1, 1], [1, 1])
  ([1], [3])
  ([1], [2, 1])
  ([1], [1, 1, 1])
  ([], [4])
  ([], [3, 1])
  ([], [2, 2])
  ([], [2, 1, 1])
  ([], [1, 1, 1, 1])
This list was created with the Sage command
   for P in PartitionTuples(2,4) : print P;
- _Joerg Arndt_, Apr 29 2013
G.f. = 1 + 2*x + 5*x^2 + 10*x^3 + 20*x^4 + 36*x^5 + 65*x^6 + 110*x^7 + 185*x^8 + ...
		

References

• H. Gupta et al., Tables of Partitions. Royal Society Mathematical Tables, Vol. 4, Cambridge Univ. Press, 1958, p. 90.
• J. Riordan, Combinatorial Identities, Wiley, 1968, p. 199.
• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
• R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 1, 1999; see Proposition 2.5.2 on page 78.

Links

• Seiichi Manyama, Table of n, a(n) for n = 0..10000 (first 501 terms from T. D. Noe)
• Arvind Ayyer, Amritanshu Prasad, and Steven Spallone, Macdonald trees and determinants of representations for finite Coxeter groups, arXiv:1812.00608 [math.RT], 2018.
• M. Baake, Structure and representations of the hyperoctahedral group, J. Math. Phys. 25 (1984) 3171, table 1.
• Roland Bacher and P. De La Harpe, Conjugacy growth series of some infinitely generated groups, hal-01285685v2, 2016.
• Jan Brandts and A Cihangir, Enumeration and investigation of acute 0/1-simplices modulo the action of the hyperoctahedral group, arXiv preprint arXiv:1512.03044 [math.CO], 2015.
• E. R. Canfield, C. D. Savage and H. S. Wilf, Regularly spaced subsums of integer partitions, arXiv:math/0308061 [math.CO], 2003.
• Alexandre Chaduteau, Nyan Raess, Henry Davenport, and Frank Schindler, Hilbert Space Fragmentation in the Chiral Luttinger Liquid, arXiv:2409.10359 [cond-mat.str-el], 2024. See pp. 8, 11.
• Alexandre Chaduteau, Nyan Raess, Henry Davenport, and Frank Schindler, Momentum-space modulated symmetries in the Luttinger liquid, Phys. Rev. B (2025) Vol. 111, Art. No. 165105. See p. 9.
• B. F. Chen, E. Ghorbani, and K. B. Wong, Cyclic decomposition of k-permutations and eigenvalues of the arrangement graphs, Electronic J. Combin. 20(4) (2013), #P22.
• W. Y. C. Chen, K. Q. Ji and H. S. Wilf, BG-ranks and 2-cores, arXiv:math/0605474 [math.CO], 2006.
• W. Edwin Clark, Mohamed Elhamdadi, Xiang-dong Hou, Masahico Saito and Timothy Yeatman, Connected Quandles Associated with Pointed Abelian Groups, arXiv preprint arXiv:1107.5777 [math.RA], 2011.
• W. Edwin Clark and Xiang-dong Hou, Galkin Quandles, Pointed Abelian Groups, and Sequence A000712 arXiv:1108.2215 [math.CO], Aug 10, 2011. [added by Jonathan Vos Post]
• Shouvik Datta, M. R. Gaberdiel, W. Li, and C. Peng, Twisted sectors from plane partitions, arXiv preprint arXiv:1606.07070 [hep-th], 2016. See Sect. 2.1.
• M. De Salvo, D. Fasino, D. Freni, and G. Lo Faro, Fully simple semihypergroups, transitive digraphs, and sequence A000712, Journal of Algebra, Volume 415, 1 October 2014, pp. 65-87.
• Mario De Salvo, Dario Fasino, Domenico Freni, and Giovanni Lo Faro, Semihypergroups Obtained by Merging of 0-semigroups with Groups, Filomat (2018) Vol. 32, No. 12, 4177-4194.
• Paul Hammond and Richard Lewis, Congruences in ordered pairs of partitions, Int. J. Math. Math. Sci. (2004), no.45--48, 2509--2512.
• Ruth Hoffmann, Özgür Akgün, and Christopher Jefferson, Composable Constraint Models for Permutation Enumeration, arXiv:2311.17581 [cs.DM], 2023.
• Saud Hussein, An Identity for the Partition Function Involving Parts of k Different Magnitudes, arXiv:1806.05416 [math.NT], 2018.
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 129.
• Han Mao Kiah, Anshoo Tandon, and Mehul Motani, Generalized Sphere-Packing Bound for Subblock-Constrained Codes, arXiv:1901.00387 [cs.IT], 2019.
• Vaclav Kotesovec, A method of finding the asymptotics of q-series based on the convolution of generating functions, arXiv:1509.08708 [math.CO], Sep 30 2015, p. 8.
• Yen-chi R. Lin and Shu-Yen Pan, A recursive relation for bipartition numbers, arXiv:2406.14851 [math.CO], 2024.
• P. Nataf, M. Lajkó, A. Wietek, K. Penc, F. Mila, and A. M. Läuchli, Chiral spin liquids in triangular lattice SU (N) fermionic Mott insulators with artificial gauge fields, arXiv preprint arXiv:1601.00958 [cond-mat.quant-gas], 2016.
• Sylvain Prolhac, Spectrum of the totally asymmetric simple exclusion process on a periodic lattice--first excited states, arXiv preprint arXiv:1404.1315 [cond-mat.stat-mech], 2014.
• N. J. A. Sloane, Transforms.
• Jacob Sprittulla, On Colored Factorizations, arXiv:2008.09984 [math.CO], 2020.
• Index entries for expansions of Product_{k >= 1} (1-x^k)^m

Crossrefs

Cf. A000165, A000041, A002107 (reciprocal of g.f.).

Cf. A002720.

Cf. A000716, A010815. - Gary W. Adamson, Oct 26 2008

Row sums of A175012. - Gary W. Adamson, Apr 03 2010

Column k=2 of A144064.

Cf. A008619, A000070, A000990, A285217, A304045.

Programs

Haskell

a000712 = p a008619_list where
   p _          0 = 1
   p ks'@(k:ks) m = if m < k then 0 else p ks' (m - k) + p ks m
-- Reinhard Zumkeller, Nov 06 2012

Julia

# DedekindEta is defined in A000594.
A000712List(len) = DedekindEta(len, -2)
A000712List(39) |> println # Peter Luschny, Mar 09 2018

Maple

with(combinat): A000712:= n-> add(numbpart(k)*numbpart(n-k), k=0..n): seq(A000712(n), n=0..40); # Emeric Deutsch

Mathematica

CoefficientList[ Series[ Product[1/(1 - x^n)^2, {n, 40}], {x, 0, 37}], x]; (* Robert G. Wilson v, Feb 03 2005 *)
Table[Count[Partitions[2*n], q_ /; Tr[(-1)^Mod[Flatten[Position[q, ?OddQ]], 2]] === 0], {n, 12}] (* _Wouter Meeussen, Apr 17 2013 *)
a[ n_] := SeriesCoefficient[ QPochhammer[ x]^-2, {x, 0, n}]; (* Michael Somos, Oct 12 2015 *)
Table[Length@IntegerPartitions[n, All, Range@n~Join~Range@n], {n, 0, 15}] (* Robert Price, Jun 15 2020 *)

PARI

{a(n) = my(A); if( n<0, 0, A = x * O(x^n); polcoeff( 1 / eta(x + A)^2, n))}; /* Michael Somos, Nov 14 2002 */

PARI

Vec(1/eta('x+O('x^66))^2) /* Joerg Arndt, Jun 25 2011 */

Python

from sympy import npartitions
def A000712(n): return (sum(npartitions(k)*npartitions(n-k) for k in range(n+1>>1))<<1) + (0 if n&1 else npartitions(n>>1)**2) # Chai Wah Wu, Sep 25 2023

SageMath

# uses[EulerTransform from A166861]
a = BinaryRecurrenceSequence(0, 1, 2, 2)
b = EulerTransform(a)
print([b(n) for n in range(40)]) # Peter Luschny, Nov 11 2020

Formula

a(n) = Sum_{k=0..n} p(k)*p(n-k), where p(n) = A000041(n).

Euler transform of period 1 sequence [ 2, 2, 2, ...]. - Michael Somos, Jul 22 2003

a(n) = A006330(n) + A001523(n). - Michael Somos, Jul 22 2003

a(0) = 1, a(n) = (1/n)*Sum_{k=0..n-1} 2*a(k)*sigma_1(n-k). - Joerg Arndt, Feb 05 2011

a(n) ~ (1/12)*3^(1/4)*n^(-5/4)*exp((2/3)*sqrt(3)*Pi*sqrt(n)). - Joe Keane (jgk(AT)jgk.org), Sep 13 2002

G.f.: Product_{i>=1} (1 + x^i)^(2*A001511(i)) (see A000041). - Jon Perry, Jun 06 2004

More precise asymptotics: a(n) ~ exp(2*Pi*sqrt(n/3)) / (4*3^(3/4)*n^(5/4)) * (1 - (Pi/(12*sqrt(3)) + 15*sqrt(3)/(16*Pi)) / sqrt(n) + (Pi^2/864 + 315/(512*Pi^2) + 35/192)/n). - Vaclav Kotesovec, Jan 22 2017

From Peter Bala, Jan 26 2016: (Start)

a(n) is odd iff n = 2*m and p(m) is odd.

a(n) = (2/n)*Sum_{k = 0..n} k*p(k)*p(n-k) for n >= 1.

Conjecture: : a(n) is divisible by 5 when n is congruent to 2, 3 or 4 modulo 5. (End)

Conjecture is proved in Hammond and Lewis. - Yen-chi R. Lin, Jun 24 2024

G.f.: exp(2*Sum_{k>=1} x^k/(k*(1 - x^k))). - Ilya Gutkovskiy, Feb 06 2018

With the convention that a(n) = 0 for n < 0 we have the recurrence a(n) = g(n) + Sum_{k >= 1} (-1)^(k+1)*(2*k + 1)*a(n - k*(k + 1)/2), where g(n) = (-1)^m if n = m*(3*m - 1)/2 is a generalized pentagonal number (A001318) else g(n) = 0. For example, n = 7 = -2*(3*(-2) - 1)/2 is a pentagonal number, g(7) = 1, and so a(7) = 1 + 3*a(6) - 5*a(4) + 7*a(1) = 1 + 195 - 100 + 14 = 110. - Peter Bala, Apr 06 2022

a(n) = p(n/2) + Sum_{k \in Z, k != 0} (-1)^{k-1} a(n-k^2), here p(n) = A000041(n) and p(x) = 0 when x is not an integer. - Yen-chi R. Lin, Jun 24 2024

Conjecture: a(25*n + 23) is divisible by 25 (checked for n < 400). - Peter Bala, Jan 13 2025

Extensions

More terms from Joe Keane (jgk(AT)jgk.org), Nov 17 2001

More terms from Michele Dondi (blazar(AT)lcm.mi.infn.it), Jun 15 2004

Definition rewritten by N. J. A. Sloane, Apr 02 2022