IZhO 2015 Problem 5

Let $A_{n}$ be the set of partitions of the sequence $(1,2, \ldots, n)$ into several subsequences such that every two neighbouring terms of each subsequence have different parity, and let $B_{n}$ be the set of partitions of the sequence $(1,2, \ldots, n)$ into several subsequences such that all the terms of each subsequence have the same parity. 2

Prove that for every positive integer $n$ the sets $A_{n}$ and $B_{n+1}$ contain the same number of elements.