On Problem 5 of IZhO 2015

Since we are asked to prove that two sets have the same number of elements, naturally we shall construct a bijection.

The first useful observation is to think of a partition in $A_n$ as consisting of integers ordered from left to right. We write the entries in every subsequence in increasing order.

Suppose that $1,2,\ldots,k-1$ have already been placed. When we come to $k$, there are only two possibilities:

(a) $k$ begins a new subsequence;

(b) $k$ is placed after the last element of an existing subsequence.

In the second case, the last element of that subsequence necessarily has parity opposite to that of $k$.

We shall build the corresponding partition in $B_{n+1}$ simultaneously through the construction of a tableau.

At the moment just before $k$ is inserted, arrange the blocks we have already constructed in a two-row tableau of the form

$$ \begin{array}{c|c|c|c||c} C_1&C_2&\cdots&C_r&\ast\\ D_1&D_2&\cdots&D_r&G \end{array}. $$

The top row consists of the current subsequences in $A_{k-1}$.

The bottom row consists of the blocks of a partition in $B_k$. Every $C_i$ is paired with the block $D_i$ directly below it, while one block $G$, which we will call distinguished, is left unpaired and placed under the symbol $\ast$.

We maintain the following two rules:

(a) all the elements of $D_i$ have the same parity as the last element of $C_i$;

(b) the distinguished block $G$ contains $k$.

Since $G$ belongs to $B_k$, all its elements consequently have the same parity as $k$.

We begin, before inserting $1$, with

$$ \begin{array}{c} \ast\ {1} \end{array}. $$

There are no blocks in the top row, and ${1}$ is the distinguished block.

We now insert $k$.

Case (a): $k$ begins a new subsequence

Suppose that $k$ starts a new block ${k}$ in the upper row.

We place this new block above the old distinguished block $G$, and introduce the new singleton ${k+1}$ as the distinguished block:

$$ \begin{array}{c||c} &\ast\ &G \end{array} \quad\longmapsto\quad \begin{array}{c||c} {k}&\ast\ G&{k+1} \end{array}. $$

The first rule is preserved, since every element of $G$ has the same parity as $k$. The new distinguished block ${k+1}$ clearly contains $k+1$, so the second rule is preserved as well.

Case (b): $k$ is appended to an existing subsequence

Suppose instead that $k$ is appended to some block $C$.

Let $D$ be the block immediately below $C$ in our tableau. Thus the elements of $D$ have the same parity as the last element of $C$.

Since $k$ may be appended to $C$, the last element of $C$ has parity opposite to that of $k$. But $k+1$ also has parity opposite to that of $k$. Hence

$$ D\cup{k+1} $$

is still monochromatic.

We now perform the following switch:

$$ \begin{array}{c||c} C&\ast\ D&G \end{array} \quad\longmapsto\quad \begin{array}{c||c} C\cup{k}&\ast\ G&D\cup{k+1} \end{array}. $$

In other words, we append $k$ to $C$, move the old distinguished block $G$ underneath it, and move $D$ into the distinguished position after adjoining $k+1$ to it.

The new last element of $C\cup{k}$ is $k$, and $G$ has the same parity as $k$. On the other hand, $D$ has parity opposite to $k$, which is precisely the parity of $k+1$, so $D\cup{k+1}$ is again a valid block of $B_{k+1}$.

All other columns of the tableau are left unchanged.

After inserting $1,2,\ldots,n$, the bottom row is a partition of

$$ {1,2,\ldots,n+1} $$

into monochromatic blocks. In other words, it is an element of $B_{n+1}$.

Thus the procedure defines a map

$$ \Phi:A_n\longrightarrow B_{n+1}. $$

As an example, let us apply the construction to

$$ \pi={(1,4,5,8),(2,3),(6,9),(7)}\in A_9. $$

After inserting $1,2,3,4$, the tableau is

$$ \begin{array}{c|c||c} (1,4)&(2,3)&\ast\ (2,4)&(3)&(1,5) \end{array}. $$

Now $5$ is appended to the first upper block. The block below it is $(2,4)$, while the distinguished block is $(1,5)$. We therefore switch them and append $6$ to the former:

$$ \begin{array}{c||c} (1,4)&\ast\ (2,4)&(1,5) \end{array} \quad\longmapsto\quad \begin{array}{c||c} (1,4,5)&\ast\ (1,5)&(2,4,6) \end{array}. $$

Continuing in the same way eventually gives $$ \Phi(\pi)

{(1,5,9),(2,4,6,10),(3),(7),(8)}, $$ which is indeed an element of $B_{10}$.

It remains to check that the map is a bijection.

Take an arbitrary partition

$$ \sigma\in B_{n+1}. $$

For $1\leq k\leq n+1$, let $\sigma_k$ denote the partition of ${1,\ldots,k}$ obtained by intersecting every block of $\sigma$ with ${1,\ldots,k}$ and deleting the empty intersections.

We reconstruct the upper row successively. Just before reconstructing the insertion of $k$, the bottom row is $\sigma_k$, and its distinguished block is forced: it is the block containing $k$.

Now consider what happens to $k+1$ when we pass from $\sigma_k$ to $\sigma_{k+1}$.

There are again two possibilities.

(a) If $k+1$ is the smallest element of its block in $\sigma$, then it appears in $\sigma_{k+1}$ as a new singleton block ${k+1}$. This can only have arisen from Case (a) above. Hence $k$ begins a new upper block, and the block of $\sigma_k$ containing $k$ is placed underneath it.

(b) Otherwise, $k+1$ joins a block $D$ already present in $\sigma_k$. Since $D$ has the parity of $k+1$, while the distinguished block containing $k$ has the parity of $k$, these are different blocks. By induction, $D$ lies underneath a unique upper block $C$. We therefore append $k$ to $C$ and reverse the switch from Case (b).

Thus at every stage there is exactly one possible inverse operation. Beginning with

$$ \begin{array}{c} \ast\ {1} \end{array} $$

and proceeding through $k=1,2,\ldots,n$, we recover a unique element of $A_n$.

Hence the construction is invertible, so $\Phi$ is a bijection. Therefore

$$ \boxed{|A_n|=|B_{n+1}|}. $$