# Inclusion Exclusion vs. Generating Functions

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?

-
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

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.

-
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

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

-
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