A305168 Number of non-isomorphic graphs on 4n vertices whose edges are the union of two n-edge matchings.

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

Offset: 0

Author

Yu Hin Au, Aug 17 2018

Keywords

• nonn

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'.

Examples

			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.
		

Crossrefs

Bisection (even part) of A002513.

Cf. A000041.

Programs

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

PARI

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

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