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