I came across this problem on a blog I've been reading (link here but not necessary for understanding the problem). You have to split an odd number N of distinct objects into three different groups such that the number of objects in each group is an odd number. In how many ways can this be done? The blog goes into a combinatorial solution, giving an answer of $\frac{3^N-3}{4}$.
My question is: Is there an elegant reason why it is almost exactly a quarter of the possible distributions that work? More interestingly, is there a simpler argument for why it is exactly the number it is?
As an example of what I'm looking for, for the easier question of how many ways there are to split an even number of distinct items into two groups with an even number of items, you can have a given item (item A, say), and for every selection where A is in the first group, there is one for which it is in the second group (just by moving it from group 1 to group 2). Since exactly one of those possibilities has an even number in each group, exactly half of the possible selections will work. Therefore the total number of ways is $2^{N-1}$.
Intuitively, something similar should work for three groups. Is there an argument along similar lines for the three group case?
Best Answer
The possible parities for the three groups are even-even-odd, even-odd-even, odd-even-even, and odd-odd-odd. The odds for each of these outcomes are approximately even, and one of the four is the desired result. (Each of the three outcomes with two even groups has $\frac{3^N+1}{4}$ ways to distribute the items.)
This is similar to the two-group problem, where the parities are either even-even or odd-odd with equal probability.