4
$\begingroup$

The function p(n) counts the number of ways a number can be made up of smaller numbers. For example, the p(5) = 7 because you can make 5 in the following ways:

1-1-1-1-1

1-1-1-2

3-2

3-1-1

2-2-1

1-4

5

According to Wikipedia, the generating function for this, counting the possible partitioning of a number, is as follows:

enter image description here

After much effort, I have been unable to make any sense of this, or contort it in such a way that it actually answer the question: what is p(n) when n = 1000?. There is a great deal about this expression that I do not understand. Please answer any of the following which, given your expertise, you can.

  1. n is the argument of this function, the number for which we are counting the partitions. What is x here? Where does it come from? Same for k? What is the significance of k? Why does it go from 1 to infinity?
  2. What is the significance of the small dot on the right side?
  3. We see the sign on the left "Sigma" so often, but the sign on the right (Big Pi) appears, at least for me, in very few places. Why is this?
  4. On the right we see that we get the product of the expression for every value of k from = 1 to infinity. How does this make sense? If we go from 1 to infinity, isn't the resulting value necessarily infinite?
  5. It is known that actually getting a series of numbers from a generating function can be non-trivial. Is it even possible to solve for p(n) using this equation? Or does it simply explain the pattern with no means of getting the numbers?
  6. How can this be implemented in a computer language, one that is general, and not math-based, for example in Python, or in JavaScript? Is it possible? Can you provide an implementation of this generating function in computer code? (See PS)
  7. What is p(1000)? How do you know?
  8. Generally, in solving generating functions, using a "Taylor series" is proposed as a possible solution. How would you explain this to someone who does not know what a Taylor series is? Is this problem even solvable without a deep knowledge of that subject?
  9. Is it correct to call this an "equation"? Or is a generating function fundamentally a different thing?

PS I am asking this question because it is my hobby. I am NOT in a university and asking you to do my work, NOR am I employed, either as a mathematician or otherwise. This is fun for me, and I hope answering it is fun for you!

$\endgroup$
  • $\begingroup$ The small dot on the right is a full stop used to indicate the end of a sentence. $\endgroup$ – Lord Shark the Unknown Mar 25 '18 at 18:44
  • $\begingroup$ I reckon that $p(1000)=24061467864032622473692149727991$. $\endgroup$ – Lord Shark the Unknown Mar 25 '18 at 18:49
7
$\begingroup$

There's too much here to give a full answer, but perhaps this will help you on your way towards understanding generating functions.

  1. n is the argument of this function, the number for which we are counting the partitions. What is x here? Where does it come from? Same for k? What is the significance of k? Why does it go from 1 to infinity?

$x$ is a dummy variable. It comes from our desire to encode a sequence of values $p(0),\, p(1),\, p(2),\, \ldots$ as a function. This is at the heart of what a generating function is: an artificial construct which turns out to be useful.

As for $k$... Although we're talking here about a generating function with an infinite number of terms, it may help your intuition (and it certainly helps in explicit calculation of terms) to think of it as a polynomial. Now, since a term $ax^i$ means that the $i$th value in the sequence is $a$, multiplication is a form of combining sequences where we take smaller structures and use them to build larger structures. This is particularly relevant with partitions. Suppose we have two generating functions $g(x)$ and $h(x)$ which give certain restricted partition functions: e.g. $g(x)$ gives the number of ways to partition a number $n$ into parts $1, 2, 5, 11$, and $h(x)$ gives the number of ways to partition a number $n$ into parts $7, 14$. If we multiply them to give $g(x)h(x)$, that tells us the number of ways to partition $n$ into parts $1,2,5,7,11,14$. Note: this depends on the two sets of permitted parts being disjoint. To be more precise, if

  1. $g(x)$ is the generating function for objects having property $P$
  2. $h(x)$ is the generating function for objects having property $Q$
  3. The objects of size $n$ having property $R$ are in bijection with pairs $(p, q)$ where $p$ is an object having property $P$, $q$ is an object having property $Q$, and the sum of the sizes of $p$ and $q$ is $n$

then the generating function for objects having property $R$ is given by $g(x)h(x)$.

Now, $\frac{1}{1-x^k}$ is $1 + x^k + x^{2k} + x^{3k} + \ldots$ by the standard analysis of a geometric progression. And that is precisely the generating function for partitioning a number $n$ into parts $k$: it's only possible if $n$ is a multiple of $k$, and in that case there's one way to do it. So if we multiply those g.f.s together for all positive integer $k$, we get the number of ways to partition $n$ into positive integers.

  1. On the right we see that we get the product of the expression for every value of k from = 1 to infinity. How does this make sense? If we go from 1 to infinity, isn't the resulting value necessarily infinite?

What resulting value? Bear in mind that we're not dealing with numbers here, but functions, and even if we take only one term it is already infinite.

If we consider instead $$\prod_{k=1}^{m} \frac{1}{1-x^k}$$ then we get the generating function for $n$ into parts of at most $m$, as explained in the previous section.

  1. It is known that actually getting a series of numbers from a generating function can be non-trivial. Is it even possible to solve for p(n) using this equation? Or does it simply explain the pattern with no means of getting the numbers?
  2. How can this be implemented in a computer language, one that is general, and not math-based, for example in Python, or in JavaScript? Is it possible? Can you provide an implementation of this generating function in computer code? (See PS)

It's possible, yes. Consider two things: if we're solving for $p(n)$ then we don't care about parts larger than $n$, and we don't care about the coefficients of $x^i$ for $i > n$. So all we need is a simple polynomial multiplication (i.e. convolution) routine and something like (pseudocode):

product = array(n+1)
product[0] = 1
for k = 1 to n:
    term = array(n+1)
    for i = 0 to n step k:
        term[i] = 1
    product = multiply(product, term).slice(0, n+1)
  1. What is p(1000)? How do you know?

There are all kinds of other ways to calculate partition numbers. You can see implementations of a few on our sister site PPCG.

  1. Generally, in solving generating functions, using a "Taylor series" is proposed as a possible solution. How would you explain this to someone who does not know what a Taylor series is? Is this problem even solvable without a deep knowledge of that subject?

I don't know what you mean by "solving" generating functions, but there's absolutely no need to bring up the subject of Taylor series if you don't want to.

  1. Is it correct to call this an "equation"? Or is a generating function fundamentally a different thing?

Technically, yes, I think it's correct, but I would instead call this an identity because it doesn't have any unbound variables (I consider $x$ to be contextually bound) and states that the two expressions are identically equal, not equal under certain values of the parameters.

$\endgroup$
  • $\begingroup$ This is a great answer, thanks for taking the time $\endgroup$ – Code Whisperer Mar 27 '18 at 10:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.