For $A_3$, I count 7 elements: \[ \begin{array}{c} (1), \ (2), \ (3) \\ (1,2), \ (3) \\ (2,1), \ (3) \\ (2,3), \ (1) \\ (3,2), \ (1) \\ (1,2,3) \\ (3,2,1) \end{array} \] However, for $B_4$, I count 9 elements: \[ \begin{array}{c} (1), \ (2), \ (3), \ (4) \\ (1,3), \ (2), \ (4) \\ (3,1), \ (2), \ (4) \\ (2,4), \ (1), \ (3) \\ (4,2), \ (1), \ (3) \\ (1,3), \ (2,4) \\ (3,1), \ (2,4) \\ (1,3), \ (4,2) \\ (3,1), \ (4,2) \end{array} \] Can anyone say where I'm going wrong?

I believe there is an implicit assumption that the elements of each subsequence must be in increasing order.

For each partition $\pi$ of $\{1,2,\ldots,n\}$, with the elements within each block written in ascending order, denote by $k(\pi)$ the number of blocks of $\pi$ ending in an even number and by $\ell(\pi)$ the number of blocks of $\pi$ ending in an odd number. Also denote $\displaystyle f_n(x,y) = \sum_{\pi \in A_n} x^{k(\pi)}y^{\ell(\pi)}$ and $\displaystyle g_n(x,y) = \sum_{\pi \in B_n} x^{k(\pi)}y^{\ell(\pi)}$. We will have $|A_n| = f_n(1,1)$. For example \[\begin{array} {l} f_1(x,y) = y \\ f_2(x,y) = x(y+1) \\ f_3(x,y) = y(xy+y+x+1) \\ f_4(x,y) = x(xy^2+y^2+3xy+3y+x+1) \\ \end{array}\] A moment of reflection will show us that \[f_{n+1}(x,y) = y\left (f_n(x,y) + \dfrac {\textrm{d}}{\textrm{d}x}f_n(x,y)\right ) \textrm{ for even } n,\] \[f_{n+1}(x,y) = x\left (f_n(x,y) + \dfrac {\textrm{d}}{\textrm{d}y}f_n(x,y)\right ) \textrm{ for \ odd } n.\] This comes from considering where the element $n+1$ may go, and how this affects the number of blocks. We will also have $|B_n| = g_n(1,1)$. For example \[\begin{array} {l} g_1(x,y) = y \\ g_2(x,y) = xy \\ g_3(x,y) = xy(y+1) \\ g_4(x,y) = xy(xy+y+x+1) \\ g_5(x,y) = xy(xy^2+y^2+3xy+3y+x+1) \\ \end{array}\] Another moment of reflection will show us that \[g_{n+1}(x,y) = y\left (g_n(x,y) + \dfrac {\textrm{d}}{\textrm{d}y}g_n(x,y)\right ) \textrm{ for even } n,\] \[g_{n+1}(x,y) = x\left (g_n(x,y) + \dfrac {\textrm{d}}{\textrm{d}x}g_n(x,y)\right ) \textrm{ for \ odd } n.\] This also comes from considering where the element $n+1$ may go, and how this affects the number of blocks. It is not hard to check that $g_{n+1}(x,y) = yf_n(x,y)$ for even $n$ and that $g_{n+1}(x,y) = xf_n(x,y)$ for odd $n$. This is seen to hold true for small values of $n$. Henceforth, for even $n$, $g_{n+1}(x,y) = y\left (g_n(x,y) + \dfrac {\textrm{d}}{\textrm{d}y}g_n(x,y)\right ) = yxf_{n-1}(x,y) + yx\dfrac {\textrm{d}}{\textrm{d}y}f_{n-1}(x,y)$ by the induction step on $g_{n}(x,y) = xf_{n-1}(x,y)$, while $yf_n(x,y) = yx\left (f_{n-1}(x,y) + \dfrac {\textrm{d}}{\textrm{d}y}f_{n-1}(x,y)\right )$. Similar computation holds for odd $n$. So $g_{n+1}(1,1) = f_n(1,1)$ in all cases, and so $\boxed{|B_{n+1}| = |A_n|}$. Once the idea of the proof arises, the problem becomes almost trivial. The sequence $(|B_n|)_{n\geq 0}$ that starts $1,1,1,2,4,10,25,75,225,\ldots$ is sequence A124419 from Sloane's Encyclopedia of Integer Sequences https://oeis.org/, listing the number of partitions of the set $\{1,2,\ldots,n\}$ having no blocks that contain both odd and even entries. It seems no closed form is available.

In fact a closed form (in terms of Bell numbers) is straightforward: we are independently choosing an arbitrary set partition of the odd and even numbers, so it is $B_{\lfloor n/2\rfloor}\cdot B_{\lceil n/2\rceil}$.

We may directly construct a bijection between $A_n$ and $B_{n+1}$. We may view each partition in $A_n$ as a collection of chains (e.g. in the example in the question, we have $1\rightarrow 4\rightarrow 5\rightarrow 8$, $2\rightarrow 3$, $6\rightarrow 9$). Now, consider each individual link $a\rightarrow b$ in the chains ($1\rightarrow 4,4\rightarrow 5,5\rightarrow 8, 2\rightarrow 3,6\rightarrow 9$) and replace it with $a\rightarrow b+1$ (so we get $1\rightarrow 5,4\rightarrow 6,5\rightarrow 9,2\rightarrow 4,6\rightarrow 10$). Combining these into chains, we get an element of $B_{n+1}$ ($1\rightarrow5\rightarrow 9$, $2\rightarrow4\rightarrow 6\rightarrow 10$, every other element is on its own). It's not hard to check that this has a bijection (e.g. by explicitly constructing an inverse).

IZHO 2015/5 wrote: Let $ A_n $ be the set of partitions of the sequence $ 1,2,..., n $ into several subsequences such that every two neighbouring terms of each subsequence have different parity,and $ B_n $ the set of partitions of the sequence $ 1,2,..., n $ into several subsequences such that all the terms of each subsequence have the same parity ( for example,the partition $ {(1,4,5,8),(2,3),(6,9),(7)} $ is an element of $ A_9 $,and the partition $ {(1,3,5),(2,4),(6)} $ is an element of $ B_6 $ ). Prove that for every positive integer $ n $ the sets $ A_n $ and $ B_{n+1} $ contain the same number of elements. Basically the same as @above. As it seems really magical, I'll outline the motivation here. Motivation. This is more noticeable when we're directly doing examples for $n = 4$. (As there are only $4$ partitions for $A_3$ and $B_4$, and it's hard to find the suitable bijection just using $n = 3$.) For $n = 4$, we have \begin{tabular}{|c|c|} \hline $A_4$ & $B_5$ \\ \hline $1, 2, 3, 4$ & $1, 2, 3, 4, 5$ \\ \hline $1 \to 2, 3, 4$ & $1 \to 3, 2, 4, 5$ \\ \hline $1 \to 4, 2, 3$ & $1 \to 5, 2, 3, 4$ \\ \hline $2 \to 3, 1, 4$ & $3 \to 5, 1, 2, 4$ \\ \hline $3 \to 4, 1, 2$ & $2 \to 4, 1, 3, 5$ \\ \hline $1 \to 2, 3 \to 4$ & $1 \to 3, 2 \to 4, 5$ \\ \hline $1 \to 4, 2 \to 3$ & $1 \to 5, 2 \to 4, 3$ \\ \hline $1 \to 2 \to 3, 4$ & $3 \to 5, 2 \to 4, 1$ \\ \hline $2 \to 3 \to 4, 1$ & $1 \to 3 \to 5, 2, 4$ \\ \hline $1 \to 2 \to 3 \to 4$ & $1 \to 3 \to 5, 2 \to 4$ \\ \hline \end{tabular}It would took time to notice that the number of partition that has $i$ arrows for both $A_4$ and $B_5$ are the same for $i = 0,1, 2, 3$. So we have a rough idea on where the bijection should send some of the elements too. Looking at the ones which has one arrow, we have \begin{align*} A_4 &: 1 \to 2, 1 \to 4, 2 \to 3, 3 \to 4 \\ B_5 &: 1 \to 3, 1 \to 5, 2 \to 4, 3 \to 5 \end{align*}and once you notice this, it's easy to state the bijection. Solution. We claim that there exists a bijection $f : A_n \to B_{n + 1}$, which by definition of bijection implies $|A_n| = |B_{n + 1}|$. Take any partition $\sigma \in A_n$. View $\sigma$ as a collection of chains, i.e. connect every two consecutive terms in a subsequence with a chain. As an example, $(1, 2, 5), (3, 6), 4$ could be written as $1 \to 2 \to 5, 3 \to 6$. Now, for every chain $a \to b$, we map them to $B_{n + 1}$, where the chains are defined by $a \to b + 1$. As an example, in the previous example, it will be mapped to $1 \to 3 \to 7, 2 \to 6$ which corresponds to $(1,3,7),(2,6), (4),(5)$. First of all, this map is allowed because the largest number in $A_n$ is $n$ and the largest number in $B_n$ is $n + 1$. Furthermore, as every chain $a \to b$ before satisfies $a,b$ are different in parity, and by our mapping condition, $a \to b + 1$ is now of the same parity -- and therefore satisfy the condition of $B_{n + 1}$. To check that this is a bijection, we could just construct the inverse function which maps every chain $a \to b$ on a partition $\sigma' \in B_{n + 1}$ to $a \to b - 1$. It's immediate to check that this satisfies the requirement of $A_n$, as the elements in every chain are now different in parity, and the largest element is $(n + 1) - 1 = n$.

This problem use famous theorem about set partition; Quote: The set partition of $[n]$ into k parts is bijectively correspond to placement of $n-k$ rooks on 'stair' shape board of size $n-1$, which rooks can't attack each other. See this link for the proof(claim and comment of second solution). By this theorem, we can find quite easy solution to our original Zhautykov problem. Solution. Let's color the stair board of size n into chessboard pattern, such that longest diagonal is black. Then by above link's bijection, set partition of $B_{n+1}$ correspond to non-attacking rook placement which is rooks can only in the white cells. Now cut out longest diagonal and make board size $n-1$, and change color of each cell. Then this placement(non-attacking rooks only in black cells) is correspond to set partition of $A_n$, again by above link's bijection. $\square$ You can easily see this bijection is essentially same to the bijection in #7, and if set partition $A \in A_n$ and $B \in B_{n+1}$ is correspond to each other, $B$ has $1$ more block than $A$.