|
%I #49 Sep 08 2022 08:45:59
%S 3,4,4,5,6,5,6,8,10,6,7,10,17,14,7,8,12,26,26,22,8,9,14,37,42,53,30,9,
%T 10,16,50,62,106,80,46,10,11,18,65,86,187,170,161,62,11,12,20,82,114,
%U 302,312,426,242,94,12,13,22,101,146,457,518,937,682,485,126,13
%N Square array M(k,g), read by antidiagonals, of the Moore lower bound on the order of a (k,g)-cage.
%C k >= 2; g >= 3.
%C The base k-1 reading of the base 10 string of A094626(g).
%C Exoo and Jajcay Theorem 1: M(k,g) <= A054760(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 n-gon of order k - 1.
%D E. Bannai and T. Ito, On finite Moore graphs, J. Fac. Sci. Tokyo, Sect. 1A, 20 (1973) 191-208.
%D R. M. Damerell, On Moore graphs, Proc. Cambridge Phil. Soc. 74 (1973) 227-236.
%H Jason Kimberley, <a href="/A198300/b198300.txt">Table of n, a(n) for n = 1..20100 (k+g = 5..204)</a>
%H Jason Kimberley, <a href="/A198300/a198300.txt">Table of n, k+g, k, g, M(k,g)=a(n) for k+g = 5..204 (n = 1..20100)</a>
%H G. Exoo and R. Jajcay, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS16">Dynamic cage survey</a>, Electr. J. Combin. (2008, 2011).
%H Gordon Royle, <a href="http://staffhome.ecm.uwa.edu.au/~00013890/remote/cages/allcages.html">Cages of higher valency</a>
%F M(k,2i) = 2 sum_{j=0}^{i-1}(k-1)^j = string "2"^i read in base k-1.
%F M(k,2i+1) = (k-1)^i + 2 sum_{j=0}^{i-1}(k-1)^j = string "1"*"2"^i read in base k-1.
%F Recurrence:
%F M(k,3) = k + 1,
%F M(k,2i) = M(k,2i-1) + (k-1)^(i-1),
%F M(k,2i+1) = M(k,2i) + (k-1)^i.
%e This is the table formed from the antidiagonals for k+g = 5..20:
%e 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
%e 4 6 10 14 22 30 46 62 94 126 190 254 382 510 766
%e 5 8 17 26 53 80 161 242 485 728 1457 2186 4373 6560
%e 6 10 26 42 106 170 426 682 1706 2730 6826 10922 27306
%e 7 12 37 62 187 312 937 1562 4687 7812 23437 39062
%e 8 14 50 86 302 518 1814 3110 10886 18662 65318
%e 9 16 65 114 457 800 3201 5602 22409 39216
%e 10 18 82 146 658 1170 5266 9362 42130
%e 11 20 101 182 911 1640 8201 14762
%e 12 22 122 222 1222 2222 12222
%e 13 24 145 266 1597 2928
%e 14 26 170 314 2042
%e 15 28 197 366
%e 16 30 226
%e 17 32
%e 18
%t Table[Function[g, FromDigits[#, k - 1] &@ IntegerDigits@ SeriesCoefficient[x (1 + x)/((1 - x) (1 - 10 x^2)), {x, 0, g}]][n - k + 3], {n, 2, 12}, {k, n, 2, -1}] // Flatten (* _Michael De Vlieger_, May 15 2017 *)
%o (Magma)
%o ExtendedStringToInt:=func<seq,base|&+[Integers()|seq[i]*base^(#seq-i):i in[1..#seq]]>;
%o M:=func<k,g|ExtendedStringToInt((IsOdd(g)select[1]else[])cat[2^^(g div 2)],k-1)>;
%o k_:=2;g_:=3;
%o anti:=func<kg|[M(kg-g,g):g in[g_..kg-k_]]>;
%o [anti(kg):kg in[5..15]];
%Y Moore lower bound on the order of a (k,g) cage: this sequence (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), 2*A053698 (g=8), 2*A053699 (g=10), 2*A053700 (g=12), 2*A053716 (g=14), 2*A053716 (g=16), 2*A102909 (g=18), 2*A103623 (g=20), 2*A060885 (g=22), 2*A105067 (g=24), 2*A060887 (g=26), 2*A104376 (g=28), 2*A104682 (g=30), 2*A105312 (g=32).
%Y Cf. A054760 (the actual order of a (k,g)-cage).
%K nonn,tabl,easy,base
%O 1,1
%A _Jason Kimberley_, Oct 27 2011
|
