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

Inspired by this question, I have been wondering if there are any useful generating functions with all non-zero coefficients equal to one. Obviously, the trivial generating function $\frac{1}{1-x}$ has significant applications, as do monomial symmetric functions but for the purposes of this question, we should ignore them. As Graham has commented, indicator functions also fall into this category. The best formulation I can think of for why these should be ignored is that they are most interesting for the purpose of taking products of generating functions, rather than being directly used for computation.

More specifically, such a generating function would (in my mind) have to be multi-variate, enumerate some object of interest and facilitate computations related to that object in a situation where direct computation is not straightforward. As an example of what I would consider cheating, by specializing many variables to one, the generating function in the aforementioned question allows for computing joint distributions of entries in a reduced word with great ease. However, to compute the generating function, it seems to me one would have to enumerate all such words anyways, hence no labor is saved. Were this not the case, this function would be an excellent example.

What would be an example of such a generating function where computation is assisted without being embedded in constructing the generating function? Even if the generating function serves as a useful book keeping device, that would be okay.

Please comment below with any suggested improvements for what should define a "useful" generating function. Explanations for why such a function cannot exist are welcome as well.

Edit 1: Added Graham's comment on indicator functions.

share|improve this question
    
I was actually thinking of a similar question the other day, although I was approaching it from the viewpoint of whether there is some nice $\mathcal{S}$- (or $\mathcal{A}$-) regular language for which there is a finite complete set of ($\mathbb{N}$-valued) invariants; the values of these invariants would of course be the exponents of the variables in each monomial. On the other hand, I suppose I may be restricting myself too much by asking for a regular language as this necessarily forces the associated generating function to be rational... –  ARupinski Jul 23 '13 at 1:23
    
You probably mean to say that all coefficients are equal to zero or one. In which case, in $n$ variables, you can identify your generating function with the indicator function of (any) subset of lattice points in ${\mathbb N}^n$. So your question is, in this sense, universal. Can you narrow it? –  Graham Denham Jul 23 '13 at 2:06
add comment

1 Answer

up vote 5 down vote accepted

Although you say you're not interested in examples with indicator functions, I think there are some examples with indicator functions of polytopes that fit your criteria. I'm writing this answer because I don't think they have the same flavor which you are trying to rule out.

To every lattice point one may associate a Laurent monomial and therefore to every polytope we may associate the sum of all such monomials corresponding to lattice points inside the polytope. This (possibly huge) Laurent polynomial is very important, for example, when one cares about weighted enumeration of lattice points inside polytopes and other facts.

Brion's formula allows one to write this Laurent polynomial as the sum of generating functions of the lattice points of the vertex cones of the polytope. Even though generating functions for cones feel easier than computing this indicator function for the polytope itself, it is not apriori obvious that this makes the computation faster.

However Barvinok's theorem uses Brion's formula together with a decomposition of cones into unimodular cones to conclude that this computation can be done in polynomial time. You can read Barvinok's "A polynomial time algorithm for counting integral points in polyhedra when the dimensionis fixed", Math. Oper. Res. 19 (1994), 769–779.

This is in my opinion one of the nicest results that uses generating functions with 0/1 coefficients in addition to some geometric fact to help compute a combinatorial function very fast. There are of course applications in Ehrhart theory etc.

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.