|
%I #30 Nov 27 2020 02:08:08
%S 1,3,9,23,54,118,246,489,940,1751,3177,5630,9776,16659,27922,46092,
%T 75039,120615,191611,301086,468342,721638,1102113,1669226,2508429,
%U 3741741,5542532,8155720,11925654,17334077,25051940,36009468,51491111,73263043,103744575
%N Number of non-isomorphic graphs on 4n vertices whose edges are the union of two n-edge matchings.
%C 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'.
%F a(n) = [x^2n] (Product_{i>=1} 1/(1-x^i))*(Product_{j>=1} 1/(1-x^(2j))).
%F a(n) = Sum_{i=0..n} b(2i)*b(n-i) where b(n) is the number of partitions of n (A000041).
%F a(n) = A002513(2n). - _Alois P. Heinz_, Aug 18 2018
%e 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=
%e 1. {{1,2}, {3,4}} --> (2',2')
%e 2. {{1,3}, {2,4}} --> (4')
%e 3. {{1,5}, {3,4}} --> (2,2')
%e 4. {{1,3}, {4,5}} --> (4)
%e 5. {{1,2}, {5,6}} --> (1,1,2')
%e 6. {{1,3}, {5,6}} --> (3,1)
%e 7. {{1,5}, {3,6}} --> (2,2)
%e 8. {{1,5}, {6,7}} --> (2,1,1)
%e 9. {{5,6}, {7,8}} --> (1,1,1,1)
%e Note that the partitions correspond to the bijection mentioned in the comments above.
%p b:= proc(n) option remember; `if`(n=0, 1, add(b(n-j)*add(d*
%p (2-irem(d, 2)), d=numtheory[divisors](j)), j=1..n)/n)
%p end:
%p a:= n-> b(2*n):
%p seq(a(n), n=0..40); # _Alois P. Heinz_, Aug 18 2018
%t a[n_] := Sum[PartitionsP[2k] PartitionsP[n-k], {k, 0, n}];
%t a /@ Range[0, 40] (* _Jean-François Alcover_, Nov 27 2020 *)
%o (PARI) a(n) = sum(i=0, n, numbpart(2*i)*numbpart(n-i)); \\ _Michel Marcus_, Aug 18 2018
%Y Bisection (even part) of A002513.
%Y Cf. A000041.
%K nonn
%O 0,2
%A _Yu Hin Au_, Aug 17 2018
|
