The complete question I would like to answer is:

Given positive integers $k,n$, how many descending lists of non-negative integers $(x_1~x_2\ldots x_k)$ are there such that $\sum_{i=1}^k x_i = n$?

As a quick first insight, it's clear that the general problem will come if we can find the solution for $k=n$. It would take a long time to explain the buildup, but I have reduced the problem to calculating the value $f(n,n)$ of a function recursively defined by: $$ f(n,m) = f(n,m-1) + f(n-m,\min(m,n-m))~, $$ $$ f(n,2) = 1+\left\lfloor\frac{n}{2}\right\rfloor~~;~f(n,1) = f(n,0) = 1~. $$ For a less clunky reformulation, posit that $f(a,b) = f(a,\min(a,b))$ for each pair $a,b$, and we have $f(n,m) = f(n,m-1) + f(n-m,m)$.

Now my attempt so far is repeatedly applying the recursive rule to the first term to yield $$ f(n,m) = 1 + \left\lfloor\frac{n}{2}\right\rfloor + \sum_{i=3}^m f(n-i,i) ~, $$ which may itself be repeated to form a summation over no more than $\left\lfloor\dfrac{n-2}{3}\right\rfloor$ variables, but the computations involved (summations over products of floor functions) become extremely tedious.

Does anyone have suggestions as for how to proceed down this particular attempt at solution, a better method of solution, or a different angle on the problem entirely?

For the curious, this number of descending lists is part of a coefficient in the expansion of the expression $D^n[f^k]$, the n$^\text{th}$ derivative of the k$^\text{th}$ power of some function. Attempting this solely out of curiosity. Thanks ahead of time for reading this mess!

  • 1
    $\begingroup$ This is the number $p_k(n)$ of partitions of $n$ into $k$ parts. For fixed $k$ it has generating function $\sum p_k(n) t^n = \frac{1}{(1 - t)(1 - t^2)...(1 - t^k)}$ (the proof is by taking the "transpose" of a partition: the transpose of a partition of $n$ into $k$ parts is a partition of $n$ into parts of size at most $k$ and vice versa). Are you familiar with generating functions? In what form would you like an answer? (For fixed $k$ and large $n$ you can write down an explicit closed form using partial fractions.) $\endgroup$ – Qiaochu Yuan Jun 26 '12 at 7:16
  • 1
    $\begingroup$ @QiaochuYuan Aha, you mean this guy -- looks like I didn't take my necessary dose of wikipedia hunting. How do you propose writing the explicit closed form? $\endgroup$ – Eugene Shvarts Jun 26 '12 at 7:35
  • $\begingroup$ Using partial fractions you can write the generating function as a linear combination of terms of the form $\sum \frac{1}{(1 - \zeta t)^r}$ where $\zeta$ is a root of unity. The coefficients of these terms can be explicitly written down using the binomial theorem with negative exponents. $\endgroup$ – Qiaochu Yuan Jun 26 '12 at 7:37

Assuming that you want your lists to be strictly decreasing, this is the number of partitions of $n$ into $k$ distinct parts; otherwise it’s the number of partitions of $n$ into $k$ parts. The former is given by the triangle A060016 at OEIS, the second by the triangle A008284. At those links you’ll find some references, and the latter also has some relevant generating functions.

  • $\begingroup$ Oops, I totally meant the latter (non-strictly). I've calculated a clutch of these numbers as it stands (more than the OEIS list!) but I was mostly curious to see if there's a more tenable and direct closed-form than something like this (with the external function $x^k$). The generating functions are an excellent step in the right direction though -- will keep toying with this and reading up. $\endgroup$ – Eugene Shvarts Jun 26 '12 at 7:56

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.