A193233 -id:A193233 - cp's OEIS frontend

A182368 Triangle T(n,k), n>=1, 0<=k<=n^2, read by rows: row n gives the coefficients of the chromatic polynomial of the square grid graph G_(n,n), highest powers first.

1, 0, 1, -4, 6, -3, 0, 1, -12, 66, -216, 459, -648, 594, -323, 79, 0, 1, -24, 276, -2015, 10437, -40614, 122662, -292883, 557782, -848056, 1022204, -960627, 682349, -346274, 112275, -17493, 0, 1, -40, 780, -9864, 90798, -647352, 3714180, -17590911, 69997383

Offset: 1

Alois P. Heinz, Apr 26 2012

The square grid graph G_(n,n) has n^2 = A000290(n) vertices and 2*n*(n-1) = A046092(n-1) edges. The chromatic polynomial of G_(n,n) has n^2+1 = A002522(n) coefficients.

			3 example graphs:                          o---o---o
.                                          |   |   |
.                             o---o        o---o---o
.                             |   |        |   |   |
.                o            o---o        o---o---o
Graph:        G_(1,1)        G_(2,2)        G_(3,3)
Vertices:        1              4              9
Edges:           0              4             12
The square grid graph G_(2,2) is the cycle graph C_4 with chromatic polynomial q^4 -4*q^3 +6*q^2 -3*q => row 2 = [1, -4, 6, -3, 0].
Triangle T(n,k) begins:
  1,    0;
  1,   -4,     6,      -3,        0;
  1,  -12,    66,    -216,      459,       -648,         594, ...
  1,  -24,   276,   -2015,    10437,     -40614,      122662, ...
  1,  -40,   780,   -9864,    90798,    -647352,     3714180, ...
  1,  -60,  1770,  -34195,   486210,   -5421612,    49332660, ...
  1,  -84,  3486,  -95248,  1926585,  -30755376,   403410654, ...
  1, -112,  6216, -227871,  6205479, -133865298,  2382122274, ...
  1, -144, 10296, -487280, 17169852, -480376848, 11114098408, ...
  ...

Alois P. Heinz, Rows n = 1..9, flattened
Eric Weisstein's World of Mathematics, Chromatic Polynomial
Eric Weisstein's World of Mathematics, Grid Graph
Wikipedia, Chromatic Polynomial

Columns 0, 1 give: A000012, (-1)*A046092(n-1).
Sums of absolute values of row elements give: A080690(n).
Cf. A000290, A002522, A182406, A185442, A193233, A193277, A193283.

Reverse /@ CoefficientList[Table[ChromaticPolynomial[GridGraph[{n, n}], x], {n, 5}], x] // Flatten (* Eric W. Weisstein, May 01 2017 *)

A286017 Number of matchings in the n-Hanoi graph.

Original entry on oeis.org

4, 125, 4007754, 132460031222098852477, 4782311037918647241715144272946478084784910628903006412891408

Offset: 1

Eric W. Weisstein, Jun 16 2017

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..7
Eric Weisstein's World of Mathematics, Independent Edge Set
Eric Weisstein's World of Mathematics, Matching
Eric Weisstein's World of Mathematics, Hanoi Graph

Cf. A288839 (chromatic polynomials of the n-Hanoi graph).
Cf. A193233 (chromatic polynomial with highest coefficients first).
Cf. A137889 (directed Hamiltonian paths in the n-Hanoi graph).
Cf. A288490 (independent vertex sets in the n-Hanoi graph).
Cf. A193136 (spanning trees of the n-Hanoi graph).
Cf. A288796 (undirected paths in the n-Hanoi graph).

next[{h0_, h1_, h2_, h3_}] := {h0^3 + 3*h0*h1^2 + 3*h1^2*h2 + h2^3, h0^2*h1 + 2*h0*h1*h2 + h1^3 + 2*h1*h2^2 + h1^2*h3 + h2^2*h3, h0*h1^2 + 2*h1^2*h2 + h0*h2^2 + 2*h1*h2*h3 + h2^3 + h2*h3^2, h1^3 + 3*h1*h2^2 + 3*h2^2*h3 + h3^3};
a[n_] := Module[{v = {1, 1, 0, 0}}, For[i = 1, i <= n, i++, v = next[v]]; v[[1]]];
Array[a, 5] (* Jean-François Alcover, Oct 02 2017, translated from Andrew Howroyd's PARI code *)
Rest @ NestList[Function[{h, i, j, k}, {h^3 + 3 h i^2 + 3 i^2 j + j^3, h^2 i + 2 h i j + i^3 + 2 i j^2 + i^2 k + j^2 k, h i^2 + 2 i^2 j + h j^2 + 2 i j k + j^3 + j k^2, i^3 + 3 i j^2 + 3 j^2 k + k^3}] @@ # &, {1, 1, 0, 0}, 5][[All, 1]] (* Eric W. Weisstein, Oct 02 2017 *)

\\ here h0..h3 are number of matchings in Hanoi graph less 0..3 apex vertices.
Next(h0, h1, h2, h3)={[ h0^3 + 3*h0*h1^2 + 3*h1^2*h2 + h2^3, h0^2*h1 + 2*h0*h1*h2 + h1^3 + 2*h1*h2^2 + h1^2*h3 + h2^2*h3, h0*h1^2 + 2*h1^2*h2 + h0*h2^2 + 2*h1*h2*h3 + h2^3 + h2*h3^2, h1^3 + 3*h1*h2^2 + 3*h2^2*h3 + h3^3]}
a(n) = {my(v); v=[1, 1, 0, 0]; for(i=1, n, v=Next(v[1], v[2], v[3], v[4])); v[1]} \\ Andrew Howroyd, Jun 17 2017

a(5) from Andrew Howroyd, Jun 17 2017

A137889 Number of directed Hamiltonian paths in the n-Hanoi graph.

Original entry on oeis.org

6, 36, 384, 5460, 84816, 1347396, 21521184, 344194740, 5506552176, 88102619556, 1409633169984, 22554096102420, 360865400232336, 5773845857280516, 92381531540306784, 1478104495968880500, 23649671900884069296, 378394750275931314276, 6054316003862820691584

Offset: 1

Eric W. Weisstein, Feb 20 2008

Andrew Howroyd, Table of n, a(n) for n = 1..100
Andrew Howroyd, Hamiltonian paths in Hanoi graphs
Eric Weisstein's World of Mathematics, Hamiltonian Path
Eric Weisstein's World of Mathematics, Hanoi Graph
Index entries for linear recurrences with constant coefficients, signature (24,-147,316,-192).

Cf. A288839 (chromatic polynomials of the n-Hanoi graph).
Cf. A193233 (chromatic polynomial with highest coefficients first).
Cf. A288490 (independent vertex sets in the n-Hanoi graph).
Cf. A286017 (matchings in the n-Hanoi graph).
Cf. A193136 (spanning trees of the n-Hanoi graph).
Cf. A288796 (undirected paths in the n-Hanoi graph).

Table[(208 + 16 3^(n + 2) + 13 4^(n + 2) + 25 16^n)/312, {n, 10}] (* Eric W. Weisstein, Jun 19 2017 *)
RecurrenceTable[{a[1] == 6, a[n] == 3 a[n - 1] + (25 16^n + 64 4^n - 512)/384}, a, {n, 10}] (* Eric W. Weisstein, Jun 19 2017 *)

a(n)=if(n==1,6,3*a(n-1) + (25*16^n + 64*4^n - 512)/384); \\ Andrew Howroyd, Jun 18 2017

Vec(6*x*(1 - 18*x + 67*x^2 - 60*x^3) / ((1 - x)*(1 - 3*x)*(1 - 4*x)*(1 - 16*x)) + O(x^30)) \\ Colin Barker, Jul 30 2017

a(n) = (208 + 16*3^(n + 2) + 13*4^(n + 2) + 25*16^n)/312. - Eric W. Weisstein, Jun 19 2017
a(n) = 3*a(n-1) + (25*16^n + 64*4^n - 512)/384 for n > 1. - Andrew Howroyd, Jun 18 2017
From Colin Barker, Jul 30 2017: (Start)
G.f.: 6*x*(1 - 18*x + 67*x^2 - 60*x^3) / ((1 - x)*(1 - 3*x)*(1 - 4*x)*(1 - 16*x)).
a(n) = 24*a(n-1) - 147*a(n-2) + 316*a(n-3) - 192*a(n-4) for n>4.
(End)

Terms a(5) and beyond from Andrew Howroyd, Jun 18 2017

A288490 Number of independent vertex sets and vertex covers in the n-Hanoi graph.

Original entry on oeis.org

4, 52, 108144, 967067994163264, 691513106932053164262669026747190128930258944

Offset: 1

Eric W. Weisstein, Jun 16 2017

nonn

Term a(6) has 135 decimal digits and a(7) has 404 decimal digits. - Andrew Howroyd, Jun 19 2017

Andrew Howroyd, Table of n, a(n) for n = 1..7
Hanlin Chen, Renfang Wu, Guihua Huang, and Hanyuan Deng, Independent Sets on the Towers of Hanoi Graphs, Ars Mathematica Contemporanea, volume 12, number 2, 2017, pages 247-260. Section 3, i_n = a(n).
Eric Weisstein's World of Mathematics, Hanoi Graph
Eric Weisstein's World of Mathematics, Independent Vertex Set
Eric Weisstein's World of Mathematics, Vertex Cover

Cf. A297536 (maximum independent vertex sets in the n-Hanoi graph).
Cf. A321249 (maximal independent vertex sets in the n-Hanoi graph).
Cf. A288839 (chromatic polynomials of the n-Hanoi graph).
Cf. A193233 (chromatic polynomial with highest coefficients first).
Cf. A137889 (directed Hamiltonian paths in the n-Hanoi graph).
Cf. A286017 (matchings in the n-Hanoi graph).
Cf. A193136 (spanning trees of the n-Hanoi graph).
Cf. A288796 (undirected paths in the n-Hanoi graph).

{1, 3, 3, 1} . # & /@ NestList[Function[{h, i, j, k}, {h^3 + 6 h^2 i + 9 h i^2 + 3 h^2 j + 2 i^3 + 6 h i j, h^2 i + 4 h i^2 + 2 h^2 j + h^2 k + 8 h i j + 3 i^3 + 4 i^2 j + 2 h j^2 + 2 h i k, h i^2 + 4 h i j + 2 i^3 + 7 i^2 j + 2 h i k + 3 h j^2 + 4 i j^2 + 2 i^2 k + 2 h j k, i^3 + 6 i^2 j + 9 i j^2 + 3 i^2 k + 2 j^3 + 6 i j k}] @@ # &, {1, 1, 0, 0}, 4]

\\ Here h0..h3 is independent sets with 0..3 of the 3 apex vertices occupied.
Next(h0,h1,h2,h3) = {[h0^3 + 6*h0^2*h1 + 9*h0*h1^2 + 3*h0^2*h2 + 2*h1^3 + 6*h0*h1*h2, h0^2*h1 + 4*h0*h1^2 + 2*h0^2*h2 + h0^2*h3 + 8*h0*h1*h2 + 3*h1^3 + 4*h1^2*h2 + 2*h0*h2^2 + 2*h0*h1*h3, h0*h1^2 + 4*h0*h1*h2 + 2*h1^3 + 7*h1^2*h2 + 2*h0*h1*h3 + 3*h0*h2^2 + 4*h1*h2^2 + 2*h1^2*h3 + 2*h0*h2*h3, h1^3 + 6*h1^2*h2 + 9*h1*h2^2 + 3*h1^2*h3 + 2*h2^3 + 6*h1*h2*h3]}
a(n) = {my(v);v=[1,1,0,0]; for(i=2,n,v=Next(v[1],v[2],v[3],v[4])); v[1]+v[4]+3*(v[2]+v[3])} \\ Andrew Howroyd, Jun 20 2017

from itertools import islice
def A288490_gen(): # generator of terms
    f,g,h,p = 1,1,0,0
    while True:
        yield f+3*(g+h)+p
        a, b = f+(g<<1), g+(h<<1)
        f,g,h,p = a*(f*(a+(b<<1)-h)+g**2), f*(p*a+b*(a+(g<<1))+2*h**2)+g**2*(g+(b<<1)), f*(g*(b+(h<<1))+3*h**2)+g*(g*((b<<1)+3*h)+(h<<1)**2)+p*(f*b+g*a), b*(g*(3*p+b+(h<<1))+h**2)
A288490_list = list(islice(A288490_gen(),5)) # Chai Wah Wu, Jan 11 2024

a(5) from Andrew Howroyd, Jun 19 2017

A288796 Number of (undirected) paths in the n-Hanoi graph.

Original entry on oeis.org

6, 279, 305868, 10210452146391, 5764678901089651494212581315486920, 7007522073643519244177937570089174585653471798870178330313274704558499562496773948518048745883

Offset: 1

Eric W. Weisstein, Jun 16 2017

nonn

Terms up to about a(10) can be computed using a transfer matrix method. - Andrew Howroyd, Jun 18 2017

Andrew Howroyd, Table of n, a(n) for n = 1..7
Eric Weisstein's World of Mathematics, Graph Path
Eric Weisstein's World of Mathematics, Hanoi Graph

Cf. A288839 (chromatic polynomials of the n-Hanoi graph).
Cf. A193233 (chromatic polynomial with highest coefficients first).
Cf. A137889 (directed Hamiltonian paths in the n-Hanoi graph).
Cf. A288490 (independent vertex sets in the n-Hanoi graph).
Cf. A286017 (matchings in the n-Hanoi graph).
Cf. A193136 (spanning trees of the n-Hanoi graph).

a(4)-a(6) from Andrew Howroyd, Jun 18 2017

A288839 Triangle read by rows: coefficients of the chromatic polynomial of the n-Hanoi graph.

Original entry on oeis.org

0, 2, -3, 1, 0, 40, -180, 370, -455, 363, -190, 63, -12, 1, 0, 608000, -6960000, 40524800, -158999200, 468979200, -1099617480, 2117585600, -3419826630, 4697231261, -5541107684, 5652058863, -5007519752, 3863562996, -2598606825, 1522861581, -776022242, 342624075, -130362394, 42424338, -11689056, 2689452, -507084, 76293, -8806, 732, -39, 1

Offset: 1

Eric W. Weisstein, Jun 17 2017

Equal to A193233 with ordering of row elements reversed.

			Polynomials:
(x-2)*(x-1)*x
(x-2)^3*(x-1)*x*(5-10*x+10*x^2-5*x^3+x^4)
(x-2)^6*(x-1)*x*(-9500+70750*x+...+x^19)
Coefficients:
0, 2, -3, 1;
0, 40, -180, 370, -455, 363, -190, 63, -12, 1;
0, 608000, -6960000, 40524800, -158999200, ..., -39, 1;

Eric Weisstein's World of Mathematics, Chromatic Polynomial
Eric Weisstein's World of Mathematics, Hanoi Graph

Cf. A193233 (chromatic polynomial with highest coefficients first).
Cf. A137889 (directed Hamiltonian paths in the n-Hanoi graph).
Cf. A288490 (independent vertex sets in the n-Hanoi graph).
Cf. A286017 (matchings in the n-Hanoi graph).
Cf. A193136 (spanning trees of the n-Hanoi graph).
Cf. A288796 (undirected paths in the n-Hanoi graph).

A193136 Numbers of spanning trees of the Hanoi graphs.

Original entry on oeis.org

3, 135, 20503125, 119709242282867431640625, 39709946214287663263304759568121660162631769708241336047649383544921875

Offset: 1

Eric W. Weisstein, Jul 16 2011

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..6
Eric Weisstein's World of Mathematics, Hanoi Graph
Eric Weisstein's World of Mathematics, Spanning Tree

Cf. A288839 (chromatic polynomials of the n-Hanoi graph).
Cf. A193233 (chromatic polynomial with highest coefficients first).
Cf. A137889 (directed Hamiltonian paths in the n-Hanoi graph).
Cf. A288490 (independent vertex sets in the n-Hanoi graph).
Cf. A286017 (matchings in the n-Hanoi graph).
Cf. A288796 (undirected paths in the n-Hanoi graph).

A193277 Triangle T(n,k), n>=1, 0<=k<=(3+3^n)/2, read by rows: row n gives the coefficients of the chromatic polynomial of the Sierpinski gasket graph S_n, highest powers first.

Original entry on oeis.org

1, -3, 2, 0, 1, -9, 32, -56, 48, -16, 0, 1, -27, 339, -2625, 14016, -54647, 160663, -362460, 631828, -848736, 866640, -653248, 343744, -112896, 17408, 0, 1, -81, 3204, -82476, 1553454, -22823259, 272286183, -2711405961, 22990179324

Offset: 1

Alois P. Heinz, Jul 20 2011

The Sierpinski graph S_n has (3+3^n)/2 vertices and 3^n edges. The chromatic polynomial of S_n has (3+3^n)/2+1 coefficients.

			3 example graphs:                        o
.                                       / \
.                                      o---o
.                                     / \ / \
.                       o            o---o---o
.                      / \          / \     / \
.            o        o---o        o---o   o---o
.           / \      / \ / \      / \ / \ / \ / \
.          o---o    o---o---o    o---o---o---o---o
Graph:      S_1        S_2              S_3
Vertices:    3          6                15
Edges:       3          9                27
The Sierpinski graph S_1 is equal to the cycle graph C_3 with chromatic polynomial q^3 -3*q^2 +2*q => [1, -3, 2, 0].
Triangle T(n,k) begins:
1,    -3,       2,           0;
1,    -9,      32,         -56,           48,              -16,  ...
1,   -27,     339,       -2625,        14016,           -54647,  ...
1,   -81,    3204,      -82476,      1553454,        -22823259,  ...
1,  -243,   29295,    -2336013,    138604878,      -6526886841,  ...
1,  -729,  265032,   -64069056,  11585834028,   -1671710903793,  ...
1, -2187, 2389419, -1738877625, 948268049436, -413339609377179,  ...

Alois P. Heinz, Rows n = 1..7, flattened
Eric Weisstein's World of Mathematics, Chromatic Polynomial.
Eric Weisstein's World of Mathematics, Sierpiński Gasket Graph.
Wikipedia, Chromatic Polynomial.

Cf. A000244, A067771, A185442, A193233.

A212084 Triangle T(n,k), n>=0, 0<=k<=2n, read by rows: row n gives the coefficients of the chromatic polynomial of the complete bipartite graph K_(n,n), highest powers first.

Original entry on oeis.org

1, 1, -1, 0, 1, -4, 6, -3, 0, 1, -9, 36, -75, 78, -31, 0, 1, -16, 120, -524, 1400, -2236, 1930, -675, 0, 1, -25, 300, -2200, 10650, -34730, 75170, -102545, 78610, -25231, 0, 1, -36, 630, -6915, 52080, -279142, 1074822, -2942445, 5552680, -6796926, 4787174

Offset: 0

Alois P. Heinz, Apr 30 2012

The complete bipartite graph K_(n,n) has 2n vertices and n^2 = A000290(n) edges. The chromatic polynomial of K_(n,n) has 2n+1 = A005408(n) coefficients.

			3 example graphs:                     +-----------+
.                 o        o   o      o   o   o   |
.                 |        |\ /|      |\ /|\ /|\ /
.                 |        | X |      | X | X | X
.                 |        |/ \|      |/ \|/ \|/ \
.                 o        o   o      o   o   o   |
.                                     +-----------+
Graph:         K_(1,1)    K_(2,2)      K_(3,3)
Vertices:         2          4            6
Edges:            1          4            9
The complete bipartite graph K_(2,2) is the cycle graph C_4 with chromatic polynomial q^4 -4*q^3 +6*q^2 -3*q => row 2 = [1, -4, 6, -3, 0].
Triangle T(n,k) begins:
  1;
  1,  -1,   0;
  1,  -4,   6,    -3,     0;
  1,  -9,  36,   -75,    78,     -31,       0;
  1, -16, 120,  -524,  1400,   -2236,    1930,     -675, ...
  1, -25, 300, -2200, 10650,  -34730,   75170,  -102545, ...
  1, -36, 630, -6915, 52080, -279142, 1074822, -2942445, ...
  ...

Alois P. Heinz, Rows n = 0..90, flattened
Eric Weisstein's World of Mathematics, Complete Bipartite Graph
Wikipedia, Chromatic Polynomial

Columns k=0-2 give: A000012, (-1)*A000290, A083374.
Row sums and last elements of rows give: A000007.
Row lengths give: A005408.
Sums of absolute values of row elements give: A048163(n+1).
T(n,2n-1) = (-1)*A092552(n).
Cf. A008277, A212085, A182368, A185442, A193233, A193277, A193283, A266695, A266972.

P:= n-> add(Stirling2(n, k) *mul(q-i, i=0..k-1) *(q-k)^n, k=0..n):
T:= n-> seq(coeff(P(n), q, 2*n-k), k=0..2*n):
seq(T(n), n=1..8);

T(n,k) = [q^(2n-k)] Sum_{j=0..n} (q-j)^n * S2(n,j) * Product_{i=0..j-1} (q-i).

T(0,0)=1 prepended by Alois P. Heinz, May 03 2024

A193283 Triangle T(n,k), n>=1, 0<=k<=n*(n+1)/2, read by rows: row n gives the coefficients of the chromatic polynomial of the n X n X n triangular grid, highest powers first.

Original entry on oeis.org

1, 0, 1, -3, 2, 0, 1, -9, 32, -56, 48, -16, 0, 1, -18, 144, -672, 2016, -4031, 5368, -4584, 2272, -496, 0, 1, -30, 419, -3612, 21477, -93207, 304555, -761340, 1463473, -2152758, 2385118, -1929184, 1075936, -369824, 58976, 0

Offset: 1

Alois P. Heinz, Jul 20 2011

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.

			4 example graphs:                           o
                                           / \
                              o           o---o
                             / \         / \ / \
                    o       o---o       o---o---o
                   / \     / \ / \     / \ / \ / \
              o   o---o   o---o---o   o---o---o---o
  n:          1     2         3             4
  Vertices:   1     3         6            10
  Edges:      0     3         9            18
The 2 X 2 X 2 triangular grid is equal to the cycle graph C_3 with chromatic polynomial q^3 -3*q^2 +2*q => [1, -3, 2, 0].
Triangle T(n,k) begins:
  1,   0;
  1,  -3,   2,      0;
  1,  -9,  32,    -56,     48,     -16,       0;
  1, -18, 144,   -672,   2016,   -4031,    5368, ...
  1, -30, 419,  -3612,  21477,  -93207,  304555, ...
  1, -45, 965, -13115, 126720, -925528, 5303300, ...
  ...

Alois P. Heinz, Rows n = 1..13, flattened
Wikipedia, Chromatic Polynomial
Wikipedia, Triangular grid graph

Cf. A000217, A045943, A178435, A182797, A185442, A193233, A193277.

cp's OEIS Frontend

A182368 Triangle T(n,k), n>=1, 0<=k<=n^2, read by rows: row n gives the coefficients of the chromatic polynomial of the square grid graph G_(n,n), highest powers first.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A286017 Number of matchings in the n-Hanoi graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A137889 Number of directed Hamiltonian paths in the n-Hanoi graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A288490 Number of independent vertex sets and vertex covers in the n-Hanoi graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Extensions

A288796 Number of (undirected) paths in the n-Hanoi graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A288839 Triangle read by rows: coefficients of the chromatic polynomial of the n-Hanoi graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A193136 Numbers of spanning trees of the Hanoi graphs.

Views

Author

Keywords

Links

Crossrefs

A193277 Triangle T(n,k), n>=1, 0<=k<=(3+3^n)/2, read by rows: row n gives the coefficients of the chromatic polynomial of the Sierpinski gasket graph S_n, highest powers first.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A212084 Triangle T(n,k), n>=0, 0<=k<=2n, read by rows: row n gives the coefficients of the chromatic polynomial of the complete bipartite graph K_(n,n), highest powers first.

Views

Author

Keywords

Comments