Question: Suppose we have a collection of m objects and a set P of p "properties," an undefined term, that the objects may or may not have. For each subset S of the set P of all properties, define Na(S) (a is for "at least") to be the number of objects in the collection that have at least the properties in S. Thus, for example, Na(∅) = m. In a typical application, formulas for Na(S) for other sets S ⊆ P are not difficult to figure out. Define Ne(S) to be the number of objects in our collection that have exactly the properties in S. Show that
Explain how this formula could be used for computing the number of onto functions in a more direct way than we did it using unions of sets. How would this formula apply to Problem in this section?
Problem: The boss asks the secretary to stuff n letters into envelopes forgetting to mention that he has been adding notes to the letters and in the process has rearranged the letters but not the envelopes. In how many ways can the letters be stuffed into the envelopes so that nobody gets the letter intended for him or her? What is the probability that nobody gets the letter intended for him or her?