A395684 Triangle read by rows: T(n,k) = number of labeled simple graphs on n vertices with clique number exactly k.

1, 1, 1, 1, 6, 1, 1, 40, 22, 1, 1, 387, 570, 65, 1, 1, 5788, 21837, 4970, 171, 1, 1, 133500, 1353096, 576247, 33887, 420, 1, 1, 4682269, 142458868, 110940707, 10151470, 201152, 988, 1, 1, 246348114, 26197715153, 37047560253, 5082607533, 144146058, 1097364, 2259, 1

Offset

1,5

Comments

By the Clique-Size Dominance Theorem, the minimum coding clique size for faithful CC-transformation embedding is K_min = k+1. This triangle gives the distribution of that threshold.

Links

Sean A. Irvine, Table of n, a(n) for n = 1..78

Alejandro Zarzuelo Urdiales, Clique-Size Dominance Threshold Distribution: Enumerating Labeled Graphs by Clique Number, Zenodo, 2026.

Alejandro Zarzuelo Urdiales, Lean 4 formalization and Python verification code, GitHub.

Formula

T(n,1) = T(n,n) = 1 (corresponding to empty and complete graphs).

T(n,k) = c(n,k) - c(n,k-1), where c(n,k) = number of K_{k+1}-free labeled graphs on n vertices (inclusion-exclusion).

T(n,n-1) = n*2^(n-1) - n*(n-1)/2 - n for n>=2.

Example

Triangle begins:
  n=1: 1;
  n=2: 1, 1;
  n=3: 1, 6, 1;
  n=4: 1, 40, 22, 1;
  n=5: 1, 387, 570, 65, 1;
  n=6: 1, 5788, 21837, 4970, 171, 1;
  n=7: 1, 133500, 1353096, 576247, 33887, 420, 1;
  n=8: 1, 4682269, 142458868, 110940707, 10151470, 201152, 988, 1.

Crossrefs

Cf. A263341 (unlabeled version), A058843 (labeled by chromatic number), A006125 (row sums), A213434 (column k=2 cumulative = triangle-free labeled graphs), A395691 (p=2 multigraphs), A395692 (p=3), A395693 (p=4), A395694 (p=5), A395695 (cumulative D(n,k)).

Sequence in context: A158116 A172343 A394473 * A058875 A156764 A156765

Adjacent sequences: A395679 A395682 A395683 * A395691 A395692 A395693

Keyword

tabl,nonn

Author

Alejandro Zarzuelo Urdiales, May 04 2026

Extensions

a(37)-a(45) from Sean A. Irvine, May 07 2026

Status

approved