# bijection between parity preserving subsets and subsets without consecutive pairs

Define $$B_n$$ to be the set of subsets of $$\{1,\cdots, n\}$$ that have no consecutive elements and $$A_n$$ to be the set of subsets of $$\{1,\cdots, n\}$$ that are parity-preserving (this includes the empty set). Here's my attempt to define a bijection $$f : A_n \to B_n$$. Let $$P\in A_n.$$ We let $$f(P) = P',$$ where $$P'$$ is obtained by the following algorithm: If $$P$$ has no consecutive elements, we stop. Otherwise, if there is an odd-length consecutive block that ends, then all elements with even-numbered positions are removed, and the process repeats. If there is an even-length consecutive block that ends, then all elements with odd-numbered positions are removed, and the process repeats.

Here is a demonstration of the algorithm for the case $$\{1,2,5,6,7,8\}.$$ There is an even-length consecutive block $$\{1,2\}$$ that ends (in $$5$$), so we remove the $$1$$ as it's in an odd-numbered position. We repeat the process on $$\{2,5,6,7,8\}.$$ There is an even-length consecutive block $$\{5,6,7,8\},$$ so we remove the odd-numbered elements to obtain $$\{2,6,8\}.$$ Below is a mapping from $$A_5$$ to $$B_5$$.

$$\{5\}\mapsto \{5\}\\ \{1,4,5\} \mapsto \{1,5\}\\ \{3,4,5\}\mapsto \{3,5\}\\ \{1,2,5\}\mapsto \{2,5\}\\ \{1,2,3,4,5\}\mapsto \{1,3,5\}\\ \{\}\mapsto \{\}\\ \{1\}\mapsto \{1\}\\ \{3\}\mapsto \{3\}\\ \{1,2\}\mapsto \{2\}\\ \{1,4\}\mapsto \{1,4\}\\ \{3,4\}\mapsto \{4\}\\ \{1,2,3\}\mapsto \{1,3\}\\ \{1,2,3,4\}\mapsto \{2,4\}.$$

Now here's my attempt to define the inverse. Let $$B := \{\alpha_1,\cdots, \alpha_k\}\in B_n.$$ We define the result of $$f^{-1}(\{\alpha_1,\cdots, \alpha_k\})$$ for $$1\leq i \leq k.$$ If $$B$$ is parity preserving, we return $$B$$. If $$i$$ and $$\alpha_i$$ differ in parity, then insert $$\alpha_i - 1$$ directly before $$\alpha_i,$$ and repeat. Here is a demonstration for $$\{2,6,8\}.$$ $$2$$ is even but in position $$1$$, so we insert $$2-1 = 1$$ before it, obtaining $$\{1,2,6,8\}.$$ Similarly, we insert $$5$$ before $$6$$ to get $$\{1,2,5,6\}$$. And we insert $$7$$ before $$8$$ to obtain $$f^{-1}(\{2,6,8\}) = \{1,2,5,6,7,8\}.$$

Are these attempts correct? If not, what would be a correct bijection?

Edit: For clarification and completeness, here is the definition of a parity preserving subset of $$\{1,\cdots, n\}.$$ A parity-preserving subset of $$\{1,\cdots, n\}$$ is a subset $$\{\alpha_1,\cdots, \alpha_k\}$$ of $$\{1,\cdots, n\}$$ so that for every $$i, \alpha_i < \alpha_{i+1}$$ and $$\alpha_i \cong i \mod 2.$$

• What did "parity preserving" mean in this context? I'm unfamiliar with it. That if the elements in the subset were listed in order with indices starting from $1$, that the $i$'th element is always the same parity as $i$? – JMoravitz Aug 24 '20 at 18:47
• @JMoravitz sorry I thought that term was well known. But you got the gist of it. The empty set also counts. – Fred Jefferson Aug 24 '20 at 18:49
• @BrianM.Scott sorry for that typo. But as you can see from my mapping from $A_5$ to $B_5$, my idea is very different from that error. – Fred Jefferson Aug 24 '20 at 19:06

Yes, what you have appears to work, but I would start with your second algorithm: it’s actually a bit simpler, since it works one element at a time.

Define $$g:B_n\to A_n$$ as follows. Let $$P=\{a_1,\ldots,a_m\}$$ have no consecutive members, where $$a_1<\ldots. If $$a_1$$ is odd, let $$P_1=\{a_1\}$$; otherwise, let $$P_1=\{a_1-1,a_1\}$$. Suppose that $$1\le k, and we’ve defined $$P_k$$. If $$P_k\cup\{a_{k+1}\}$$ is parity-preserving, let $$P_{k+1}=P_k\cup\{a_{k+1}\}$$; otherwise, let $$P_{k+1}=P_k\cup\{a_{k+1}-1,a_{k+1}\}$$. Then $$g(P)=P_m$$ is parity-preserving. This really is just your insertion algorithm.

Now let $$P=\{a_1,\ldots,a_m\}$$ be parity-preserving, where $$a_1<\ldots. Partition $$P$$ into maximal subsets of consecutive integers.

For instance, $$\{1,2,5,6,7,8,11,14,15,16\}$$ is partitioned into the sets $$\{1,2\}$$, $$\{5,6,7,8\}$$, $$\{11\}$$, and $$\{14,15,16\}$$.

If $$S$$ is one of these sets, let $$S'=\{k\in S:k\equiv\max S\pmod2\}$$; this has the effect of omitting every second member of $$S$$ counting down from $$\max S$$. Let $$f(P)$$ be the union of the sets $$S'$$; then $$f(P)$$ has no consecutive elements.

In the example we have $$\{1,2\}'=\{2\}$$, $$\{5,6,7,8\}'=\{6,8\}$$, $$\{11\}'=\{11\}$$, $$\{14,15,16\}'=\{14,16\}$$, and $$f(P)=\{2,6,8,11,14,16\}$$.

It’s not too hard to check now that $$f$$ and $$g$$ are mutual inverses and hence bijections.