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

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,2

Links

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.

Formula

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

Example

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 ...
  ...

Crossrefs

Main diagonal is A080690.

Rows 1..2 are A000079(n-1), A109808.

Cf. A116469 (spanning trees), A178435, A207868 (unlabeled colorings).

Sequence in context: A248238 A268009 A263224 * A267957 A204978 A204705

Adjacent sequences: A360919 A360920 A360921 * A360923 A360924 A360925

Keyword

nonn,tabl

Author

Andrew Howroyd, Mar 07 2023

Status

approved