OFFSET
0,2
COMMENTS
The sequence encodes labeled digraph topologies as described by and counted in A000798.
The topologies are represented as ("binary") numbers where a nonzero bit means the respective subset of n is an element of the topology, where the subsets are again represented by the numbers whose nonzero bits correspond to the elements that are in the subset. (For the n-set, we can take n = {0, 1, ..., n-1}.)
Since the empty set (represented by 0) and the complete set (represented by 2^n-1) must be element of any topology on n, all numbers in the n-th row of the table have bit 0 and bit 2^n-1 set, i.e., they lie between 2^0 + 2^(2^n-1) and 2^(2^n) - 1 inclusive, except for row n = 0 where 0 and 2^n-1 are the same, so the row starts and ends with 2^0 = 2^(2^n-1) = 2^(2^n)-1 = 1. - M. F. Hasler, Jun 18 2026
FORMULA
T(n, 1) = 2^(2^n-1) + [n>0]; T(n, A000798(n)) = 2^2^n - 1. - M. F. Hasler, Jun 21 2026
EXAMPLE
Let a = 2, b = 4, c = 16, d = 256, ...
a(19) = 171 because we can map { }, a, ab, ac, abc to 1 + 2 + 8 + 32 + 128
Viewed as an array the table begins:
row n | topologies of n (represented as bitmask of the included subsets)
------+-----------------------------------------------------------------
0 | 1 -- Here, 1 = 2^0 represents tau = {{}}.
1 | 3 -- Here, 3 = 2^0 + 2^1 represents tau = {{}, {0}}.
2 | 9, 11, 13, 15 : Here 9 = 2^0 + 2^3 represents tau = {{}, {0,1}}.
3 | 129, 131, 133, 137, 139, 141, 143, 145, 153, 161, 163, 165, 171, 175, 177,
| 179, 187, 193, 195, 197, 205, 207, 209, 213, 221, 241, 243, 245, 255
4 | 32769, 32771, ..., 65535, where 32769 = 2^0 + 2^15 ~ {{}, {0,1,2,3}}.
... | ...
with respectively 1, 1, 4, 29, 355, ... (A000798) entries on each row.
PROG
(PARI)
is_A101620(n)={my(e, b); n%2 && hammingweight(1+e=exponent(n))==1 && !foreach(b=[k|k<-[1..e-1], bittest(n, k)], k, foreach(b, j, j<k||break; (bittest(n, bitand(k, j)) && bittest(n, bitor(k, j)))|| return))}
row(n)=select(is_A101620, [2^(2^n-1)..2^2^n-1]) \\ For illustration only -- not practical for n >= 5. - M. F. Hasler, Jun 18 2026
(Python)
import functools, itertools
@functools.cache
def bits(r: int) -> tuple[int]: # return tuple of indices of nonzero bits
bit_list = []
while r: bit_list.append((r & -r).bit_length() - 1); r &= r-1
return tuple(bit_list)
@functools.cache
def preorders(n: int) -> list[tuple[int]]:
if n < 2: return [(1, )if n else()]
matrices = []; N = n-1; bit_N = 1<<N
for P in preorders(N):
preds = [0] * N
for i, row in enumerate(P):
for j in bits(row): preds[j] |= 1 << i
for A in itertools.product((0, 1, 2, 3), repeat=N):
D_mask = sum([1 << i for i, a in enumerate(A) if a&1])
U_mask = sum([1 << i for i, a in enumerate(A) if a&2])
if any(a&1 and (p & ~D_mask or U_mask & ~r) or
a&2 and r & ~U_mask for a, r, p in zip(A, P, preds)): continue
P_new = [r|bit_N if a&1 else r for a, r in zip(A, P)]
P_new.append(U_mask | bit_N)
matrices.append(tuple(P_new))
return matrices
def topology(R):
T = 1; L = [0] * 2**(n := len(R))
for i, r in enumerate(R):
for s in range(b := 2**i): L[s|b] = L[s]|r; T |= 1 << L[s|b]
return T
@functools.cache
def A101620_row(n): return sorted(topology(P)for P in preorders(n)) # M. F. Hasler, Jun 19 2026
CROSSREFS
KEYWORD
nonn,tabf,changed
AUTHOR
Alford Arnold, Dec 10 2004
EXTENSIONS
Offset changed to 0 and more terms by M. F. Hasler, Jun 18 2026
STATUS
approved