Return to Answer

This answer is inspired by JBL's comment on Aaron's answer:

Fix $n$, so that I don't have to include it in my notation. In all other respects, copy Aaron's notation. JBL observes that there appear to be numbers $f(1)$, $f(2)$, ..., $f(n-1)$ such that $$ p_{\lambda} = \sum_{k \in \lambda} f(k). \quad \quad (*)$$

We will show that such $f$'s exist, and give formulas for them. In particular, it will be clear that $f(1) = (n-1)^2/n$, proving the result. For convenience, we set $k(0)=f(n)=0$.

It seems best to describe the $f$'s by the following relation $$ \frac{k}{n} = \frac{k(n-k)}{n(n-1)} \left( - f(k-1) + 2 f(k) - f(k+1) \right) \ \mbox{for} \ 1 \leq k \leq n-1 \quad \quad (**)$$

Our proof breaks into two parts: showing that there is a unique solution to $(**)$ and showing that the resulting $f$'s obey $(*)$. We do the second part first.

We must establish the Markov relation: $$\sum_{k \in \lambda} f(k) = 1 + \sum_{\mu} p(\lambda \to \mu) \sum_{k \in \mu} f(k).$$ For any $k$ in $\lambda$, the modified partition $\mu$ contains either $k-1$, $k+1$ or $k$, depending on whether we lost a ball of the corresponding color, gained one, or kept the same number. The probabilities of these events are $k(n-k)/n(n-1)$, $k(n-k)/n(n-1)$, and $1-2 k(n-k)/n(n-1)$, respectively.

So we must show that $$\sum_{k \in \lambda} f(k) = 1 + \sum_{k \in \lambda} \left( \frac{k(n-k)} f(k-1) + \left( 1- \frac{2k(n-k)}{n(n-1)} f(k) \right) + \frac{k(n-k)} f(k+1)\right).$$ Canceling $\sum_{k \in \lambda} f(k)$ from both sides, we must show that $$0 = 1 - \sum_{k \in \lambda} \frac{k(n-k)}{n(n-1)} \left( - f(k-1) + 2 f(k) - f(k+1) \right). $$

By $(**)$, the defining equation of the $f$'s, this is $$1- \sum_{k \in \lambda} (k/n) = 1 - |\lambda|/n=0$$~ as desired.

So, if we can find $f$'s obeying $(**)$, we will have $(*)$.

Let $g_j$ be the length $(n-1)$ vector $$( n-j, 2(n-j), 3(n-j), \ldots, j(n-j), \ldots, 3j, 2j, j)$$ The key feature of $g_j$ is that $$- g_j(k-1) + 2 g_j(k) - g_j(k+1) = \begin{cases} n \quad k=j \\ 0 \quad k \neq j \end{cases}$$ where we set $g_j(0)=g_j(n)=0$. Let $f$ be the vector $(f(1), f(2), \ldots, f(n-1))$.

Rewrite $(**)$ as $$ \frac{n-1}{n-k} = - f(k-1) + 2 f(k) - f(k+1).$$ So we see that $$f = \sum_{k=1}^{n-1} \frac{n-1}{n(n-k)} g_k$$

In particular, $$f(1) = \sum_{k=1}^{n-1} \frac{n-1}{n(n-k)} (n-k) = \frac{(n-1)^2}{n}$$ as desired. More generally, $$f(j) = \sum_{k=1}^{j-1} \frac{n-1}{n(n-k)} k(n-j) + \sum_{k=j}^{n-1} \frac{n-1}{n(n-k)} j(n-k) = \frac{(n-1)(n-j)}{n} \sum_{k=1}^{j-1} \frac{k}{n-k} + \frac{j(n-j)(n-1)}{n}.$$

This answer is inspired by JBL's comment on Aaron's answer:

Fix $n$, so that I don't have to include it in my notation. In all other respects, copy Aaron's notation. JBL observes that there appear to be numbers $f(1)$, $f(2)$, ..., $f(n-1)$ such that $$ p_{\lambda} = \sum_{k \in \lambda} f(k). \quad \quad (*)$$

We will show that such $f$'s exist, and give formulas for them. In particular, it will be clear that $f(1) = (n-1)^2/n$, proving the result. For convenience, we set $f(0)=f(n)=0$.

It seems best to describe the $f$'s by the following relation $$ \frac{k}{n} = \frac{k(n-k)}{n(n-1)} \left( - f(k-1) + 2 f(k) - f(k+1) \right) \ \mbox{for} \ 1 \leq k \leq n-1 \quad \quad (**)$$

Our proof breaks into two parts: showing that there is a unique solution to $(**)$ and showing that the resulting $f$'s obey $(*)$. We do the second part first.

We must establish the Markov relation: $$\sum_{k \in \lambda} f(k) = 1 + \sum_{\mu} p(\lambda \to \mu) \sum_{k \in \mu} f(k).$$ For any $k$ in $\lambda$, the modified partition $\mu$ contains either $k-1$, $k+1$ or $k$, depending on whether we lost a ball of the corresponding color, gained one, or kept the same number. The probabilities of these events are $k(n-k)/n(n-1)$, $k(n-k)/n(n-1)$, and $1-2 k(n-k)/n(n-1)$, respectively.

So we must show that $$\sum_{k \in \lambda} f(k) = 1 + \sum_{k \in \lambda} \left( \frac{k(n-k)}{n(n-1)} f(k-1) + \left( 1- \frac{2k(n-k)}{n(n-1)} f(k) \right) + \frac{k(n-k)}{n(n-1)} f(k+1)\right).$$ Canceling $\sum_{k \in \lambda} f(k)$ from both sides, we must show that $$0 = 1 - \sum_{k \in \lambda} \frac{k(n-k)}{n(n-1)} \left( - f(k-1) + 2 f(k) - f(k+1) \right). $$

By $(**)$, the defining equation of the $f$'s, this is $$1- \sum_{k \in \lambda} (k/n) = 1 - |\lambda|/n=0$$~ as desired.

So, if we can find $f$'s obeying $(**)$, we will have $(*)$.

Let $g_j$ be the length $(n-1)$ vector $$( n-j, 2(n-j), 3(n-j), \ldots, j(n-j), \ldots, 3j, 2j, j)$$ The key feature of $g_j$ is that $$- g_j(k-1) + 2 g_j(k) - g_j(k+1) = \begin{cases} n \quad k=j \\ 0 \quad k \neq j \end{cases}$$ where we set $g_j(0)=g_j(n)=0$. Let $f$ be the vector $(f(1), f(2), \ldots, f(n-1))$.

Rewrite $(**)$ as $$ \frac{n-1}{n-k} = - f(k-1) + 2 f(k) - f(k+1).$$ So we see that $$f = \sum_{k=1}^{n-1} \frac{n-1}{n(n-k)} g_k$$

In particular, $$f(1) = \sum_{k=1}^{n-1} \frac{n-1}{n(n-k)} (n-k) = \frac{(n-1)^2}{n}$$ as desired. More generally, $$f(j) = \sum_{k=1}^{j-1} \frac{n-1}{n(n-k)} k(n-j) + \sum_{k=j}^{n-1} \frac{n-1}{n(n-k)} j(n-k) = \frac{(n-1)(n-j)}{n} \sum_{k=1}^{j-1} \frac{k}{n-k} + \frac{j(n-j)(n-1)}{n}.$$

This answer is inspired by JBL's comment on Aaron's answer:

Fix $n$, so that I don't have to include it in my notation. In all other respects, copy Aaron's notation. JBL observes that there appear to be numbers $f(1)$, $f(2)$, ..., $f(n-1)$ such that $$ p_{\lambda} = \sum_{k \in \lambda} f(k). \quad \quad (*)$$

We will show that such $f$'s exist, and give formulas for them. In particular, it will be clear that $f(1) = (n-1)^2/n$, proving the result. For convenience, we set $k(0)=f(n)=0$.

It seems best to describe the $f$'s by the following relation $$ \frac{k}{n} = \frac{k(n-k)}{n(n-1)} \left( - f(k-1) + 2 f(k) - f(k+1) \right) \ \mbox{for} \ 1 \leq k \leq n-1 \quad \quad (**)$$

Our proof breaks into two parts: showing that there is a unique solution to $(**)$ and showing that the resulting $f$'s obey $(*)$. We do the second part first.

We must establish the Markov relation: $$\sum_{k \in \lambda} f(k) = 1 + \sum_{\mu} p(\lambda \to \mu) \sum_{k \in \mu} f(k).$$ For any $k$ in $\lambda$, the modified partition $\mu$ contains either $k-1$, $k+1$ or $k$, depending on whether we lost a ball of the corresponding color, gained one, or kept the same number. The probabilities of these events are $k(n-k)/n(n-1)$, $k(n-k)/n(n-1)$, and $1-2 k(n-k)/n(n-1)$, respectively.

So we must show that $$\sum_{k \in \lambda} f(k) = 1 + \sum_{k \in \lambda} \left( \frac{k(n-k)} f(k-1) + \left( 1- \frac{2k(n-k)}{n(n-1)} f(k) \right) + \frac{k(n-k)} f(k+1)\right).$$ Canceling $\sum_{k \in \lambda} f(k)$ from both sides, we must show that $$0 = 1 - \sum_{k \in \lambda} \frac{k(n-k)}{n(n-1)} \left( - f(k-1) + 2 f(k) - f(k+1) \right). $$

By $(**)$, the defining equation of the $f$'s, this is $$1- \sum_{k \in \lambda} (k/n) = 1 - |\lambda|/n=0$$~ as desired.

So, if we can find $f$'s obeying $(**)$, we will have $(*)$.

Let $g_j$ be the length $(n-1)$ vector $$( n-j, 2(n-j), 3(n-j), \ldots, j(n-j), \ldots, 3j, 2j, j)$$ The key feature of $g_j$ is that $$- g_j(k-1) + 2 g_j(k) - g_j(k+1) = \begin{cases} n \quad k=j \\ 0 \quad k \neq j \end{cases}$$ where we set $g_j(0)=g_j(n)=0$. Let $f$ be the vector $(f(1), f(2), \ldots, f(n-1))$.

Rewrite $(**)$ as $$ \frac{n-1}{n-k} = - f(k-1) + 2 f(k) - f(k+1).$$ So we see that $$f = \sum_{k=1}^{n-1} \frac{n-1}{n(n-k)} g_k$$

In particular, $$f(1) = \sum_{k=1}^{n-1} \frac{n-1}{n(n-k)} (n-k) = \frac{(n-1)^2}{n}$$ as desired. More generally, $$f(j) = \sum_{k=1}^{j-1} \frac{n-1}{n(n-k)} k(n-j) + \sum_{k=j}^{n-1} j \frac{n-1}{n(n-k)} j(n-k) = \frac{(n-1)(n-j)}{n} \sum_{k=1}^{j-1} \frac{k}{n-k} + \frac{j(n-j)(n-1)}{n}.$$

This answer is inspired by JBL's comment on Aaron's answer:

Fix $n$, so that I don't have to include it in my notation. In all other respects, copy Aaron's notation. JBL observes that there appear to be numbers $f(1)$, $f(2)$, ..., $f(n-1)$ such that $$ p_{\lambda} = \sum_{k \in \lambda} f(k). \quad \quad (*)$$

We will show that such $f$'s exist, and give formulas for them. In particular, it will be clear that $f(1) = (n-1)^2/n$, proving the result. For convenience, we set $k(0)=f(n)=0$.

It seems best to describe the $f$'s by the following relation $$ \frac{k}{n} = \frac{k(n-k)}{n(n-1)} \left( - f(k-1) + 2 f(k) - f(k+1) \right) \ \mbox{for} \ 1 \leq k \leq n-1 \quad \quad (**)$$

Our proof breaks into two parts: showing that there is a unique solution to $(**)$ and showing that the resulting $f$'s obey $(*)$. We do the second part first.

We must establish the Markov relation: $$\sum_{k \in \lambda} f(k) = 1 + \sum_{\mu} p(\lambda \to \mu) \sum_{k \in \mu} f(k).$$ For any $k$ in $\lambda$, the modified partition $\mu$ contains either $k-1$, $k+1$ or $k$, depending on whether we lost a ball of the corresponding color, gained one, or kept the same number. The probabilities of these events are $k(n-k)/n(n-1)$, $k(n-k)/n(n-1)$, and $1-2 k(n-k)/n(n-1)$, respectively.

So we must show that $$\sum_{k \in \lambda} f(k) = 1 + \sum_{k \in \lambda} \left( \frac{k(n-k)} f(k-1) + \left( 1- \frac{2k(n-k)}{n(n-1)} f(k) \right) + \frac{k(n-k)} f(k+1)\right).$$ Canceling $\sum_{k \in \lambda} f(k)$ from both sides, we must show that $$0 = 1 - \sum_{k \in \lambda} \frac{k(n-k)}{n(n-1)} \left( - f(k-1) + 2 f(k) - f(k+1) \right). $$

By $(**)$, the defining equation of the $f$'s, this is $$1- \sum_{k \in \lambda} (k/n) = 1 - |\lambda|/n=0$$~ as desired.

So, if we can find $f$'s obeying $(**)$, we will have $(*)$.

Let $g_j$ be the length $(n-1)$ vector $$( n-j, 2(n-j), 3(n-j), \ldots, j(n-j), \ldots, 3j, 2j, j)$$ The key feature of $g_j$ is that $$- g_j(k-1) + 2 g_j(k) - g_j(k+1) = \begin{cases} n \quad k=j \\ 0 \quad k \neq j \end{cases}$$ where we set $g_j(0)=g_j(n)=0$. Let $f$ be the vector $(f(1), f(2), \ldots, f(n-1))$.

Rewrite $(**)$ as $$ \frac{n-1}{n-k} = - f(k-1) + 2 f(k) - f(k+1).$$ So we see that $$f = \sum_{k=1}^{n-1} \frac{n-1}{n(n-k)} g_k$$

In particular, $$f(1) = \sum_{k=1}^{n-1} \frac{n-1}{n(n-k)} (n-k) = \frac{(n-1)^2}{n}$$ as desired. More generally, $$f(j) = \sum_{k=1}^{j-1} \frac{n-1}{n(n-k)} k(n-j) + \sum_{k=j}^{n-1} \frac{n-1}{n(n-k)} j(n-k) = \frac{(n-1)(n-j)}{n} \sum_{k=1}^{j-1} \frac{k}{n-k} + \frac{j(n-j)(n-1)}{n}.$$

This answer is inspired by JBL's comment on Aaron's answer:

Fix $n$, so that I don't have to include it in my notation. In all other respects, copy Aaron's notation. JBL observes that there appear to be numbers $f(1)$, $f(2)$, ..., $f(n-1)$ such that $$ p_{\lambda} = \sum_{k \in \lambda} f(k). \quad \quad (*)$$

We will show that such $f$'s exist, and give formulas for them. In particular, it will be clear that $f(1) = (n-1)^2/n$, proving the result. For convenience, we set $k(0)=f(n)=0$.

It seems best to describe the $f$'s by the following relation $$ \frac{k}{n} = \frac{k(n-k)}{n(n-1)} \left( - f(k-1) + 2 f(k) - f(k+1) \right) \ \mbox{for} \ 1 \leq k \leq n-1 \quad \quad (**)$$

Our proof breaks into two parts: showing that there is a unique solution to $(**)$ and showing that the resulting $f$'s obey $(*)$. We do the second part first.

We must establish the Markov relation: $$\sum_{k \in \lambda} f(k) = 1 + \sum_{\mu} p(\lambda \to \mu) \sum_{k \in \mu} f(k).$$ For any $k$ in $\lambda$, the modified partition $\mu$ contains either $k-1$, $k+1$ or $k$, depending on whether we lost a ball of the corresponding color, gained one, or kept the same number. The probabilities of these events are $k(n-k)/n(n-1)$, $k(n-k)/n(n-1)$, and $1-2 k(n-k)/n(n-1)$, respectively.

So we must show that $$\sum_{k \in \lambda} f(k) = 1 + \sum_{k \in \lambda} \left( \frac{k(n-k)} f(k-1) + \left( 1- \frac{2k(n-k)}{n(n-1)} f(k) \right) + \frac{k(n-k)} f(k+1)\right).$$ Canceling $\sum_{k \in \lambda} f(k)$ from both sides, we must show that $$0 = 1 - \sum_{k \in \lambda} \frac{k(n-k)}{n(n-1)} \left( - f(k-1) + 2 f(k) - f(k+1) \right). \quad (***)$$

By $(**)$, the defining equation of the $f$'s, this is $$1- \sum_{k \in \lambda} (k/n) = 1 - |\lambda|/n=0$$~ as desired.

So, if we can find $f$'s obeying $(**)$, we will have $(*)$.

Let $g_j$ be the length $(n-1)$ vector $$( n-j, 2(n-j), 3(n-j), \ldots, j(n-j), \ldots, 3j, 2j, j)$$ The key feature of $g_j$ is that $$- g_j(k-1) + 2 g_j(k) - g_j(k+1) = \begin{cases} n \quad k=j \\ 0 \quad k \neq j \end{cases}$$ where we set $g_j(0)=g_j(n)=0$. Let $f$ be the vector $(f(1), f(2), \ldots, f(n-1))$.

Rewrite $(**)$ as $$ \frac{n-1}{n-k} = - f(k-1) + 2 f(k) - f(k+1).$$ So we see that $$f = \sum_{k=1}^{n-1} \frac{n-1}{n(n-k)} g_k$$

In particular, $$f(1) = \sum_{k=1}^{n-1} \frac{n-1}{n(n-k)} (n-k) = \frac{(n-1)^2}{n}$$ as desired. More generally, $$f(j) = \sum_{k=1}^{j-1} \frac{n-1}{n(n-k)} k(n-j) + \sum_{k=j}^{n-1} j \frac{n-1}{n(n-k)} j(n-k) = \frac{(n-1)(n-j)}{n} \sum_{k=1}^{j-1} \frac{k}{n-k} + \frac{j(n-j)(n-1)}{n}.$$

A word about motivation. JBL's observation is inspired, and I don't know how he or she spotted it. Once you believe something like that should be true, you can follow your nose to get to $(***)$. Then notice that the summand is only a function of $k$ and $n$; call it $h(k,n)$. We are supposed to have $\sum_{k \in \lambda} h(k,n)=1$ for every $\lambda$, which suggests that $h(k,n) = k/n$. That is equation $(**)$, and from there it is routine linear algebra.

This answer is inspired by JBL's comment on Aaron's answer:

Fix $n$, so that I don't have to include it in my notation. In all other respects, copy Aaron's notation. JBL observes that there appear to be numbers $f(1)$, $f(2)$, ..., $f(n-1)$ such that $$ p_{\lambda} = \sum_{k \in \lambda} f(k). \quad \quad (*)$$

We will show that such $f$'s exist, and give formulas for them. In particular, it will be clear that $f(1) = (n-1)^2/n$, proving the result. For convenience, we set $k(0)=f(n)=0$.

It seems best to describe the $f$'s by the following relation $$ \frac{k}{n} = \frac{k(n-k)}{n(n-1)} \left( - f(k-1) + 2 f(k) - f(k+1) \right) \ \mbox{for} \ 1 \leq k \leq n-1 \quad \quad (**)$$

Our proof breaks into two parts: showing that there is a unique solution to $(**)$ and showing that the resulting $f$'s obey $(*)$. We do the second part first.

We must establish the Markov relation: $$\sum_{k \in \lambda} f(k) = 1 + \sum_{\mu} p(\lambda \to \mu) \sum_{k \in \mu} f(k).$$ For any $k$ in $\lambda$, the modified partition $\mu$ contains either $k-1$, $k+1$ or $k$, depending on whether we lost a ball of the corresponding color, gained one, or kept the same number. The probabilities of these events are $k(n-k)/n(n-1)$, $k(n-k)/n(n-1)$, and $1-2 k(n-k)/n(n-1)$, respectively.

So we must show that $$\sum_{k \in \lambda} f(k) = 1 + \sum_{k \in \lambda} \left( \frac{k(n-k)} f(k-1) + \left( 1- \frac{2k(n-k)}{n(n-1)} f(k) \right) + \frac{k(n-k)} f(k+1)\right).$$ Canceling $\sum_{k \in \lambda} f(k)$ from both sides, we must show that $$0 = 1 - \sum_{k \in \lambda} \frac{k(n-k)}{n(n-1)} \left( - f(k-1) + 2 f(k) - f(k+1) \right). $$

By $(**)$, the defining equation of the $f$'s, this is $$1- \sum_{k \in \lambda} (k/n) = 1 - |\lambda|/n=0$$~ as desired.

So, if we can find $f$'s obeying $(**)$, we will have $(*)$.

Let $g_j$ be the length $(n-1)$ vector $$( n-j, 2(n-j), 3(n-j), \ldots, j(n-j), \ldots, 3j, 2j, j)$$ The key feature of $g_j$ is that $$- g_j(k-1) + 2 g_j(k) - g_j(k+1) = \begin{cases} n \quad k=j \\ 0 \quad k \neq j \end{cases}$$ where we set $g_j(0)=g_j(n)=0$. Let $f$ be the vector $(f(1), f(2), \ldots, f(n-1))$.

Rewrite $(**)$ as $$ \frac{n-1}{n-k} = - f(k-1) + 2 f(k) - f(k+1).$$ So we see that $$f = \sum_{k=1}^{n-1} \frac{n-1}{n(n-k)} g_k$$

In particular, $$f(1) = \sum_{k=1}^{n-1} \frac{n-1}{n(n-k)} (n-k) = \frac{(n-1)^2}{n}$$ as desired. More generally, $$f(j) = \sum_{k=1}^{j-1} \frac{n-1}{n(n-k)} k(n-j) + \sum_{k=j}^{n-1} j \frac{n-1}{n(n-k)} j(n-k) = \frac{(n-1)(n-j)}{n} \sum_{k=1}^{j-1} \frac{k}{n-k} + \frac{j(n-j)(n-1)}{n}.$$