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!)
A305168 Number of non-isomorphic graphs on 4n vertices whose edges are the union of two n-edge matchings. 1
1, 3, 9, 23, 54, 118, 246, 489, 940, 1751, 3177, 5630, 9776, 16659, 27922, 46092, 75039, 120615, 191611, 301086, 468342, 721638, 1102113, 1669226, 2508429, 3741741, 5542532, 8155720, 11925654, 17334077, 25051940, 36009468, 51491111, 73263043, 103744575 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

a(n) is also the number of partitions of 2n with two kinds of parts where all parts of the second kind are even. E.g., the a(2) = 9 such partitions are (2', 2'), (4'), (2,2'), (4), (1,1,2'), (3,1), (2,2), (2,1,1), (1,1,1,1). A bijection is to take each component in the graph whose edges are the union of two n-edge matchings, map each path of length p to a part p and each cycle (which must be even) of length p to a part p'.

LINKS

Table of n, a(n) for n=0..34.

FORMULA

a(n) = [x^2n] (Product_{i>=1} 1/(1-x^i))*(Product_{j>=1} 1/(1-x^(2j))).

a(n) = Sum_{i=0..n} b(2i)*b(n-i) where b(n) is the number of partitions of n (A000041).

a(n) = A002513(2n). - Alois P. Heinz, Aug 18 2018

EXAMPLE

To see a(2)=9, observe that all graphs that are the union of two matchings of size n=2 are isomorphic to the union of S = {{1,2},{3,4}} and one of T=

  1. {{1,2}, {3,4}} --> (2',2')

  2. {{1,3}, {2,4}} --> (4')

  3. {{1,5}, {3,4}} --> (2,2')

  4. {{1,3}, {4,5}} --> (4)

  5. {{1,2}, {5,6}} --> (1,1,2')

  6. {{1,3}, {5,6}} --> (3,1)

  7. {{1,5}, {3,6}} --> (2,2)

  8. {{1,5}, {6,7}} --> (2,1,1)

  9. {{5,6}, {7,8}} --> (1,1,1,1)

Note that the partitions correspond to the bijection mentioned in the comments above.

MAPLE

b:= proc(n) option remember; `if`(n=0, 1, add(b(n-j)*add(d*

      (2-irem(d, 2)), d=numtheory[divisors](j)), j=1..n)/n)

    end:

a:= n-> b(2*n):

seq(a(n), n=0..40);  # Alois P. Heinz, Aug 18 2018

MATHEMATICA

a[n_] := Sum[PartitionsP[2k] PartitionsP[n-k], {k, 0, n}];

a /@ Range[0, 40] (* Jean-Fran├žois Alcover, Nov 27 2020 *)

PROG

(PARI) a(n) = sum(i=0, n, numbpart(2*i)*numbpart(n-i)); \\ Michel Marcus, Aug 18 2018

CROSSREFS

Bisection (even part) of A002513.

Cf. A000041.

Sequence in context: A146440 A244331 A183155 * A274099 A147126 A147212

Adjacent sequences:  A305165 A305166 A305167 * A305169 A305170 A305171

KEYWORD

nonn

AUTHOR

Yu Hin Au, Aug 17 2018

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 October 5 06:51 EDT 2022. Contains 357252 sequences. (Running on oeis4.)