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'.
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
KEYWORD
nonn
AUTHOR
Yu Hin Au, Aug 17 2018
STATUS
approved