PERMUTATIONS AND COMBINATIONS

Brief Overview

graph TD; A[Combinatorics] --> B[Permutations]; A --> C[Combinations]; B --> D[Order Matters]; C --> E[Order Does Not Matter]; D --> F[nPr = n! / n-r!]; E --> G[nCr = n! / r!n-r!];

Introduction

Permutations and Combinations are foundational concepts in combinatorics, a branch of mathematics concerned with counting, arranging, and selecting objects. These concepts are heavily used in probability, computer science, and statistics.

1. Fundamental Principle of Counting

Rule of Multiplication: If one event can occur in $m$ different ways, and a second event can occur in $n$ different ways, then the total number of ways both events can occur in sequence is $m \times n$.
Rule of Addition: If two events are mutually exclusive (cannot happen at the same time), and one can occur in $m$ ways while the other can occur in $n$ ways, the total number of ways either event can occur is $m + n$.

Numerical Example:
If you have 3 shirts and 4 pairs of pants, how many different outfits can you make?
Using the Rule of Multiplication: $3 \times 4 = 12$ outfits.

MCQs - Fundamental Principle of Counting

The Fundamental Principle of Counting primarily deals with:
a) Geometry
b) Finding the number of possible outcomes
c) Measuring distances
d) Solving algebraic equations
Answer: b
If a restaurant offers 4 appetizers and 5 main courses, how many combinations of one appetizer and one main course are possible?
a) 9
b) 20
c) 16
d) 25
Answer: b
The rule of addition in counting applies when:
a) Events happen one after another
b) Events are mutually exclusive (either/or)
c) Events are dependent
d) Dealing with fractions
Answer: b
A combination lock has 3 dials, each with digits 0-9. How many possible codes are there?
a) 30
b) 100
c) 1000
d) 300
Answer: c ($10 \times 10 \times 10$)
You can travel from City A to B by 3 different buses or 2 different trains. How many ways can you travel from A to B?
a) 6
b) 5
c) 9
d) 1
Answer: b (Rule of Addition: $3 + 2 = 5$)
A coin is tossed and a six-sided die is rolled. How many possible outcomes are there?
a) 8
b) 12
c) 36
d) 2
Answer: b
If you have 5 different pairs of shoes and 3 different hats, in how many ways can you select one pair of shoes and one hat?
a) 8
b) 15
c) 2
d) 125
Answer: b
A test consists of 5 true/false questions. How many different ways can the test be answered?
a) 10
b) 25
c) 32
d) 120
Answer: c ($2^5$)
How many 2-digit numbers can be formed using the digits 1, 2, 3, 4 if repetition of digits is allowed?
a) 8
b) 12
c) 16
d) 24
Answer: c
If an event can occur in $p$ ways and another independent event can occur in $q$ ways, the total ways both can occur is:
a) $p+q$
b) $p \times q$
c) $p/q$
d) $p-q$
Answer: b

2. Factorial Notation

Definition: The factorial of a non-negative integer $n$, denoted by $n!$, is the product of all positive integers less than or equal to $n$.
Formula: $n! = n \times (n-1) \times (n-2) \times \dots \times 1$.
Special Case: $0!$ is defined to be $1$.
Expansion: $n! = n \times (n-1)!$

Numerical Example:
Calculate $5!$.
$5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$.

MCQs - Factorial Notation

What is the value of $4!$?
a) 12
b) 16
c) 24
d) 40
Answer: c
By definition, what is the value of $0!$?
a) 0
b) 1
c) Undefined
d) Infinity
Answer: b
The expression $\frac{6!}{4!}$ simplifies to:
a) 1.5
b) 2
c) 30
d) 720
Answer: c ($ \frac{6 \times 5 \times 4!}{4!} = 30 $)
Which of the following is equivalent to $n!$?
a) $n \times (n-1)$
b) $n \times (n-1)!$
c) $(n+1)! / n$
d) $n^2$
Answer: b
What is the value of $3! \times 2!$?
a) 12
b) 5!
c) 6!
d) 36
Answer: a ($6 \times 2 = 12$)
Which expression is equal to $\frac{8!}{7!}$?
a) 1
b) 7
c) 8
d) 56
Answer: c
What is $1!$?
a) 0
b) 1
c) -1
d) Undefined
Answer: b
The value of $\frac{5!}{3!2!}$ is:
a) 5
b) 10
c) 15
d) 20
Answer: b
Find $n$ if $(n+1)! = 12 \times (n-1)!$.
a) 2
b) 3
c) 4
d) 5
Answer: b
What is $4! - 3!$?
a) 1
b) 18
c) 24
d) 6
Answer: b

3. Permutations (Arrangements)

Definition: A permutation is an arrangement of objects in a specific order. Order matters! (e.g., AB is different from BA).
Formula: The number of permutations of $n$ distinct objects taken $r$ at a time is denoted by $^nP_r$ or $P(n,r)$.
$^nP_r = \frac{n!}{(n-r)!}$

Numerical Example:
How many 3-letter words can be formed from the letters A, B, C, D, E without repetition?
Here $n=5$ and $r=3$.
$^5P_3 = \frac{5!}{(5-3)!} = \frac{5!}{2!} = \frac{120}{2} = 60$.

MCQs - Permutations

In permutations, which of the following is crucial?
a) Size of the objects
b) Color of the objects
c) Order of arrangement
d) Shape of the objects
Answer: c
The formula for $^nP_r$ is:
a) $\frac{n!}{r!}$
b) $\frac{n!}{(n-r)!}$
c) $\frac{n!}{r!(n-r)!}$
d) $n^r$
Answer: b
In how many ways can 4 people be seated in 4 chairs?
a) 4
b) 16
c) 24
d) 256
Answer: c ($^4P_4 = 4! = 24$)
Evaluate $^6P_2$:
a) 15
b) 30
c) 12
d) 360
Answer: b ($\frac{6!}{4!} = 6 \times 5 = 30$)
Which of the following scenarios is a permutation problem?
a) Picking a team of 3 from 10 people
b) Choosing 2 toppings for a pizza
c) Arranging 3 books on a shelf from a selection of 10
d) Selecting lottery numbers
Answer: c (Order matters on a shelf)
In how many ways can the letters of the word "CAT" be arranged?
a) 3
b) 6
c) 9
d) 27
Answer: b
What is the value of $^5P_0$?
a) 0
b) 1
c) 5
d) 120
Answer: b
A president, vice president, and secretary are chosen from a group of 8 people. How many different ways can these positions be filled?
a) 24
b) 336
c) 512
d) 56
Answer: b
Evaluate $^7P_3$:
a) 21
b) 35
c) 210
d) 840
Answer: c
How many 4-digit PIN codes can be formed from digits 0-9 without repetition?
a) 10000
b) 5040
c) 40
d) 3024
Answer: b

4. Combinations (Selections)

Definition: A combination is a selection of objects where the order does not matter. (e.g., selecting team AB is the same as selecting team BA).
Formula: The number of combinations of $n$ distinct objects taken $r$ at a time is denoted by $^nC_r$ or $C(n,r)$.
$^nC_r = \frac{n!}{r!(n-r)!} = \frac{^nP_r}{r!}$

Numerical Example:
How many different 3-person committees can be formed from a group of 5 people?
Here $n=5$ and $r=3$. Order doesn't matter for a committee.
$^5C_3 = \frac{5!}{3!(5-3)!} = \frac{120}{6 \times 2} = 10$.

MCQs - Combinations

In combinations, unlike permutations, what is ignored?
a) The total number of items
b) The order of items
c) The size of the selection
d) The formula
Answer: b
The formula for $^nC_r$ is:
a) $\frac{n!}{(n-r)!}$
b) $\frac{n!}{r!(n-r)!}$
c) $n! \times r!$
d) $\frac{n!}{r!}$
Answer: b
Evaluate $^5C_2$:
a) 20
b) 10
c) 60
d) 120
Answer: b ($\frac{5 \times 4}{2 \times 1} = 10$)
Which scenario represents a combination?
a) Creating a password
b) Determining the batting order in baseball
c) Dealing a 5-card poker hand from a deck
d) Awarding 1st, 2nd, and 3rd place medals
Answer: c (Order of cards in hand doesn't matter)
What is the relationship between $^nC_r$ and $^nP_r$?
a) $^nC_r = ^nP_r \times r!$
b) $^nP_r = ^nC_r \times r!$
c) $^nC_r = ^nP_r$
d) They are unrelated
Answer: b
In how many ways can a team of 4 players be chosen from 10 players?
a) 40
b) 210
c) 5040
d) 24
Answer: b
What is the value of $^7C_7$?
a) 0
b) 1
c) 7
d) 49
Answer: b
If $^nC_2 = 15$, find $n$.
a) 5
b) 6
c) 7
d) 8
Answer: b
Which property holds true for combinations?
a) $^nC_r = ^nC_{n-r}$
b) $^nC_r = n \times ^nC_{r-1}$
c) $^nC_r = ^nP_r$
d) $^nC_r = r!$
Answer: a
How many lines can be drawn passing through 2 points out of 5 non-collinear points?
a) 5
b) 10
c) 20
d) 25
Answer: b

Fun Facts about Permutations and Combinations!

The Enigma Machine: During WWII, the German Enigma machine relied on permutations. The number of possible configurations was approximately $158,000,000,000,000,000,000$ (158 quintillion)! Alan Turing's team had to break these permutations to win the war.
Shuffling Cards: There are $52!$ ways to arrange a standard deck of cards. That number is so massively huge ($8 \times 10^{67}$) that every time you shuffle a deck properly, it is almost certain that specific arrangement has never existed before in the history of the universe!
Rubik's Cube: A standard $3\times3$ Rubik's Cube has $43,252,003,274,489,856,000$ valid permutations. Despite this, it can always be solved in 20 moves or fewer (known as "God's Number").

Permutations And Combinations