A011975 Covering numbers C(n,3,2).

1, 3, 4, 6, 7, 11, 12, 17, 19, 24, 26, 33, 35, 43, 46, 54, 57, 67, 70, 81, 85, 96, 100, 113, 117, 131, 136, 150, 155, 171, 176, 193, 199, 216, 222, 241, 247, 267, 274, 294, 301, 323, 330, 353, 361, 384, 392, 417, 425, 451, 460, 486, 495, 523, 532, 561, 571, 600

Offset

3,2

Comments

Also, minimal number of triangles needed to cover every edge (and node) of a complete graph on n nodes. - Dmitry Kamenetsky, Jan 24 2016

References

P. J. Cameron, Combinatorics, ..., Cambridge, 1994, see p. 121.

CRC Handbook of Combinatorial Designs, 1996, p. 262.

W. H. Mills and R. C. Mullin, Coverings and packings, pp. 371-399 of Jeffrey H. Dinitz and D. R. Stinson, editors, Contemporary Design Theory, Wiley, 1992.

Links

T. D. Noe, Table of n, a(n) for n = 3..1000

Marek Cygan, Marcin Pilipczuk and Michał Pilipczuk, Known algorithms for EDGE CLIQUE COVER are probably optimal, arXiv:1203.1754 [cs.DS], 2012.

Marion K. Fort, Jr. and G. A. Hedlund, Minimal coverings of pairs by triples, Pac. J. Math., 8 (4), pp. 709-719, 1958.

Oliver Goldschmidt, Dorit S. Hochbaum, Cor Hurkens and Gang Yu, Approximation Algorithms for the k-Clique Covering Problem, Journal of Discrete Mathematics, volume 9, issue 3, pages 492-509, 1995, doi: 10.1137/S089548019325232X.

D. Gordon, La Jolla Repository of Coverings

Jenö Lehel, The minimum number of triangles covering the edges of a graph, Journal of Graph Theory, volume 13, issue 3, pages 369-384, 1989.

Uenal Mutlu, Tables of coverings.

J. Schoenheim, On coverings, Pac. J. Math. 14 (4) (1964) 1405-1411.

Wikipedia, Covering design.

Index entries for covering numbers.

Index entries for linear recurrences with constant coefficients, signature (1,1,-1,0,0,1,-1,-1,1).

Formula

From R. J. Mathar, Aug 12 2012: (Start)

G.f.: x^3 * ( -1-2*x-2*x^5+x^7+x^6-x^8 ) / ( (1+x+x^2)*(x^2-x+1)*(1+x)^2*(x-1)^3 ).

a(n) = a(n-1) + a(n-2) - a(n-3) + a(n-6) - a(n-7) - a(n-8) + a(n-9). (End)

a(n) = ceiling((n/3)*ceiling((n-1)/2)). - Nathaniel Johnston, Jan 10 2024

Maple

L := proc(v, k, t, l) local i, t1; t1 := l; for i from v-t+1 to v do t1 := ceil(t1*i/(i-(v-k))); od: t1; end; # gives Schoenheim bound L_l(v, k, t). Present sequence is L_1(n, 3, 2, 1).

Mathematica

L[v_, k_, t_, m_] := Module[{t1 = m}, Do[t1 = Ceiling[t1*i/(i - (v - k))], {i, v - t + 1, v}]; t1]; Table[L[n, 3, 2, 1], {n, 3, 100}] (* T. D. Noe, Sep 28 2011 *)

Crossrefs

Cf. A011976, A011977, A001839. A column of A066010. Also a column of A036838.

Sequence in context: A335059 A047514 A345716 * A202112 A079249 A374981

Adjacent sequences: A011972 A011973 A011974 * A011976 A011977 A011978

Keyword

nonn,easy

Author

N. J. A. Sloane

Status

approved