Results 1 to 2 of 2

Math Help - Two combinatorics questions.

  1. #1
    Senior Member
    Joined
    Apr 2009
    Posts
    308

    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.
    Last edited by usagi_killer; December 4th 2009 at 09:29 PM. Reason: Typo
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by usagi_killer View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: June 13th 2011, 05:18 PM
  2. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 27th 2010, 12:17 PM
  3. Help with combinatorics?
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 31st 2010, 10:52 AM
  4. Combinatorics
    Posted in the Statistics Forum
    Replies: 8
    Last Post: October 27th 2008, 05:02 PM
  5. combinatorics
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 30th 2008, 05:27 AM

Search Tags


/mathhelpforum @mathhelpforum