login
Number of disconnected 2-regular graphs on n vertices.
23

%I #30 Sep 08 2022 08:45:48

%S 0,0,0,0,0,0,1,1,2,3,4,5,8,9,12,16,20,24,32,38,48,59,72,87,109,129,

%T 157,190,229,272,330,390,467,555,659,778,926,1086,1283,1509,1774,2074,

%U 2437,2841,3322,3871,4509,5236,6094,7055,8181,9464,10944,12624,14577,16778,19322,22209

%N Number of disconnected 2-regular graphs on n vertices.

%C a(n) is also the number of partitions of n such that each part i satisfies 2<i<n.

%C For n>=2, it appears that a(n+1) is the number of (1,0)-separable partitions of n, as defined at A239482. For example, the four (1,0)-separable partitions of 9 are 621, 531, 441, 31212, corresponding to a(10) = 4. - _Clark Kimberling_, Mar 21 2014.

%H Andrew van den Hoeven, <a href="/A165652/b165652.txt">Table of n, a(n) for n = 0..10000</a>

%H Jason Kimberley, <a href="/wiki/User:Jason_Kimberley/A068933">Disconnected regular graphs (with girth at least 3)</a>

%H Jason Kimberley, <a href="/wiki/User:Jason_Kimberley/D_k-reg_girth_ge_g_index">Index of sequences counting disconnected k-regular simple graphs with girth at least g</a>

%F a = A008483 - A179184 = Euler_tranformation(A179184) - A179184.

%F For n > 2, since there is exactly one connected 2-regular graph on n vertices (the n cycle C_n) then a(n) = A008483(n) - 1.

%F (A008483(n) is also the number of not necessarily connected 2-regular graphs on n vertices.)

%F Column D(n, 2) in the triangle A068933.

%e The a(6)=1 graph is C_3+C_3. The a(7)=1 graph is C_3+C_4. The a(8)=2 graphs are C_3+C_5, C_4+C_4. The a(9)=3 graphs are 3C_3, C_3+C_6, C_4+C_5.

%o (Magma) p := NumberOfPartitions; a := func< n | n lt 3 select 0 else p(n) - p(n-1) - p(n-2) + p(n-3) - 1 >;

%Y 2-regular simple graphs: A179184 (connected), this sequence (disconnected), A008483 (not necessarily connected).

%Y Disconnected regular simple graphs: A068932 (any degree), A068933 (triangular array), specified degree k: A157928 (k=0), A157928 (k=1), this sequence (k=2), A165653 (k=3), A033483 (k=4), A165655 (k=5), A165656 (k=6), A165877 (k=7), A165878 (k=8).

%Y Disconnected 2-regular simple graphs with girth at least g: this sequence (g=3), A185224 (g=4), A185225 (g=5), A185226 (g=6), A185227 (g=7), A185228 (g=8), A185229 (g=9).

%Y Cf. A239482.

%K easy,nonn

%O 0,9

%A _Jason Kimberley_, Sep 28 2009