MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Are there computer packages which calculate coefficients of generating functions, such as

$$D_n(q)=\sum_m d_{m,n}q^m= \frac{1}{\prod_{i=1}^n (1-q^i)^2} \text{ or}$$

$$S_d(q)=\sum_m s_{m,d}q^m = \frac{q^d}{\prod_{i=1}^d (1-q^i)} \; ?$$

The effort, to calculate all coefficients e.g. $d_{k,l}$ for $k$ and $l$ smaller than $N$ should grow with $N^3$, as they satisfy recursion relations such as

$$d_{m,n} = \sum_{k=0}^{[m/n]}(k+1)d_{m-k\cdot n,n-1}$$

which allow to express each of the $N^2$ coefficients as a sum of at most $N$ terms ($d_{m,1}=m+1$, $d_{0,0}=1$, $d_{m,0}=0$ for $m>0$).

Before I revive my rusty computer knowledge I would like to know whether computer packages such as GAP tackle my problem to solve recursion relations with given initial conditions, save the solutions to files and allow to read them in again if one wants to tackle the next case $N+1$.

share|cite|improve this question
Your LaTeX was not displayed properly for two reasons: enclosing something with backticks makes it code, and MathJax cannot parse it: for eg, $H$. If you want to see H, you'd say $H$. Also, to center the display, it is best to enclose the equation by double dollars. Do not have a number of spaces in the beginning of a line. Any line that begins with four space is treated as code and once again, MathJaX cannot parse it. – knsam Jun 27 '13 at 20:19
@knsam I approved the edit and only made a slight change to display the formulas more compactly, including the 'or' in the same line and avoiding a 'lonely' questionmark. – user9072 Jun 27 '13 at 20:24
Regarding the question itself, AFAIK, sage itself does not do generating functions per se; but, in this context, I can see a much simpler algorithmic code, which is based on the observation that I can truncate $(1 - q^i)^{-1}$ after a certain index that is an easy-to-figure function of $m$. So, there are ways to handle this, but, thinking of them as generating functions as such is not going to help make matters nice. – knsam Jun 27 '13 at 23:00
@qknsam: Isn't the truncation which you suggest the content of the recursion relation, $D_n(q) = (1-q^n)^{-2} D_{n-1}(q)$, $(1-q^n)^{-2}=\sum_k (k+1)q^{k\cdot n}$ ? – Norbert Dragon Jun 28 '13 at 12:02
I know I have used Maple to calculate similar things, but as I am currently without Maple access I can't test it for you. – Gerry Myerson Jul 1 '13 at 6:13

Check out Bruno Salvy (et al's) gfun package.

share|cite|improve this answer

In Maple you can do


to get $D_{10}(q)$ as far as $q^{999}$; this took 0.9 seconds on my laptop. Alternatively, you can do

d := proc(m,n)
 option remember;

 if n = 0 then
  if m = 0 then
   return 1;
   return 0;
  return add((k+1)*d(m-k*n,n-1),k=0..floor(m/n));

This calculates $d(1000,10)$ in about 0.9 seconds again. It remembers all instances of $d(m,n)$ that it has already computed.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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