cp's OEIS Frontend

Let Q(n) be the standard n-dimensional hypercube graph. Two vertices x and y in Q(n) are called "opposites" if they differ in every bit. A "pairs-only half-set" in Q(n) is a subset S of size 2^(n-1) such that for every pair of opposite vertices, S either contains both of them or contains neither. By distinct half sets, we mean that any set is being counted along with its complement only once.

We say S is "equitable" if all vertices in S have the same number of neighbors inside S, and all vertices in the complement of S have the same number of neighbors inside that complement.

Define a(n) as the number of pairs-only half-sets S that are equitable and admit an automorphism of Q(n) (a combination of bitwise XOR by a mask and a permutation of the n coordinates) mapping S onto its complement. In this context, an "n-bit mask", m, means a fixed n-bit binary string. To "bitwise XOR by a mask" means: for each vertex x (which is itself an n-bit string), we look at the bits of m. Wherever m has a 1 bit, we flip (invert) that corresponding bit in x; wherever m has a 0 bit, we leave that bit in x unchanged. Thus, an automorphism of Q(n) is any combination of: 1) Bitwise XOR by an n-bit mask (flip certain bits in every vertex), and 2) A permutation of the n coordinate positions (re-label the bits in each vertex).

A specialized C++ program enumerates all distinct pairs-only half-sets, for Q(1) up to Q(6), checks which are equitable, and then tests whether they can be mapped to their complements by such an automorphism. It also checks for isomorphism using the degree sequence (which is not sufficient for isomorphism), but since a set passes the test through the existence of an automorphism, the isomorphism follows as a by-product.

The equivalence classes are defined based on a problem described on page 10 of the paper "On super-strong Wilf equivalence classes of permutations" by Ioannis Michos, Christina Savvidou, and Demetris Hadjiloucas, The Electronic Journal of Combinatorics 25 (2) (2018). For each permutation of n elements, distances are calculated as the absolute difference in positions for each pair of elements. For each element in a permutation of S_n, that is less than or equal to n-1, one calculates the absolute difference with every other element that comes after it. Permutations are then grouped into equivalence classes when their multisets of distances match. The sequence was generated using a Python as well as a C++ program. The program enumerates all permutations of n elements and classifies them into these equivalence classes.