I've got the following homework question. If anybody could possibly point me in the right direction, that would be great:

Suppose X is a sequence with 10 terms built from 26 letters {a, b, c, ..., z} such that e, n, r, and s occur at least once. Please determine with proof the number of such Xs.

I'm looking to create an exponential generating function to solve this problem. From what I understand, if ALL 26 letters had to occur at least once, the exponential generating function could be described as $ (e^x-1)^{26}$.

Since there are $4$ values that must occur at least once, my assumption is that the generating function will be $$(e^x-1)^4(e^x)^{22}$$

And then to find the actual answer, I believe I will need the coefficient on $$\frac{x^{10}}{10!}$$

Am I on the right track here?


You are right. Now multiply out and get the coefficients.

  • $\begingroup$ Alright, thanks! I've had a bit of trouble grasping the concept of EGF's, so confirmation that I'm doing this right is really helpful. $\endgroup$ – Nate Apr 20 '14 at 0:15
  • 2
    $\begingroup$ Take a peek at analytic combinatorics, or at Segdewick and Flajolet's "Introduction to the Analysis of Algorithms", check out the basic proofs for labelled structures. I believe this will clarify the mess (and give you tools to solve all sorts of hairy problems in a few lines). $\endgroup$ – vonbrand Apr 20 '14 at 0:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.