# 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

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