Tag Archives: generating functions

A Distinctly Odd Coincidence

Counting/Probability, Proofs, , , , , , ,

This week’s topic comes from partition theory. Consider all the ways to write 7 as the sum of positive integers:
$$\begin{align*}
&7, && 3+2+2,\\
&6+1, && 3+2+1+1,\\
&5+2, && 3+1+1+1+1,\\
&5+1+1, && 2+2+2+1,\\
&4+3, && 2+2+1+1+1,\\
&4+2+1, && 2+1+1+1+1+1,\\
&4+1+1+1, && 1+1+1+1+1+1+1+1.\\
&3+3+1, &&
\end{align*}$$ (We don’t care about order: for example, \(5+2\) and \(2+5\) are the same.) These are called the partitions of 7, and there are 15 of them.

We can also consider imposing constraints on these partitions: For example, how many of these partitions of 7 use only odd integers? These “odd” partitions are
$$\begin{align*}
& 7, && 3+1+1+1+1, \\
& 5+1+1, && 1+1+1+1+1+1+1, \\
& 3+3+1, &&
\end{align*}$$ and there are 5 of them. Here’s a very different question: how many partition of 7 have no repeated parts? These “distinct” partition are
$$\begin{align*}
& 7, && 6+1, && 5+2, && 4+3, && 4+2+1,
\end{align*}$$ and there are 5 of these as well.

This must be coincidence, right? Let’s try a bigger example. How many partitions of 11 use only odd parts? You can (and should!) check that there are 12. And how many partitions of 11 use only distinct parts? Again, there are 12. Surprisingly, these numbers will always match!:

Theorem (Euler): For any positive integer \(n\), the number of “odd” partitions of \(n\) is the same as the number of “distinct” partitions of \(n\).

Transforming Between “Odd” and “Distinct” Partitions

Let’s try to make sense of this. Given a partition of \(n\) into odd parts, there is a simple way to transform it into a partition with distinct parts: whenever two parts are the same, add them together, and repeat until they are all distinct. For example, the partition \(7+3+3+3+3+3+3+1+1+1\) of 28 is transformed into
$$\begin{align*}
& 7+(3+3)+(3+3)+(3+3)+(1+1)+1 \\
& \quad \to 7+(6+6)+6+2+1 \\
& \quad \to 12+7+6+2+1,
\end{align*}$$ which has distinct parts. In the other direction, to transform a “distinct” partition to an “odd” one, we can reverse this process: whenever there is an even part, cut it in half and write it twice. Our example \(12+7+6+2+1\) from above becomes
$$\begin{align*}
& (6+6)+7+(3+3)+(1+1)+1 \\
&\quad \to (3+3)+(3+3)+7+3+3+1+1+1,
\end{align*}$$ which is the “odd” permutation we started with. These transformations can be shown to match “odd” permutations with “distinct” permutations in pairs, proving that these sets have the same size. (A careful argument uses binary representation.) For example, the 5 partitions of 7 above are paired as follows:
$$\begin{align*}
& 7 &&\leftrightarrow && 7 \\
& 6+1 &&\leftrightarrow && 3+3+1 \\
& 5+2 &&\leftrightarrow && 5+1+1 \\
& 4+3 &&\leftrightarrow && 3+1+1+1+1 \\
& 4+2+1 &&\leftrightarrow && 1+1+1+1+1+1+1.
\end{align*}$$ (If you know something about generating functions, then a different proof follows by proving the identity
$$\frac{1}{(1-x)(1-x^3)(1-x^5)(1-x^7)\cdots} = (1+x)(1+x^2)(1+x^3)(1+x^4)\cdots$$ and noting that the coefficients of \(x^n\) in the expansions of the left and right products equals the number of “odd” and “distinct” permutations of \(n\), respectively.)

More Coincidences

These apparent coincidences are characteristic of many results in partition theory. Try your hand at proving the following generalization:

Theorem: The number of partitions of \(n\) into parts that are not divisible by 10 equals the number of partitions of \(n\) where no part is repeated 10 or more times. The same is true for any positive integer in place of 10.

(Hint: both methods used above can be extended to prove this.) If instead we want the parts to be really distinct and make sure no two parts are equal or consecutive, then we want my favorite partition theory result:

Theorem (Rogers-Ramanujan Identity): The number of partitions of \(n\) where any two parts differ by at least 2 is the same as the number of partitions of \(n\) where every part is one more or one less than a multiple of 5.

Despite the simplicity of the statement, this is much harder to prove than the previous theorems.

Secret Santa (Now with Fewer Hats!)

Counting/Probability, Proofs, , , , ,

As we approach the holiday season, some of you may soon participate in—or perhaps even organize—a “Secret Santa” exchange. Specifically, some number of people enter the exchange, and each is assigned one person (their Santee) to give a gift to (or multiple gifts… or other craziness…), in such a way that each person also receives from one person (their Santa). As organizers of such an exchange, how should we choose a permutation of the participants, i.e., an assignment of each person to his/her Santee? Here’s one method: put all names in a hat, and let each player extract a name at random. What could go wrong?

For starters, someone might pick their own name! Shopping for yourself might make the task easier, but this seems to contradict the (Christmas) spirit of the exchange. If we pick randomly as above, and if there are \(n\) people in the exchange, what is the probability that no one picks him/herself? For large \(n\), this answer tends toward \(1/e = .3679\ldots\), where \(e = 2.718\ldots\) is Euler’s number. So, with more than a 63 percent chance, someone is left out. (See below for a proof of this fact.)

What else might go wrong? Perhaps we also want to avoid two people being assigned each other, so that this pair doesn’t feel excluded. What is the chance of a randomly chosen permutation having no excluded person or pair? This can be computed to tend toward \(1/e^{3/2} = .2231\ldots\), so there is some left out person or pair with almost 80% probability. And if we wish to make sure there are no excluded groups of size at most 6, say, then the chance of failure limits to $$1-e^{-1-\frac{1}{2}-\frac{1}{3}-\frac{1}{4}-\frac{1}{5}-\frac{1}{6}} = .9137$$ for large \(n\).

So, while Santa hats may be fluffy and festive, Secret Santa hats are a bad idea. What should we do to organize our exchange? Here’s one option: just make a big cycle. Specifically, write all names in some random order and chain them up, e.g., \(2\to 6\to 7\to 3\to 1\to 4\to 5\to 2\) (if the “names” are just 1, 2, …, 7).

Where do these numbers come from?

How can we compute the probabilities mentioned above? One common method to prove the \(1/e\) probability uses the principle of Inclusion-Exclusion, but here is a sketch of an argument that doesn’t rely on this technique. Let \(A_n\) be the number of permutations of \(n\) people with no person assigned to him/herself. Such a permutation is called a Derangement, and a direct counting argument can be used to show that \(A_n = (n-1)(A_{n-1} + A_{n-2})\) (see the Wikipedia page for derangements, for example). As there are \(n!\) total permutations of the players, the desired probability is \(P_n = A_n/n!\), so the above formula can be manipulated to \(P_n-P_{n-1} = -\frac{1}{n}(P_{n-1}-P_{n-2})\). This produces \(P_n-P_{n-1} = \frac{(-1)^n}{n!}\) by induction, so we obtain $$P_n = 1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\cdots+\frac{(-1)^n}{n!}.$$ As \(n\) gets big this value tends toward the infinite sum \(\sum_{i=0}^\infty \frac{(-1)^i}{i!} = 1/e\).

The other probabilities mentioned take more work. A well-suited tool is that of (Exponential) Generating Functions, which in this case help organize a more complicated Inclusion-Exclusion argument. Using these, it can be shown that the probability that a random permutation of \(n\) players has no groups of size 6 or less is equal to the coefficient of \(x^n\) in the power series expansion of $$\frac{1}{1-x}\cdot e^{-\left(x+\frac{x^2}{2} + \cdots + \frac{x^6}{6}\right)}.$$