1
$\begingroup$

Is there a easy way to compute the coefficients of the power series which represents

\begin{equation*} \frac{x - x^k + x^{k+1}}{1-2x + x^k - x^{k+1}}. \end{equation*}

I am currently solving this by assuming it has the form

\begin{equation*} a_1x+a_2x^2+a_3x^3+\dots+a_nx^n+\dots \end{equation*}

and solving tedious recurrences obtained from

\begin{equation*} x - x^k + x^{k+1} = (1-2x + x^k - x^{k+1}) \times (a_1x+a_2x^2+a_3x^3+\dots+a_nx^n+\dots). \end{equation*}

Motivation: If my calculations are right, the above is the generating function of the number of compositions of an integer which do not involve a given integer $k$.

  • 3
    There is no method faster and simpler than those "tedious recurrences". Maybe you should adjust your expectations! :P2010-08-30
  • 0
    The continued fraction form looks interesting: $-\cfrac{1}{1+\cfrac{1}{x^k+\cfrac{1}{1-\frac1{x}}}}$2010-08-30
  • 0
    What do you mean by composition? Addition or multiplication?2010-08-30
  • 0
    Another interesting thing about your function: if you construct the matrix whose (k,n) entry is the nth derivative of the kth function, the columns in the strictly lower triangular part of the matrix are constant. They seem to be this sequence: research.att.com/~njas/sequences/A002866 . The diagonal of that matrix on the other hand looks like this sequence: research.att.com/~njas/sequences/A0526652010-08-30
  • 0
    Have you tried taking the derivative at x = 0?2010-08-30
  • 0
    Matt : The compositions of 3 are 1+1+1,1+2,2+1,32010-08-30
  • 0
    I thought you meant addition. Are you aware of the exact formula for the number of partitions of a natural number N? http://en.wikipedia.org/wiki/Partition_%28number_theory%29 (Everybody calls these things "partitions", not "compositions")2010-08-30
  • 0
    Matt: In partitions order is not important, in compositions, the order is important. So 1+2 and 2+1 will correspond to different compositions but the same partition.2010-08-30

2 Answers 2

2

Depends on what you want to do with them. If you want to prove things about them, there are theorems which tell you what such sequences look like in terms of the reciprocals of the roots of the denominator, but if you can't solve for the roots explicitly these are not useful for computation (although they tell you the asymptotic behavior rather precisely). I wrote some notes on this and other topics in generating functions if you're interested (Section 5).

If you actually want to compute them for large indices, there is a way to do it faster than just running the recurrence. The idea is that for sufficiently large indices $n$ there exists a matrix $A$ and vectors $v, w$ such that $a_n = v^T A^n w$ and one can use binary exponentiation to compute $A^n$ when $n$ is large. In fact one can take $A$ to be the companion matrix of the characteristic polynomial. A special case of this idea includes the doubling formulas for the Fibonacci numbers. For sequences with combinatorial interpretations it is often possible to choose $A$ to be the adjacency matrix of a graph and to choose particularly nice $v$ and $w$. Stanley's Enumerative Combinatorics, I think, discusses such issues; two keywords here are "regular languages" and "finite state machines."

  • 0
    Qiaochu's idea is fast when one wants to compute isolated coefficients. I don't think it can be turned into an efficient way of computing an *initial segment* of the list of coefficients, though.2010-08-30
  • 0
    Thanks. I will a take a look at your notes.2010-08-30
1

There is an easier way to obtain the recurrences.

First rewrite in the more manageable form

$\displaystyle g(x) = \frac{1-x}{1-2x+x^k-x^{k+1}} - 1$

Let $\displaystyle f(x) = \frac{1-x}{1-2x+x^k-x^{k+1}}$

Then we have that

$\displaystyle f(x)(1-2x+x^k-x^{k+1}) = 1-x$

Now use Leibniz's formula for the $n^{th}$ derivative of a product.

$\sum_{r=0}^{n} {n \choose r} {f^{(n-r)'}(x)(1-2x+x^{k}-x^{k+1})^{r'}} = (1-x)^{n'}$

($r'$ is the $r^{th}$ derivative)

You are interested in this when $x = 0$.

The only terms that matter are on the LHS would be for $r=0,1,k,k+1$.

The coefficient of the power series can be gotten by dividing the $n^{th}$ derivative at $0$ by $n!$.

You can probably also see all the above if you do a partial fraction reduction of the rational function.

  • 0
    Hi M: Isn't it simpler to directly set up the recurrences?2010-08-30
  • 0
    @Acarchau: This gives us the recurrence for _every_ $n$ in one shot. Why do you think it is harder?2010-08-30