Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|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. –  quid 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
add comment

2 Answers

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

share|improve this answer
add comment

In Maple you can do

series(mul((1-q^i)^(-2),i=1..10),q=0,1000)

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;
  else
   return 0;
  fi;
 else
  return add((k+1)*d(m-k*n,n-1),k=0..floor(m/n));
 fi;
end:

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|improve this answer
add comment

Your Answer

 
discard

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.