|
%I #11 Jul 03 2020 01:02:34
%S 1,2,2,4,18,4,8,162,162,8,16,1458,6570,1458,16,32,13122,266454,266454,
%T 13122,32,64,118098,10806354,48697686,10806354,118098,64,128,1062882,
%U 438264342,8900099046,8900099046,438264342,1062882,128,256,9565938,17774323650,1626602228838,7330125946050,1626602228838,17774323650,9565938,256
%N Array read by antidiagonals: T(m,n) = number of m-by-n hexagonal digraphs without oriented 3-cycles (for m >= 1, n >= 1).
%C More precisely, consider the directed graph with m*n vertices i,j
%C for 0<=i<m and 0<=j<n, with i,j adjacent to i,(j+1), (i+1),j, and
%C (i+1),(j+1) when those vertices exist. [There are m(n-1)+(m-1)n=(m-1)(n-1) arcs.]
%C Each arc between neighboring vertices is directed, one way or the
%C other. We are not allowed to have vertices u,v,w with u->v->w->u.
%D D. E. Knuth, The Art of Computer Programming, Section 7.2.2.3, in preparation.
%e The array begins:
%e 1, 2, 4, 8, 16, 32, 64, 128, 256, ...
%e 2, 18, 162, 1458, 13122, 118098, 1062882, 9565938, 86093442, ...
%e 4, 162, 6570, 266454, 10806354, 438264342, 17774323650, 720858511494, 29235261145554, ...
%e 8, 1458, 266454, 48697686, 8900099046, 1626602228838, 297281501943462, 54331839604996902, 9929809879071710886, ...
%e 16, 13122, 10806354, 8900099046, 7330125946050, 6037095692927862, 4972155285312413586, 4095069788483623200006, 3372701697814125393026946, ...
%e 32, 118098, 438264342, 1626602228838, 6037095692927862, 22406540276117433798, 83161353485088190184022, 308651430745402593036755238, 1145552611990801975992739211382, ...
%e 64, 1062882, 17774323650, 297281501943462, 4972155285312413586, 83161353485088190184022, 1390908038123039657933009250, 23263512314950157506021612227654, 389091866894670127046561452469612466, ...
%e 128, 9565938, 720858511494, 54331839604996902, 4095069788483623200006, 308651430745402593036755238, 23263512314950157506021612227654, 1753405140846978937849992172443469926, 132156724503381398420197323509979254463366, ...
%e 256, 86093442, 29235261145554, 9929809879071710886, 3372701697814125393026946, 1145552611990801975992739211382, 389091866894670127046561452469612466, 132156724503381398420197323509979254463366,
%e 44887599350675449085445484460546360180897201250, ...
%e ...
%e The initial antidiagonals are:
%e [1]
%e [2, 2]
%e [4, 18, 4]
%e [8, 162, 162, 8]
%e [16, 1458, 6570, 1458, 16]
%e [32, 13122, 266454, 266454, 13122, 32]
%e [64, 118098, 10806354, 48697686, 10806354, 118098, 64]
%e [128, 1062882, 438264342, 8900099046, 8900099046, 438264342, 1062882, 128]
%e [256, 9565938, 17774323650, 1626602228838, 7330125946050, 1626602228838, 17774323650, 9565938, 256]
%e [512, 86093442, 720858511494, 297281501943462, 6037095692927862, 6037095692927862, 297281501943462, 720858511494, 86093442, 512]
%e [1024, 774840978, 29235261145554, 54331839604996902, 4972155285312413586, 22406540276117433798, 4972155285312413586, 54331839604996902, 29235261145554, 774840978, 1024]
%e ...
%Y First two rows are A000079, A270369; main diagonal is A335685.
%K nonn,tabl
%O 1,2
%A _N. J. A. Sloane_, Jul 03 2020, based on an email from _Don Knuth_.
|
