<commit_before>.. _combinatorics:

Combinatorics
=============

Combinatorics is the art of counting without counting. It is a fundamental mathematical task to determine how many things there are in a given collection, and when the collection is large, it can be tedious or infeasible to count the elements individually. Moreover, when the collection is described in terms of a changing parameter (say, a natural number, :math:`n`), we would like a formula that tells us how the number of objects depends on that parameter. In this chapter we will set up a foundation for achieving this goal, and learn some of the tricks of the
trade.

Finite Sets and Cardinality
---------------------------

It will be helpful, for every natural number :math:`n`, to have a canonical set of elements of size :math:`n`. To that end, we will choose the set

.. math::

   [n] = \{ m \mid m < n \} = \{ 0, 1, \ldots, n-1 \}.

We used the same notation, :math:`[n]`, to describe equivalence classes with respect to an equivalence relation, but hopefully our intended meaning will always be clear from the context.

A set :math:`A` of elements is said to be *finite* if there is a bijection from :math:`[n]` to :math:`A` for some :math:`n`. In that case, we would like to say that :math:`A` *has* :math:`n` *elements*, or that the set :math:`A` *has cardinality* :math:`n`, and write :math:`|A| = n`. But to do so, we need to know that when :math:`A` is finite, there is a unique :math:`n` with the property above.

Suppose there are bijections from both :math:`[m]` and :math:`[n]` to :math:`A`. Composing the first bijection with the inverse of the second, we get a bijection from :math:`[m]` to :math:`[n]`. It seems intuitively clear that this implies :math:`m = n`, but our goal is to prove this from the fundamental properties of sets, functions, and the natural numbers.

So suppose, for the sake of contradiction, :math:`m \neq n`. Without loss of generality, we can assume :math:`m > n` (why?). In particular, there is an injective function :math:`f` from :math:`[m]` to :math:`[n]`. Since :math:`m > n`, :math:`m \geq n+1`, and so we can restrict :math:`f` to get an injective function from :math:`[n+1]` to :math:`[n]`. The next theorem shows that this cannot happen.

----

**Theorem.** For any natural number :math:`n`, there is no injective function from :math:`[n+1]` to :math:`[n]`.

**Proof.** By induction on :math:`n`. The theorem is clear when :math:`n = 0`, because :math:`[1] = \{ 0 \}` and :math:`[0] = \emptyset`. If :math:`f` were an injective function from :math:`[1]` to :math:`[0]`, we would have :math:`f(0) \in \emptyset`, which is impossible.

So suppose the claim is true for :math:`n`, and suppose :math:`f` is an injective function from :math:`[n+2]` to :math:`[n+1]`. We consider two cases.

In the first case, suppose :math:`n` is not in the image of :math:`f`. Then :math:`f` maps :math:`[n+2]` to :math:`[n]`, and restricting the domain, we have an injective function from :math:`[n+1]` to :math:`[n]`, contradicting the inductive hypothesis.

In the second case, there is some :math:`m < n + 2` such that :math:`f(m) = n`. The idea is to alter :math:`f` slightly to get an injective function from :math:`[n+1]` to :math:`[n]`, again contradicting the inductive hypothesis. If :math:`m = n + 1`, which is to say it is the last element of :math:`[n+2]` that is mapped to the last element of :math:`[n+1]`, we can just restrict :math:`f` to :math:`[n+1]`. The fact that :math:`f` was injective implies that all the elements in :math:`[n+1]` are mapped to :math:`n`.

Otherwise, define :math:`f' : [n+1] \to [n]` by

.. math::

   f'(i) =
     \begin{cases}
       f(i) & \mbox{if $i \neq m$} \\
       f(n+1) & \mbox{if $i = m$.}
     \end{cases}

In other words, we map :math:`m` to the value that :math:`n+1` was mapped to. Since :math:`f` is injective, :math:`f(n+1) \neq f(m)`, and so :math:`f(n+1) < n`, as required. It is not hard to check that :math:`f'` is injective, so we have the contradiction we were after.

----

This theorem is known as the "pigeonhole principle." It implies that if :math:`n + 1` pigeons inhabit :math:`n` holes, then at least one hole has more than one pigeon. The principle implies that for every finite set :math:`A`, there is a unique :math:`n` such that there is a bijection from :math:`[n]` to :math:`A`, and we can define the cardinality of :math:`A` to be that :math:`n`.

.. _counting_principles:

Counting Principles
-------------------

Here is a basic counting principle.

----

**Theorem.** Let :math:`A` and :math:`B` be disjoint finite sets. Then :math:`| A \cup B | = | A | + | B |`.

**Proof.** Suppose :math:`f : [m] \to A` and :math:`g : [n] \to B` are bijections. Define :math:`h : [m + n] \to A \cup B` by

.. math::

   h(i) =
     \begin{cases}
       f(i) & \mbox{if $i < m$} \\
       g(i - m) & \mbox{if $m \leq i < m + n$.}
     \end{cases}

To see that :math:`h` is surjective, note that every :math:`k` in :math:`A \cup B` can be written as either :math:`k = f(i)` for some :math:`i \in [m]` or :math:`k = g(j)` for some :math:`j \in [n]`. In the first case, :math:`k = f(i) = h(i)`, and in the second case, :math:`k = g(j) = h(m + j)`.

It is not hard to show that :math:`h` is also injective. Suppose :math:`h(i) = h(j)`. If :math:`h(i)` is in :math:`A`, then it is not in the range of :math:`g`, and so we must have :math:`h(i) = f(i)` and :math:`h(j) = f(j)`. Then :math:`f(i) = f(j)`, the injectivity of :math:`f` implies that :math:`i = j`. If :math:`h(i)` is instead in :math:`B`, the argument it similar.

----

The proof only spells out our basic intuitions: if you want to list all of the elements of :math:`A \cup B`, you can list all the elements of :math:`A` and then all the elements of :math:`B`. And if :math:`A` and :math:`B` have no elements in common, then to count the elements of :math:`A \cup B`, you can count the elements of :math:`A` and then continue counting the elements of :math:`B`. Once you are comfortable translating the intuitive argument into a precise mathematical proof (and mathematicians generally are), you can use the more intuitive descriptions (and mathematicians generally do).

Here is another basic counting principle:<commit_msg>combinatorics: introduce sums and products over finite sets<commit_after>.. _combinatorics:

Combinatorics
=============

Combinatorics is the art of counting without counting. It is a fundamental mathematical task to determine how many things there are in a given collection, and when the collection is large, it can be tedious or infeasible to count the elements individually. Moreover, when the collection is described in terms of a changing parameter (say, a natural number, :math:`n`), we would like a formula that tells us how the number of objects depends on that parameter. In this chapter we will set up a foundation for achieving this goal, and learn some of the tricks of the
trade.

Finite Sets and Cardinality
---------------------------

It will be helpful, for every natural number :math:`n`, to have a canonical set of elements of size :math:`n`. To that end, we will choose the set

.. math::

   [n] = \{ m \mid m < n \} = \{ 0, 1, \ldots, n-1 \}.

We used the same notation, :math:`[n]`, to describe equivalence classes with respect to an equivalence relation, but hopefully our intended meaning will always be clear from the context.

A set :math:`A` of elements is said to be *finite* if there is a bijection from :math:`[n]` to :math:`A` for some :math:`n`. In that case, we would like to say that :math:`A` *has* :math:`n` *elements*, or that the set :math:`A` *has cardinality* :math:`n`, and write :math:`|A| = n`. But to do so, we need to know that when :math:`A` is finite, there is a unique :math:`n` with the property above.

Suppose there are bijections from both :math:`[m]` and :math:`[n]` to :math:`A`. Composing the first bijection with the inverse of the second, we get a bijection from :math:`[m]` to :math:`[n]`. It seems intuitively clear that this implies :math:`m = n`, but our goal is to prove this from the fundamental properties of sets, functions, and the natural numbers.

So suppose, for the sake of contradiction, :math:`m \neq n`. Without loss of generality, we can assume :math:`m > n` (why?). In particular, there is an injective function :math:`f` from :math:`[m]` to :math:`[n]`. Since :math:`m > n`, :math:`m \geq n+1`, and so we can restrict :math:`f` to get an injective function from :math:`[n+1]` to :math:`[n]`. The next theorem shows that this cannot happen.

----

**Theorem.** For any natural number :math:`n`, there is no injective function from :math:`[n+1]` to :math:`[n]`.

**Proof.** By induction on :math:`n`. The theorem is clear when :math:`n = 0`, because :math:`[1] = \{ 0 \}` and :math:`[0] = \emptyset`. If :math:`f` were an injective function from :math:`[1]` to :math:`[0]`, we would have :math:`f(0) \in \emptyset`, which is impossible.

So suppose the claim is true for :math:`n`, and suppose :math:`f` is an injective function from :math:`[n+2]` to :math:`[n+1]`. We consider two cases.

In the first case, suppose :math:`n` is not in the image of :math:`f`. Then :math:`f` maps :math:`[n+2]` to :math:`[n]`, and restricting the domain, we have an injective function from :math:`[n+1]` to :math:`[n]`, contradicting the inductive hypothesis.

In the second case, there is some :math:`m < n + 2` such that :math:`f(m) = n`. The idea is to alter :math:`f` slightly to get an injective function from :math:`[n+1]` to :math:`[n]`, again contradicting the inductive hypothesis. If :math:`m = n + 1`, which is to say it is the last element of :math:`[n+2]` that is mapped to the last element of :math:`[n+1]`, we can just restrict :math:`f` to :math:`[n+1]`. The fact that :math:`f` was injective implies that all the elements in :math:`[n+1]` are mapped to :math:`n`.

Otherwise, define :math:`f' : [n+1] \to [n]` by

.. math::

   f'(i) =
     \begin{cases}
       f(i) & \mbox{if $i \neq m$} \\
       f(n+1) & \mbox{if $i = m$.}
     \end{cases}

In other words, we map :math:`m` to the value that :math:`n+1` was mapped to. Since :math:`f` is injective, :math:`f(n+1) \neq f(m)`, and so :math:`f(n+1) < n`, as required. It is not hard to check that :math:`f'` is injective, so we have the contradiction we were after.

----

This theorem is known as the "pigeonhole principle." It implies that if :math:`n + 1` pigeons inhabit :math:`n` holes, then at least one hole has more than one pigeon. The principle implies that for every finite set :math:`A`, there is a unique :math:`n` such that there is a bijection from :math:`[n]` to :math:`A`, and we can define the cardinality of :math:`A` to be that :math:`n`.

We now introduce the notation :math:`\sum_{i \in A} f(i)` and :math:`\prod_{i \in A} f(i)` for sums and products over finite sets. If :math:`A = \{ a_0, \ldots, a_{n-1} \}`, then :math:`\sum_{i \in A} f(i)` is defined to be :math:`f(a_0) + \cdots + f(a_{n-1})`, and similarly for products. Formally, what we are doing is choosing a bijection :math:`g : [n] \to A` and defining :math:`\sum_{i \in A} f(i)` to be :math:`\sum_{j < n} f(g(j))`. It takes some work to show that this makes sense, which is to say, the answer we get doesn't depend on which bijection we choose. We will just take this fact for granted here.

.. _counting_principles:

Counting Principles
-------------------

Here is a basic counting principle.

----

**Theorem.** Let :math:`A` and :math:`B` be disjoint finite sets. Then :math:`| A \cup B | = | A | + | B |`.

**Proof.** Suppose :math:`f : [m] \to A` and :math:`g : [n] \to B` are bijections. Define :math:`h : [m + n] \to A \cup B` by

.. math::

   h(i) =
     \begin{cases}
       f(i) & \mbox{if $i < m$} \\
       g(i - m) & \mbox{if $m \leq i < m + n$.}
     \end{cases}

To see that :math:`h` is surjective, note that every :math:`k` in :math:`A \cup B` can be written as either :math:`k = f(i)` for some :math:`i \in [m]` or :math:`k = g(j)` for some :math:`j \in [n]`. In the first case, :math:`k = f(i) = h(i)`, and in the second case, :math:`k = g(j) = h(m + j)`.

It is not hard to show that :math:`h` is also injective. Suppose :math:`h(i) = h(j)`. If :math:`h(i)` is in :math:`A`, then it is not in the range of :math:`g`, and so we must have :math:`h(i) = f(i)` and :math:`h(j) = f(j)`. Then :math:`f(i) = f(j)`, the injectivity of :math:`f` implies that :math:`i = j`. If :math:`h(i)` is instead in :math:`B`, the argument it similar.

----

The proof only spells out our basic intuitions: if you want to list all of the elements of :math:`A \cup B`, you can list all the elements of :math:`A` and then all the elements of :math:`B`. And if :math:`A` and :math:`B` have no elements in common, then to count the elements of :math:`A \cup B`, you can count the elements of :math:`A` and then continue counting the elements of :math:`B`. Once you are comfortable translating the intuitive argument into a precise mathematical proof (and mathematicians generally are), you can use the more intuitive descriptions (and mathematicians generally do).

Here is another basic counting principle:
{'fraction_non_alphanumeric': 0.15811446789130104, 'fraction_numerical': 0.004858053742219523, 'mean_word_length': 3.8634182355112587, 'pattern_counts': {'":': 0, '<': 14, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3258386', 'n_tokens_mistral': 4317, 'n_tokens_neox': 4161, 'n_words': 2018}