User:Jason Kimberley/A068933

A068933

Triangular array D(n,r) that counts the isomorphism classes of disconnected r-regular simple graphs on n vertices.

C D E

Triangle

For odd $r$, by the handshaking lemma, there are no $r$-regular graphs with an odd number of vertices. So, for odd $r$, the column sequences count disconnected $r$-regular simple graphs on $2n$ vertices.

A068932	$n$	A157928	A157928	A165652	A165653	A033483	A165655	A165656	A165877	A165878
$\forall$	$r$	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39
0	1
1	2	1
1	3	1
2	4	1	1
1	5	1	0
3	6	1	1	1
2	7	1	0	1
5	8	1	1	2	1
4	9	1	0	3	0
9	10	1	1	4	2	1
7	11	1	0	5	0	1
23	12	1	1	8	9	3	1
18	13	1	0	9	0	8	0
74	14	1	1	12	31	25	3	1
106	15	1	0	16	0	88	0	1
619	16	1	1	20	147	378	66	5	1
2076	17	1	0	24	0	2026	0	25	0
22526	18	1	1	32	809	13351	8029	297	5	1
112834	19	1	0	38	0	104595	0	8199	0	1
4799825	20	1	1	48	5855	930586	3484760	377004	1562	7	1
31138965	21	1	0	59	0	9124662	0	22014143	0	100	0
4207943011	22	1	1	72	54477	96699987	2595985770	1493574756	21617036	10901	9	1
115979718015	23	1	0	87	0	1095469608	0	114880777582	0	3470736	0	1
13482672647959	24	1	1	109	633057	13175272208	2815099031417	9919463450855	733460349818	1473822243	88238	11	1
	25	1	0	129	0	167460699184	0		0	734843169811	0	550	0
	26	1	1	157	8724874	2241578965849					113315027550	806174	13	1
	27	1	0	190	0	31510542635443	0		0		0	2585947720	0	1
	28	1	1	229	137047391	464047929509794						9802278927562	8037887	18	1
	29	1	0	272	0	7143991172244290	0		0		0		0	4224	0
	30	1	1	330	2391169355	114749135506381940								86228020	21	1
	31	1	0	390	0	1919658575933845129	0		0		0		0	2807191554105	0	1
	32	1	1	467	45626910415	33393712487076999918									985884104	26	1
	33	1	0	555	0	603152722419661386031	0		0		0		0		0	42135	0
	34	1	1	659	942659626031											11946634677	33	1
	35	1	0	778	0		0		0		0		0		0		0	1
	36	1	1	926	20937539944549												152808994328	40	1
	37	1	0	1086	0		0		0		0		0		0		0	516383	0
	38	1	1	1283	497209670658529													2056701656260	49	1
	39	1	0	1509	0		0		0		0		0		0		0		0	1
	40	1	1	1774	12566853576025106															61	1
	41	1	0	2074	0		0		0		0		0		0		0		0	7373984	0
	42	1	1	2437	336749273734805530																73	1
	43	1	0	2841	0		0		0		0		0		0		0		0		0	1
	44	1			9534909974420181226																	89	1
	45	1	0		0		0		0		0		0		0		0		0		0	118573680	0
	46	1																					110	1
	47	1	0		0		0		0		0		0		0		0		0		0		0	1
	48	1																						131	1
	49	1	0		0		0		0		0		0		0		0		0		0		0	2103205868	0
	50	1																							158	1
	51	1	0		0		0		0		0		0		0		0		0		0		0		0	1
	52	1																								192	1
	53	1	0		0		0		0		0		0		0		0		0		0		0		0	40634185593	0
	54	1																									230	1
	55	1	0		0		0		0		0		0		0		0		0		0		0		0		0	1
	56	1																										274	1
	57	1	0		0		0		0		0		0		0		0		0		0		0		0		0	847871397697	0
	58	1																											331	1
	59	1	0		0		0		0		0		0		0		0		0		0		0		0		0		0	1
	60	1																												392	1
	61	1	0		0		0		0		0		0		0		0		0		0		0		0		0		0	18987149095396	0
	62	1																													468	1
	63	1	0		0		0		0		0		0		0		0		0		0		0		0		0		0		0	1
	64	1																														557	1
	65	1	0		0		0		0		0		0		0		0		0		0		0		0		0		0		0	454032821689310	0
	66	1																															660	1
	67	1	0		0		0		0		0		0		0		0		0		0		0		0		0		0		0		0	1
	68	1																																780	1
	69	1	0		0		0		0		0		0		0		0		0		0		0		0		0		0		0		0	11544329612486760	0
	70	1																																	927	1
	71	1	0		0		0		0		0		0		0		0		0		0		0		0		0		0		0		0		0	1
	72	1																																		1088	1
	73	1	0		0		0		0		0		0		0		0		0		0		0		0		0		0		0		0		0	310964453836199398	0
	74	1																																			1284	1
	75	1	0		0		0		0		0		0		0		0		0		0		0		0		0		0		0		0		0		0	1
	76	1																																				1511	1
	77	1	0		0		0		0		0		0		0		0		0		0		0		0		0		0		0		0		0		0	8845303172513782781	0
	78	1																																					1775	1
	79	1	0		0		0		0		0		0		0		0		0		0		0		0		0		0		0		0		0		0		0	1
	80	1																																							1

Diagonals

• $D(2k+2,k)=$A12$(k)$.

• $D(4k+3,2k)=$A12$(k)$.

• $D(2k+4,k)=$A184324(k)

=$(k+1)\!\!\!\!\mod 2\;+\;$A8483$(k+3)$, for $k>0$.

=A040001(k)+A165652(k+3), for $k\geq 0$.

Proof:$D(2k+4,k)=C(k+1,k)\times C(k+3,k)+\triangle (C(k+2,k))$,

where $\triangle$=triangular numbers.

We have

• $C(k+1,k)=1$,
• $C(k+3,k)=E(k+3,k)=E(k+3,2)=$A8483$(k+3)$, and
• $C(k+2,k)=E(k+2,k)=E(k+2,1)=(k+1)\!\!\!\!\mod 2$.

(note that $\triangle (0)=0$ and $\triangle (1)=1$.) $\blacksquare$

• $D(4k+5,2k)=$A184325(k)

$=C(2k+1,2k)\times C(2k+4,2k)+C(2k+2,2k)\times C(2k+3,2k)$

$=E(2k+1,2k)\times E(2k+4,2k)+E(2k+2,2k)\times E(2k+3,2k)$

$=E(2k+1,0)\times E(2k+4,3)+E(2k+2,1)\times E(2k+3,2)$

$=1\times E(2k+4,3)+1\times E(2k+3,2)$

=A051031(2k+4,3) + A051031(2k+3,2)

=A005638(k+2) + A008483(2k+3).

• $D(2k+6,k)=$A184326(k)

$=C(k+1,k).C(k+5,k)+C(k+2,k).C(k+4,k)+$A217$(C(k+3,k))$;

$=E(k+1,k).E(k+5,k)+E(k+2,k).E(k+4,k)+$A217$(E(k+3,k))$, for large enough $k$;

$=E(k+1,0).E(k+5,4)+E(k+2,1).E(k+4,3)+$A217$(E(k+3,2))$;

= E(k+5,4) + E(k+4,3) + A217(E(k+3,2));

= A033301(k+5) + ((k+1) mod 2).A005638(k div 2 + 2) + A217(A008483(k+3));