1
$\begingroup$

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!

  • 0
    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.2012-06-26

1 Answers 1

3

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.

  • 0
    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](http://en.wikipedia.org/wiki/Fa%C3%A0_di_Bruno%27s_formula#Combinatorial_form) (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.2012-06-26