I was asked to work out the number of ways 11 distinct objects could be distributed between three people such that each had an odd number of objects. I worked that out fine (it’s 44,286) and generalised it to $2n+1$ objects having $\frac{3}{4}\br{9^n-1}$ arrangements – but I struggled to prove it. Can you help?

Obviously, But Just Explain Counting To Students

Hi, OBJECTS, and thank you for your message! I have a fairly nice proof, but I wonder if there’s a nicer one!

Let’s start with a lemma: if $k$ is even, there are $2^{k-1}$ ways to arrange $k$ distinct objects between two people so they each get an odd number.

A handwavey argument: There are $2^k$ ways to arrange them anyhow, and half of those are “both even”, so half of them must be “both odd”.

So, combining that lemma with all of the possibilities of Person 1 taking an odd number of objects, we have the total number of possibilities, $S$ as:

$S = \nCr{2n+1}{1} \br{2^{2n-2}} + \nCr{2n+1}{3} \br{2^{2n-4}} + \dots + \nCr{2n+1}{2n-1} \br{2^1}$

Not exactly nice, but bear with me, I’m going to make it worse.

Because $\nCr{n}{r} = \nCr{n}{n-r}$, I can rewrite $S$ as:

$S = \nCr{2n+1}{2} \br{2^1} + \nCr{2n+1}{4} \br{2^3} + \dots + \nCr{2n+1}{2n}\br{2^{2n-1}}$

Double that:

$2S =\nCr{2n+1}{2}\br{2^2} + \nCr{2n+1}{4} \br{2^4} + \dots + \nCr{2n+1}{2n}\br{2^{2n}}$

Now it’s getting neater.

Consider:

$A = (1+x)^{2n+1} = 1 + \nCr{2n+1}{1} x + \dots + x^{2n+1}$

$B = (1-x)^{2n+1} = 1 - \nCr{2n+1}{1} x + \dots - x^{n+1}$

$\frac{A + B}{2} = 1 + \nCr{2n+1}{2} x^2 + \nCr{2n+1}{4} x^4 + \dots \nCr{2n+1}{2n}x^{2n}$

If we let $x = 2$:

$\frac{A+B}{2} = 2S+1$

So:

$3^{2n+1} - 1 = 4S + 2$

$4S = 3^{2n+1} - 3$

$S = \frac{3}{4} \br {3^{2n} - 1}$

$\dots = \frac{3}{4} \br{9^n - 1}$

$\blacksquare$

I can’t help but wonder if there’s a still neater method – it looks a bit difference-of-two-squares-y, but I can’t see why.

Hope that helps!

- Uncle Colin

* Edited 2022-08-16 to fix LaTeX. Thanks, Adam!