OFFSET
0,1
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.
LINKS
Nathan L. Skirrow, Table of n, a(n) for n = 0..59
Adam P. Goucher, Combinatorics I, Mathematical Olympiad Dark Arts (2005), 8-11.
Nathan L. Skirrow, dimensional_INT_enumerator.py (unreduced version of Python program below, that also finds equations for fixed n).
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.
EXAMPLE
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, ...
...
PROG
(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))*(d<dims-1)+')'*n+(')'*n+'*'+str(size**i))*bool(i))(*m[i], i))
boardCells=size**dims
matrindex=(lambda p: sum((e-sum(e>d 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<<k-1|1<<(k-1>>1)
A054247=lambda n: (1, 2, 6)[n] if n<3 else 1<<n**2-3|2**(n+3>>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)))) # Nathan L. Skirrow, May 29 2023
CROSSREFS
KEYWORD
tabl,nonn
AUTHOR
Nathan L. Skirrow, May 28 2023
STATUS
approved