A395684 - OEIS

%I #21 May 11 2026 03:04:48

%S 1,1,1,1,6,1,1,40,22,1,1,387,570,65,1,1,5788,21837,4970,171,1,1,

%T 133500,1353096,576247,33887,420,1,1,4682269,142458868,110940707,

%U 10151470,201152,988,1,1,246348114,26197715153,37047560253,5082607533,144146058,1097364,2259,1

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

%C 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.

%H Sean A. Irvine, <a href="/A395684/b395684.txt">Table of n, a(n) for n = 1..78</a>

%H Alejandro Zarzuelo Urdiales, <a href="https://doi.org/10.5281/zenodo.20004703">Clique-Size Dominance Threshold Distribution: Enumerating Labeled Graphs by Clique Number</a>, Zenodo, 2026.

%H Alejandro Zarzuelo Urdiales, <a href="https://github.com/alejandrozu/Clique-OEIS">Lean 4 formalization and Python verification code</a>, GitHub.

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

%F 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).

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

%e Triangle begins:

%e   n=1: 1;

%e   n=2: 1, 1;

%e   n=3: 1, 6, 1;

%e   n=4: 1, 40, 22, 1;

%e   n=5: 1, 387, 570, 65, 1;

%e   n=6: 1, 5788, 21837, 4970, 171, 1;

%e   n=7: 1, 133500, 1353096, 576247, 33887, 420, 1;

%e   n=8: 1, 4682269, 142458868, 110940707, 10151470, 201152, 988, 1.

%Y 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)).

%K tabl,nonn

%O 1,5

%A _Alejandro Zarzuelo Urdiales_, May 04 2026

%E a(37)-a(45) from _Sean A. Irvine_, May 07 2026