# Two combinatorics questions.

Printable View

• December 4th 2009, 08:39 PM
usagi_killer
Two combinatorics questions.
1. In an office, at various times during the day, the boss gives the secretary a letter to type, each time putting the letter on top of the pile in the secretary's in-box. When there is time, the secretary takes the top letter off the pile and types it. There are nine letters to be typed during the day and the boss delivers them in the order 1,2,3,4,5,6,7,8,9. While leaving for lunch, the secretary tells a colleague that letter 8 has already been typed, but says nothing else about the morning's typing. The colleague wonders which of the nine letters remain to be typed after lunch and in what order they will be typed. Based upon the information given, how many such after-lunch typing orders are possible? (There are no letters left to typed is one of the possibilities.)

2. Let $\mathbb{P}_n$ be the set of subsets of $\{1,2, \cdots, n\}$. Let $c(n,m)$ be the number of functions $f : \mathbb{P}_n \to \{1,2, \cdots, m\}$ such that $f(A \cap B) = \mbox{min}\{f(A), f(B)\}$. Prove that $c(n,m) = \sum_{j=1}^m j^n$.
• December 5th 2009, 12:47 PM
Opalg
Quote:

Originally Posted by usagi_killer
1. In an office, at various times during the day, the boss gives the secretary a letter to type, each time putting the letter on top of the pile in the secretary's in-box. When there is time, the secretary takes the top letter off the pile and types it. There are nine letters to be typed during the day and the boss delivers them in the order 1,2,3,4,5,6,7,8,9. While leaving for lunch, the secretary tells a colleague that letter 8 has already been typed, but says nothing else about the morning's typing. The colleague wonders which of the nine letters remain to be typed after lunch and in what order they will be typed. Based upon the information given, how many such after-lunch typing orders are possible? (There are no letters left to typed is one of the possibilities.)

The calculation will depend on whether or not letter 9 has already been typed during the morning. If it has been, then the letters remaining to be typed are a subset of numbers 1,2,3,4,5,6,7. Any such subset (including the empty set and the whole set) can occur, and the letters must be typed in decreasing numerical order. The number of possible orders is therefore $2^7 = 128$.

Now suppose that letter 9 was not typed before lunch. It may already be waiting on top of the pile when the secretary returns from lunch, or it may be added at any time during the afternoon. Apart from letter 9, there can again be any subset of letters 1 to 7 remaining to by typed. If there are k such letters, then letter 9 can be inserted at any of k+1 points (before all of them, after all of them, or at any intermediate point). The total number of orders is thus $\sum_{k=0}^7(k+1){7\choose k} = 64\times 9 = 576$.

So the final answer is $128 + 576 = 704$.