|
%I M1376 N0536 #255 Dec 05 2023 17:23:53
%S 1,2,5,10,20,36,65,110,185,300,481,752,1165,1770,2665,3956,5822,8470,
%T 12230,17490,24842,35002,49010,68150,94235,129512,177087,240840,
%U 326015,439190,589128,786814,1046705,1386930,1831065,2408658,3157789,4126070,5374390
%N Generating function = Product_{m>=1} 1/(1 - x^m)^2; a(n) = number of partitions of n into parts of 2 kinds.
%C 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
%C 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
%C 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
%C Convolution of partition numbers (A000041) with itself. - _Graeme McRae_, Jun 07 2006
%C 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
%C 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
%C 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
%C 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
%C 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
%C Also the number of all multi-graphs with exactly n-edges and with vertex degrees 1 or 2. - _Ebrahim Ghorbani_, Dec 02 2013
%C 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
%C 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
%C Also the number of orbits of projections in the partition monoid P_n under conjugation by permutations. - _James East_, Jul 21 2020
%D H. Gupta et al., Tables of Partitions. Royal Society Mathematical Tables, Vol. 4, Cambridge Univ. Press, 1958, p. 90.
%D J. Riordan, Combinatorial Identities, Wiley, 1968, p. 199.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 1, 1999; see Proposition 2.5.2 on page 78.
%H Seiichi Manyama, <a href="/A000712/b000712.txt">Table of n, a(n) for n = 0..10000</a> (first 501 terms from T. D. Noe)
%H Arvind Ayyer, Amritanshu Prasad, and Steven Spallone, <a href="https://arxiv.org/abs/1812.00608">Macdonald trees and determinants of representations for finite Coxeter groups</a>, arXiv:1812.00608 [math.RT], 2018.
%H M. Baake, <a href="http://dx.doi.org/10.1063/1.526087">Structure and representations of the hyperoctahedral group</a>, J. Math. Phys. 25 (1984) 3171, table 1.
%H Roland Bacher and P. De La Harpe, <a href="https://hal.archives-ouvertes.fr/hal-01285685/document">Conjugacy growth series of some infinitely generated groups</a>, hal-01285685v2, 2016.
%H Jan Brandts and A Cihangir, <a href="http://arxiv.org/abs/1512.03044">Enumeration and investigation of acute 0/1-simplices modulo the action of the hyperoctahedral group</a>, arXiv preprint arXiv:1512.03044 [math.CO], 2015.
%H E. R. Canfield, C. D. Savage and H. S. Wilf, <a href="https://arxiv.org/abs/math/0308061">Regularly spaced subsums of integer partitions</a>, arXiv:math/0308061 [math.CO], 2003.
%H B. F. Chen, E. Ghorbani, and K. B. Wong, <a href="https://doi.org/10.37236/3711">Cyclic decomposition of k-permutations and eigenvalues of the arrangement graphs</a>, Electronic J. Combin. 20(4) (2013), #P22.
%H W. Y. C. Chen, K. Q. Ji and H. S. Wilf, <a href="https://arxiv.org/abs/math/0605474">BG-ranks and 2-cores</a>, arXiv:math/0605474 [math.CO], 2006.
%H W. Edwin Clark, Mohamed Elhamdadi, Xiang-dong Hou, Masahico Saito and Timothy Yeatman, <a href="http://arxiv.org/abs/1107.5777">Connected Quandles Associated with Pointed Abelian Groups</a>, arXiv preprint arXiv:1107.5777 [math.RA], 2011.
%H W. Edwin Clark and Xiang-dong Hou, <a href="http://arxiv.org/abs/1108.2215">Galkin Quandles, Pointed Abelian Groups, and Sequence A000712</a> arXiv:1108.2215 [math.CO], Aug 10, 2011. [added by Jonathan Vos Post]
%H Shouvik Datta, M. R. Gaberdiel, W. Li, and C. Peng, <a href="https://arxiv.org/abs/1606.07070">Twisted sectors from plane partitions</a>, arXiv preprint arXiv:1606.07070 [hep-th], 2016. See Sect. 2.1.
%H M. De Salvo, D. Fasino, D. Freni, and G. Lo Faro, <a href="http://dx.doi.org/10.1016/j.jalgebra.2014.05.033">Fully simple semihypergroups, transitive digraphs, and sequence A000712</a>, Journal of Algebra, Volume 415, 1 October 2014, pp. 65-87.
%H Mario De Salvo, Dario Fasino, Domenico Freni, and Giovanni Lo Faro, <a href="https://doi.org/10.2298/FIL1812177S">Semihypergroups Obtained by Merging of 0-semigroups with Groups</a>, Filomat (2018) Vol. 32, No. 12, 4177-4194.
%H Ruth Hoffmann, Özgür Akgün, and Christopher Jefferson, <a href="https://arxiv.org/abs/2311.17581">Composable Constraint Models for Permutation Enumeration</a>, arXiv:2311.17581 [cs.DM], 2023.
%H Saud Hussein, <a href="https://arxiv.org/abs/1806.05416">An Identity for the Partition Function Involving Parts of k Different Magnitudes</a>, arXiv:1806.05416 [math.NT], 2018.
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=129">Encyclopedia of Combinatorial Structures 129</a>.
%H Han Mao Kiah, Anshoo Tandon, and Mehul Motani, <a href="https://arxiv.org/abs/1901.00387">Generalized Sphere-Packing Bound for Subblock-Constrained Codes</a>, arXiv:1901.00387 [cs.IT], 2019.
%H Vaclav Kotesovec, <a href="http://arxiv.org/abs/1509.08708">A method of finding the asymptotics of q-series based on the convolution of generating functions</a>, arXiv:1509.08708 [math.CO], Sep 30 2015, p. 8.
%H P. Nataf, M. Lajkó, A. Wietek, K. Penc, F. Mila, and A. M. Läuchli, <a href="https://arxiv.org/abs/1601.00958">Chiral spin liquids in triangular lattice SU (N) fermionic Mott insulators with artificial gauge fields</a>, arXiv preprint arXiv:1601.00958 [cond-mat.quant-gas], 2016.
%H Sylvain Prolhac, <a href="http://arxiv.org/abs/1404.1315">Spectrum of the totally asymmetric simple exclusion process on a periodic lattice--first excited states</a>, arXiv preprint arXiv:1404.1315 [cond-mat.stat-mech], 2014.
%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>.
%H Jacob Sprittulla, <a href="https://arxiv.org/abs/2008.09984">On Colored Factorizations</a>, arXiv:2008.09984 [math.CO], 2020.
%H <a href="/index/Pro#1mxtok">Index entries for expansions of Product_{k >= 1} (1-x^k)^m</a>
%F a(n) = Sum_{k=0..n} p(k)*p(n-k), where p(n) = A000041(n).
%F Euler transform of period 1 sequence [ 2, 2, 2, ...]. - _Michael Somos_, Jul 22 2003
%F a(n) = A006330(n) + A001523(n). - _Michael Somos_, Jul 22 2003
%F a(0) = 1, a(n) = (1/n)*Sum_{k=0..n-1} 2*a(k)*sigma_1(n-k)). - _Joerg Arndt_, Feb 05 2011
%F 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
%F G.f.: Product_{i>=1} (1 + x^i)^(2*A001511(i))) (see A000041). - _Jon Perry_, Jun 06 2004
%F 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
%F From _Peter Bala_, Jan 26 2016: (Start)
%F a(n) is odd iff n = 2*m and p(m) is odd.
%F a(n) = (2/n)*Sum_{k = 0..n} k*p(k)*p(n-k) for n >= 1.
%F Conjecture: a(n) is divisible by 5 when n is congruent to 2, 3 or 4 modulo 5 (checked up to n = 1000). (End)
%F G.f.: exp(2*Sum_{k>=1} x^k/(k*(1 - x^k))). - _Ilya Gutkovskiy_, Feb 06 2018
%F 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
%e 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
%e There are a(4)=20 partitions of 4 into 2 sorts of parts. Here p:s stands for "part p of sort s":
%e 01: [ 1:0 1:0 1:0 1:0 ]
%e 02: [ 1:0 1:0 1:0 1:1 ]
%e 03: [ 1:0 1:0 1:1 1:1 ]
%e 04: [ 1:0 1:1 1:1 1:1 ]
%e 05: [ 1:1 1:1 1:1 1:1 ]
%e 06: [ 2:0 1:0 1:0 ]
%e 07: [ 2:0 1:0 1:1 ]
%e 08: [ 2:0 1:1 1:1 ]
%e 09: [ 2:0 2:0 ]
%e 10: [ 2:0 2:1 ]
%e 11: [ 2:1 1:0 1:0 ]
%e 12: [ 2:1 1:0 1:1 ]
%e 13: [ 2:1 1:1 1:1 ]
%e 14: [ 2:1 2:1 ]
%e 15: [ 3:0 1:0 ]
%e 16: [ 3:0 1:1 ]
%e 17: [ 3:1 1:0 ]
%e 18: [ 3:1 1:1 ]
%e 19: [ 4:0 ]
%e 20: [ 4:1 ]
%e - _Joerg Arndt_, Apr 28 2013
%e The a(4)=20 ordered pairs (R,S) of partitions for n=4 are
%e ([4], [])
%e ([3, 1], [])
%e ([2, 2], [])
%e ([2, 1, 1], [])
%e ([1, 1, 1, 1], [])
%e ([3], [1])
%e ([2, 1], [1])
%e ([1, 1, 1], [1])
%e ([2], [2])
%e ([2], [1, 1])
%e ([1, 1], [2])
%e ([1, 1], [1, 1])
%e ([1], [3])
%e ([1], [2, 1])
%e ([1], [1, 1, 1])
%e ([], [4])
%e ([], [3, 1])
%e ([], [2, 2])
%e ([], [2, 1, 1])
%e ([], [1, 1, 1, 1])
%e This list was created with the Sage command
%e for P in PartitionTuples(2,4) : print P;
%e - _Joerg Arndt_, Apr 29 2013
%e 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 + ...
%p with(combinat): A000712:= n-> add(numbpart(k)*numbpart(n-k), k=0..n): seq(A000712(n), n=0..40); # _Emeric Deutsch_
%t CoefficientList[ Series[ Product[1/(1 - x^n)^2, {n, 40}], {x, 0, 37}], x]; (* _Robert G. Wilson v_, Feb 03 2005 *)
%t Table[Count[Partitions[2*n], q_ /; Tr[(-1)^Mod[Flatten[Position[q, _?OddQ]], 2]] === 0], {n, 12}] (* _Wouter Meeussen_, Apr 17 2013 *)
%t a[ n_] := SeriesCoefficient[ QPochhammer[ x]^-2, {x, 0, n}]; (* _Michael Somos_, Oct 12 2015 *)
%t Table[Length@IntegerPartitions[n, All, Range@n~Join~Range@n], {n, 0, 15}] (* _Robert Price_, Jun 15 2020 *)
%o (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 */
%o (PARI) Vec(1/eta('x+O('x^66))^2) /* _Joerg Arndt_, Jun 25 2011 */
%o (Haskell)
%o a000712 = p a008619_list where
%o p _ 0 = 1
%o p ks'@(k:ks) m = if m < k then 0 else p ks' (m - k) + p ks m
%o -- _Reinhard Zumkeller_, Nov 06 2012
%o (Julia) # DedekindEta is defined in A000594.
%o A000712List(len) = DedekindEta(len, -2)
%o A000712List(39) |> println # _Peter Luschny_, Mar 09 2018
%o (SageMath) # uses[EulerTransform from A166861]
%o a = BinaryRecurrenceSequence(0, 1, 2, 2)
%o b = EulerTransform(a)
%o print([b(n) for n in range(40)]) # _Peter Luschny_, Nov 11 2020
%o (Python)
%o from sympy import npartitions
%o 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
%Y Cf. A000165, A000041, A002107 (reciprocal of g.f.).
%Y Cf. A002720.
%Y Cf. A000716, A010815. - _Gary W. Adamson_, Oct 26 2008
%Y Row sums of A175012. - _Gary W. Adamson_, Apr 03 2010
%Y Column k=2 of A144064.
%Y Cf. A008619, A000070, A000990, A285217, A304045.
%K nonn,easy,nice
%O 0,2
%A _N. J. A. Sloane_
%E More terms from Joe Keane (jgk(AT)jgk.org), Nov 17 2001
%E More terms from Michele Dondi (blazar(AT)lcm.mi.infn.it), Jun 15 2004
%E Definition rewritten by _N. J. A. Sloane_, Apr 02 2022
|
