I am lookin for any reasonable formula for the number of graphs on $n$ vertices which have at least one $\lfloor \frac{n}{2} \rfloor$-clique.
The naive attempt is to try to count all possible cliques and then fill in the rest of the graph - but this is overcounting by a lot. I also tried OEIS and it did not help me much.
Thanks.