How Many Typing Orders Are Possible If Letter 8 Is Typed First?

[Gtotheiles]

I've been working on this problem for near three days now, with two other people. We cannot completely figure it out


(a) 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 inbox. 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 above information, how many such after lunch typing orders are possible? (That there are no letters left to be typed is one of the possibilities.)
(b) Suppose there are n letters in the problem above and letter (n - 1) has been typed. Write a general expression for the number of after lunch typing orders possible.

Like I said, we've been doing this one for a couple days. If the 9th letter is delivered before lunch, there are 256 possibilities. But that doesn't take into account it being delivered after lunch, which is the part we cannot figure out. We think you have to find some type of formula that involves combinations, but we're not 100%. Help please?

 

[OlderDan]

I've been working on this problem for near three days now, with two other people. We cannot completely figure it out


(a) 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 inbox. 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 above information, how many such after lunch typing orders are possible? (That there are no letters left to be typed is one of the possibilities.)
(b) Suppose there are n letters in the problem above and letter (n - 1) has been typed. Write a general expression for the number of after lunch typing orders possible.

Like I said, we've been doing this one for a couple days. If the 9th letter is delivered before lunch, there are 256 possibilities. But that doesn't take into account it being delivered after lunch, which is the part we cannot figure out. We think you have to find some type of formula that involves combinations, but we're not 100%. Help please?

Start by considering only letters #1 through #7. A pile of any given size has only one typing order, so all you need to know is the number of combinations possible for any size pile.

A pile of size 1 could have any of 7 letters in it. A pile of size 2 can have any compination of the 7 letters taken 2 at a time. A pile of size 3 can have any combination of 7 letters taken 3 at a time. etc., etc. up to size 7. Without letter #9, the total number of possilble combinations (and possible orders) is the sum of all combinations of 7 things taken x at a time for x from 0 to 7. If #9 were already in the pile, it would be all possible combinations of 8 things taken x at a time for x from 0 to 8, and your number 2^8 = 256 would be the correct answer. With only letters #1 through #7 considered it is 2^7 = 128, which is the sum of 8 terms corresponding to piles of size 0 through 7.

What you have to do is figure out how many ways letter #9 could fit into each size pile containing letters from among the first 7. For example, if letters from among #1 through #7 were in a pile of size 3, how many positions could #9 be put into that pile? Each of the 8 terms in the sum of combinations of 7 things taken x at a time is going to be multiplied by a factor that increases with pile size. I'll leave it to you to find those factors and add up the results.

 

[Gtotheiles]

Thank you. We actually figured it out about an hour after I posted, but it turns out we used the method you described. Thanks man!