cp's OEIS Frontend

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

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