login
Triangular array D(n, r) = number of disconnected r-regular graphs with n nodes, 0 <= r < n.
18

%I #11 Jul 27 2016 10:25:41

%S 0,1,0,1,0,0,1,1,0,0,1,0,0,0,0,1,1,1,0,0,0,1,0,1,0,0,0,0,1,1,2,1,0,0,

%T 0,0,1,0,3,0,0,0,0,0,0,1,1,4,2,1,0,0,0,0,0,1,0,5,0,1,0,0,0,0,0,0,1,1,

%U 8,9,3,1,0,0,0,0,0,0,1,0,9,0,8,0,0,0,0,0,0,0,0,1,1,12,31,25,3,1,0,0,0,0,0

%N Triangular array D(n, r) = number of disconnected r-regular graphs with n nodes, 0 <= r < n.

%C A graph is called r-regular if every node has exactly r edges. Row sums give A068932.

%H Jason Kimberley, <a href="/A068933/b068933.txt">Rows 1..23 of A068933 triangle, flattened</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 D(n, r) = A051031(n, r) - A068934(n, r).

%e This sequence can be computed using the information in A068934. We'll abbreviate A068934(n, r) as C(n, r). To compute D(13, 4), note that the connected components of a 4-regular graph must have at least 5 elements. So a disconnected 13-node 4-regular graph must have two components and their sizes are either 8 and 5, or 7 and 6. So D(13, 4) = C(8, 4)*C(5, 4) + C(7, 4)*C(6, 4) = 6*1 + 2*1 = 8.

%e 0;

%e 1, 0;

%e 1, 0, 0;

%e 1, 1, 0, 0;

%e 1, 0, 0, 0, 0;

%e 1, 1, 1, 0, 0, 0;

%e 1, 0, 1, 0, 0, 0, 0;

%e 1, 1, 2, 1, 0, 0, 0, 0;

%e 1, 0, 3, 0, 0, 0, 0, 0, 0;

%e 1, 1, 4, 2, 1, 0, 0, 0, 0, 0;

%e 1, 0, 5, 0, 1, 0, 0, 0, 0, 0, 0;

%e 1, 1, 8, 9, 3, 1, 0, 0, 0, 0, 0, 0;

%e 1, 0, 9, 0, 8, 0, 0, 0, 0, 0, 0, 0, 0;

%e 1, 1, 12, 31, 25, 3...

%Y Cf. A051031, A068932, A068934.

%K nonn,tabl

%O 1,31

%A _David Wasserman_, Mar 08 2002