A185304 Triangular array E(n,k) counting not necessarily connected k-regular simple graphs on n vertices with girth at least 4.

1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 2, 2, 1, 1, 0, 2, 0, 0, 1, 1, 3, 6, 2, 1, 1, 0, 3, 0, 2, 0, 1, 1, 5, 23, 12, 1, 1, 1, 0, 5, 0, 31, 0, 0, 1, 1, 7, 112, 220, 7, 1, 1, 1, 0, 8, 0, 1606, 0, 1, 0, 1, 1, 11, 801, 16829, 388, 9, 1, 1, 1, 0, 12, 0, 193900, 0, 6, 0, 0, 1, 1, 16, 7840, 2452820, 406824, 267, 8, 1, 1, 1, 0, 18, 0, 32670332, 0, 3727, 0, 0, 0

Offset: 1

Author

Jason Kimberley, Jan 19 2013

Keywords

• nonn
• hard
• tabf

Comments

Row sums give A185314.

Examples

			1: 1;
2: 1, 1;
3: 1, 0;
4: 1, 1, 1;
5: 1, 0, 1;
6: 1, 1, 1, 1;
7: 1, 0, 1, 0;
8: 1, 1, 2, 2, 1;
9: 1, 0, 2, 0, 0;
10: 1, 1, 3, 6, 2, 1;
11: 1, 0, 3, 0, 2, 0;
12: 1, 1, 5, 23, 12, 1, 1;
13: 1, 0, 5, 0, 31, 0, 0;
14: 1, 1, 7, 112, 220, 7, 1, 1;
15: 1, 0, 8, 0, 1606, 0, 1, 0;
16: 1, 1, 11, 801, 16829, 388, 9, 1, 1;
17: 1, 0, 12, 0, 193900, 0, 6, 0,0;
18: 1, 1, 16, 7840, 2452820, 406824, 267, 8, 1, 1;
19: 1, 0, 18, 0, 32670332, 0, 3727, 0,0, 0;
20: 1, 1, 24, 97723, 456028489, 1125022326, 483012, 741, 13, 1, 1;
21: 1, 0, 27, 0, 6636066134, 0, 69823723, 0, 1, 0, 0;
22: 1, 1, 34, 1436873, 100135577994, 3813549359275, 14836130862, 2887493, ?, 14, 1;
		

Links

• Jason Kimberley, Table of n, a(i)=E(n,k) for i = 1..139 (n = 1..22)
• Jason Kimberley, Not necessarily connected k-regular graphs with girth at least 4
• Jason Kimberley, Index of sequences counting not necessarily connected k-regular simple graphs with girth at least g

Crossrefs

Not necessarily connected k-regular simple graphs with girth at least 4: A185314 (any k), this sequence (triangle); specified degree k: A008484 (k=2), A185334 (k=3), A185344 (k=4), A185354 (k=5), A185364 (k=6).

Formula

E(n,k) = A186714(n,k) + A185204(n,k).

Extensions

E(10,2) corrected by the author, Mar 26 2013

a(32)=E(10,2) in b-file corrected as above by Andrew Howroyd, Feb 22 2018