quad9/combinatorics/homework/hw1/main.tex

\documentclass[11pt,a4paper,dvipsnames]{article}
\usepackage[utf8]{inputenc}

\usepackage[english]{babel}
\input{../../../hw_preamble.tex}
\input{../../combinatorics_defs.tex}

\title{First assignment\\Combinatorics and graph theory}
\author{Adrià Vilanova Martínez}

\showcorrectionsfalse % Change "true" to "false" in order to show corrections as
                      % if they weren't corrections (in black instead of red).

\begin{document}

\maketitle

\begin{FreeProblem}
  \textbf{Problem 1.} (Euler) Show that the number of partitions of an integer $n$ into \textit{odd parts} equals the number of partitions in \textit{distinct parts}.
\end{FreeProblem}

Let's begin by showing an example of what this means. There are 6 ways to partition the number $n = 5$:

\[ \begin{array}{rcl}
  5 & = & \textcolor{PineGreen}{1 + 1 + 1 + 1 + 1}, \\
  & & 2 + 1 + 1 + 1, \\
  & & 2 + 2 + 1, \\
  & & \textcolor{PineGreen}{3 + 1 + 1}, \\
  & & \textcolor{red}{3 + 2}, \\
  & & \textcolor{red}{4 + 1}, \\
  & & \textbf{5}.
\end{array} \]

We can clearly see that, in this case, there are 3 ways to \textcolor{PineGreen}{partition 5 into odd parts}, and also 3 ways to \textcolor{red}{partition 5 into distinct parts}, thus verifying the statement.

Let's prove that via the symbolic method:

Let's define the combinatorical class
\[ \mathcal{P} = \Seq(\{1\}) \times \Seq(\{3\}) \times \Seq(\{5\}) \times \cdots, \]
whose objects represent partitions of an integer into odd parts. The size function is the trivial one (the size of integers is their value).

Note that this combinatorical class is the same one we used in class to count partitions of an integer without any constraints, but deleting from the product of sequences those sequences of even integers.

To represent partitions of a number into distinct parts, we're going to use a similar combinatorical class. In this case, instead of removing sequences of even integers, we will truncate each sequence so each object contains at most 1 instance of each integer. Thus, we define:
\[ \tilde{\mathcal{P}} = (\varepsilon + \{1\}) \times (\varepsilon + \{2\}) \times (\varepsilon + \{3\}) \times \cdots, \]
whose size function is again the trivial one.

\newpage

Then, to show that both numbers are equal, we simply must prove that their generating functions are equal.\footnote{This is because this would mean that the coefficients are equal, and since these coefficients count the number of elements with a fixed size, and the size corresponds to the integer $n$ being partitioned, this would mean both numbers are equal.}

The generating functions corresponding to each combinatorial class are:
\[ P(z) = \frac{1}{1 - z} \frac{1}{1 - z^3} \frac{1}{1 - z^5} \cdots, \]
\[ \tilde{P}(z) = (1 + z) (1 + z^2) (1 + z^3) \cdots. \]

We can use the identity $1 - z^{2k} = (1 + z^k) (1 - z^k)$ to show that:
\[ \tilde{P}(z) = \frac{1 - z^2}{1 - z} \frac{1 - z^4}{1 - z^2} \frac{1 - z^6}{1 - z^3} \cdots \]

From the first expression, it is clear that $[z^0] \tilde{P}(z) = 1$, so $\tilde{P}(z)$ is invertible. Thus, it suffices to show that $P(z) \tilde{P}(z)^{-1} = 1$.

\[ P(z) \tilde{P}(z)^{-1} = \left( \frac{1}{1 - z} \frac{1}{1 - z^3} \frac{1}{1 - z^5} \cdots \right) \left( \frac{1 - z}{1 - z^2} \frac{1 - z^2}{1 - z^4} \frac{1 - z^3}{1 - z^6} \cdots \right) = \]
\[ = \frac{(1 - z) (1 - z^2) (1 - z^3) \cdots}{(1 - z) (1 - z^3) (1 - z^5) \cdots (1 - z^2) (1 - z^4) (1 - z^6) \cdots} = \]
\[ = \frac{(1 - z) (1 - z^2) (1 - z^3) \cdots}{(1 - z) (1 - z^2) (1 - z^3) \cdots} = 1. \]

\end{document}