

A305168


Number of nonisomorphic graphs on 4n vertices whose edges are the union of two nedge 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 nedge 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/(1x^i))*(Product_{j>=1} 1/(1x^(2j))).
a(n) = Sum_{i=0..n} b(2i)*b(ni) 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(nj)*add(d*
(2irem(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[nk], {k, 0, n}];
a /@ Range[0, 40] (* JeanFrançois Alcover, Nov 27 2020 *)


PROG

(PARI) a(n) = sum(i=0, n, numbpart(2*i)*numbpart(ni)); \\ 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



