Choose from 5 items Put them into 3 boxes _____ _____ _____ | 5 | | 4 | | 3 | |_____| |_____| |_____| Box 1 Box 2 Box 3
\[ \boxed{ \begin{array}{rrrrrrrrrr} ^{n}P_{k} &= &\frac{ \begin{array}{rrrrrrrrrr} n! \end{array} } { \begin{array}{rrrrrrrrrr} (n-k)! \end{array} } \end{array} } \]
Number of Ways to From 5 distinct items Permutate (Select and Arrange) 3 distinct items = 5 Permuate 3 = P(5,3) = [#ways] [#ways] [#ways] [items] [items] [items] [box 1] * [box 2] * [box 3] = 5 * 4 * 3 = 60
\[ \\\\\\\\ \\\\\\\\ \]
\[ \begin{array}{ccc} ^{5}P_{3} &= &\begin{array}{lll} 5 &\cdot &4 &\cdot &3 \\\\ \end{array} \\\\ &= &\frac{ \begin{array}{rrrrrrrrrr} 5 &\cdot &4 &\cdot &3 &\cdot &2 &\cdot &1 \end{array} } { \begin{array}{rrrrrrrrrr} &&&&&&& 2 &\cdot &1 \end{array} } \\\\ &= &\frac{ \begin{array}{rrrrrrrrrr} 5! \end{array} } { \begin{array}{rrrrrrrrrr} 2! \end{array} } \\\\ ^{5}P_{3} &= &\frac{ \begin{array}{rrrrrrrrrr} 5! \end{array} } { \begin{array}{rrrrrrrrrr} (5-3)! \end{array} } \\\\ ^{n}P_{k} &= &\frac{ \begin{array}{rrrrrrrrrr} n! \end{array} } { \begin{array}{rrrrrrrrrr} (n-k)! \end{array} } \\\\ \end{array} \]
\[ \boxed{ \begin{array}{rrrrrrrrrr} ^{n}P_{k} &= &\frac{ \begin{array}{rrrrrrrrrr} n! \end{array} } { \begin{array}{rrrrrrrrrr} (n-k)! \end{array} } \end{array} } \]
\[ \boxed{ \begin{array}{rrrrrrrrrr} ^{n}C_{k} &= &\frac{ \begin{array}{rrrrrrrrrr} n! \end{array} } { \begin{array}{rrrrrrrrrr} k! \cdot (n-k)! \end{array} } \end{array} } \]
Divide by the number of ways we OVERCOUNTED earlier
__________ __________ __________
| | | | | |
| Box ? | | Box ? | | Box ? |
| | | | | |
|__________| |__________| |__________|
Posi 1 Posi 2 Posi 3
Choose from:
_____ _____ _____
| | | | | |
|_____| |_____| |_____|
Box 1 Box 2 Box 3
Number of Ways to From 5 distinct items Combine (Select Only) 3 distinct items = 5 Choose 3 = C(5,3) = [#ways] [#ways] [#ways] / ( [#ways] * [#ways] * [#ways] ) [items] [items] [items] [boxes] [boxes] [boxes] [box 1] * [box 2] * [box 3] [posi1] * [posi2] * [posi3] = 5 * 4 * 3 / ( 3 * 2 * 1 ) = 60 / 6 = 10
\[ \\\\\\\\ \\\\\\\\ \]
\[ \begin{array}{ccc} ^{5}C_{3} &= &\frac{ \begin{array}{rrrrrrrrrr} 5 &\cdot &4 &\cdot &3 &\cdot &2 &\cdot &1 \end{array} } { \begin{array}{rrrrrrrrrr} &(3\cdot 2\cdot 1) &\cdot & (2 \cdot 1) \end{array} } \\\\ ^{5}C_{3} &= &\frac{ \begin{array}{rrrrrrrrrr} 5! \end{array} } { \begin{array}{rrrrrrrrrr} 3! \cdot 2! \end{array} } \\\\ ^{5}C_{3} &= &\frac{ \begin{array}{rrrrrrrrrr} 5! \end{array} } { \begin{array}{rrrrrrrrrr} 3! \cdot (5-3)! \end{array} } \\\\ ^{n}C_{k} &= &\frac{ \begin{array}{rrrrrrrrrr} n! \end{array} } { \begin{array}{rrrrrrrrrr} k! \cdot (n-k)! \end{array} } \\\\ ^{n}C_{k} &= &\frac{ \begin{array}{rrrrrrrrrr} 1 \end{array} } { \begin{array}{rrrrrrrrrr} k! \end{array} } \cdot \frac{ \begin{array}{rrrrrrrrrr} n! \end{array} } { \begin{array}{rrrrrrrrrr} (n-k)! \end{array} } \\\\ ^{n}C_{k} &= &\frac{ \begin{array}{rrrrrrrrrr} 1 \end{array} } { \begin{array}{rrrrrrrrrr} k! \end{array} } \cdot ^{n}P_{k} \\\\ \end{array} \]
\[ \boxed{ \begin{array}{rrrrrrrrrr} ^{n}C_{k} &= &\frac{ \begin{array}{rrrrrrrrrr} n! \end{array} } { \begin{array}{rrrrrrrrrr} k! \cdot (n-k)! \end{array} } \end{array} } \]
There are 5 seats in a front row to be seated with students. There are 10 unique students, of which 3 are naughty, 7 are good. Any of the 10 unique students can be chosen to sit at the front row. The 3 naughty students have to be seated in the front row. Naughty students have to be separated by at least 1 good student. How many different possible arrangements are there for the front row?
Case 1: Minimal 5 Seats
T = 10 = Total students
N = 3 = Naughty students cannot be together = Need 2 bars
G = 7 = Good students to separate the Naughty = To fill the seats
S = 5 = Number of seats in a row
= * | * | *
N N N
G G
--------------------------------
General Method: Stars and Bars
--------------------------------
# Ways = (Fr 3 stars Choose 3 Seats for N)
* (Arrange 3 N)
* (Fr 7 Select and Arrange 2 bars)
= 3C3
* (3 * 2 * 1)
* (7 * 6)
= 1
* 6
* 42
= 252
Case 1: Minimal 5 Seats
T = 10 = Total students
N = 3 = Naughty students cannot be together = Need 2 bars
G = 7 = Good students to separate the Naughty = To fill the seats
S = 5 = Number of seats in a row
= * | * | *
N N N
G G
--------------------------------
Logic Method
--------------------------------
* | * | *
3 2 1 ==> 6
7 6 ==> 42
# Ways = 6 * 42
= 252
There are 6 seats in a front row to be seated with students. There are 10 unique students, of which 3 are naughty, 7 are good. Any of the 10 unique students can be chosen to sit at the front row. The 3 naughty students have to be seated in the front row. Naughty students have to be separated by at least 1 good student. How many different possible arrangements are there for the front row?
Case 2: Minimal 5 Seats + 1 Seat
T = 10 = Total students
N = 3 = Naughty students cannot be together = Need 2 bars
G = 7 = Good students to separate the Naughty = To fill the seats
S = 6 = Number of seats in a row
= * | * | * *
N N N
G G G
--------------------------------
General Method: Stars and Bars
--------------------------------
# Ways = (Fr 4 stars Choose 3 Seats for N)
* (Arrange 3 N)
* (Fr 7 Select and Arrange in remaining 3 seats)
= 4C3
* (3 * 2 * 1)
* (7 * 6 * 5)
= (4 * 3 * 2) / (3 * 2 * 1)
* 6
* 210
= 4
* 6
* 210
= 5040
Case 2: Minimal 5 Seats + 1 Seat
T = 10 = Total students
N = 3 = Naughty students cannot be together = Need 2 bars
G = 7 = Good students to separate the Naughty = To fill the seats
S = 6 = Number of seats in a row
= * | * | * *
N N N
G G G
--------------------------------
Logic Method
--------------------------------
* | * | * *
3 2 1 ==> 6
7 6 5 ==> 210
N N N
G N N N ==> 4 ways for extra G seat
N G N N
N N G N
N N N G
# Ways = 6 * 210 * 4
= 5040
There are 7 seats in a front row to be seated with students. There are 10 unique students, of which 3 are naughty, 7 are good. Any of the 10 unique students can be chosen to sit at the front row. The 3 naughty students have to be seated in the front row. Naughty students have to be separated by at least 1 good student. How many different possible arrangements are there for the front row?
Case 2: Minimal 5 Seats + 2 Seats
T = 10 = Total students
N = 3 = Naughty students cannot be together = Need 2 bars
G = 7 = Good students to separate the Naughty = To fill the seats
S = 7 = Number of seats in a row
= * | * | * * *
N N N
G G G G
--------------------------------
General Method: Stars and Bars
--------------------------------
# Ways = (Fr 5 stars Choose 3 Seats for N)
* (Arrange 3 N)
* (Fr 7 Select and Arrange in remaining 4 seats)
= 5C3
* (3 * 2 * 1)
* (7 * 6 * 5 * 4)
= (5 * 4 * 3) / (3 * 2 * 1)
* 6
* 840
= 10
* 6
* 840
= 50,400
Case 2: Minimal 5 Seats + 2 Seats
T = 10 = Total students
N = 3 = Naughty students cannot be together = Need 2 bars
G = 7 = Good students to separate the Naughty = To fill the seats
S = 6 = Number of seats in a row
= * | * | * * *
N N N
G G G G
--------------------------------
Logic Method
--------------------------------
* | * | * * *
3 2 1 ==> * 6
7 6 5 4 ==> * 840
N N N
1 2 3 4 ==> * 4 ways to place the 1st extra seat
1 2 3 4 5 ==> * 5 ways to place the 2nd extra seat
/ 2! since we don't differentiate
which extra seat goes first
= 6 * 840 * 4 * 5 / 2!
= 50,400