A345249 -id:A345249 - cp's OEIS frontend

A006786 Number of squarefree graphs on n vertices.

1, 2, 4, 8, 18, 44, 117, 351, 1230, 5069, 25181, 152045, 1116403, 9899865, 104980369, 1318017549, 19427531763, 333964672216, 6660282066936

Offset: 1

N. J. A. Sloane

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

CombOS - Combinatorial Object Server, Generate graphs
Brendan McKay, Emails to N. J. A. Sloane, 1991
B. D. McKay, Isomorph-free exhaustive generation, J Algorithms, 26 (1998) 306-324.
S. Uijlen, B. Westerbaan, A Kochen-Specker system has at least 22 vectors, arXiv preprint arXiv:1412.8544 [cs.DM], 2014.
S. Uijlen and B. Westerbaan, A Kochen-Specker System Has at Least 22 Vectors, New Generation Computing, Vol. 34, No. 1-2 (2016), 3-23.
Eric Weisstein's World of Mathematics, Square-Free Graph
Index entries for sequences of squarefree graphs

Cf. A000088, A077269 (connected), A345249 (labeled), A039751 (complement). Row sums of A300756.

2 more terms (from the McKay paper) from Vladeta Jovovic, May 17 2008

2 more terms from Brendan McKay, Mar 11 2018

A352472 Triangle T(n,k) read by rows: the number of traceless symmetric binary n X n matrices with 2k one's and no all-1 2 X 2 submatrix.

Original entry on oeis.org

1, 1, 1, 1, 3, 3, 1, 1, 6, 15, 20, 12, 1, 10, 45, 120, 195, 162, 15, 1, 15, 105, 455, 1320, 2508, 2680, 900, 1, 21, 210, 1330, 5880, 18564, 40474, 54750, 35595, 6615, 1, 28, 378, 3276, 20265, 93240, 320040, 795120, 1333080, 1323840, 619920, 90720, 1, 36, 630, 7140, 58527, 364896

Offset: 1

R. J. Mathar, Mar 17 2022

Symmetry and traceless mean that the number of 1's is always even; the corresponding zeros for odd numbers are not shown here.

			The triangle starts at 1 X 1 matrices and 0,2,4,... ones as
1: 1;
2: 1  1;
3: 1  3   3    1;
4: 1  6  15   20    12;
5: 1 10  45  120   195    162      15;
6: 1 15 105  455  1320   2508    2680     900;
7: 1 21 210 1330  5880  18564   40474   54750    35595     6615;
8: 1 28 378 3276 20265  93240  320040  795120  1333080  1323840   619920    90720;
9: 1 36 630 7140 58527 364896 1763076 6578640 18514935 37535932 50808870 40684140 15892065 1995840;

Max Alekseyev, Table of n, a(n) for n = 1..205
Index entries for sequences of squarefree graphs

Cf. A350189 (allows nonzero trace), A345249 (row sums), A006855 (row lengths minus 1), A191966 (rightmost values).

T(n,1) = A000217(n-1). - R. J. Mathar, Mar 25 2022
T(n,2) = 3*A000332(n+1). T(n,3) = A093566(n+1). - Conjectured by R. J. Mathar, Mar 25 2022; proved by Max Alekseyev, Apr 02 2022
G.f.: F(x,y) = Sum_{n,k} T(n,k)*(x^n/n!)*y^k = exp( Sum_G x^n(G) * y^e(G) / |Aut(G)| ), where G runs over the connected squarefree graphs (cf. A077269), n(G) and e(G) are the numbers of nodes and edges in G, and Aut(G) is the automorphism group of G. It follows that F(x,y) = exp(x) * (1 + (1/2)*x^2*y + ((1/2)*x^3 + (1/8)*x^4)*y^2 + ((1/6)*x^3 + (2/3)*x^4 + (1/4)*x^5 + (1/48)*x^6)*y^3 + O(y^4)), implying the above formulas for T(n,2) and T(n,3). - Max Alekseyev, Apr 02 2022

A352258 Number of symmetric binary n X n matrices with no 2 X 2 submatrix of all 1s.

Original entry on oeis.org

2, 7, 42, 399, 5614, 112221, 3102020, 116076057, 5774524092, 376068483351, 31643635513816, 3401292647423655, 462391295351625128, 78801283167350942685, 1775935516860530625139, 230933325874558862792569

Offset: 1

Brendan McKay, Mar 09 2022

Equivalently, the number of labeled graphs (loops but not multiple edges allowed) with none of these subgraphs: 4-cycle, edge with a loop on each end, triangle with at least one loop.

Row sums of A350189.

Cf. A345249 (traceless matrices).

A345248 Number of labeled connected simple graphs on n vertices without cycles of length 4.

Original entry on oeis.org

1, 1, 4, 28, 302, 4776, 106732, 3249352, 131290812, 6922560160, 470586936176, 40833342324864, 4482709905772936, 617622136930640128, 106013904370382120400, 22516967955697072408576, 5880701545642715236590608, 1877504184190590494772860928

Offset: 1

Brendan McKay, Jun 12 2021

From R. J. Mathar, Apr 03 2022 (Start)
The sequence contains the row sums of the number of labeled connected simple graphs on V vertices with E edges, the triangle with V>=0, E>=0:
;
;
1;
0  3  1;
0  0 16  12;
0  0  0 125  162    15;
0  0  0   0 1296  2580   900;
0  0  0   0    0 16807  47715   35595     6615 ;
0  0  0   0    0     0 262144 1006488  1270080   619920    90720;
0  0  0   0    0     0      0 4782969 23859108 44893170 39867660  15892065  1995840 ;
(End)

LOG transform of A345249.
A077269 counts isomorphism classes.
Cf. A345218.

cp's OEIS Frontend

A006786 Number of squarefree graphs on n vertices.

Views

Author

Keywords

References

Links

Crossrefs

Extensions

A352472 Triangle T(n,k) read by rows: the number of traceless symmetric binary n X n matrices with 2k one's and no all-1 2 X 2 submatrix.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A352258 Number of symmetric binary n X n matrices with no 2 X 2 submatrix of all 1s.

Views

Author

Keywords

Comments

Crossrefs

A345248 Number of labeled connected simple graphs on n vertices without cycles of length 4.

Views

Author

Keywords

Comments

Crossrefs