# A Distinctly Odd Coincidence

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.

There’s something unsatisfyingly arbitrary about the number 10. When we write numbers, e.g. 1729, our notation means that we have 1 thousand ($$10^3$$), 7 hundreds ($$10^2$$), 2 tens ($$10^1$$), and 9 ones ($$10^0$$), so the number 10 is ingrained in our very writing system. And it’s not just the Arabic numeral system: Roman numerals also organize themselves around powers of 10 (such as I=1, X=10, C=100, etc.). But why 10? (Other than the fact that we usually have 10 fingers and 10 toes [why not 20 instead?].)
Our “decimal” system centers around powers of 10, but there are other equally useful systems based on other numbers. For example, we could use sums of powers of 2, and instead of needing 10 digits (0,1,…,9) we can use just 2, namely 0 and 1. For example, the number 1101 in base 2 means $$1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0$$, also known as 13 in base 10. This may seem inefficient, since we need more digits (or, more correctly, “bits” in the binary setting) to express the same value, but it has many benefits. Each bit has only 2 choices, and can therefore be represented by a pair of opposites such as “on/off” (e.g. in circuits) or the two magnetic polarities. The latter is how hard drive disks store information (in binary!), which is one reason this system is beloved by computer scientists. It also allows for jokes like this: “There are 10 types of people in the world: those that understand binary, and those that don’t.”
Another common base is Hexadecimal, using powers of 16 with digits 0,…,9,A,B,C,D,E,F. (A hexadecimal digit is sometimes called a “nibble”.) It is common to prefix a hexadecimal number with “0x”, so 0x3B7 means $$3 \cdot 16^2 + 11 \cdot 16 + 7 = 951$$ in decimal. It also makes the phrase “I see 0xDEAD people” perfectly reasonable (how many is that?).
The possibilities are endless! We can use base $$n$$ for any positive integer $$n>1$$ in similar ways, but we can also use negative $$n$$ as well! (My favorite is base -4.) If you want to go ever further, think about what base $$(1+\sqrt{5})/2$$ (a.k.a. phinary) would look like! Or the related bases Fibonacci and NegaFibonacci!