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

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, 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, 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

Offset: 1

Author

David Wasserman, Mar 08 2002

Keywords

• nonn
• tabl

Comments

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

Examples

			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.
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, 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, 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...
		

Links

• Jason Kimberley, Rows 1..23 of A068933 triangle, flattened.
• Jason Kimberley, Disconnected regular graphs (with girth at least 3)
• Jason Kimberley, Index of sequences counting disconnected k-regular simple graphs with girth at least g

Crossrefs

Cf. A051031, A068932, A068934.

Formula

D(n, r) = A051031(n, r) - A068934(n, r).