:tocdepth: 2

.. _sum_of_squares:

Pieces of Numbers
============================================================================

.. contents:: :local:

.. highlight:: python

We will spend some time learning about a very simple new concept - one
that only requires addition. We’ll explore it.


Pieces of Numbers – The Simplest Addition 
------------------------------------------

Here is a question nearly every human could answer.

How many ways can you divide a pile of :math:`5` sticks into (non-empty)
piles?

Let’s see.

There is the trivial one where you don’t divide it at all.  :math:`5=5`.
There is the one where you just make five piles of one stick each.
 :math:`1+1+1+1+1=5`. You could have four in one pile.  That leaves
:math:`4+1=5`. But if you have three in one pile, there are two ways to
do the other two.

:math:`3+2=5`. :math:`3+1+1=5`.

Almost done!  I guess the only other possibility is if there are piles
of :math:`2` and :math:`1`.

:math:`2+2+1=5`. :math:`2+1+1+1=5`.

That makes seven ways in total.  We call these things *integer
partitions*.  As George Andrews says in `this delightful little
book <http://www.cambridge.org/gb/academic/subjects/mathematics/number-theory/integer-partitions>`__:
“An integer partition is a way of splitting a number into integer
parts.”  More precisely, a partition of a nonnegative integer :math:`n`
is a representation of :math:`n` as a sum of positive integers, called
summands or parts of the partition. The order of the summands is
irrelevant.

.. raw:: html

   </div>

The function giving the number of partitions of :math:`n` is called
:math:`p(n)`.  So our example shows that :math:`p(5)=7`. Amazingly,
there are *real physics applications* of this! See `this list of
articles <https://empslocal.ex.ac.uk/people/staff/mrwatkin/zeta/partitioning.htm>`__ and
`this more dubious
example <https://www8.cs.umu.se/kurser/TDBA77/VT06/algorithms/BOOK/BOOK4/NODE153.HTM>`__.
 A typical quote: “The number partitioning problem can be interpreted
physically in terms of a thermally isolated noninteracting Bose gas
trapped in a one-dimensional harmonic-oscillator potential.”

Exploration 1 
^^^^^^^^^^^^^^

Try to compute :math:`p(n)` for :math:`n\leq 10`. Divide up this work in
groups! Maybe three or four people should work on each one, and then
cross-check their work.


Exploration 2 
^^^^^^^^^^^^^^

The question to explore is:

-  *Partitions of :math:`n` using only odd parts. This is notated
   :math:`p(n \mid \text{ odd parts })`.*


Exploration 3 
^^^^^^^^^^^^^^

The question to explore is:

-  *Partitions of :math:`n` using only even parts, or
   :math:`p(n \mid \text{ even parts })`.*


Exploration 4 
^^^^^^^^^^^^^^

The question to explore is:

-  *Partitions of :math:`n` using distinct parts; that is, all the
   numbers in the partition are different.*


Try these out for small (!) :math:`n`. See if you find any possible
patterns. Again, it is probably best if some larger groups work together
and split up the work to make it more efficient.