Displaying 1-10 of 11 results found.
Square array A(n,k), n>=1, k>=1, read by antidiagonals: A(n,k) is the number of n-colorings of the k X k X k triangular grid.
+10
22
1, 0, 2, 0, 0, 3, 0, 0, 6, 4, 0, 0, 6, 24, 5, 0, 0, 6, 192, 60, 6, 0, 0, 6, 2112, 1620, 120, 7, 0, 0, 6, 32640, 98820, 7680, 210, 8, 0, 0, 6, 718080, 13638780, 1574400, 26250, 336, 9, 0, 0, 6, 22665216, 4260983940, 1034019840, 13676250, 72576, 504, 10
COMMENTS
The k X k X k triangular grid has k rows with i vertices in row i. Each vertex is connected to the neighbors in the same row and up to two vertices in each of the neighboring rows. The graph has A000217(k) vertices and 3* A000217(k-1) edges altogether. The coefficients of the chromatic polynomials for the column sequences are given by the rows of A193283. - Georg Fischer, Jul 31 2023
EXAMPLE
Square array A(n,k) begins:
1, 0, 0, 0, 0, 0, ...
2, 0, 0, 0, 0, 0, ...
3, 6, 6, 6, 6, 6, ...
4, 24, 192, 2112, 32640, 718080, ...
5, 60, 1620, 98820, 13638780, 4260983940, ...
6, 120, 7680, 1574400, 1034019840, 2175789895680, ...
CROSSREFS
Columns k=1-11 give: A000027, A007531, A182788, A182789, A182790, A182791, A182792, A182793, A182794, A182795, A182796. Rows n=1-10 give: A000007(k-1), A000038(k-1), A040006(k-1), A182798, A153467*4, A153468*5, A153469*6, A153470*7, A153471*8, A153472*9, A153473*10.
Number of acyclic orientations of the n X n X n triangular grid.
+10
12
1, 6, 162, 19602, 10619910, 25753129470, 279488630719746, 13573527285845525634, 2949851294016821586137934, 2868652614504623418332698354038, 12483073717920041560887416137620435882, 243068197882943244196175524589364487906969746, 21178547618859581967063811182618272071362317831449326
COMMENTS
The n X n X n triangular grid has n rows with i vertices in row i. Each vertex is connected to the neighbors in the same row and up to two vertices in each of the neighboring rows. The graph has A000217(n) vertices and 3* A000217(n-1) edges altogether. An acyclic orientation is an assignment of a direction to each edge such that no cycle in the graph is consistently oriented. Stanley showed that the number of acyclic orientations of a graph G is equal to the absolute value of the chromatic polynomial X_G(q) evaluated at q=-1.
CROSSREFS
Cf. A182797, A182788, A182789, A182790, A182791, A182792, A182793, A182794, A182795, A182796, A182798, A000217.
Number of n-colorings of the 3 X 3 X 3 triangular grid.
+10
12
0, 0, 0, 6, 192, 1620, 7680, 26250, 72576, 172872, 368640, 721710, 1320000, 2283996, 3773952, 5997810, 9219840, 13770000, 20054016, 28564182, 39890880, 54734820, 73920000, 98407386, 129309312, 167904600, 215654400, 274218750, 345473856
COMMENTS
The 3 X 3 X 3 triangular grid has 3 rows with k vertices in row k. Each vertex is connected to the neighbors in the same row and up to two vertices in each of the neighboring rows. The graph has 6 vertices and 9 edges altogether.
REFERENCES
Burkard Polster and Marty Ross, Math Goes to the Movies, The Johns Hopkins University Press, Baltimore, 2013, ยง1.10 Mathematics: Graph Theory 3, pp. 16-17.
FORMULA
a(n) = n*(n-1)*(n-2)^4.
G.f.: 6*x^3*(1 + 25*x + 67*x^2 + 27*x^3) / (1-x)^7.
a(0)=0, a(1)=0, a(2)=0, a(3)=6, a(4)=192, a(5)=1620, a(6)=7680, a(n) = 7*a(n-1) -21*a(n-2) +35*a(n-3) -35*a(n-4) +21*a(n-5) -7*a(n-6) +a(n-7). - Harvey P. Dale, Dec 10 2011
MAPLE
a:= n-> n*(n-1)*(n-2)^4: seq(a(n), n=0..30);
MATHEMATICA
Table[n(n-1)(n-2)^4, {n, 0, 30}] (* or *) LinearRecurrence[ {7, -21, 35, -35, 21, -7, 1}, {0, 0, 0, 6, 192, 1620, 7680}, 30] (* Harvey P. Dale, Dec 10 2011 *)
Number of n-colorings of the 4 X 4 X 4 triangular grid.
+10
12
0, 0, 0, 6, 2112, 98820, 1574400, 13676250, 80631936, 363204072, 1342218240, 4261697550, 12000120000, 30653510316, 72237215232, 159067919010, 330577363200, 653537970000, 1236951760896, 2253171240342, 3967187906880, 6776444390100, 11264003520000, 18268445544426
COMMENTS
The 4 X 4 X 4 triangular grid has 4 rows with k vertices in row k. Each vertex is connected to the neighbors in the same row and up to two vertices in each of the neighboring rows. The graph has 10 vertices and 18 edges altogether.
LINKS
Index entries for linear recurrences with constant coefficients, signature (11,-55,165,-330,462,-462,330,-165,55,-11,1).
FORMULA
a(n) = n*(n-1)*(n-2)^4*(n^4-9*n^3+31*n^2-49*n+31).
G.f.: -6*x^3*(3267*x^7 +51359*x^6 +195679*x^5 +241075*x^4 +100425*x^3 +12653*x^2 +341*x +1) / (x -1)^11. - Colin Barker, Oct 01 2014
MAPLE
a:= n-> n^10 -18*n^9 +144*n^8 -672*n^7 +2016*n^6 -4031*n^5 +5368*n^4 -4584*n^3 +2272*n^2 -496*n:
seq(a(n), n=0..30);
Number of n-colorings of the 5 X 5 X 5 triangular grid.
+10
12
0, 0, 0, 6, 32640, 13638780, 1034019840, 29699591250, 460772395776, 4674233282040, 34753231503360, 203842711924830, 991765602960000, 4148317444266996, 15316041761879040, 50925154505624490, 154877550296286720, 436185098521110000, 1148935457273020416
COMMENTS
The 5 X 5 X 5 triangular grid has 5 rows with k vertices in row k. Each vertex is connected to the neighbors in the same row and up to two vertices in each of the neighboring rows. The graph has 15 vertices and 30 edges altogether.
LINKS
Index entries for linear recurrences with constant coefficients, signature (16,-120,560,-1820,4368,-8008,11440,-12870,11440,-8008,4368,-1820,560,-120,16,-1).
FORMULA
a(n) = n*(n-1)*(n^9 -21*n^8 +198*n^7 -1102*n^6 +3999*n^5 -9840*n^4 +16475*n^3 -18177*n^2 +12056*n -3686)*(n-2)^4.
G.f.: 6*x^3*(1769985*x^12 +130265584*x^11 +2438678946*x^10 +17020599920*x^9 +51993920175*x^8 +74836435680*x^7 +51909140892*x^6 +17013829728*x^5 +2462276655*x^4 +136618800*x^3 +2186210*x^2 +5424*x +1)/(x-1)^16.
MAPLE
a:= n-> n^15 -30*n^14 +419*n^13 -3612*n^12 +21477*n^11 -93207*n^10 +304555*n^9 -761340*n^8 +1463473*n^7 -2152758*n^6 +2385118*n^5 -1929184*n^4 +1075936*n^3 -369824*n^2 +58976*n:
seq(a(n), n=0..30);
Number of n-colorings of the 6 X 6 X 6 triangular grid.
+10
12
0, 0, 0, 6, 718080, 4260983940, 2175789895680, 268832232086250, 13543515506658816, 368471361307591080, 6399096250242170880, 78976960885082392110, 745151003161018080000, 5660706546633925834476, 35971041412788697313280
COMMENTS
The 6 X 6 X 6 triangular grid has 6 rows with k vertices in row k. Each vertex is connected to the neighbors in the same row and up to two vertices in each of the neighboring rows. The graph has 21 vertices and 45 edges altogether.
LINKS
Index entries for linear recurrences with constant coefficients, signature (22, -231, 1540, -7315, 26334, -74613, 170544, -319770, 497420, -646646, 705432, -646646, 497420, -319770, 170544, -74613, 26334, -7315, 1540, -231, 22, -1).
FORMULA
a(n) = n^21 -45*n^20 + ... (see Maple program).
MAPLE
a:= n-> n^21 -45*n^20 +965*n^19 -13115*n^18 +126720*n^17 -925528*n^16 +5303300*n^15 -24419511*n^14 +91795611*n^13 -284572218*n^12 +731723164*n^11 -1563764362*n^10 +2773460910*n^9 -4060976822*n^8 +4861918772*n^7 -4686537246*n^6 +3551696188*n^5 -2039006608*n^4 +833782816*n^3 -216349280*n^2 +26756288*n: seq(a(n), n=0..30);
Number of n-colorings of the 7 X 7 X 7 triangular grid.
+10
12
0, 0, 0, 6, 22665216, 3013780700340, 14668353488732160, 10142843465859326250, 2047585083571827265536, 177922459478738381782536, 8379024937788205785415680, 247855358008532074713890670, 5089690042011600555045120000
COMMENTS
The 7 X 7 X 7 triangular grid has 7 rows with k vertices in row k. Each vertex is connected to the neighbors in the same row and up to two vertices in each of the neighboring rows. The graph has 28 vertices and 63 edges altogether.
LINKS
Index entries for linear recurrences with constant coefficients, signature (29, -406, 3654, -23751, 118755, -475020, 1560780, -4292145, 10015005, -20030010, 34597290, -51895935, 67863915, -77558760, 77558760, -67863915, 51895935, -34597290, 20030010, -10015005, 4292145, -1560780, 475020, -118755, 23751, -3654, 406, -29, 1).
FORMULA
a(n) = n^28 -63*n^27 + ... (see Maple program).
MAPLE
a:= n-> n^28 -63*n^27 +1917*n^26 -37515*n^25 +530415*n^24 -5770367*n^23 +50229001*n^22 -359161581*n^21 +2149154827*n^20 -10907730408*n^19 +47421892719*n^18 -177879720291*n^17 +578605822984*n^16 -1637514420168*n^15 +4039146735437*n^14 -8685828617404*n^13 +16263806276269*n^12 -26442885506316*n^11 +37160408393135*n^10 -44834641208000*n^9 +46004737388704*n^8 -39623922744400*n^7
+28128173982016*n^6 -16032767219808*n^5 +7056432341248*n^4 -2251430597120*n^3 +463382611200*n^2 -46172626432*n: seq(a(n), n=0..30);
Number of n-colorings of the 8 X 8 X 8 triangular grid.
+10
12
0, 0, 0, 6, 1031276544, 4826149802070660, 316827094291524894720, 1595091571660292411606250, 1592275064882420035249606656, 526249245643156296389047576104, 78022473527414400196098852126720, 6300701001267935948773824927446190
COMMENTS
The 8 X 8 X 8 triangular grid has 8 rows with k vertices in row k. Each vertex is connected to the neighbors in the same row and up to two vertices in each of the neighboring rows. The graph has 36 vertices and 84 edges altogether.
LINKS
Index entries for linear recurrences with constant coefficients, signature (37, -666, 7770, -66045, 435897, -2324784, 10295472, -38608020, 124403620, -348330136, 854992152, -1852482996, 3562467300, -6107086800, 9364199760, -12875774670, 15905368710, -17672631900, 17672631900, -15905368710, 12875774670, -9364199760, 6107086800, -3562467300, 1852482996, -854992152, 348330136, -124403620, 38608020, -10295472, 2324784, -435897, 66045, -7770, 666, -37, 1).
FORMULA
a(n) = n^36 -84*n^35 + ... (see Maple program).
a(n) = (n^30 + ... )*n*(n-1)*(n-2)^4 (see PARI program), therefore all terms are divisible by 6. - M. F. Hasler, Dec 02 2010
MAPLE
a:= n-> n^36 -84*n^35 +3437*n^34 -91266*n^33 +1767948*n^32 -26626641*n^31 +324474230*n^30 -3287527515*n^29 +28241112564*n^28 -208720581316*n^27 +1342098781876*n^26 -7574085510428*n^25 +37773151152128*n^24 -167375021582772*n^23 +661739022592885*n^22 -2341944556478962*n^21 +7436934470326959*n^20 -21224613967949058*n^19 +54488667645973816*n^18 -125859887740997948*n^17 +261444368727996373*n^16 -487829426279117443*n^15 +816027319948726718*n^14 -1220298815193350831*n^13 +1625157969312740380*n^12 -1917859440184087949*n^11 +1992559474100473934*n^10 -1807335902805940076*n^9 +1415695106519940144*n^8 -943996557462968752*n^7 +525570615466126368*n^6 -237792323595423264*n^5 +84014216771282688*n^4 -21747100909979904*n^3 +3668087119290368*n^2 -302469084548608*n: seq(a(n), n=0..12);
PROG
(PARI) a(n) = n*(n-1)*(n-2)^4*(n^30 -15*(5*n^20 -182*n^19 -73212*n^17 +968723*n^16 -10321679*n^15 +90965902*n^14 -42239514291692*n^5 +728948069669224)*n^9 -64240*n^27 +10138842074*n^22 -64422107890*n^21 +353781404418*n^20 -1692797609642*n^19 +7100833446102*n^18 -26231755759998*n^17 +85617623199383*n^16 -247408302649363*n^15 -1437889343008038*n^13 +2888477744794634*n^12 -5124456558208194*n^11 +8000185529836163*n^10 +12990665090694358*n^8 -13287807554341505*n^7 +11549829535832291*n^6 -8378308904565234*n^5 +4943464695686292*n^4 -2282977532565696*n^3 +775401219820384*n^2 -172542491602784*n +18904317784288) \\ - M. F. Hasler, Dec 02 2010
Number of n-colorings of the 9 X 9 X 9 triangular grid.
+10
12
0, 0, 0, 6, 67849629696, 17497810918123218900, 21925009706068920874598400, 1045584233565048659578102256250, 6368832392862110714579731514351616, 9534235558912413569697852308677120776
COMMENTS
The 9 X 9 X 9 triangular grid has 9 rows with k vertices in row k. Each vertex is connected to the neighbors in the same row and up to two vertices in each of the neighboring rows. The graph has 45 vertices and 108 edges altogether.
LINKS
Index entries for linear recurrences with constant coefficients, signature (46, -1035, 15180, -163185, 1370754, -9366819, 53524680, -260932815, 1101716330, -4076350421, 13340783196, -38910617655, 101766230790, -239877544005, 511738760544, -991493848554, 1749695026860, -2818953098830, 4154246671960, -5608233007146, 6943526580276, -7890371113950, 8233430727600, -7890371113950, 6943526580276, -5608233007146, 4154246671960, -2818953098830, 1749695026860, -991493848554, 511738760544, -239877544005, 101766230790, -38910617655, 13340783196, -4076350421, 1101716330, -260932815, 53524680, -9366819, 1370754, -163185, 15180, -1035, 46, -1).
FORMULA
a(n) = n^45 -108*n^44 + ... (see Maple program).
MAPLE
a:= n-> n^45 -108*n^44 +5714*n^43 -197372*n^42 +5004951*n^41 -99331939*n^40 +1606376002*n^39 -21760175421*n^38+251900492473*n^37 -2529947375509*n^36 +22305591797446*n^35 -174257688976920*n^34 +1215408574487125*n^33 -7615215090082277*n^32 +43080094524111690*n^31 -220967851371444614*n^30 +1031210769134504204*n^29 -4391099235591937845*n^28 +17100876656070073880*n^27 -61022823409833058201*n^26
+199812365243382363912*n^25 -600991376049390898992*n^24 +1661619908871238912196*n^23 -4224371709444972487708*n^22 +9875485316923894342417*n^21 -21221061699176359482887*n^20 +41886723683404956818991*n^19 -75858892195631057087330*n^18 +125862045971633675717554*n^17 -190930468100539717386672*n^16 +264149971345371552591904*n^15 -332242305634477726845448*n^14 +378446023463873654411519*n^13
-388532455150677959308540*n^12 +357418193476328504707252*n^11 -292480744218652691170096*n^10 +210981642121913298294408*n^9 -132621489649268878766112*n^8 +71568787087815309389792*n^7 -32504434438954975091968*n^6 +12087094618713177654080*n^5 -3534893963007018617856*n^4 +762559875649969442816*n^3 -107896190008663345152*n^2 +7511367180771568640*n: seq(a(n), n=0..12);
Number of n-colorings of the 10 X 10 X 10 triangular grid.
+10
12
0, 0, 0, 6, 6468240187392, 143635721907943000938060, 4861091521972177266672058368000, 2856800670438221106476061284736341250, 131028911804088893672445293407292154494976
COMMENTS
The 10 X 10 X 10 triangular grid has 10 rows with k vertices in row k. Each vertex is connected to the neighbors in the same row and up to two vertices in each of the neighboring rows. The graph has 55 vertices and 135 edges altogether.
LINKS
Index entries for linear recurrences with constant coefficients, signature (56, -1540, 27720, -367290, 3819816, -32468436, 231917400, -1420494075, 7575968400, -35607051480, 148902215280, -558383307300, 1889912732400, -5804731963800, 16253249498640, -41648951840265, 97997533741800, -212327989773900, 424655979547800, -785613562163430, 1346766106565880, -2142582442263900, 3167295784216200, -4355031703297275, 5574440580220512, -6646448384109072, 7384942649010080, -7648690600760440, 7384942649010080, -6646448384109072, 5574440580220512, -4355031703297275, 3167295784216200, -2142582442263900, 1346766106565880, -785613562163430, 424655979547800, -212327989773900, 97997533741800, -41648951840265, 16253249498640, -5804731963800, 1889912732400, -558383307300, 148902215280, -35607051480, 7575968400, -1420494075, 231917400, -32468436, 3819816, -367290, 27720, -1540, 56, -1).
FORMULA
a(n) = n^55 -135*n^54 + ... (see Maple program).
MAPLE
a:= n-> n^55 -135*n^54 +8964*n^53 -390222*n^52 +12525057*n^51 -316076903*n^50 +6530286070*n^49 -113573987769*n^48 +1696787220520*n^47 -22113112510550*n^46 +254428951045842*n^45 -2609511250718613*n^44 +24045856082285419*n^43 -200371113856491240*n^42 +1518133675627952270*n^41 -10506651071221868153*n^40 +66680463251797921915*n^39 -389373183471975572302*n^38 +2098028797385404193010*n^37
-10456871082871436486097*n^36 +48311408769374448761586*n^35 -207268123118278617037243*n^34 +827002152243388922174239*n^33 -3072694198727638003487979*n^32 +10641864949286796056022377*n^31 -34383949683339954923684782*n^30 +103704885062207595279156312*n^29 -292098504456226533053440510*n^28 +768501708532085822533190556*n^27 -1888698433570434475839725929*n^26 +4335279422341414825800378209*n^25
-9290907905051445440799000716*n^24 +18580084162229028469273798451*n^23 -34646102938311786771803477712*n^22 +60179271229381177090538625964*n^21 -97248893234106206859587981511*n^20 +145984266730291101055714541723*n^19 -203195282517216004808829603690*n^18 +261670683045031491886557091942*n^17 -310956138275834795608083550274*n^16 +339941943100528554861813262560*n^15
-340628682378318048979653175381*n^14 +311484260127833509262781795600*n^13 -258586709722348835998646850788*n^12 +193670730551369756737363762352*n^11 -129863868693889627423240097464*n^10 +77228998619164716149657770512*n^9 -40252487790410927197535447840*n^8 +18109784947870880558334595968*n^7 -6892748007729626216676319168*n^6 +2158618972888431826460898944*n^5 -534180587663008964293559296*n^4
+97953970795833012084624384*n^3 -11833494445627750018634752*n^2 +706434229524151535286272*n: seq(a(n), n=0..12);
Search completed in 0.011 seconds
|