Search: a037233 -id:a037233
|
|
A062318
|
|
Numbers of the form 3^m - 1 or 2*3^m - 1; i.e., the union of sequences A048473 and A024023.
|
|
+10
43
|
|
|
0, 1, 2, 5, 8, 17, 26, 53, 80, 161, 242, 485, 728, 1457, 2186, 4373, 6560, 13121, 19682, 39365, 59048, 118097, 177146, 354293, 531440, 1062881, 1594322, 3188645, 4782968, 9565937, 14348906, 28697813, 43046720, 86093441, 129140162
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
WARNING: The offset of this sequence has been changed from 0 to 1 without correcting the formulas and programs, many of them correspond to the original indexing a(0)=0, a(1)=1, ... - M. F. Hasler, Oct 06 2014
Numbers n such that no entry in n-th row of Pascal's triangle is divisible by 3, i.e., such that A062296(n) = 0.
The base 3 representation of these numbers is 222...222 or 122...222.
a(n+1) is also the Moore lower bound on the order of a (4,g)-cage. - Jason Kimberley, Oct 30 2011
|
|
LINKS
|
|
|
FORMULA
|
a(n) = 2*3^(n/2-1)-1 if n is even; a(n) = 3^(n/2-1/2)-1 if n is odd. - Emeric Deutsch, Feb 03 2005, offset updated.
a(n) = a(n-1) + 3*a(n-2) - 3*a(n-3).
G.f.: x^2*(1+x)/((1-x)*(1-3*x^2)). - Colin Barker, Apr 02 2012
a(2n+1) = 3*a(2n-1) + 2; a(2n) = ( a(2n-1) + a(2n+1) )/2. See A060647 for case where a(1)= 1. - Richard R. Forberg, Nov 30 2013
a(n) = 2^((1+(-1)^n)/2) * 3^((2*n-3-(-1)^n)/4) - 1. - Luce ETIENNE, Aug 29 2014
E.g.f.: (1 - 3*cosh(x) + 2*cosh(sqrt(3)*x) - 3*sinh(x) + sqrt(3)*sinh(sqrt(3)*x))/3. - Stefano Spezia, Apr 06 2022
a(n) = (1/3)*([n=0] - 3 + (1+(-1)^n)*3^(n/2) + ((1-(-1)^n)/2)*3^((n+1)/2)). - G. C. Greubel, Apr 17 2023
|
|
EXAMPLE
|
The first rows in Pascal's triangle with no multiples of 3 are:
row 0: 1;
row 1: 1, 1;
row 2: 1, 2, 1;
row 5: 1, 5, 10, 10, 5, 1;
row 8: 1, 8, 28, 56, 70, 56, 28, 8, 1;
|
|
MAPLE
|
if n mod 2 = 1 then
3^((n-1)/2)-1
else
2*3^(n/2-1)-1
fi
end proc:
|
|
MATHEMATICA
|
CoefficientList[Series[x^2*(1+x)/((1-x)*(1-3*x^2)), {x, 0, 40}], x] (* Vincenzo Librandi, Apr 20 2012 *)
A062318[n_]:= (1/3)*(Boole[n==0] -3 +3^(n/2)*(2*Mod[n+1, 2] +Sqrt[3] *Mod[n, 2]));
|
|
PROG
|
(Magma) I:=[0, 1, 2]; [n le 3 select I[n] else Self(n-1)+3*Self(n-2) -3*Self(n-3): n in [1..40]]; // Vincenzo Librandi, Apr 20 2012
(PARI) a(n)=3^(n\2)<<bittest(n, 0)-1 \\ [Program corresponds to offset=0, a(0)=0, a(1)=1.] - M. F. Hasler, Oct 06 2014
(SageMath)
def A062318(n): return (1/3)*(int(n==0) - 3 + 2*((n+1)%2)*3^(n/2) + (n%2)*3^((n+1)/2))
|
|
CROSSREFS
|
Moore lower bound on the order of a (k,g) cage: A198300 (square); rows: A000027 (k=2), A027383 (k=3), this sequence (k=4), A061547 (k=5), A198306 (k=6), A198307 (k=7), A198308 (k=8), A198309 (k=9), A198310 (k=10), A094626 (k=11); columns: A020725 (g=3), A005843 (g=4), A002522 (g=5), A051890 (g=6), A188377 (g=7). - Jason Kimberley, Oct 30 2011
Cf. A037233 (actual order of a (4,g)-cage).
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
Ahmed Fares (ahmedfares(AT)my-deja.com), Jul 05 2001
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|
|
A054760
|
|
Table T(n,k) = order of (n,k)-cage (smallest n-regular graph of girth k), n >= 2, k >= 3, read by antidiagonals.
|
|
+10
22
|
|
|
3, 4, 4, 5, 6, 5, 6, 8, 10, 6, 7, 10, 19, 14, 7, 8, 12, 30, 26, 24, 8, 9, 14, 40, 42, 67, 30, 9, 10, 16, 50, 62
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,1
|
|
REFERENCES
|
P. R. Christopher, Degree monotonicity of cages, Graph Theory Notes of New York, 38 (2000), 29-32.
|
|
LINKS
|
Andries E. Brouwer, Cages
|
|
FORMULA
|
T(k,g) >= A198300(k,g) with equality if and only if: k = 2 and g >= 3; g = 3 and k >= 2; g = 4 and k >= 2; g = 5 and k = 2, 3, 7 or possibly 57; or g = 6, 8, or 12, and there exists a symmetric generalized g/2-gon of order k - 1. - Jason Kimberley, Jan 01 2013
|
|
EXAMPLE
|
First eight antidiagonals are:
3 4 5 6 7 8 9 10
4 6 10 14 24 30 58
5 8 19 26 67 80
6 10 30 42 ?
7 12 40 62
8 14 50
9 16
10
|
|
CROSSREFS
|
Orders of cages: this sequence (n,k), A000066 (3,n), A037233 (4,n), A218553 (5,n), A218554 (6,n), A218555 (7,n), A191595 (n,5).
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
Edited by Jason Kimberley, Apr 25 2010, Oct 26 2011, Dec 21 2012, Jan 01 2013
|
|
STATUS
|
approved
|
|
|
|
|
A000066
|
|
Smallest number of vertices in trivalent graph with girth (shortest cycle) = n.
(Formerly M1013 N0380)
|
|
+10
16
|
|
|
|
OFFSET
|
3,1
|
|
COMMENTS
|
Also called the order of the (3,n) cage graph.
Recently (unpublished) McKay and Myrvold proved that the minimal graph on 112 vertices is unique. - May 20 2003
If there are n vertices and e edges, then 3n=2e, so n is always even.
Current lower bounds for a(13)..a(32) are 202, 258, 384, 512, 768, 1024, 1536, 2048, 3072, 4096, 6144, 8192, 12288, 16384, 24576, 32768, 49152, 65536, 98304, 131072. - from Table 3 of the Dynamic cage survey via Jason Kimberley, Dec 31 2012
Current upper bounds for a(13)..a(32) are 272, 384, 620, 960, 2176, 2560, 4324, 5376, 16028, 16206, 49326, 49608, 108906, 109200, 285852, 415104, 1141484, 1143408, 3649794, 3650304. - from Table 3 of the Dynamic cage survey via Jason Kimberley, Dec 31 2012
|
|
REFERENCES
|
A. T. Balaban, Trivalent graphs of girth nine and eleven and relationships among cages, Rev. Roum. Math. Pures et Appl. 18 (1973) 1033-1043.
Brendan McKay, personal communication.
H. Sachs, On regular graphs with given girth, pp. 91-97 of M. Fiedler, editor, Theory of Graphs and Its Applications: Proceedings of the Symposium, Smolenice, Czechoslovakia, 1963. Academic Press, NY, 1964.
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).
|
|
LINKS
|
Andries E. Brouwer, Cages
|
|
FORMULA
|
For all g > 2, a(g) >= A027383(g-1), with equality if and only if g = 3, 4, 5, 6, 8, or 12. - Jason Kimberley, Dec 21 2012 and Jan 01 2013
|
|
CROSSREFS
|
Orders of cages: A054760 (n,k), this sequence (3,n), A037233 (4,n), A218553 (5,n), A218554 (6,n), A218555 (7,n), A191595 (n,5).
|
|
KEYWORD
|
nonn,hard,more,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
Balaban proved 112 as an upper bound for a(11). The proof that it is also a lower bound is in the paper by Brendan McKay, W. Myrvold and J. Nadon.
|
|
STATUS
|
approved
|
|
|
|
|
A184940
|
|
Irregular triangle C(n,g) counting the connected 4-regular simple graphs on n vertices with girth exactly g.
|
|
+10
8
|
|
|
1, 1, 2, 5, 1, 16, 0, 57, 2, 263, 2, 1532, 12, 10747, 31, 87948, 220, 803885, 1606, 8020590, 16828, 86027734, 193900, 983417704, 2452818, 11913817317, 32670329, 1, 152352034707, 456028472, 2, 2050055948375, 6636066091, 8, 28466137588780, 100135577616, 131
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
5,3
|
|
COMMENTS
|
The first column is for girth exactly 3. The row length sequence starts: 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4. The row length is incremented to g-2 when n reaches A037233(g).
|
|
LINKS
|
|
|
EXAMPLE
|
1;
1;
2;
5, 1;
16, 0;
57, 2;
263, 2;
1532, 12;
10747, 31;
87948, 220;
803885, 1606;
8020590, 16828;
86027734, 193900;
983417704, 2452818;
11913817317, 32670329, 1;
152352034707, 456028472, 2;
2050055948375, 6636066091, 8;
28466137588780, 100135577616, 131;
|
|
CROSSREFS
|
Connected 4-regular simple graphs with girth exactly g: this sequence (triangle); chosen g: A184943 (g=3), A184944 (g=4), A184945 (g=5), A184946 (g=6).
Triangular arrays C(n,g) counting connected simple k-regular graphs on n vertices with girth exactly g: A198303 (k=3), this sequence (k=4), A184950 (k=5), A184960 (k=6), A184970 (k=7), A184980 (k=8).
|
|
KEYWORD
|
nonn,hard,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A184941
|
|
Irregular triangle C(n,g) counting the connected 4-regular simple graphs on n vertices with girth at least g.
|
|
+10
7
|
|
|
1, 1, 2, 6, 1, 16, 0, 59, 2, 265, 2, 1544, 12, 10778, 31, 88168, 220, 805491, 1606, 8037418, 16828, 86221634, 193900, 985870522, 2452818, 11946487647, 32670330, 1, 152808063181, 456028474, 2, 2056692014474, 6636066099, 8, 28566273166527, 100135577747, 131
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
5,3
|
|
COMMENTS
|
The first column is for girth at least 3. The row length sequence starts: 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4. The row length is incremented to g-2 when n reaches A037233(g).
|
|
LINKS
|
|
|
EXAMPLE
|
1;
1;
2;
6, 1;
16, 0;
59, 2;
265, 2;
1544, 12;
10778, 31;
88168, 220;
805491, 1606;
8037418, 16828;
86221634, 193900;
985870522, 2452818;
11946487647, 32670330, 1;
152808063181, 456028474, 2;
2056692014474, 6636066099, 8;
28566273166527, 100135577747, 131;
|
|
CROSSREFS
|
Connected 4-regular simple graphs with girth at least g: this sequence (triangle); chosen g: A006820 (g=3), A033886 (g=4), A058343 (g=5), A058348 (g=6).
Triangular arrays C(n,g) counting connected simple k-regular graphs on n vertices with girth at least g: A185131 (k=3), this sequence (k=4), A184951 (k=5), A184961 (k=6), A184971 (k=7), A184981 (k=8).
|
|
KEYWORD
|
nonn,hard,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A191595
|
|
Order of smallest n-regular graph of girth 5.
|
|
+10
7
|
|
|
|
OFFSET
|
2,1
|
|
COMMENTS
|
Current upper bounds for a(8)..a(20) are 80, 96, 124, 154, 203, 230, 288, 312, 336, 448, 480, 512, 576. - Corrected from "Lower" to "Upper" and updated, from Table 4 of the Dynamic cage survey, by Jason Kimberley, Dec 29 2012
Current lower bounds for a(8)..a(20) are 67, 86, 103, 124, 147, 174, 199, 230, 259, 294, 327, 364, 403. - from Table 4 of the Dynamic cage survey via Jason Kimberley, Dec 31 2012
|
|
LINKS
|
Andries E. Brouwer, Cages
|
|
FORMULA
|
|
|
CROSSREFS
|
Orders of cages: A054760 (n,k), A000066 (3,n), A037233 (4,n), A218553 (5,n), A218554 (6,n), A218555 (7,n), this sequence (n,5).
Moore lower bound on the orders of (k,g) cages: A198300 (square); rows: A000027 (k=2), A027383 (k=3), A062318 (k=4), A061547 (k=5), A198306(k=6), A198307 (k=7), A198308 (k=8), A198309 (k=9), A198310 (k=10),A094626 (k=11); columns: A020725 (g=3), A005843 (g=4), A002522 (g=5), A051890 (g=6), A188377 (g=7). - Jason Kimberley, Nov 02 2011
|
|
KEYWORD
|
nonn,more,hard
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|
|
A218553
|
|
Order of (5,n) cage, i.e., minimal order of 5-regular graph of girth n.
|
|
+10
7
|
|
|
|
OFFSET
|
3,1
|
|
COMMENTS
|
a(7) <= 152, a(8) = 170, a(12) = 2730. - From Royle's page via Jason Kimberley, Dec 21 2012
|
|
LINKS
|
Andries E. Brouwer, Cages
Eric Weisstein's World of Mathematics, Cage Graph (claims too much)
|
|
FORMULA
|
|
|
CROSSREFS
|
Orders of cages: A054760 (n,k), A000066 (3,n), A037233 (4,n), this sequence (5,n), A218554 (6,n), A218555 (7,n), A191595 (n,5).
|
|
KEYWORD
|
hard,more,nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|
|
A218554
|
|
Order of (6,n) cage, i.e., minimal order of 6-regular graph of girth n.
|
|
+10
7
|
|
|
|
OFFSET
|
3,1
|
|
COMMENTS
|
a(7) <= 294, a(8) = 312, a(12) = 7812. - From Royle's page via Jason Kimberley, Dec 26 2012
|
|
LINKS
|
Andries E. Brouwer, Cages
Eric Weisstein's World of Mathematics, Cage Graph (claims too much)
|
|
FORMULA
|
|
|
CROSSREFS
|
Orders of cages: A054760 (n,k), A000066 (3,n), A037233 (4,n), A218553 (5,n), this sequence (6,n), A218555 (7,n), A191595 (n,5).
|
|
KEYWORD
|
hard,more,nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|
|
A218555
|
|
Order of (7,n) cage, i.e., minimal order of 7-regular graph of girth n.
|
|
+10
7
|
|
|
|
OFFSET
|
3,1
|
|
COMMENTS
|
|
|
LINKS
|
Andries E. Brouwer, Cages
Eric Weisstein's World of Mathematics, Cage Graph (claims too much)
|
|
FORMULA
|
|
|
CROSSREFS
|
Orders of cages: A054760 (n,k), A000066 (3,n), A037233 (4,n), A218553 (5,n), A218554 (6,n), this sequence (7,n), A191595 (n,5).
|
|
KEYWORD
|
hard,more,nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|
|
A185140
|
|
Irregular triangle E(n,g) counting not necessarily connected 4-regular simple graphs on n vertices with girth exactly g.
|
|
+10
2
|
|
|
1, 1, 2, 5, 1, 16, 0, 58, 2, 264, 2, 1535, 12, 10755, 31, 87973, 220, 803973, 1606, 8020967, 16829, 86029760, 193900, 983431053, 2452820, 11913921910, 32670331, 1, 152352965278, 456028487, 2, 2050065073002, 6636066126, 8, 28466234288520, 100135577863, 131, 8020967, 16829
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
5,3
|
|
COMMENTS
|
The first column is for girth at least 3. The column for girth g commences when n reaches A037233(g).
|
|
LINKS
|
|
|
FORMULA
|
The n-th row is the sequence of differences of the n-th row of A185340:
|
|
EXAMPLE
|
05: 1;
06: 1;
07: 2;
08: 5, 1;
09: 16, 0;
10: 58, 2;
11: 264, 2;
12: 1535, 12;
13: 10755, 31;
14: 87973, 220;
15: 803973, 1606;
16: 8020967, 16829;
17: 86029760, 193900;
18: 983431053, 2452820;
19: 11913921910, 32670331, 1;
20: 152352965278, 456028487, 2;
21: 2050065073002, 6636066126, 8;
22: 28466234288520, 100135577863, 131;
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,hard,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
Search completed in 0.013 seconds
|