A193331 Triangle read by rows: T(n,k) = floor((k-1)*n^2/(2*k)) is an upper bound on the number of edges in the (n-k)-Turán graph.

0, 0, 1, 0, 2, 3, 0, 4, 5, 6, 0, 6, 8, 9, 10, 0, 9, 12, 13, 14, 15, 0, 12, 16, 18, 19, 20, 21, 0, 16, 21, 24, 25, 26, 27, 28, 0, 20, 27, 30, 32, 33, 34, 35, 36, 0, 25, 33, 37, 40, 41, 42, 43, 44, 45, 0, 30, 40, 45, 48, 50, 51, 52, 53, 54, 55, 0, 36, 48, 54, 57, 60, 61, 63, 64, 64, 65, 66

Offset

1,5

Comments

From Mikhail Lavrov, Apr 05 2021: (Start)

This is the bound derived from Turán's theorem; it is tight when n is divisible by k.

The exact number of edges is given by A198787(n,k). The difference between the two is at most k/8; in particular, A198787 and this sequence agree for all k<8. When n=12 and k=8, A198787 gives 62 and this sequence gives 63. (End)

Links

Reinhard Zumkeller, Rows n = 1..100 of triangle, flattened

P. Erdős, R. J. Faudree, and C. C. Rousseau, Extremal problems involving vertices and edges on odd cycles, Disc. Math. 101 (1992) 23-31.

Brian M. Scott, Deriving the number of edges in a Turán graph, Math StackExchange, 2015.

Eric Weisstein's World of Mathematics, Turan Graph

Eric Weisstein's World of Mathematics, Turans Theorem

Formula

T(n,k) = floor((k-1)*n^2/(2*k)).

Example

The triangle T(n,k) begins:
  0;
  0, 1;
  0, 2,  3;
  0, 4,  5,  6;
  0, 6,  8,  9, 10;
  0, 9, 12, 13, 14, 15;
  ...

Mathematica

Flatten[Table[Floor[(k - 1) n^2/(2k)], {n, 20}, {k, n}]]

Prog

(Haskell)
a193331 n k = a193331_tabl !! (n-1) !! (k-1)
a193331_tabl = map a193331_row [1..]
a193331_row n = zipWith div (map (* n^2) [0..n-1]) (map (2 *) [1..n])
-- Reinhard Zumkeller, Aug 08 2011
(PARI) T(n, k)=(k-1)*n^2\(2*k) \\ Charles R Greathouse IV, Aug 01 2016

Crossrefs

Cf. A198787 (the number of edges in the (n,k)-Turán graph).

Sequence in context: A011150 A100112 A198787 * A091246 A271439 A334655

Adjacent sequences: A193328 A193329 A193330 * A193332 A193333 A193334

Keyword

nonn,nice,tabl,easy,look

Author

Eric W. Weisstein, Jul 22 2011

Extensions

Name clarified by Mikhail Lavrov, Apr 05 2021

Status

approved