generatingfunctions

[Mitch Harris]

On Fri, 25 Apr 2003, Kimberling, Clark wrote:

>Here's one of those questions that's probably been looked at many times,
>but...
>
>Given a strictly increasing sequence r of positive integers, let r* be
>the complement of r, obtained by arranging in increasing order all the
>positive integers not in r.  How can the generating function of r* be
>obtained from that of r?

Since r(n) is monotonically increasing, convert to the characteristic eqn

  c(z) = sum z^n [n = r(k)],

(i.e. all coeffs are 0 or 1, and 1 only where the exponent in c(z) matches
some coeff in r(z))
then those numbers not in the set has the ogf

  1/(1-z) - c(z).

Reverse the transformation to go back. Yes, I know I didn't give any
details to this "transformation" because...

>Possibly someone knows of references to special cases?

I think this is hard in general: take r(z) = 1/(1-2z), so r(n) = 2^n. I
don't know of a 'good' (rational function or even special function)
representation of the ogf

  \sum z^n [n=2^k]

Off the top of my head, combinations of linear functions (an+b) seem to be
the only r for which you can do this transformation easily (er... at all)
in rational functions.

  r(z) = \sum z^n (an+b)

-->

  c(z) = {z^b \over 1-z^a}

As to actual references for this ... can't think of anything that isn't
obvious (an exercise in Wilf, generatingfunctionology, or Stanley,
Enumerative Combinatorics, or Graham, Knuth, Patashnik, Concrete
Mathematics) (and may not be in those either). This topic makes me think
of Flajeolet and rational functions/regular languages vs.
nonregular/algebraic, transcendental functions.

-- 
Mitch Harris

Department of Computer Science
University of Illinois at Urbana-Champaign
http://www.uiuc.edu/~maharri