It is true that the generating function for the number of ways to partition an integer $n$ into a sum of ones is \begin{align} f(x) = 1 + x + x^2 + x^3 + \cdots \end{align} But I don't see how the $1$ corresponds to no ones in your partition, $x$ corresponds to one one in your partition, $x^2$ corresponds to two ones in your partition, etc. So in order to have the size of your partition less than $k$, you would truncate this generating function and consider the generating function \begin{align} f(x) = 1+x+x^2+\cdots+x^k. \end{align} Could anyone clarify this?

up vote 2 down vote accepted

But I don't see how the $1$ corresponds to no ones in your partition, $x$ corresponds to one one in your partition, $x^2$ corresponds to two ones in your partition, etc.

What is a generating function? In the simplest case of one variable, it's a function $$A(x) = a_0 + a_1 x + a_2 x^2 + \ldots$$ whose coefficients $a_n$ correspond to a sequence of interest. When the sequence of interest is

the number of ways to partition an integer $n$ into a sum of ones

we want $a_n$ to be the number of partitions of $n$ into ones. Therefore $a_0$ is the number of partitions of $0$ into ones, $a_1$ is the number of partitions of $1$ into ones, etc. If you have two ones in your partition, their sum is $2$ and so they count towards $a_2$; since this is the only way to partition $2$ into ones, $a_2 = 1$ and so the coefficient of $x^2$ is $1$.

The number of ways to partition and integer $\, n \,$ into a sum of ones is one because there is only one way to do it. That is, for all $\, n \ge 0 \,$ the sequence $\, a_n = 1. \,$ Thus, the generating function of this sequence is, as you asked, $\, f(x) = 1 + x + x^2 + x^3 + \dots. \,$ If you place more restrictions on the partition, then the generating function will change to reflect those restrictions. Agian, as you asked, if you restrict to size of partition always less than $\, k, \,$ then the the sequence $\, a_n = 1 \,$ if $\, n < k \,$ and $\, a_n = 0 \,$ if $ n\ge k \,$ and thus its generating function is now $\, f(x) = 1 + x + x^2 + \dots + x^{k-1}. \,$

  • I am more asking why do we know the restriction is doing what we want. That is, in $1 + x + x^2 + ...$, why is the $1$ saying you have no ones, the $x$ is saying there is one one, the $x^2$ is saying there is two ones, etc? Understanding that would clarify why $(1+x+x^2+...+x^k)$ is for the partition of size at most $k$. – norm850 Sep 12 at 15:14
  • Oh I think see now... because if you go any higher, the number of ways to partition, i.e. coefficient, would be zero since the partition would be larger than $k$. – norm850 Sep 12 at 15:19

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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