Proving injectivity for a function between sets of different types of partitions

Question

I am attempting to solve the following problem:

Let $A$ be the set of partitions of $n$ with elements $(a_1, \dots, a_s)$ such that $a_i > a_{i+1}+a_{i+2}$ for all $i < s,$ taking $a_{s+1} = 0.$ Define $g_n = F_{n+2}-1$ and let $B$ be the set of partitions of $n$ as $b_1 \ge \dots \ge b_s$ such that $b_i \in \{g_n\}$ for all $i,$ and if $b_1 = g_k$ for some $k,$ then $g_1, \dots, g_k$ all appear as some $b_i.$ Prove $|A|=|B|.$

Attempt: Let $e_i$ be the vector with $1$ at position $i$ and $0$ elsewhere. If $b_1 = g_k,$ let $c=(c_k, \dots, c_1)$ count how many times $g_i$ appears. We calculate $f: B \to A$ as follows:

Let $c=(c_k,\dots,c_1), a=(0,\dots,0).$ While $c \ne 0,$ let $d_1 > \dots > d_k$ be the indices such that $c_{d_i} \ne 0.$ Replace $c, a$ with $c-(e_{d_1}+\dots+e_{d_k}), a+(g_{d_1} e_1 + \dots + g_{d_k} e_k)$ respectively. After the while loop ends, let $f(b)=a.$

Let $\sum a, \sum b, \sum c$ be the sum of the components of $a, b, c$ respectively. Since $\sum c$ decreases after every loop, the algorithm terminates and $f(b)$ is well-defined. Since $c_k g_k + \dots + c_1 g_1 + \sum a$ does not change after every iteration, is $\sum b$ at the start and $\sum a$ at the end, we have $\sum f(b) = \sum b = n,$ so $f(b)$ is also a partition of $n.$ Now $a = (g_k, \dots, g_1)$ after the first loop, which satisfies the condition $g_i > g_{i-1}+g_{i-2}$ since $g_i = F_{n+2}-1 = (F_{n+1}-1)+(F_n-1)+1 > g_{i-1}+g_{i-2}.$ Furthermore, after every iteration of the loop, the difference $a_i - (a_{i-1}+a_{i-2})$ changes by $0, g_{d_j}-g_{d_{j-1}} > 0,$ or $g_{d_j}-(g_{d_{j-1}}+g_{d_{j-2}}) > 0,$ so we have $a_i > a_{i-1} + a_{i-2}$ at the end and hence $f(b) \in A.$ Thus, $f: B \to A$ is well-defined.

In order to prove the injectivity of $f,$ it suffices to prove each loop iteration as a mapping $(c,a) \to (c',a')$ is injective, which would imply the mapping $(c,0) \to (0,a)$ that the while loop creates is injective. Indeed, if $f(b_1) = f(b_2) = a$ with $(c_1, 0), (c_2, 0)$ being sent to $(0, f(b_1)) = (0,a), (0, f(b_2)) = (0,a)$ respectively, then we have $(c_1, 0) = (c_2, 0) \Rightarrow c_1 = c_2 \Rightarrow b_1 = b_2.$

Suppose $d_1 > \dots > d_i, f_1 > \dots > f_j$ are the non-zero indices of $c_1, c_2$ respectively and $c_1 - (e_{d_1}+\dots+e_{d_i}) = c_2 - (e_{f_1}+\dots+e_{f_j}), a_1+g_{d_1}e_1 + \dots+ g_{d_i} e_i = a_2 + g_{f_1} e_1 + \dots + g_{f_j} e_j.$ If $x \ge 2$ is an entry of $c_1,$ it decreases by $1,$ so the corresponding entry in $c_2$ after $c_2$ is modified is also $x-1,$ which means it must've been $(x-1)+1 = x$ before since $x-1>0.$ Thus, if the values of two positions of $c_1, c_2$ differ, one is $1$ and the other is $0.$ However, if $c_1 = (1,0), a_1 = (3,1), c_2 = (0,1), a_2 = (4,1),$ then $(a_1, c_1), (a_2, c_2)$ both get sent to $((5,1), (0,0)).$ I can rule out this specific example by arguing that one of the pairs is illegal and could not have come from any choice of initial $c,$ but I have no idea on how to do this in general.

What should I do next in order to show $f$ is injective? Furthermore, since the problem I'm trying to prove is correct, injectivity would imply $f$ is secretly a bijection. But I have no clue on how to even start on the surjectivity of $f,$ so I just constructed a similar algorithm for $g: A \to B$ in the hopes of proving $g$ is injective too. If I can show $f$ is injective I will probably know how to show $g$ is.

Here is an example of $f, g$ in practice:

Let $n = 41, b = (12, 7, 7, 4, 4, 2, 2, 2, 1) \Rightarrow c = (1, 2, 2, 3, 1).$

$$((1, 2, 2, 3, 1), (0,0,0,0,0)) \to ((0, 1, 1, 2, 0), (12, 7, 4, 2, 1)) \to ((0, 0, 0, 1, 0), (19,11,6,2,1)) \to ((21,11,6,2,1),(0,0,0,0,0)),$$ so $f(b) = (21,11,6,2,1).$

Let $a = (21, 11, 6, 2, 1).$

$$((21,11,6,2,1),(0,0,0,0,0)) \to ((9,4,2,0,0), (1,1,1,1,1)) \to ((2,0,0,0,0),(1,2,2,2,1)) \to ((0,0,0,0,0),(1,2,2,3,1)),$$ so $g(a) = (12, 7, 7, 4, 4, 2, 2, 2, 1).$

Answer 1

Unfortunately, the map $f: B \to A$, although well-defined, is not injective.

Here is a counterexample with $n = 5$.

• Let $b_1 = (2, 1, 1, 1) \Rightarrow c = (1, 3).$ We have $((1, 3), (0,0)) \to ((0, 2), (2, 1)) \to ((0,0), (4,1)).$ so $f(b_1) = (4,1).$

• Let $b_2 = (2, 2, 1) \Rightarrow c = (2, 1).$ We have $((2, 1), (0,0)) \to ((1, 0), (2, 1)) \to ((0,0), (4,1)).$ so $f(b_2) = (4,1).$

---

Here is the way to prove $|A|=|B|$.

List one or more left-justified rows of initial contiguous Fibonacci numbers (cells) backwards, with the number of cells in non-increasing order. Call such a diagram "Fibonacci-Young diagram". Such a diagram is called "of order $n$" if the sum of all cells is $n$. Such a diagram is called "continual" if the number of cells in any row is at most one more than the number of cells in the row immediate below. Here is an illustration of a continual Fibonacci-Young diagram of order 41 with 5 columns and 11 rows.

$$\begin{array} {rrrrrr} \color{#d0d0d0}{\text{row sums}}& & & & & &\\ \color{#d0d0d0}{12}&5 &3 &2 &1 &1\\ \color{#d0d0d0}{7}&3 &2 &1 &1 &\\ \color{#d0d0d0}{4}&2 &1 &1 & &\\ \color{#d0d0d0}{4}&2 &1 &1 & &\\ \color{#d0d0d0}{4}&2 &1 &1 & &\\ \color{#d0d0d0}{2}&1 &1 & & &\\ \color{#d0d0d0}{2}&1 &1 & & &\\ \color{#d0d0d0}{2}&1 &1 & & &\\ \color{#d0d0d0}{1}&1 & & & &\\ \color{#d0d0d0}{1}&1 & & & &\\ \color{#d0d0d0}{1}&1 & & & &\\ \color{#d0d0d0}{1}&1 & & & &\\ &\color{#d0d0d0}{21} & \color{#d0d0d0}{11} &\color{#d0d0d0}{6} &\color{#d0d0d0}{2}&\color{#d0d0d0}{1} &\color{#d0d0d0}{\text{column sums}} \\ \end{array}$$

Let $C$ be the set of all continual Fibonacci-Yong diagrams of order $n$. Let $c\in C$ have $t$ rows and $s$ columns.

• Let $a_i$ be the sum of cells on $i$-th column of $c$. Verify that $a=(a_1, \cdots, a_s)\in A$. Use induction on $n$ to show the map $c\to a$ is a one-one correspondence between $C$ and $A$.
• Let $b_i$ be the sum of cells on $i$-th row of $c$. Verify that $b=(b_1, \cdots, b_t)\in B$. Use induction on $n$ to show the map $c\to b$ is a one-one correspondence between $C$ and $B$.