A335684 Array read by antidiagonals: T(m,n) = number of m-by-n hexagonal digraphs without oriented 3-cycles (for m >= 1, n >= 1).

1, 2, 2, 4, 18, 4, 8, 162, 162, 8, 16, 1458, 6570, 1458, 16, 32, 13122, 266454, 266454, 13122, 32, 64, 118098, 10806354, 48697686, 10806354, 118098, 64, 128, 1062882, 438264342, 8900099046, 8900099046, 438264342, 1062882, 128, 256, 9565938, 17774323650, 1626602228838, 7330125946050, 1626602228838, 17774323650, 9565938, 256

Offset

1,2

Comments

More precisely, consider the directed graph with m*n vertices i,j

for 0<=i<m and 0<=j<n, with i,j adjacent to i,(j+1), (i+1),j, and

(i+1),(j+1) when those vertices exist. [There are m(n-1)+(m-1)n=(m-1)(n-1) arcs.]

Each arc between neighboring vertices is directed, one way or the

other. We are not allowed to have vertices u,v,w with u->v->w->u.

References

D. E. Knuth, The Art of Computer Programming, Section 7.2.2.3, in preparation.

Links

Table of n, a(n) for n=1..45.

Example

The array begins:
1, 2, 4, 8, 16, 32, 64, 128, 256, ...
2, 18, 162, 1458, 13122, 118098, 1062882, 9565938, 86093442, ...
4, 162, 6570, 266454, 10806354, 438264342, 17774323650, 720858511494, 29235261145554, ...
8, 1458, 266454, 48697686, 8900099046, 1626602228838, 297281501943462, 54331839604996902, 9929809879071710886, ...
16, 13122, 10806354, 8900099046, 7330125946050, 6037095692927862, 4972155285312413586, 4095069788483623200006, 3372701697814125393026946, ...
32, 118098, 438264342, 1626602228838, 6037095692927862, 22406540276117433798, 83161353485088190184022, 308651430745402593036755238, 1145552611990801975992739211382, ...
64, 1062882, 17774323650, 297281501943462, 4972155285312413586, 83161353485088190184022, 1390908038123039657933009250, 23263512314950157506021612227654, 389091866894670127046561452469612466, ...
128, 9565938, 720858511494, 54331839604996902, 4095069788483623200006, 308651430745402593036755238, 23263512314950157506021612227654, 1753405140846978937849992172443469926, 132156724503381398420197323509979254463366, ...
256, 86093442, 29235261145554, 9929809879071710886, 3372701697814125393026946, 1145552611990801975992739211382, 389091866894670127046561452469612466, 132156724503381398420197323509979254463366,
44887599350675449085445484460546360180897201250, ...
...
The initial antidiagonals are:
[1]
[2, 2]
[4, 18, 4]
[8, 162, 162, 8]
[16, 1458, 6570, 1458, 16]
[32, 13122, 266454, 266454, 13122, 32]
[64, 118098, 10806354, 48697686, 10806354, 118098, 64]
[128, 1062882, 438264342, 8900099046, 8900099046, 438264342, 1062882, 128]
[256, 9565938, 17774323650, 1626602228838, 7330125946050, 1626602228838, 17774323650, 9565938, 256]
[512, 86093442, 720858511494, 297281501943462, 6037095692927862, 6037095692927862, 297281501943462, 720858511494, 86093442, 512]
[1024, 774840978, 29235261145554, 54331839604996902, 4972155285312413586, 22406540276117433798, 4972155285312413586, 54331839604996902, 29235261145554, 774840978, 1024]
...

Crossrefs

First two rows are A000079, A270369; main diagonal is A335685.

Sequence in context: A367681 A376085 A232161 * A052628 A006853 A120417

Adjacent sequences: A335681 A335682 A335683 * A335685 A335686 A335687

Keyword

nonn,tabl

Author

N. J. A. Sloane, Jul 03 2020, based on an email from Don Knuth.

Status

approved