6
$\begingroup$

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?

$\endgroup$

6 Answers 6

8
$\begingroup$

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.

$\endgroup$
2
  • 4
    $\begingroup$ +1 but "The odds...are approximately even" might be confusing terminology in a problem with odd/even. :) $\endgroup$
    – RobPratt
    Mar 30, 2023 at 2:44
  • 7
    $\begingroup$ @RobPratt Agreed, but I could not resist the play on words. $\endgroup$ Mar 30, 2023 at 2:45
5
$\begingroup$

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.

$\endgroup$
2
  • 3
    $\begingroup$ The part about how "the rest (even, non-empty) can be split into two even or two odd groups with equally many possibilities" could maybe use some elaboration. (I mean, it does work: just set aside one item and arrange the (odd number of) others into two groups any way you like; now adding the remaining item to one of the two groups (one always being odd-sized, the other even-sized) makes the number of items in the groups either both odd or both even, thus showing that there's a 1:1 correspondence between odd-odd and even-even groupings. But that's hardly obvious at a glance.) $\endgroup$ Mar 30, 2023 at 10:55
  • 2
    $\begingroup$ @IlmariKaronen a non-empty set has as many even subsets as odd subsets. This is well-known in combinatorics. Put this subset to group 2 and the rest to group 3, if the initial set is even, group 2 and 3 are both even or odd $\endgroup$ Mar 30, 2023 at 11:06
5
$\begingroup$

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 $$

$\endgroup$
1
  • 3
    $\begingroup$ +1 but destruction=distribution? $\endgroup$
    – RobPratt
    Mar 30, 2023 at 4:25
2
$\begingroup$

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 one 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.

$\endgroup$
1
  • $\begingroup$ Thanks! I accepted this answer as it seems to be the most intuitive to me, and the closest to what I was trying to think through on my own. The step I was missing was "marking" the two groups where an element is being switched. $\endgroup$ Apr 2, 2023 at 23:54
2
$\begingroup$

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)$$

$\endgroup$
1
  • $\begingroup$ Slightly less intuitive, but using exponential generating functions in this way is quite pleasing. Also it seems like it would very easily extend to more groups, in a way that the other approaches don't. $\endgroup$ Apr 3, 2023 at 0:00
0
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .