login
A355756
Triangle read by rows: A(n,k) is the intersection number of the Turán graph T(n,k), 1 <= k <= n.
1
0, 0, 1, 0, 2, 1, 0, 4, 2, 1, 0, 6, 4, 2, 1, 0, 9, 4, 4, 2, 1, 0, 12, 6, 4, 4, 2, 1, 0, 16, 9, 5, 4, 4, 2, 1, 0, 20, 9, 6, 5, 4, 4, 2, 1, 0, 25, 12, 9, 6, 5, 4, 4, 2, 1, 0, 30, 16, 9, 6, 6, 5, 4, 4, 2, 1
OFFSET
1,5
FORMULA
A(n,1) = 0.
A(n,2) = floor(n^2/4) = A002620(n).
A(n,3) = floor((n+1)/3)*floor((n+2)/3) = A008133(n+1).
A(n,n-k) = A(2*k,k) for 2 <= k <= n/2.
A(n,n-1) = 2 for n >= 3.
A(n,n) = 1 for n >= 2.
A(n,k) >= floor((n+k-1)/k)*floor((n+k-2)/k) for k >= 2.
EXAMPLE
Triangle begins:
n\k | 1 2 3 4 5 6 7 8 9 10 11
----+--------------------------------
1 | 0
2 | 0 1
3 | 0 2 1
4 | 0 4 2 1
5 | 0 6 4 2 1
6 | 0 9 4 4 2 1
7 | 0 12 6 4 4 2 1
8 | 0 16 9 5 4 4 2 1
9 | 0 20 9 6 5 4 4 2 1
10 | 0 25 12 9 6 5 4 4 2 1
11 | 0 30 16 9 6 6 5 4 4 2 1
PROG
(Python)
from networkx import find_cliques, turan_graph
from itertools import combinations, count
def A355756(n, k):
if k==1: return 0
G=turan_graph(n, k)
cliques=[sorted(c) for c in find_cliques(G)]
ne=G.number_of_edges()
for r in count(1):
for c0 in combinations(cliques[1:], r-1):
c=(cliques[0], )+c0
if len(set().union(e for i in range(r) for e in combinations(c[i], 2)))==ne:
return r
CROSSREFS
KEYWORD
nonn,tabl,more
AUTHOR
STATUS
approved