A361870 Array read by downward antidiagonals: A(n,k) is the number of nonequivalent 2-colorings of the cells of an n-dimensional hypercube with edges k cells long under action of symmetry.

2, 2, 1, 2, 2, 1, 2, 3, 2, 1, 2, 6, 6, 2, 1, 2, 10, 102, 22, 2, 1, 2, 20, 8548, 2852288, 402, 2, 1, 2, 36, 4211744, 384307306807269376, 6296489398464125698304, 1228158, 2, 1

Offset: 0

Author

Natalia L. Skirrow, May 28 2023

Keywords

• tabl
• nonn

Comments

A(0,0) = 2 by the convention that 0^0 = 1, in spirit with A003992.

A(n,2) = A000616(n), because the Boolean functions' truth tables are n-dimensional edge-length-2 hypercubes, and are considered equivalent under action of input permutation (transposition of dimensions) and applications of NOT to inputs (reflection in dimensions) that compose for the hypercube's symmetry group.

A(n,3) is the number of transitions in an isotropic non-totalistic Life-like cellular automaton with an n-dimensional Moore neighborhood.

A(n,k) ~ 2^(k^n)/(n!*2^n) for large k where n >= 1, and large n where k >= 2, and converges from above. Proof: When computing it with the Pólya enumeration theorem (for each action, count colorings of cycles under it instead of cells, average result over actions), the asymptotic form describes the number of states contributed by the identity action. Over k, the values contributed by the other actions are at most O(2^(k^n/2)), so the proportion that they contribute may be made arbitrarily small by choosing a large enough n. Over n, there are no more than n!*2^n such non-identity actions, assuming that they are all of order 2 (as an upper bound). Each one may have no more than a hyperplane (2^k^(n-1)) of fixed points, which (if it is of order 2) will multiply its colorings by 2^(k^(n-1)/2). The ratio of the identity term to the others is at least O(2^k^n/(n!*2^n*2^(k^(n-1)/2))), and its base-2 logarithm, by Stirling's approximation, is O(k^n-n*log(n)-n-k^(n-1)/2), so the 2^(k^n) term will dominate.

A(1,k) is the only row >= 1 that is linear-recurrent over k (and has a rational generating function), all other nontrivial rows and columns grow faster than any linear-recurrent function.

A000120(A(n,k)) is eventually periodic over k if and only if n <= 2.

Examples

			n\k|0, 1,       2,                      3,                  4,       5,  6, 7, ...
---+------------------------------------------------------------------------------
 0 |2, 2,       2,                      2,                  2,       2,  2, 2, ...
 1 |1, 2,       3,                      6,                 10,      20, 36, ...
 2 |1, 2,       6,                    102,               8548, 4211744, ...
 3 |1, 2,      22,                2852288, 384307306807269376, ...
 4 |1, 2,     402, 6296489398464125698304, ...
 5 |1, 2, 1228158, ...
 6 |1, 2, ...
 7 |1, ...
...
		

Links

• Natalia L. Skirrow, Table of n, a(n) for n = 0..59
• Adam P. Goucher, Combinatorics I, Mathematical Olympiad Dark Arts (2005), 8-11.
• LifeWiki, Isotropic non-totalistic rule, Pólya enumeration theorem.
• Natalia L. Skirrow, dimensional_INT_enumerator.py (unreduced version of Python program below, that also finds equations for fixed n).

Crossrefs

Cf. A000616, A005418, A054247, A003992.

Programs

Python

from functools import reduce
from itertools import accumulate
from math import isqrt,lcm,factorial as fact
tap=lambda f,*i:tuple(map(f,*i))
redumulate=lambda f,l,i=None: accumulate(l,f,initial=i)
expumulate=lambda f,l: lambda i: accumulate(range(l),lambda x,i: f(x),initial=i)
factorise=lambda m: tuple(filter(lambda n: not m%n,range(1,m//2+1)))+(m,)
def cycleLengths(dims,size):
    convert=(lambda m,i,a: (lambda d,n,i: ('('*bool(i)+str(size)+'+~(')*n+a+("//"+str(size**d))*bool(d)+('%'+str(size))*(dd for d,m in p[:i]))*fact(len(p)+~i)*2**dims+2**i*n for i,(e,n) in enumerate(p)))
    matrices=sorted((tuple((j,n>>i&1) for i,j in enumerate((lambda t: tuple(reduce(lambda e,n: e+(e>=n),t[i-1::-1],e)%dims for i,e in enumerate(t)))(tuple(a[0]%(dims-i) for i,a in enumerate(redumulate(lambda m,i: divmod(m[0],i),range(dims,1,-1),(m,0))))))) for m in range(fact(dims)) for n in range(2**dims)),key=matrindex) if dims else []
    exps=tap(lambda m: tap(matrindex,expumulate(lambda i: tap(lambda j: (lambda k,l: (k,l^j[1]))(*i[j[0]]),m),lcm(4,fact(dims)))(matrices[0])),matrices)
    lambdas=tap(lambda m: eval("lambda s: ["+','.join('s['+str(eval('+'.join(map(lambda i: convert(m,i,str(j)),range(dims)))))+']' for j in range(boardCells))+']'),matrices)
    test=list(range(1,boardCells+1))
    factors=tap(lambda e: factorise(e[1:].index(0)+1),exps)
    subperiods=tuple(tuple(sum(map(int._eq_,test,lambdas[exps[i][a]](test))) for a in f) for i,f in enumerate(factors))
    return((lambda t: tap(lambda t: reduce(lambda r,t: r+((t[0],t[1]-sum(i[1] for i in r if not t[0]%i[0])),),t,()),t))(tap(lambda a,b: tuple(zip(a,b)),factors,subperiods)))
specific=(lambda cycles: int(bool(cycles) and sum(2**sum(i[1]//i[0] for i in c) for c in cycles)//len(cycles)))
line=lambda k: (1,2)[k] if k<2 else 1<>1)
A054247=lambda n: (1,2,6)[n] if n<3 else 1<>1)+3**(~n&1)<<(n**2-5>>1)|1<<(n**2-5>>2)
cube=lambda k: (2**k**3+3*2**((k+1>>1)*k**2)+9*2**((k**2+1>>1)*k)+2**(k**3+1>>1)+6*2**(k**2*(k+1)>>1)+6*2**((k**2+3)//4*k)+6*2**((k**2+1>>1)*k+1>>1)+8*2**(k*(k**2+2)//3)+8*2**(k*(k**2+2)//3+1>>1))//48
tesseract=lambda k: (2**k**4+4*2**((k+1>>1)*k**3)+30*2**((k**2+1>>1)*k**2)+16*2**((k**3+1>>1)*k)+2**(k**4+1>>1)+12*2**(k**3*(k+1)>>1)+12*2**((k**2+3>>2)*k**2)+48*2**(((k**2+1>>1)*k+1>>1)*k)+12*2**((k**2+1>>1)*k**2+1>>1)+32*2**(k**2*(k**2+2)//3)+32*2**((k+1>>1)*k*(k**2+2)//3)+32*2**((k*(k**2-1)//3+k+1>>1)*k)+32*2**(k**2*(k**2+2)//3+1>>1)+12*2**(k**2*(k**2+1)>>1)+12*2**(k**4+3>>2)+48*2**(k*(k**3+k+2)>>2)+48*2**(k**4+7>>3))//384
nonequivalents=lambda n,k: (lambda k: 2,line,A054247,cube,tesseract)[n](k) if n<5 else 2**k if k<2 else specific(cycleLengths(n,k))
A002262=(lambda n: (lambda s: (lambda o: (o,s-o))(n-s*(s+1)//2))(isqrt((n<<3)+1)-1>>1))
print(tuple(map(lambda n: nonequivalents(*A002262(n)),range(28)))) # Natalia L. Skirrow, May 29 2023

Formula

Where an expression can be simplified by dividing a power of 2's coefficient by 2 and incrementing its exponent by 1, it is left as-is, so that the 2^ can be changed to c^ for general c-colorings.

A(n,2) = A000616(n).

A(0,k) = 2.

Herein, c(x) denotes the ceiling function.

A(1,k) = A005418(k+1) = (2^k + 2^c(k/2))/2.

A(2,k) = A054247(k) = (2^k^2 + 2*2^(k*(k+1)/2) + 2*2^(c(k/2)*k) + 2^c(k^2/2) + 2*2^c(k^2/4))/8.

A(3,k) = (2^k^3 + 3*2^(c(k/2)*k^2) + 9*2^(c(k^2/2)*k) + 2^c(k^3/2) + 6*2^(k^2*(k+1)/2) + 6*2^(c(k^2/4)*k) + 6*2^c(c(k^2/2)*k/2) + 8*2^(k*(k^2+2)/3) + 8*2^c(k*(k^2+2)/6))/48.

A(4,k) = (2^k^4 + 4*2^(c(k/2)*k^3) + 30*2^(c(k^2/2)*k^2) + 16*2^(c(k^3/2)*k) + 2^c(k^4/2) + 12*2^(k^3*(k+1)/2) + 12*2^(c(k^2/4)*k^2) + 48*2^(c(c(k^2/2)*k/2)*k) + 12*2^c((c(k^2/2)*k^2)/2) + 32*2^(k^2*(k^2+2)/3) + 32*2^(c(k/2)*k*(k^2+2)/3) + 32*2^(c((k*(k^2-1)/3+k)/2)*k) + 32*2^c((k^2*(k^2+2)/3)/2) + 12*2^(k^2*(k^2+1)/2) + 12*2^c(k^4/4) + 48*2^(k*(k^3+k+2)/4) + 48*2^c(k^4/8))/384.