A011975 -id:A011975 - cp's OEIS frontend

A036838 Triangle read by rows: T(n,k) = value of Schoenheim bound L_1(n+2,k+2,k+1) on covering numbers (0 <= k <= n).

1, 2, 1, 2, 3, 1, 3, 4, 4, 1, 3, 6, 6, 5, 1, 4, 7, 11, 9, 6, 1, 4, 11, 14, 18, 12, 7, 1, 5, 12, 25, 26, 27, 16, 8, 1, 5, 17, 30, 50, 44, 39, 20, 9, 1, 6, 19, 47, 66, 92, 70, 54, 25, 10, 1, 6, 24, 57, 113, 132, 158, 105, 72, 30, 11, 1, 7, 26, 78, 149, 245, 246

Offset: 0

N. J. A. Sloane, Jan 11 2002

The relation with Schoenheim's notation is L(v,k,t,l) = psi(k,t,l,v). - R. J. Mathar, Aug 12 2012

			Triangle begins
  1;
  2,  1;
  2,  3,  1;
  3,  4,  4,  1;
  3,  6,  6,  5,  1;
  4,  7, 11,  9,  6,  1;
  4, 11, 14, 18, 12,  7,  1;
  5, 12, 25, 26, 27, 16,  8,  1;
  ...

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. See Eq. 1.

J. Schoenheim, On coverings, Pac. J. Math. 14 (4) (1964) 1405-1411.
Index entries for covering numbers

Columns give A011975, A036831, A036832, A036833, A036834, A036835, A036836, A014125, A036830, A036837.

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;
A036838 := proc(n,k)
    L(n+2,k+2,k+1,1) ;
end proc:

L[v_, k_, t_, l_] := Module[{i, t1}, t1 = l; For[i = v-t+1, i <= v, i++, t1 = Ceiling[t1*i/(i-(v-k))]]; t1]; A036838[n_, k_] := L[n+2, k+2, k+1, 1]; Table[A036838[n, k], {n, 0, 11}, {k, 0, n}] // Flatten (* Jean-François Alcover, Sep 16 2013, translated from Maple *)

A066010 Triangle of covering numbers T(n,k) = C(n,k,k-1), n >= 2, 2 <= k <= n.

Original entry on oeis.org

1, 2, 1, 2, 3, 1, 3, 4, 4, 1, 3, 6, 6, 5, 1, 4, 7, 12, 9, 6, 1, 4, 11, 14, 20, 12, 7, 1, 5, 12, 25, 30, 30, 16, 8, 1, 5, 17, 30, 51, 50, 45, 20, 9, 1, 6, 19, 47, 66

Offset: 2

N. J. A. Sloane, Dec 30 2001

C(v,k,t) is the smallest number of k-subsets of an n-set such that every t-subset is contained in at least one of the k-subsets.

			Table of values of C(v,k,k-1):
v\k.2..3..4...5...6...7...8..9.10.11.12.13
.2 .1
.3 .2..1
.4 .2..3..1
.5 .3..4..4...1
.6 .3..6..6...5...1
.7 .4..7.12...9...6...1
.8 .4.11.14..20..12...7...1
.9 .5.12.25..30..30..16...8..1
10 .5.17.30..51..50..45..20..9..1
11 .6.19.47..66...a..84..63.25.10..1
12 .6.24.57.113.132...b.126.84.30.11..1
13 .7.26.78.???.245.???..?.185.??.36.12.1
where a in range 96-100, b in range 165-176

CRC Handbook of Combinatorial Designs, 1996, p. 263.
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.

D. Applegate, E. M. Rains and N. J. A. Sloane, On asymmetric coverings and covering numbers, J. Comb. Des. 11 (2003), 218-228.
D. Gordon, La Jolla Repository of Coverings
K. J. Nurmela and Patric R. J. Östergård, New coverings of t-sets with (t+1)-sets, J. Combinat. Designs, 7 (1999), 217-226.
K. J. Nurmela and Patric R. J. Östergård, New coverings of t-sets with (t+1)-sets (appendix), J. Combinat. Designs, 7 (1999), 217-226.
Index entries for covering numbers

Columns give A011975, A011979, A011983, A011987, A066009, A066011, A066137, A066140, A066225.
Triangle in A066701 gives number of nonisomorphic solutions.
Triangle in A036838 (the Schoenheim bound) gives lower bounds to these entries.

A001839 The coding-theoretic function A(n,4,3).

Original entry on oeis.org

0, 0, 1, 1, 2, 4, 7, 8, 12, 13, 17, 20, 26, 28, 35, 37, 44, 48, 57, 60, 70, 73, 83, 88, 100, 104, 117, 121, 134, 140, 155, 160, 176, 181, 197, 204, 222, 228, 247, 253, 272, 280, 301, 308, 330, 337, 359, 368, 392, 400, 425, 433, 458, 468, 495, 504, 532, 541, 569, 580, 610, 620, 651, 661, 692, 704, 737, 748, 782, 793

Offset: 1

N. J. A. Sloane

Maximum number of edge-disjoint K_3's in a K_n.
Maximum number of clauses in a reduced 1 in 3 SAT instance. Given N items taken three at a time, what is the maximum number of combinations such that no two combinations share more than one item in common. There are reduction rules for 1 in 3 SAT that guarantee no two clauses share more than one variable in common. a(n) is the maximum number of clauses a reduced instance with n variables can have. Example: a(6)=4: (a,b,c)(a,d,e)(b,d,f)(c,e,f). - Russell Easterly, Oct 02 2005
Agrees with independence number of the n-tetrahedral graph for at least a(6)-a(12). - Eric W. Weisstein, Jun 14 2017 and Jul 24 2017
Packing number D(n,3,2). - Rob Pratt, Feb 26 2024

			Codes illustrating A(4,3,4) = a(3) = 1, A(5,3,4) = a(5) = 2 and A(6,3,4) = a(6) = 4 are:
   1110...11100..111000
   .......10011..100110
   ..............010101
   ..............001011

P. J. Cameron, Combinatorics, ..., Cambridge, 1994, see p. 121.
CRC Handbook of Combinatorial Designs, 1996, p. 411.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 1..10000
A. E. Brouwer, Bounds for constant weight binary codes
A. E. Brouwer, J. B. Shearer, N. J. A. Sloane and W. D. Smith, New table of constant weight codes, IEEE Trans. Info. Theory 36 (1990), 1334-1380.
P. Erdős et al., Edge disjoint monochromatic triangles in 2-colored graphs, Discrete Math., 231 (2001), 135-141.
R. K. Guy, A problem of Zarankiewicz, Research Paper No. 12, Dept. of Math., Univ. Calgary, Jan. 1967. [Annotated and scanned copy, with permission]
Alice Miller and Michael Codish, Graphs with girth at least 5 with orders between 20 and 32, arXiv:1708.06576 [math.CO], 2017, Table 3.
Eric Weisstein's World of Mathematics, Independence Number
Eric Weisstein's World of Mathematics, Tetrahedral Graph
Index entries for sequences related to A(n,d,w)
Index entries for linear recurrences with constant coefficients, signature (1,1,-1,0,0,1,-1,-1,1).

Cf. A001843, A011975, A060407.

Table[Floor[n Floor[(n - 1)/2]/3] - Boole[Mod[n, 6] == 5], {n, 20}] (* Eric W. Weisstein, Jul 13 2017 *)
Table[(6 n^2 - 9 n - 10 - 3 (-1)^n (n - 2) - 6 Cos[n Pi/3] + 10 Cos[2 n Pi/3] + 10 Sqrt[3] Sin[n Pi/3] + 6 Sqrt[3] Sin[2 n Pi/3])/36, {n, 20}]  (* Eric W. Weisstein, Jul 13 2017 *)
LinearRecurrence[{1, 1, -1, 0, 0, 1, -1, -1, 1}, {0, 0, 1, 1, 2, 4, 7,
   8, 12}, 20] (* Eric W. Weisstein, Jul 13 2017 *)
CoefficientList[Series[(x^2 (-1 - 2 x^3 - 2 x^4 + x^5))/((-1 + x)^3 (1 + x)^2 (1 - x + x^2) (1 + x + x^2)), {x, 0, 20}], x] (* Eric W. Weisstein, Jul 13 2017 *)

Known exactly for all n - see Theorem 4 of Brouwer et al. (1990): A(n, 4, 3) = floor((n/3)*floor((n-1)/2))-1 if n is congruent to 5 (mod 6) and A(n, 4, 3) = floor((n/3)*floor((n-1)/2)) if n is not congruent to 5 (mod 6). - Shelly Jones (shellysalt(AT)yahoo.com), Apr 27 2004
a(n) = a(n-1) + a(n-2) - a(n-3) + a(n-6) - a(n-7) - a(n-8) + a(n-9). - Eric W. Weisstein, Jul 13 2017
G.f.: x^3*(x^5-2*x^4-2*x^3-1) / ((x-1)^3*(x+1)^2*(x^2-x+1)*(x^2+x+1)). - Colin Barker, Sep 21 2013

More terms from Shelly Jones (shellysalt(AT)yahoo.com), Apr 27 2004

A036831 Schoenheim bound L_1(n,4,3).

Original entry on oeis.org

1, 4, 6, 11, 14, 25, 30, 47, 57, 78, 91, 124, 140, 183, 207, 257, 285, 352, 385, 466, 510, 600, 650, 763, 819, 950, 1020, 1163, 1240, 1411, 1496, 1689, 1791, 1998, 2109, 2350, 2470, 2737, 2877, 3161, 3311, 3634, 3795, 4148, 4332, 4704, 4900, 5317, 5525, 5976

Offset: 4

N. J. A. Sloane, Jan 11 2002

nonn

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. See Eq. 1.

Index entries for covering numbers

Lower bound to A011979. Cf. A011975.

A column of A036838.

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). Current sequence is L_1(n,4,3,1).

L[v_, k_, t_, l_] := Module[{i, t1}, t1 = l; For[i = v - t + 1, i <= v, i++, t1 = Ceiling[t1*i/(i - (v - k))]]; t1];
T[n_, k_] := L[n + 2, k + 2, k + 1, 1];
a[n_] := T[n - 2, 2];
Table[a[n], {n, 4, 49}] (* Jean-François Alcover, Mar 07 2023, after Maple code *)

A240115 Schoenheim lower bound L(n,4,2).

Original entry on oeis.org

1, 3, 3, 4, 6, 7, 8, 11, 12, 13, 18, 19, 20, 26, 27, 29, 35, 37, 39, 46, 48, 50, 59, 61, 63, 73, 75, 78, 88, 91, 94, 105, 108, 111, 124, 127, 130, 144, 147, 151, 165, 169, 173, 188, 192, 196, 213, 217, 221, 239, 243, 248, 266, 271, 276, 295, 300, 305, 326

Offset: 4

Colin Barker, Apr 01 2014

Only differs from A011976 when n = 7, 9, 10, or 19. - Nathaniel Johnston, Jan 10 2024

Colin Barker, Table of n, a(n) for n = 4..1000
D. Gordon, G. Kuperberg and O. Patashnik, New constructions for covering designs, arXiv:math/9502238 [math.CO], 1995.

Cf. A240116, A240117, A240118, A240119.

Cf. A011975, A036831, A036832, A036833, A036834, A036835, A036836.

schoenheim[n_, k_, t_] := Module[{lb = 1, n1 = n, k1 = k, t1 = t}, n1 += 1 - t1; k1 += 1 - t1; While[t1 > 0, lb = Ceiling[(lb*n1)/k1]; t1--; n1++; k1++]; lb];
Table[schoenheim[n, 4, 2], {n, 4, 100}] (* Jean-François Alcover, Jan 26 2019, from PARI *)

schoenheim(n, k, t) = {
  my(lb = 1);
  n += 1-t; k += 1-t;
  while(t>0,
    lb = ceil((lb*n)/k);
    t--; n++; k++
  );
  lb
}
s=[]; for(n=4, 100, s=concat(s, schoenheim(n, 4, 2))); s

Empirical g.f.: x^4*(x^15 -x^13 -x^12 +2*x^10 +x^7 +x^5 +2*x +1) / ( -x^16 +x^15 +x^13 -x^12 +x^4 -x^3 -x +1).

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

A240116 Schoenheim lower bound L(n,5,2).

Original entry on oeis.org

1, 3, 3, 4, 4, 6, 7, 8, 8, 12, 12, 13, 14, 18, 19, 20, 21, 27, 28, 29, 30, 37, 38, 40, 41, 48, 50, 52, 53, 62, 63, 65, 67, 76, 78, 80, 82, 93, 95, 97, 99, 111, 113, 116, 118, 130, 133, 136, 138, 152, 154, 157, 160, 174, 177, 180, 183, 199, 202, 205, 208, 225

Offset: 5

Colin Barker, Apr 01 2014

Colin Barker, Table of n, a(n) for n = 5..1000
D. Gordon, G. Kuperberg and O. Patashnik, New constructions for covering designs, arXiv:math/9502238 [math.CO], 1995.

Cf. A240115, A240117, A240118, A240119.

Cf. A011975, A011977, A036831, A036832, A036833, A036834, A036835, A036836.

schoenheim[n_, k_, t_] := Module[{lb = 1, n1 = n, k1 = k, t1 = t}, n1 += 1 - t1; k1 += 1 - t1; While[t1 > 0, lb = Ceiling[(lb*n1)/k1]; t1--; n1++; k1++]; lb];
Table[schoenheim[n, 5, 2], {n, 5, 100}] (* Jean-François Alcover, Jan 26 2019, from PARI *)

schoenheim(n, k, t) = {
  my(lb = 1);
  n += 1-t; k += 1-t;
  while(t>0,
    lb = ceil((lb*n)/k);
    t--; n++; k++
  );
  lb
}
s=[]; for(n=5, 100, s=concat(s, schoenheim(n, 5, 2))); s

Empirical g.f.: x^5*(x^24 -x^21 -x^20 +2*x^17 +x^14 +x^12 -x^10 +2*x^9 +x^6 -x^4 +x^3 +2*x +1) / ( -x^25 +x^24 +x^21 -x^20 +x^5 -x^4 -x +1).

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

A240117 Schoenheim lower bound L(n,6,2).

Original entry on oeis.org

1, 3, 3, 3, 4, 4, 6, 7, 7, 8, 8, 12, 12, 13, 14, 14, 19, 20, 20, 21, 22, 27, 28, 29, 30, 31, 38, 39, 40, 41, 42, 50, 51, 52, 54, 55, 63, 65, 66, 68, 69, 79, 80, 82, 84, 85, 96, 98, 99, 101, 103, 114, 116, 118, 120, 122, 135, 137, 139, 141, 143, 157, 159, 161

Offset: 6

Colin Barker, Apr 01 2014

nonn

Colin Barker, Table of n, a(n) for n = 6..1000
D. Gordon, G. Kuperberg and O. Patashnik, New constructions for covering designs, arXiv:math/9502238 [math.CO], 1995.

Cf. A240115, A240116, A240118, A240119.

Cf. A011975, A036831, A036832, A036833, A036834, A036835, A036836.

schoenheim[n_, k_, t_] := Module[{lb = 1, n1 = n, k1 = k, t1 = t}, n1 += 1 - t1; k1 += 1 - t1; While[t1 > 0, lb = Ceiling[(lb*n1)/k1]; t1--; n1++; k1++]; lb];
Table[schoenheim[n, 6, 2], {n, 6, 100}] (* Jean-François Alcover, Jan 26 2019, from PARI *)

schoenheim(n, k, t) = {
  my(lb = 1);
  n += 1-t; k += 1-t;
  while(t>0,
    lb = ceil((lb*n)/k);
    t--; n++; k++
  );
  lb
}
s=[]; for(n=6, 100, s=concat(s, schoenheim(n, 6, 2))); s

Empirical g.f.: x^6*(x^35 -x^31 -x^30 +2*x^26 +x^23 +x^20 -x^18 +x^17 +x^16 +x^13 -x^12 +2*x^11 +x^7 -x^5 +x^4 +2*x +1) / ( -x^36 +x^35 +x^31 -x^30 +x^6 -x^5 -x +1).

A240118 Schoenheim lower bound L(n,5,3).

Original entry on oeis.org

1, 4, 5, 7, 11, 14, 18, 27, 32, 37, 54, 61, 68, 94, 103, 116, 147, 163, 180, 221, 240, 260, 319, 342, 366, 438, 465, 500, 581, 619, 658, 756, 800, 844, 968, 1016, 1066, 1210, 1265, 1329, 1485, 1555, 1627, 1805, 1882, 1960, 2173, 2257, 2343, 2582, 2673, 2778

Offset: 5

Colin Barker, Apr 01 2014

nonn

Colin Barker, Table of n, a(n) for n = 5..1000
D. Gordon, G. Kuperberg and O. Patashnik, New constructions for covering designs, arXiv:math/9502238 [math.CO], 1995.

Cf. A240115, A240116, A240117, A240119.

Cf. A011975, A036831, A036832, A036833, A036834, A036835, A036836.

schoenheim[n_, k_, t_] := Module[{lb = 1, n1 = n, k1 = k, t1 = t}, n1 += 1 - t1; k1 += 1 - t1; While[t1 > 0, lb = Ceiling[(lb*n1)/k1]; t1--; n1++; k1++]; lb];
Table[schoenheim[n, 5, 3], {n, 5, 100}] (* Jean-François Alcover, Jan 26 2019, from PARI *)

schoenheim(n, k, t) = {
  my(lb = 1);
  n += 1-t; k += 1-t;
  while(t>0,
    lb = ceil((lb*n)/k);
    t--; n++; k++
  );
  lb
}
s=[]; for(n=5, 100, s=concat(s, schoenheim(n, 5, 3))); s

A240119 Schoenheim lower bound L(n,6,3).

Original entry on oeis.org

1, 4, 4, 6, 7, 11, 14, 18, 19, 30, 32, 37, 42, 57, 64, 70, 77, 104, 112, 121, 130, 167, 178, 194, 205, 248, 267, 286, 301, 362, 378, 401, 425, 494, 520, 547, 574, 667, 697, 728, 759, 870, 904, 948, 984, 1105, 1153, 1202, 1242, 1394, 1438, 1492, 1547, 1711

Offset: 6

Colin Barker, Apr 01 2014

nonn

Colin Barker, Table of n, a(n) for n = 6..1000
D. Gordon, G. Kuperberg and O. Patashnik, New constructions for covering designs, arXiv:math/9502238 [math.CO], 1995.

Cf. A240115, A240116, A240117, A240118.

Cf. A011975, A036831, A036832, A036833, A036834, A036835, A036836.

schoenheim[n_, k_, t_] := Module[{lb = 1, n1 = n, k1 = k, t1 = t}, n1 += 1 - t1; k1 += 1 - t1; While[t1 > 0, lb = Ceiling[(lb*n1)/k1]; t1--; n1++; k1++]; lb];
Table[schoenheim[n, 6, 3], {n, 6, 100}] (* Jean-François Alcover, Jan 26 2019, from PARI *)

schoenheim(n, k, t) = {
  my(lb = 1);
  n += 1-t; k += 1-t;
  while(t>0,
    lb = ceil((lb*n)/k);
    t--; n++; k++
  );
  lb
}
s=[]; for(n=6, 100, s=concat(s, schoenheim(n, 6, 3))); s

A011977 Covering numbers C(n,5,2).

Original entry on oeis.org

1, 3, 3, 4, 5, 6, 7, 9, 10, 12, 13, 15, 16, 18, 19, 21, 21, 27, 28, 30, 30, 37, 38, 40

Offset: 5

N. J. A. Sloane

It is known that 42 <= a(29) <= 43. The next few values are known: a(30) = 48, a(31) = 50, a(32) = 52. - Nathaniel Johnston, Jan 10 2024

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

D. Gordon, La Jolla Repository of Coverings
Uenal Mutlu (uenalm(AT)metronet.de), Tables of coverings
Index entries for covering numbers

Cf. A011975, A240116.

a(28) from Nathaniel Johnston, Jan 10 2024

cp's OEIS Frontend

A036838 Triangle read by rows: T(n,k) = value of Schoenheim bound L_1(n+2,k+2,k+1) on covering numbers (0 <= k <= n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

A066010 Triangle of covering numbers T(n,k) = C(n,k,k-1), n >= 2, 2 <= k <= n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A001839 The coding-theoretic function A(n,4,3).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A036831 Schoenheim bound L_1(n,4,3).

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

A240115 Schoenheim lower bound L(n,4,2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A240116 Schoenheim lower bound L(n,5,2).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A240117 Schoenheim lower bound L(n,6,2).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A240118 Schoenheim lower bound L(n,5,3).

Views

Author

Keywords