# Thread: Elementary Combinatorics

1. ## 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.

2. Originally Posted by riemann
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!$.