A178435 -id:A178435 - cp's OEIS frontend

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.

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.

A360922 Array read by antidiagonals: T(m,n) is the number of acyclic orientations in the grid graph P_m X P_n.

Original entry on oeis.org

1, 2, 2, 4, 14, 4, 8, 98, 98, 8, 16, 686, 2398, 686, 16, 32, 4802, 58670, 58670, 4802, 32, 64, 33614, 1435414, 5015972, 1435414, 33614, 64, 128, 235298, 35118638, 428816558, 428816558, 35118638, 235298, 128, 256, 1647086, 859207558, 36659327366, 128091434266, 36659327366, 859207558, 1647086, 256

Offset: 1

Andrew Howroyd, Mar 07 2023

			Array begins:
=====================================================
m\n|  1     2        3           4              5 ...
---+-------------------------------------------------
1  |  1     2        4           8             16 ...
2  |  2    14       98         686           4802 ...
3  |  4    98     2398       58670        1435414 ...
4  |  8   686    58670     5015972      428816558 ...
5  | 16  4802  1435414   428816558   128091434266 ...
6  | 32 33614 35118638 36659327366 38261306901842 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..253 (first 22 antidiagonals).
Eric Weisstein's World of Mathematics, Grid Graph.
Wikipedia, Acyclic orientation.

Main diagonal is A080690.
Rows 1..2 are A000079(n-1), A109808.
Cf. A116469 (spanning trees), A178435, A207868 (unlabeled colorings).

T(m,n) = T(n,m).

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs