Tag: algorithm

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