login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000712 Number of partitions of n into parts of 2 kinds.
(Formerly M1376 N0536)
101
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

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

T. D. Noe, Table of n, a(n) for n=0..500

E. R. Canfield, C. D. Savage and H. S. Wilf, Regularly spaced subsums of integer partitions

B. F. Chen, E. Ghorbani, 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.CO/0605474.

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, 2011

W. Edwin Clark and Xiang-dong Hou, Galkin Quandles, Pointed Abelian Groups, and Sequence A000712 (arXiv:1108.2215v1 [math.CO]), Aug 10, 2011 [added by Jonathan Vos Post]

M. De Salvo, D. Fasino, D. Freni, G. Lo Faro, Fully simple semihypergroups, transitive digraphs, and sequence A000712, Journal of Algebra, Volume 415, 1 October 2014, Pages 65-87.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 129

Sylvain Prolhac, Spectrum of the totally asymmetric simple exclusion process on a periodic lattice--first excited states, arXiv preprint arXiv:1404.1315, 2014

N. J. A. Sloane, Transforms

Index entries for expansions of Product_{k >= 1} (1-x^k)^m

FORMULA

G.f.: 1/prod(m>=1, 1-x^m )^2.

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*3^(1/2)*Pi*n^(1/2)). - 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

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

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 *)

PROG

(PARI) {a(n) = local(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

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 2 of A144064.

Cf. A008619, A000070, A000990.

Sequence in context: A103928 A103929 A121597 * A032442 A227356 A102688

Adjacent sequences:  A000709 A000710 A000711 * A000713 A000714 A000715

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane

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

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified May 27 10:00 EDT 2015. Contains 257872 sequences.