# Counting solutions to equations involving partitions

This is a problem that has come up in my research and seems to be true from numerical tests via Mathematica. It should be provable in general, but I have been unable to show it so far. It would be greatly appreciated if someone could help with a proof or a method in order to solve such problems.

Given integer partitions $\rho$ and $\mu$ and a non-zero natural number $H$ such that $\ell(\mu)\leqslant H$ and $\ell(\rho)<H$, I am interested in two statistics:

1. For how many $x \in \{1,\dots,\ell(\mu)\}$ is it the case that $\rho^\vee (\mu(x))=x$?

2. For how many $x \in \{1,\dots,H\}$ is it the case that $\mu^\vee(\rho(x)+1)=x-1$?

My claim is that when $\ell(\mu)=H$ the first statistic is equal to the second statistic, while when $\ell(\mu)<H$ the second statistic is one greater than the first.

To be clear on notation

$\mu(n)$ is the $n^{\text{th}}$ part of $\mu$ and is defined to be zero if $n\neq 1,\dots,\ell(\mu)$.

$\mu^\vee$ is the dual of the partition $\mu$ defined by $\mu^\vee(x):=|\{y|\mu(y)\geqslant x\}|$.

$\ell(\mu)$ is the length of $\mu$ and obeys $\ell(\mu)=\mu^\vee(1)$.

• Partitions of what? – Paul Sinclair Apr 9 '18 at 23:47
• The two partitions are completely arbitrary except for the condition on their lengths. They need not even be partitions of the same number. – Alec B-G Apr 10 '18 at 7:18
• The claim needs to hold for all partitions. A single counterexample would be an answer. I am counting the number of possible solutions to $\rho^\vee(\mu(x))=x$ for $x$ in the domain $\{1,\dots,\ell(\mu)\}$, but I am not saying that the equation holds for every $x$. It may only hold for $x=2$ for example. However if this is the case then given $\ell(\mu)=H$ there is only one solution to equation 2. – Alec B-G Apr 10 '18 at 10:09
• For example if $\mu=(2,1)$ and $\rho=(2,1)$ and $H>2$ then we have solutions to 1 $\rho^\vee(\mu(1))=1$ and $\rho^\vee(\mu(2))=2$. Solutions to 2 are $\mu^\vee(\rho(1)+1)=0$, $\mu^\vee(\rho(2)+1)=1$ and $\mu^\vee(\rho(3)+1)=2$. – Alec B-G Apr 10 '18 at 10:13

$\rho^\vee (a)=x$ means $|\{y\mid\rho(y)\geqslant a\}| = x$, which given that the parts are in descending order means that $\rho(x+1) < a \leqslant \rho(x)$.

So statistic 1 is $\chi_{\rho, \mu} =|\{ x \mid \rho(x+1) < \mu(x) \leqslant \rho(x) \}|$ and statistic 2 is $\psi_{\rho, \mu} = |\{ x \mid \mu(x) < \rho(x)+1 \leqslant \mu(x-1) \}|$, which since we're dealing with integers is equivalent to $\psi_{\rho, \mu} = |\{ x \mid \mu(x) \leqslant \rho(x) < \mu(x-1) \}|$

In fact, since we're dealing with integers we can carefully add some small offsets and write $$\chi_{\rho, \mu} =\left|\left\{ x \mid \rho(x+1) + \tfrac12 < \mu(x) < \rho(x) + \tfrac12 \right\}\right| \\ \psi_{\rho, \mu} = \left|\left\{ x \mid \mu(x) < \rho(x) + \tfrac12 < \mu(x-1) \right\}\right|$$

Merge the parts $\mu(i)$ and the offset parts $\rho(j)+\tfrac12$ into a single list $\nu(k)$ in descending order, and define an asymmetry statistic $\sigma(k)$ such that $\sigma(-1) = 0$, $\sigma(k) = \sigma(k-1) - 1$ when $\nu(k)$ comes from $\mu$, and $\sigma(k) = \sigma(k-1) + 1$ when $\nu(k)$ comes from $\rho$. Then $\chi_{\rho, \mu}$ is the number of $k$ for which $\nu(k)$ comes from $\mu$ and $\sigma(k) = 0$ (i.e the number of steps from $1$ to $0$); and $\psi_{\rho, \mu}$ is the number of $k$ for which $\nu(k)$ comes from $\rho$ and $\sigma(k) = 1$ (i.e. the number of steps from $0$ to $1$).

Now it all becomes clear: since we start at $0$ and always step up or down by $1$, the number of steps from $1$ to $0$ in the first $k$ steps is either equal to the number of steps from $0$ to $1$ or one less, and the latter is only possible when we've taken more parts from $\rho$ than from $\mu$. When $\ell(\mu) = H > \ell(\rho)$, we end up with a negative $\sigma$ and so the two statistics must be equal.

It's slightly more interesting when $\ell(\mu) < H$. Why must we end up with positive $\sigma$, even if $\ell(\mu) = \ell(\rho)$? Essentially: by making $x$ run up to $H$ we effectively pad both partitions, but because of the offset of $\tfrac12$ we're padding $\rho$ with positive values and $\mu$ with zeroes.

I don't claim that this is a rigorous proof, but I think it explains the core intuition sufficiently to be convincing.

• Thank you for your answer, I'm reading through it now. I'm struggling to understand your definition of $\sigma$. When you say $\sigma(k)=\sigma(k)-1$, do you mean $\sigma(k)=\sigma(k-1)$? Also when you say asymmetry statistic does that mean $\sigma$ is valued in $\mathbb Z_2$? – Alec B-G Apr 11 '18 at 10:00
• @AlecB-G, no (although I did have a typo, now corrected) and no. $\sigma$ counts how many more parts from $\rho$ we've seen vs $\mu$, so it goes up or down one with each part processed. – Peter Taylor Apr 11 '18 at 10:11
• Do you mean $\sigma(0)=0$ for the definition of $\sigma$ or are you counting your list of $\nu$ from 0? – Alec B-G Apr 11 '18 at 11:17
• Assuming $\sigma(0)=0$ I now understand your proof. It's very nice, thank you for the help. – Alec B-G Apr 11 '18 at 11:28
• @AlecB-G, I was counting from 0. It's a fair point that in the context of partitions it's preferable to count from 1. – Peter Taylor Apr 11 '18 at 12:41