1
$\begingroup$

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.$

$\endgroup$
3
  • $\begingroup$ 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$? $\endgroup$ – JMoravitz Aug 24 '20 at 18:47
  • $\begingroup$ @JMoravitz sorry I thought that term was well known. But you got the gist of it. The empty set also counts. $\endgroup$ – Fred Jefferson Aug 24 '20 at 18:49
  • $\begingroup$ @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. $\endgroup$ – Fred Jefferson Aug 24 '20 at 19:06
0
$\begingroup$

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<a_m$. If $a_1$ is odd, let $P_1=\{a_1\}$; otherwise, let $P_1=\{a_1-1,a_1\}$. Suppose that $1\le k<m$, 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<a_m$. 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.

$\endgroup$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.