1
$\begingroup$

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$.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – knsam
    Jun 27, 2013 at 23:00
  • $\begingroup$ @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}$ ? $\endgroup$ Jun 28, 2013 at 12:02
  • $\begingroup$ 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. $\endgroup$ Jul 1, 2013 at 6:13

2 Answers 2

1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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