login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000712 Generating function = Product_{m>=1} 1/(1 - x^m)^2; a(n) = number of partitions of n into parts of 2 kinds.
(Formerly M1376 N0536)
183
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 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,2
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
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.
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.
Ruth Hoffmann, Özgür Akgün, and Christopher Jefferson, Composable Constraint Models for Permutation Enumeration, arXiv:2311.17581 [cs.DM], 2023.
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.
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.
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 (checked up to n = 1000). (End)
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
EXAMPLE
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 + ...
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 *)
PROG
(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 */
(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
(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
(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
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.
Sequence in context: A103928 A103929 A121597 * A032442 A327293 A327292
KEYWORD
nonn,easy,nice
AUTHOR
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
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 07:48 EDT 2024. Contains 370958 sequences. (Running on oeis4.)