A115400 -id:A115400 - cp's OEIS frontend

A268283 Number of distinct directed Hamiltonian cycles of the Platonic graphs (in the order of tetrahedral, cubical, octahedral, dodecahedral, and icosahedral graph).

6, 12, 32, 60, 2560

Offset: 1

Melvin Peralta, Jan 29 2016

a(n)/2 is the number of distinct undirected Hamiltonian cycles of the Platonic graph corresponding to a(n).

Eric Weisstein's World of Mathematics, Tetrahedral Graph
Eric Weisstein's World of Mathematics, Cubical Graph
Eric Weisstein's World of Mathematics, Octahedral Graph
Eric Weisstein's World of Mathematics, Dodecahedral Graph
Eric Weisstein's World of Mathematics, Icosahedral Graph

Cf. A052762 (tetrahedral graph), A140986 (cubical graph), A115400 (octahedral graph), A218513 (dodecahedral graph), A218514 (icosahedral graph).

A334279 Irregular table read by rows: T(n, k) is the coefficient of x^k in the chromatic polynomial of the 1-skeleton of the n-dimensional cross polytope, 0 <= k <= 2n.

Original entry on oeis.org

0, 0, 1, 0, -3, 6, -4, 1, 0, -64, 154, -137, 58, -12, 1, 0, -2790, 7467, -7852, 4300, -1346, 244, -24, 1, 0, -205056, 593016, -698250, 448015, -175004, 43608, -6990, 700, -40, 1, 0, -22852200, 70164670, -89812001, 64407806, -29113410, 8790285, -1822164, 260868, -25405, 1610, -60, 1

Offset: 1

Peter Kagey, Apr 21 2020

A033815 is the number of acyclic orientations of the n-dimensional cross polytope, which is the absolute value of the chromatic polynomial evaluated at -1.
Sums of absolute values of entries in each row give A033815.
These graphs are chromatically unique, that is, there is no nonisomorphic graph with the same chromatic polynomial.
Conjectures from Peter Kagey, Apr 26 2020: (Start)
T(n,1) = -A161131(2n-1).
T(n,2n-2) = A212689(2n - 1).
T(n,2n-1) = A046092(n-1). (End)

			Table begins:
n/k| 0       1      2       3      4       5     6     7   8   9 10
---+---------------------------------------------------------------
  1| 0       0      1
  2| 0      -3      6      -4      1
  3| 0     -64    154    -137     58     -12     1
  4| 0   -2790   7467   -7852   4300   -1346   244   -24   1
  5| 0 -205056 593016 -698250 448015 -175004 43608 -6990 700 -40  1

Peter Kagey, Table of n, a(n) for n = 1..2600 (first 50 rows)
Chong-Yun Chao and George A. Novacky Jr., On maximally saturated graphs, Discrete Math., 41 (1982), 139-143.
Eric Weisstein's World of Mathematics, Chromatic Polynomial
Eric Weisstein's World of Mathematics, Cocktail Party Graph
Wikipedia, Cross-polytope
Wikipedia, Turán graph

A334278 is analogous for the n-dimensional hypercube.
Cf. A033815, A115400.
Cf. A161131, A212689, A046092.

A218514 Number of n-colorings of the icosahedral graph.

Original entry on oeis.org

0, 0, 0, 0, 240, 80400, 4012560, 76848240, 825447840, 6005512800, 33014872800, 146953113120, 554770648080, 1835249610480, 5448481998960, 14778817981200, 37135461679680, 87386816771520, 194264943433920, 410876964198720, 831638579799600, 1618744884780240

Offset: 0

Eric M. Schmidt, Oct 31 2012

N. Biggs, Algebraic Graph Theory, 2nd ed. Cambridge University Press, 1993. See p. 69.

Eric M. Schmidt, Table of n, a(n) for n = 0..1000
Eric W. Weisstein, Icosahedral Graph
Index entries for linear recurrences with constant coefficients, signature (13,-78,286,-715,1287,-1716,1716,-1287,715,-286,78,-13,1).

Cf. A052762, A140986, A115400, A218513, A296916, A296917..

A218514(n):=n*(n-1)*(n-2)*(n-3)*(n^8 -24*n^7 +260*n^6 -1670*n^5 +6999*n^4 -19698*n^3 +36408*n^2 -40240*n +20170)$
makelist(A218514(n), n, 0, 30); /* Martin Ettl, Nov 03 2012 */

def A218514(n) : return n*(n-1)*(n-2)*(n-3)*(n^8 -24*n^7 +260*n^6 -1670*n^5 +6999*n^4 -19698*n^3 +36408*n^2 -40240*n +20170);

a(n) = n(n-1)(n-2)(n-3)(n^8 -24n^7 +260n^6 -1670n^5 +6999n^4 -19698n^3 +36408n^2 -40240n +20170).
Hence a(n) = n^12 - 30*n^11 + 415*n^10 - 3500*n^9 + 20023*n^8 - 81622*n^7 + 241605*n^6 - 517360*n^5 + 780286*n^4 - 782108*n^3 + 463310*n^2 - 121020*n (cf. A296917) - N. J. A. Sloane, Dec 23 2017
G.f.: -240*x^4*(12547*x^8 +131518*x^7 +481078*x^6 +743494*x^5 +485740*x^4 +128698*x^3 +12442*x^2 +322*x +1)/(x-1)^13. [Colin Barker, Nov 06 2012]

A218513 Number of n-colorings of the dodecahedral graph.

Original entry on oeis.org

0, 0, 0, 7200, 168506880, 112603286160, 15108392957760, 775405390866960, 20886647215714560, 353998543659193440, 4231366997071432320, 38508081275604409920, 281586666065022616320, 1720887594454493527920, 9053942417801770507200, 41955877772610102690480

Offset: 0

Eric M. Schmidt, Oct 31 2012

N. Biggs, Algebraic Graph Theory, 2nd ed. Cambridge University Press, 1993. See pp. 69-70.

Eric M. Schmidt, Table of n, a(n) for n = 0..1000
Eric W. Weisstein, Dodecahedral Graph
Index entries for linear recurrences with constant coefficients, signature (21, -210, 1330, -5985, 20349, -54264, 116280, -203490, 293930, -352716, 352716, -293930, 203490, -116280, 54264, -20349, 5985, -1330, 210, -21, 1).

Cf. A052762, A140986, A115400, A218514, A296918, A296919.

A218513(n):=n*(n-1)*(n-2)*(n^17 -27*n^16 +352*n^15 -2950*n^14 +17839*n^13 -82777*n^12 +305866*n^11 -921448*n^10 +2297495*n^9 -4783425*n^8 +8347700*n^7 -12195590*n^6 +14808795*n^5 -14713381*n^4 +11613602*n^3 -6892084*n^2 +2751604*n -555984)$
makelist(A218513(n), n, 0, 30); /* Martin Ettl, Nov 03 2012 */

def A218513(n) : return n*(n-1)*(n-2)*(n^17 -27*n^16 +352*n^15 -2950*n^14 +17839*n^13 -82777*n^12 +305866*n^11 -921448*n^10 +2297495*n^9 -4783425*n^8 +8347700*n^7 -12195590*n^6 +14808795*n^5 -14713381*n^4 +11613602*n^3 -6892084*n^2 +2751604*n -555984);

a(n) = n(n-1)(n-2)(n^17 - 27n^16 + 352n^15 - 2950n^14 + 17839n^13 - 82777n^12 + 305866n^11 - 921448n^10 + 2297495n^9 - 4783425n^8 + 8347700n^7 - 12195590n^6 + 14808795n^5 - 14713381n^4 + 11613602n^3 - 6892084n^2 + 2751604n - 555984).
See A296919 for the coefficients of the expanded form of a(n). - N. J. A. Sloane, Dec 23 2017
G.f.: -240*x^3*(2007273*x^17 +678113783*x^16 +62897280675*x^15 +2149103163405*x^14 +32571452423195*x^13 +246267894384141*x^12 +1000326687571911*x^11 +2283861589692665*x^10 +3002531231655465*x^9 +2288662487004975*x^8 +1001857651156729*x^7 +244960098705399*x^6 +31779760521705*x^5 +2006465657455*x^4 +53246253405*x^3 +454442307*x^2 +701482*x +30)/(x-1)^21. - Colin Barker, Nov 06 2012

A334281 Number of n-colorings of the vertices of the 4-dimensional cross polytope such that no two adjacent vertices have the same color.

Original entry on oeis.org

0, 0, 0, 0, 24, 600, 7560, 61320, 351120, 1515024, 5266800, 15531120, 40308840, 94534440, 204228024, 412284600, 786283680, 1428742560, 2490276960, 4186173024, 6816915000, 10793253240, 16666437480, 25164280680, 37233759024, 54090894000, 77278702800

Offset: 0

Peter Kagey, Apr 21 2020

The 4-dimensional cross-polytope is sometimes called the 16-cell. It is one of the six convex regular 4-polytopes.

Colin Barker, Table of n, a(n) for n = 0..1000
Eric Weisstein's World of Mathematics, Chromatic Polynomial
Wikipedia, Cross-polytope
Wikipedia, Turán graph
Index entries for linear recurrences with constant coefficients, signature (9,-36,84,-126,126,-84,36,-9,1).

Cf. A091940 (2-dimensional), A115400 (3-dimensional).

Cf. A334279.

concat([0,0,0,0], Vec(24*x^4*(1 + 16*x + 126*x^2 + 536*x^3 + 1001*x^4) / (1 - x)^9 + O(x^30))) \\ Colin Barker, Apr 22 2020

a(n) = n*(n - 1)*(n - 2)*(n - 3)*(465 - 392n + 125n^2 - 18n^3 + n^4).
a(n) = -2790n + 7467n^2 - 7852n^3 + 4300n^4 - 1346n^5 + 244n^6 - 24n^7 + n^8.
From Colin Barker, Apr 22 2020: (Start)
G.f.: 24*x^4*(1 + 16*x + 126*x^2 + 536*x^3 + 1001*x^4) / (1 - x)^9.
a(n) = 9*a(n-1) - 36*a(n-2) + 84*a(n-3) - 126*a(n-4) + 126*a(n-5) - 84*a(n-6) + 36*a(n-7) - 9*a(n-8) + a(n-9) for n>8.
(End)

A342088 Triangle read by rows: T(n,k) is the number of n-colorings of the vertices of the k-dimensional cross polytope such that no two adjacent vertices have the same color. 0 <= k <= n.

Original entry on oeis.org

1, 1, 1, 1, 4, 2, 1, 9, 18, 6, 1, 16, 84, 96, 24, 1, 25, 260, 780, 600, 120, 1, 36, 630, 4080, 7560, 4320, 720, 1, 49, 1302, 15330, 61320, 78120, 35280, 5040, 1, 64, 2408, 45696, 351120, 913920, 866880, 322560, 40320

Offset: 0

Peter Kagey, Feb 27 2021

			Triangle begins:
  n\k| 0   1     2      3       4       5       6       7      8
  ---+----------------------------------------------------------
   0 | 1
   1 | 1,  1
   2 | 1,  4,    2
   3 | 1,  9,   18,     6
   4 | 1, 16,   84,    96,     24
   5 | 1, 25,  260,   780,    600,    120
   6 | 1, 36,  630,  4080,   7560,   4320,    720
   7 | 1, 49, 1302, 15330,  61320,  78120,  35280,   5040
   8 | 1, 64, 2408, 45696, 351120, 913920, 866880, 322560, 40320

Peter Kagey, Rows n = 0..100, flattened
Eric Weisstein's World of Mathematics, Chromatic Polynomial
Eric Weisstein's World of Mathematics, Cocktail Party Graph
Wikipedia, Cross-polytope
Wikipedia, Turán graph

Cf. A000012 (k=0), A000290 (k=1), A091940 (k=2), A115400 (k=3), A334281 (k=4), A342073 (k=5), A342074 (k=6), A342075 (k=7).

Cf. A334279.

T[n_, k_] := Sum[n! k!/((n - k - j)! (k - j)! j!), {j, 0, k}]

T(n,n) = n!.
T(n,k) = Sum_{i=0..2*k} A334279(k,i)*n^i.
T(n,k) = n*T(n-1,k-1) + n*(n-1)*T(n-2,k-1).
T(n,k) = Sum_{j=0..k} n!k!/((n-k-j)!(k-j)!j!).

A342073 Number of n-colorings of the vertices of the 5-dimensional cross polytope such that no two adjacent vertices have the same color.

Original entry on oeis.org

0, 0, 0, 0, 0, 120, 4320, 78120, 913920, 7575120, 46751040, 224587440, 881591040, 2946869640, 8659691040, 22915652760, 55611279360, 125508233760, 266320172160, 535945217760, 1030028705280, 1901347885080, 3386866301280, 5844714201480, 9803816225280

Offset: 0

Peter Kagey, Feb 27 2021

nonn

Peter Kagey, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (11,-55,165,-330,462,-462,330,-165,55,-11,1).

Analogous for k-dimensional cross polytope: A091940 (k=2), A115400 (k=3), A334281 (k=4), A342074 (k=6), A342075 (k=7)

Cf. A334279, A342088.

p = ChromaticPolynomial[CompleteGraph[Table[2, 5]], x];
Table[p /. x -> n, {n, 0, 50}]

a(n) = -205056*n + 593016*n^2 - 698250*n^3 + 448015*n^4 - 175004*n^5 + 43608*n^6 - 6990*n^7 + 700*n^8 - 40*n^9 + n^10.
a(n) = (n - 4)*(n - 3)*(n - 2)*(n - 1)*n*(-8544 + 6909*n - 2240*n^2 + 365*n^3 - 30*n^4 + n^5).
a(n) = Sum_{i=1..10} A334279(5,i)*n^i.
From Chai Wah Wu, Jan 19 2024: (Start)
a(n) = 11*a(n-1) - 55*a(n-2) + 165*a(n-3) - 330*a(n-4) + 462*a(n-5) - 462*a(n-6) + 330*a(n-7) - 165*a(n-8) + 55*a(n-9) - 11*a(n-10) + a(n-11) for n > 10.
G.f.: x^5*(-2170680*x^5 - 1145400*x^4 - 272400*x^3 - 37200*x^2 - 3000*x - 120)/(x - 1)^11. (End)

A342074 Number of n-colorings of the vertices of the 6-dimensional cross polytope such that no two adjacent vertices have the same color.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 720, 35280, 866880, 13849920, 158004000, 1347524640, 8866186560, 46496324160, 201705744240, 748737990000, 2444976293760, 7178449299840, 19276199691840, 47983899216960, 111920569776000, 246727594270080, 517702915311120, 1039979954779920

Offset: 0

Peter Kagey, Feb 27 2021

nonn

Peter Kagey, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (13,-78,286,-715,1287,-1716,1716,-1287,715,-286,78,-13,1).

Analogous for k-dimensional cross polytope: A091940 (k=2), A115400 (k=3), A334281 (k=4), A342073 (k=5), A342075 (k=7).

Cf. A334279, A342088.

p = ChromaticPolynomial[CompleteGraph[Table[2, 6]], x];
Table[p /. x -> n, {n, 0, 50}]

a(n) = -22852200*n + 70164670*n^2 - 89812001*n^3 + 64407806*n^4 - 29113410*n^5 + 8790285*n^6 - 1822164*n^7 + 260868*n^8 - 25405*n^9 + 1610*n^10 - 60*n^11 + n^12.
a(n) = (n - 5)*(n - 4)*(n - 3)*(n - 2)*(n - 1)*n*(190435 - 149879*n + 49144*n^2 - 8605*n^3 + 850*n^4 - 45*n^5 + n^6).
a(n) = Sum_{i=1..12} A334279(6,i)*n^i.
From Chai Wah Wu, Jan 19 2024: (Start)
a(n) = 13*a(n-1) - 78*a(n-2) + 286*a(n-3) - 715*a(n-4) + 1287*a(n-5) - 1716*a(n-6) + 1716*a(n-7) - 1287*a(n-8) + 715*a(n-9) - 286*a(n-10) + 78*a(n-11) - 13*a(n-12) + a(n-13) for n > 12.
G.f.: x^6*(-287250480*x^6 - 150137280*x^5 - 35996400*x^4 - 5126400*x^3 - 464400*x^2 - 25920*x - 720)/(x - 1)^13. (End)

A342075 Number of n-colorings of the vertices of the 7-dimensional cross polytope such that no two adjacent vertices have the same color.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 5040, 322560, 10342080, 216518400, 3261535200, 37026823680, 325474269120, 2264594492160, 12789814237200, 60389186457600, 245221330273920, 877374833287680, 2821277454690240, 8284633867238400, 22503569636419200, 57135310310453760

Offset: 0

Peter Kagey, Feb 27 2021

nonn

Peter Kagey, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (15,-105,455,-1365,3003,-5005,6435,-6435,5005,-3003,1365,-455,105,-15,1).

Analogous for k-dimensional cross polytope: A091940 (k=2), A115400 (k=3), A334281 (k=4), A342073 (k=5), A342074 (k=6).

Cf. A334279, A342088.

p = ChromaticPolynomial[CompleteGraph[Table[2, 7]], x];
Table[p /. x -> n, {n, 0, 50}]

a(n) = -3597143040*n + 11590795728*n^2 - 15837356724*n^3 + 12355698460*n^4 - 6212542175*n^5 + 2144307578*n^6 - 526197678*n^7 + 93450369*n^8 - 12064836*n^9 + 1122618*n^10 - 73423*n^11 + 3206*n^12 - 84*n^13 + n^14.
a(n) = (n - 6)*(n - 5)*(n - 4)*(n - 3)*(n - 2)*(n - 1)*n*(n^7 - 63 n^6 + 1708 n^5 - 25795 n^4 + 234094 n^3 - 1275281 n^2 + 3858049 n - 4996032).
a(n) = Sum_{i=1..14} A334279(7,i)*n^i.
From Chai Wah Wu, Jan 19 2024: (Start)
a(n) = 15*a(n-1) - 105*a(n-2) + 455*a(n-3) - 1365*a(n-4) + 3003*a(n-5) - 5005*a(n-6) + 6435*a(n-7) - 6435*a(n-8) + 5005*a(n-9) - 3003*a(n-10) + 1365*a(n-11) - 455*a(n-12) + 105*a(n-13) - 15*a(n-14) + a(n-15) for n > 14.
G.f.: x^7*(-52370755920*x^7 - 27190754640*x^6 - 6557740560*x^5 - 959792400*x^4 - 92962800*x^3 - 6032880*x^2 - 246960*x - 5040)/(x - 1)^15. (End)

A212221 Square array A(n,k), n>=1, k>=1, read by antidiagonals: A(n,k) is 1/(2*n) times the number of n-colorings of the complete tripartite graph K_(k,k,k).

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 0, 0, 1, 3, 0, 0, 1, 12, 6, 0, 0, 1, 30, 78, 10, 0, 0, 1, 66, 474, 340, 15, 0, 0, 1, 138, 2238, 4780, 1095, 21, 0, 0, 1, 282, 9546, 46420, 32955, 2856, 28, 0, 0, 1, 570, 38958, 385660, 617775, 168546, 6412, 36

Offset: 1

Alois P. Heinz, May 06 2012

The complete tripartite graph K_(n,n,n) has 3*n vertices and 3*n^2 = A033428(n) edges; see A212220 for example. The chromatic polynomial of K_(n,n,n) has 3*n+1 = A016777(n) coefficients.

			Square array A(n,k) begins:
   0,    0,     0,      0,       0,         0,          0, ...
   0,    0,     0,      0,       0,         0,          0, ...
   1,    1,     1,      1,       1,         1,          1, ...
   3,   12,    30,     66,     138,       282,        570, ...
   6,   78,   474,   2238,    9546,     38958,     155994, ...
  10,  340,  4780,  46420,  385660,   2995540,   22666780, ...
  15, 1095, 32955, 617775, 9248595, 123920295, 1569542955, ...

Alois P. Heinz, Antidiagonals n = 1..100, flattened
Eric Weisstein's World of Mathematics, Complete Tripartite Graph
Wikipedia, Chromatic Polynomial

Rows 1+2,3-4 give: A000004, A000012, A089143(n-1) = 1/2*A182464(n-2) = 1/3*A182467(n-2).
Columns 1-2 give: A000217(n-2), 1/(2*n)*A115400(n).
Cf. A008277, A016777, A033428, A212220, A282247.

P:= proc(n) option remember;
      unapply(expand(add(add(Stirling2(n, k) *Stirling2(n, m)
       *mul(q-i, i=0..k+m-1) *(q-k-m)^n, m=1..n), k=1..n)), q)
    end:
A:= (n, k)-> P(k)(n)/(2*n):
seq(seq(A(n, 1+d-n), n=1..d), d=1..12);

p[n_] := p[n] = Function[q, Expand[Sum[Sum[StirlingS2[n, k] * StirlingS2[n, m] * Product[q-i, {i, 0, k+m-1}]*(q-k-m)^n, {m, 1, n}], {k, 1, n}]]]; a[n_, k_] := p[k][n]/(2*n); Table[Table[a[n, 1+d-n], {n, 1, d}], {d, 1, 12}] // Flatten (* Jean-François Alcover, Dec 13 2013, translated from Maple *)

A(n,k) = 1/(2*n) * Sum_{j,m=1..k} S2(k,j) * S2(k,m) * (n-j-m)^k * Product_{i=0..j+m-1} (n-i) with S2 = A008277.

A(n,n) = A282247(n).

cp's OEIS Frontend

A268283 Number of distinct directed Hamiltonian cycles of the Platonic graphs (in the order of tetrahedral, cubical, octahedral, dodecahedral, and icosahedral graph).

Views

Author

Keywords

Comments

Links

Crossrefs

A334279 Irregular table read by rows: T(n, k) is the coefficient of x^k in the chromatic polynomial of the 1-skeleton of the n-dimensional cross polytope, 0 <= k <= 2n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A218514 Number of n-colorings of the icosahedral graph.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maxima

Sage

Formula

A218513 Number of n-colorings of the dodecahedral graph.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maxima

Sage

Formula

A334281 Number of n-colorings of the vertices of the 4-dimensional cross polytope such that no two adjacent vertices have the same color.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A342088 Triangle read by rows: T(n,k) is the number of n-colorings of the vertices of the k-dimensional cross polytope such that no two adjacent vertices have the same color. 0 <= k <= n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A342073 Number of n-colorings of the vertices of the 5-dimensional cross polytope such that no two adjacent vertices have the same color.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A342074 Number of n-colorings of the vertices of the 6-dimensional cross polytope such that no two adjacent vertices have the same color.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A342075 Number of n-colorings of the vertices of the 7-dimensional cross polytope such that no two adjacent vertices have the same color.

Views

Author

Keywords