Results 1 to 2 of 2

Math Help - Elementary Combinatorics

  1. #1
    Newbie
    Joined
    Feb 2010
    Posts
    4

    Elementary Combinatorics

    There are 10 persons and 10 prizes, each prize belonging to a distinct person. Find the number of ways of distributing prizes among all the persons such that 3 particular persons never get their respective prizes in any of the distributions. Each person must get 1 prize.

    For example:

    Suppose the persons are named as A,B,C,D,E,F,G,H,I,J and their respective prizes are numbered 1,2,3,4,5,6,7,8,9,10. (Its like prize 1 goes to person A, prize 2 goes to person B and so on.) Now,
    A-1 B-2 C-3 D-6 E-7 F-4 G-5 H-8 I-9 J-10 (Here D, E, F are the 3 particular persons who didn't get their respective prizes. The rest may or may not get their respective prizes) is one such possible distribution.

    In other words, if it were 4 people, 4 prizes, and 2 "particular" persons never get the correct prize, here's what I would say:
    Call the people A,B,C,D... call their prizes a,b,c,d
    Our two "particular" people are A and B
    The possibilities:
    Ab, Ba, Cc, Dd
    Ab, Ba, Cd, Dc
    Ab, Bc, Ca, Dd
    Ab, Bc, Cd, Da
    Ab, Bd, Ca, Dc
    Ab, Bd, Cc, Da
    Ac, Ba, Cb, Dd
    Ac, Ba, Cd, Db
    Ac, Bd, Ca, Db
    Ac, Bd, Cb, Da
    Ad, Ba, Cb, Dc
    Ad, Ba, Cc, Db
    Ad, Bc, Ca, Db
    Ad, Bc, Cb, Da

    So... 14.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by riemann View Post
    There are 10 persons and 10 prizes, each prize belonging to a distinct person. Find the number of ways of distributing prizes among all the persons such that 3 particular persons never get their respective prizes in any of the distributions. Each person must get 1 prize.

    For example:

    Suppose the persons are named as A,B,C,D,E,F,G,H,I,J and their respective prizes are numbered 1,2,3,4,5,6,7,8,9,10. (Its like prize 1 goes to person A, prize 2 goes to person B and so on.) Now,
    A-1 B-2 C-3 D-6 E-7 F-4 G-5 H-8 I-9 J-10 (Here D, E, F are the 3 particular persons who didn't get their respective prizes. The rest may or may not get their respective prizes) is one such possible distribution.

    In other words, if it were 4 people, 4 prizes, and 2 "particular" persons never get the correct prize, here's what I would say:
    Call the people A,B,C,D... call their prizes a,b,c,d
    Our two "particular" people are A and B
    The possibilities:
    Ab, Ba, Cc, Dd
    Ab, Ba, Cd, Dc
    Ab, Bc, Ca, Dd
    Ab, Bc, Cd, Da
    Ab, Bd, Ca, Dc
    Ab, Bd, Cc, Da
    Ac, Ba, Cb, Dd
    Ac, Ba, Cd, Db
    Ac, Bd, Ca, Db
    Ac, Bd, Cb, Da
    Ad, Ba, Cb, Dc
    Ad, Ba, Cc, Db
    Ad, Bc, Ca, Db
    Ad, Bc, Cb, Da

    So... 14.
    Hi riemann,

    If I understand you correctly, you want to find the number of ways prizes can be assigned to people so that none of A, B, and C gets his "correct" prize, right?

    Here is a solution via the "Principle of Inclusion and Exclusion" (PIE).

    The total number of arrangements without any restriction on who gets what is N = 10!.

    The number of arrangements in which one of A,B,C gets his correct prize is
    S_1 = \binom{3}{1} 9!
    because there are \binom{3}{1} ways to pick one of A,B,C and then there are 9! ways to arrange the remaining prizes.

    The number of arrangements in which two of A,B,C get their correct prizes is
    S_2 = \binom{3}{2} 8!.

    The number of arrangements in which all three of A,B,C get their correct prizes is
    S_3 = \binom{3}{3} 7!.

    By PIE, the number of arrangements in which none of A,B,C gets his correct prize is
    N - S_1 + S_2 - S_3
    = 10! -  \binom{3}{1} 9! + \binom{3}{2} 8! - \binom{3}{3} 7!.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: August 24th 2011, 04:09 PM
  2. elementary signal help please!
    Posted in the Advanced Applied Math Forum
    Replies: 0
    Last Post: January 12th 2009, 01:11 PM
  3. Elementary Algebra Help please
    Posted in the Algebra Forum
    Replies: 2
    Last Post: December 21st 2008, 08:50 PM
  4. Elementary Row Operations
    Posted in the Advanced Algebra Forum
    Replies: 13
    Last Post: June 10th 2008, 11:34 AM
  5. Is this elementary.
    Posted in the Calculus Forum
    Replies: 3
    Last Post: January 19th 2006, 07:00 PM

Search Tags


/mathhelpforum @mathhelpforum