Counting the number of ways of organizing an odd number of objects into 3 odd groups, elegant method?

Question

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?

Answer 1

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.

Answer 2

There are $3^{N}-3$ ways to organise the objects such that no combinations of two groups are empty.

Of these, there are as many ways to organise with $ooo$ patern as ways to organise with $oee$ pattern. This is quite trivial, because once you assign an odd number of objects to the first group, the rest (even, non-empty) can be split into two even or two odd groups with equally many possibilities.

Because of symmetry, the number of possibilities with $oee$ pattern must equal those with $eoe$ and $eeo$ pattern.

Thus, there are $\frac{3^{N}-3}{4}$ ways to organise the objects with $ooo$ pattern.

Answer 3

We can give a bijective proof of this fact.

Call the groups $1,2,3$. First, let us show that there are $(3^n-1)/2$ ways to distribute the objects such that group $1$ has an odd number of members.

Consider the transformation $T$ defined on the set of the $3^n$ possible distributions as follows. Given a distribution, $x$, we define $T(x)$ to be the result of finding the smallest element in the union of groups $1$ and $2$, and moving it to the other group (if it was in $1$, it goes to $2$, and vice versa). The only exception is the distribution where all the objects are in group $3$, for which we say $T(x)=x$, which is the only fixed point of $T$.

The set of $(3^n-1)$ distributions where at least one object is in groups $1$ or $2$ are partitioned into pairs of the form $\{x,T(x)\}$. In each pair, exactly one of the distributions has group $1$ being odd. Therefore, the number of distributions where group $1$ is odd is $(3^n-1)/2$.

We then rinse and repeat. Consider the set of $(3^n-1)/2$ distributions where the first group is odd, and define the transformation $S$ on this set where you find the smallest element in either group $2$ or $3$ and move it to the other group. By the same logic, $S$ divides the distributions where group $1$ is odd into pairs, where exactly one distribution in each pair has group $2$ odd, and therefore group $3$ odd as well. The only exception is the transformation where all the objects are in group $1$. Therefore, the number of distributions where all groups are odd is $$ \frac12\left[\frac{3^n-1}{2}-1\right]=\frac{3^n-3}4 $$

Answer 4

Looking over the current answers, I think that my solution is mostly the same as Rezha's, but I will still present it, in the way that I think about it.

I will show a bijection between the set of all partitions of the $N$-element set into three sets such that at most one of them is empty (of those there are $3^N - 3$) and four times the set of all partitions into three sets of odd cardinality. Indeed I will refer to a partition in of those four copies as a partition with either a pair of sets marked (there are three possibilities of that) or none.

Given any partition of the $N$-set into three sets, either none or two of them will have an even number of elements. If none of them do, we just map the partition to itself, with no pair marked. If two of the sets have even cardinality, we mark this pair of sets and move the smallest number in those two sets (which cannot both be empty) to the other set in the pair, making both of them odd.

In the other direction, map an unmarked partition to itself, and for a partition with a pair marked, move the smallest number in those two sets to the other of the two.

This is easily checked to be a bijection.

Answer 5

For a fourth approach ,we can make use of exponential generating functions to distribute N distinct odd number of object in 3 distinct boxes where each boxes have odd number of elements.

We know that each box can have such number of elements: $1,3,5,7,9,11,13,15,17...$

So , the exponential generating function for these number of elements are $$\frac{x^1}{1!}+\frac{x^3}{3!}+\frac{x^5}{5!}+\frac{x^7}{7!}+..+..$$

If $$e^x =1+\frac{x^1}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}+\frac{x^5}{5!}+\frac{x^6}{6!}+\frac{x^7}{7!}+..+..$$

and

$$e^{-x} =1-\frac{x^1}{1!}+\frac{x^2}{2!}-\frac{x^3}{3!}+\frac{x^4}{4!}-\frac{x^5}{5!}+\frac{x^6}{6!}-\frac{x^7}{7!}+..+..$$

Then , $$\frac{e^x -e^{-x}}{2}=\frac{x^1}{1!}+\frac{x^3}{3!}+\frac{x^5}{5!}+\frac{x^7}{7!}+..+..$$

So , find the coefficient of $\frac{x^N}{N!}$ in the expansion of $\bigg(\frac{e^x -e^{-x}}{2}\bigg)^3$

$$\frac{e^x -e^{-x}}{2}=\frac{(e^{2x}-1)^3}{(2e^x)^3}=\frac{1}{8}\frac{e^{6x}-3e^{4x}+3e^{2x}-1}{e^{3x}}$$

$$\bigg[\frac{x^N}{N!}\bigg]\frac{1}{8}({e^{3x}-3e^{x}+3e^{-x}-e^{-3x}})$$

$$\frac{1}{8}(3^N -3+3(-1)^N-(-3)^N)$$

We know that N is odd , so $$\frac{1}{8}(3^N -3-3+3^N)=\frac{1}{4}(3^N-3)$$

Answer 6

Let $p_N$ be the probability that a uniformly random division of the objects gives three odd groups. Take $N\geq 3$. Then there are two ways this can happen:

1. the first $N-2$ objects form three odd groups and the last two objects go in the same group.

2. The first $N-2$ objects form one odd and two even groups and the last two objects go into the two even groups in either order.

Thus we have $p_N=\frac{1}{3}p_{N-2}+\frac{2}{9}(1-p_{N-2})$ for $N\geq 3$, which rearranges to $p_N-\frac14=\frac19\big(p_{N-2}-\frac14\big)$.

Clearly this means $p_N-\frac14\to0$; in fact we have $p_N-\frac14=3^{-N}c$ for some constant $c$ which we can determine from the value of $p_1$.