A036838 -id:A036838 - cp's OEIS frontend

A014125 Bisection of A001400.

1, 3, 6, 11, 18, 27, 39, 54, 72, 94, 120, 150, 185, 225, 270, 321, 378, 441, 511, 588, 672, 764, 864, 972, 1089, 1215, 1350, 1495, 1650, 1815, 1991, 2178, 2376, 2586, 2808, 3042, 3289, 3549, 3822, 4109, 4410, 4725, 5055, 5400, 5760, 6136, 6528, 6936, 7361, 7803

Offset: 0

N. J. A. Sloane

Also Schoenheim bound L_1(n,5,4).
Degrees of polynomials defined by p(n) = (x^(n+1)*p(n-1)p(n-3) + p(n-2)^2)/p(n-4), p(-4)=p(-3)=p(-2)=p(-1)=1. - Michael Somos, Jul 21 2004
Degrees of polynomial tau-functions of q-discrete Painlevé I, which generate sequence A095708 when q=2 (up to an offset of 3). - Andrew Hone, Jul 29 2004
Because of the Laurent phenomenon for the general q-discrete Painlevé I tau-function recurrence p(n) = (a*x^(n+1)*p(n-1)*p(n-3) + b*p(n-2)^2)/p(n-4), p(n) for n > -1 will always be a polynomial in x and a Laurent polynomial in a,b and the initial data p(-4),p(-3),p(-2),p(-1). - Andrew Hone, Jul 29 2004
Create the sequence 0,0,0,0,0,6,18,36,66,108,... so that the sum of three consecutive terms b(n) + b(n+1) + b(n+2) = A007531(n), with b(0)=0; then a(n) = b(n+5)/6. - J. M. Bergot, Jul 30 2013
Number of partitions of n into three kinds of part 1 and one kind of part 3. - Joerg Arndt, Sep 28 2015
First differences are A001840(k) starting with k=2; second differences are A086161(k) starting with k=1. - Bob Selcoe, Sep 28 2015
Maximum Wiener index of all maximal planar graphs with n+2 vertices.  The extremal graphs are cubes of paths. - Allan Bickle, Jul 09 2022
Maximum Wiener index of all maximal 3-degenerate graphs with n+2 vertices.  (A maximal 3-degenerate graph can be constructed from a 3-clique by iteratively adding a new 3-leaf (vertex of degree 3) adjacent to three existing vertices.)  The extremal graphs are cubes of paths, so the bound also applies to 3-trees. - Allan Bickle, Sep 18 2022

			Polynomials: p(0)=x+1, p(1)=x^3+x^2+1, p(2)=x^6+x^5+x^3+x^2+2x+1, ...
a(12)=185:  A000217(13)=91 + a(9)=94 == 91+55+28+10+1 = 185. - _Bob Selcoe_, Sep 27 2015
a(3)=11: the 11 partitions of 3 are {1a,1a,1a}, {1a,1a,1b}, {1a,1a,1c}, {1a,1b,1b}, {1a,1b,1c}, {1a,1c,1c}, {1b,1b,1b}, {1b,1b,1c}, {1b,1c,1c}, {1c,1c,1c}, {3}. - _Bob Selcoe_, Oct 04 2015

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.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
L. Smiley, Hidden Hexagons (preprint).

Michael De Vlieger, Table of n, a(n) for n = 0..10000
Joshua Alman, Cesar Cuenca, and Jiaoyang Huang, Laurent phenomenon sequences, Journal of Algebraic Combinatorics 43(3) (2015), 589-633.
Allan Bickle and Zhongyuan Che, Wiener indices of maximal k-degenerate graphs, arXiv:1908.09202 [math.CO], 2019.
Allan Bickle, A Survey of Maximal k-degenerate Graphs and k-Trees, Theory and Applications of Graphs 0 1 (2024) Article 5.
Z. Che and K. L. Collins, An upper bound on Wiener indices of maximal planar graphs, Discrete Appl. Math. 258 (2019), 76-86.
Éva Czabarka, Peter Dankelmann, Trevor Olsen, and László A. Székely, Wiener Index and Remoteness in Triangulations and Quadrangulations, arXiv:1905.06753 [math.CO], 2019.
S. Fomin and A. Zelevinsky, The Laurent Phenomenon, Advances in Applied Mathematics, 28 (2002), 119-144.
D. Ghosh, E. Győri, A. Paulos, N. Salia, and O. Zamora, The maximum Wiener index of maximal planar graphs, Journal of Combinatorial Optimization 40, (2020), 1121-1135.
H. R. Henze and C. M. Blair, The number of structurally isomeric hydrocarbons of the ethylene series, J. Amer. Chem. Soc., 55 (1933), 680-685.
H. R. Henze and C. M. Blair, The number of structurally isomeric Hydrocarbons of the Ethylene Series, J. Amer. Chem. Soc., 55 (2) (1933), 680-685. (Annotated scanned copy)
A. N. W. Hone, Algebraic curves, integer sequences and a discrete Painlevé transcendent, arXiv:0807.2538 [nlin.SI], 2008; Proceedings of SIDE 6, Helsinki, Finland, 2004. [Set a(n)=d(n+3) on p. 8]
Brian O'Sullivan and Thomas Busch, Spontaneous emission in ultra-cold spin-polarised anisotropic Fermi seas, arXiv 0810.0231v1 [quant-ph], 2008. [Eq 10a, lambda=3]
Index entries for two-way infinite sequences
Index entries for covering numbers
Index entries for linear recurrences with constant coefficients, signature (3,-3,2,-3,3,-1).

Cf. A000217, A000631, A001840, A014126, A086161, A095708.
A column of A036838.
Cf. A002623, A014125, A122046, A122047. - Johannes W. Meijer, May 20 2011
Maximum Wiener index of all maximal k-degenerate graphs for k=1..6: A000292, A002623, A014125, A122046, A122047, A175724.

[n^3/18+n^2/2+4*n/3+1+(((n+1) mod 3)-1)/9 : n in [0..50]]; // Wesley Ivan Hurt, Apr 14 2015

I:=[1,3,6,11,18,27]; [n le 6 select I[n] else 3*Self(n-1) -3*Self(n-2) +2*Self(n-3)-3*Self(n-4)+3*Self(n-5)-Self(n-6): n in [1..50]]; // Vincenzo Librandi, Apr 15 2015

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,n-3,n-4,1).

CoefficientList[Series[1/((1 - x)^3*(1 - x^3)), {x, 0, 50}], x] (* Wesley Ivan Hurt, Apr 14 2015 *)

a(n)=if(n<-5,-a(-6-n),polcoeff(1/(1-x)^3/(1-x^3)+x^n*O(x),n)) /* Michael Somos, Jul 21 2004 */

my(x='x+O('x^50)); Vec(1/((1-x)^3*(1-x^3))) \\ Altug Alkan, Oct 16 2015

a(n)=(n^3 + 9*n^2 + 24*n + 19)\/18 \\ Charles R Greathouse IV, Jun 29 2020

[(binomial(n+4,3) - ((n+4)//3))/3 for n in (0..50)] # G. C. Greubel, Apr 28 2019

G.f.: 1/((1-x)^3*(1-x^3)).
a(n) = -a(-6-n) = 3*a(n-1) -3*a(n-2) +2*a(n-3) -3*a(n-4) +3*a(n-5) -a(n-6).
The simplest recurrence is fourth order: a(n) = a(n-1) + a(n-3) - a(n-4) + n + 1, which gives the g.f.: 1/((1-x)^3*(1-x^3)), with a(-4) = a(-3) = a(-2) = a(-1) = 0.
a(n) = n^3/18 + n^2/2 + 4*n/3 + 1 + 2/(9*sqrt(3))*sin(2*Pi*n/3). - Andrew Hone, Jul 29 2004
a(n) = n^3/18 + n^2/2 + 4*n/3 + 1 + (((n+1) mod 3) - 1)/9. - same formula, simplified by Gerald Hillier, Apr 14 2015
a(n) = (2*A000027(n+1) + 3*A000292(n+1) + A049347(n-1) + 1 + 3*A000217(n+1))/9. - R. J. Mathar, Nov 16 2007
From Johannes W. Meijer, May 20 2011: (Start)
a(n) = A144677(n) + A144677(n-1) + A144677(n-2).
a(n) = A190717(n-4) + 2*A190717(n-3) + 3*A190717(n-2) + 2*A190717(n-1) + A190717(n). (End)
3*a(n) = binomial(n+4,3) - floor((n+4)/3). - Bruno Berselli, Nov 08 2013
a(n) = A000217(n+1) + a(n-3) = Sum_{j>=0, n>=3*j} (n-3*j+1)*(n-3*j+2)/2. - Bob Selcoe, Sep 27 2015
a(n) = round(((2*n+5)^3 + 3*(2*n+5)^2 - 9*(2*n+5))/144). - Giacomo Guglieri, Jun 28 2020
a(n) = floor(((n+2)^3 + 3*(n+2)^2)/18). - Allan Bickle, Aug 01 2020
a(n) = Sum_{j=0..n} (n-j+1)*floor((j+3)/3). - G. C. Greubel, Oct 18 2021
E.g.f.: exp(x) + exp(x)*x*(34 + 12*x + x^2)/18 + 2*exp(-x/2)*sin(sqrt(3)*x/2)/(9*sqrt(3)). - Stefano Spezia, Apr 05 2023

More terms from James Sellers, Dec 24 1999

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

Original entry on oeis.org

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

Offset: 3

N. J. A. Sloane

Also, minimal number of triangles needed to cover every edge (and node) of a complete graph on n nodes. This problem is also known as the edge clique covering problem. - Dmitry Kamenetsky, Jan 24 2016

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.

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.
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 (uenalm(AT)metronet.de), Tables of coverings
Wikipedia, Clique Cover Problem.
Index entries for covering numbers

Cf. A011976, A011977, A001839. A column of A066010. Also 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). Present sequence is L_1(n,3,2,1).

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 *)

Conjecture: G.f. ( -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 ) with a(n) = a(n-1) + a(n-2) - a(n-3) + a(n-6) - a(n-7) - a(n-8) + a(n-9). - R. J. Mathar, Aug 12 2012

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

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.

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 *)

A036832 Schoenheim bound L_1(n,5,4).

Original entry on oeis.org

1, 5, 9, 18, 26, 50, 66, 113, 149, 219, 273, 397, 476, 659, 787, 1028, 1197, 1549, 1771, 2237, 2550, 3120, 3510, 4273, 4751, 5700, 6324, 7444, 8184, 9595, 10472, 12161, 13254, 15185, 16451, 18800, 20254, 22991, 24743, 27817, 29799, 33433, 35673, 39821, 42454

Offset: 5

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 A011983.

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,5,4,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, 3];
Table[a[n], {n, 5, 46}] (* Jean-François Alcover, Mar 07 2023, after Maple code *)

A036833 Schoenheim bound L_1(n,6,5).

Original entry on oeis.org

1, 6, 12, 27, 44, 92, 132, 245, 348, 548, 728, 1125, 1428, 2087, 2624, 3598, 4389, 5938, 7084, 9321, 11050, 14040, 16380, 20653, 23755, 29450, 33728, 40942, 46376, 55971, 62832, 74993, 83942, 98703, 109674, 128467, 141778, 164769

Offset: 6

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 A011987.

A column of A036838.

A036834 Schoenheim bound L_1(n,7,6).

Original entry on oeis.org

1, 7, 16, 39, 70, 158, 246, 490, 746, 1253, 1768, 2893, 3876, 5963, 7872, 11308, 14421, 20359, 25300, 34621, 42622, 56160, 67860, 88513, 105201, 134629, 159004, 198862, 231880, 287851, 332112, 407105, 467677, 564018, 642377

Offset: 7

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 A066009.

A column of A036838.

A036835 Schoenheim bound L_1(n,8,7).

Original entry on oeis.org

1, 8, 20, 54, 105, 257, 431, 919, 1492, 2663, 3978, 6871, 9690, 15653, 21648, 32511, 43263, 63622, 82225, 116846, 149177, 203580, 254475, 342988, 420804, 555345, 675767, 870022, 1043460, 1331311, 1577532, 1984637, 2338385, 2890593

Offset: 8

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 A066011.

A column of A036838.

A036836 Schoenheim bound L_1(n,9,8).

Original entry on oeis.org

1, 9, 25, 72, 152, 400, 719, 1634, 2819, 5326, 8398, 15269, 22610, 38263, 55323, 86696, 120175, 183797, 246675, 363521, 480682, 678600, 876525, 1219513, 1542948, 2097970, 2627983, 3480088, 4289780, 5621091, 6835972, 8820609

Offset: 9

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 A066137.

A column of A036838.

A036830 Schoenheim bound L_1(n,n-4,n-5).

Original entry on oeis.org

3, 7, 14, 26, 44, 70, 105, 152, 213, 291, 388, 508, 654, 829, 1037, 1281, 1566, 1896, 2276, 2710, 3203, 3761, 4388, 5091, 5875, 6746, 7710, 8774, 9944, 11228, 12632, 14164, 15831, 17641, 19602, 21722, 24009, 26472, 29120, 31961, 35005

Offset: 6

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 A066225.

A column of A036838.

A036830 := proc(n) local i,t1; t1 := 1; for i from 6 to n do t1 := ceil(t1*i/(i-4)); od: t1; end;
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)

PARI
```
a(n)=if(n<7,3,ceil(n/(n-4)*a(n-1)))
```

a(6)=3; a(n) = ceiling(n/(n-4)*a(n-1)). - Benoit Cloitre, May 31 2003

cp's OEIS Frontend

A014125 Bisection of A001400.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Magma

Maple

Mathematica

PARI

PARI

PARI

Sage

Formula

Extensions

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

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

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

A036832 Schoenheim bound L_1(n,5,4).

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

A036833 Schoenheim bound L_1(n,6,5).

Views

Author

Keywords

References

Links

Crossrefs

A036834 Schoenheim bound L_1(n,7,6).

Views

Author

Keywords

References

Links

Crossrefs

A036835 Schoenheim bound L_1(n,8,7).

Views

Author

Keywords