Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

To what extent are the Inclusion Exclusion principle and Generating Functions interchangeable? Is there a general principle? For instance, I asked the following question, Number of 5 letter words over a 4 letter group using each letter at least once. Could it be solved with generating functions?

In general, what classes of problems solvable by inclusion exclusion are solvable by generating functions?

share|improve this question
2  
Most problems solved with generating functions have no relation to inclusion-exclution. A few problems that are naturally solved by inclusion-exclusion may instead by solved using generating function. So: NO, they are not interchangeable. –  GEdgar Feb 13 '12 at 18:50
    
So what types / classes of Inclusion - Exclusion problems lend themselves to generating functions? –  Robert S. Barnes Feb 13 '12 at 18:53
add comment

2 Answers

I think you would be very interested to read Section 4.2 of Wilf's generatingfunctionology.

share|improve this answer
    
I'll take a look. –  Robert S. Barnes Feb 13 '12 at 20:08
    
@Robert: I agree with Greg. Note that what Wilf calls the sieve method is precisely inclusion-exclusion. –  Brian M. Scott Feb 13 '12 at 21:09
add comment

Inclusion-exclusion can be thought of, in some sense, as a special case of the use of generating functions, but both should be understood in a fairly broad sense for this to be true. A broad context for inclusion-exclusion is Möbius inversion on a poset, which reduces to ordinary inclusion-exclusion in many cases such as when the poset is the poset of subsets of a set. Möbius inversion naturally takes place in the incidence algebra of a poset, which can be thought of as a place where generating functions associated to the poset naturally live. In particular, three of the most important types of generating functions (ordinary, exponential, Dirichlet) can be thought of as associated to posets in roughly this manner, although the details are a bit subtle.

For details, see Doubilet, Rota, and Stanley's On the foundations of combinatorial theory (VI): the idea of generating function.

share|improve this answer
    
Great, I'll take a look, although this might be over the head of an undergrad who's just finishing up a discrete course :-) –  Robert S. Barnes Feb 13 '12 at 20:15
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.