Neural Sync Active

Week 6: Permutations & Combinations

Registry Synced

Week 6: Permutations & Combinations

2849 words

14 min read

2026-09-12

Reading compass

Now · TL;DR

Statistics for Data Science I — Week 6: Permutations & Combinations

IITM’s Week 6 continues counting with permutations and combinations.

TL;DR

The central question is:

Does order matter?

If yes:

\boxed{\text{Permutation}}

If no:

\boxed{\text{Combination}}

The core formulas are:

\boxed{ {}^nP_r=\frac{n!}{(n-r)!} }

and

\boxed{ {}^nC_r=\frac{n!}{r!(n-r)!} }

1. Permutation

A permutation is an ordered arrangement.

Example: choose 2 people from A, B, C for:

president
vice-president

Then:

(A,B)\neq(B,A)

because the roles differ.

So order matters.

2. Permutation formula

Selecting and arranging

r

objects from

n

distinct objects:

\boxed{ {}^nP_r= \frac{n!}{(n-r)!} }

3. Why the formula works

First position:

n

choices.

Second:

n-1.

Continue for

r

positions:

n(n-1)(n-2)\cdots(n-r+1).

That equals:

\frac{n!}{(n-r)!}.

4. Example

Arrange 3 people from 8 people in three distinct roles.

{}^8P_3 = \frac{8!}{5!}

=8\cdot7\cdot6

\boxed{336}

5. Permuting all objects

If:

r=n,

then:

{}^nP_n = \frac{n!}{0!}.

Since:

0!=1,

we get:

\boxed{ {}^nP_n=n! }

6. Combination

A combination is a selection where order does not matter.

Suppose we choose 2 people from:

A,B,C.

For a committee:

\{A,B\}=\{B,A\}.

So these should count as one outcome.

7. Combination formula

Choosing

r

objects from

n

distinct objects:

\boxed{ {}^nC_r= \binom nr = \frac{n!}{r!(n-r)!} }

8. Why divide by $r!$ ?

Start with permutations:

{}^nP_r.

Each unordered group of

r

selected objects has been counted:

r!

times because those objects can be arranged internally in

r!

orders.

Therefore:

{}^nC_r = \frac{{}^nP_r}{r!}.

So:

\boxed{ {}^nP_r = {}^nC_r\,r! }

9. Example

Choose 3 students from 8 for a committee.

{}^8C_3 = \frac{8!}{3!5!}.

Cancel:

= \frac{8\cdot7\cdot6}{3\cdot2\cdot1}

=56.

Thus:

\boxed{56}

10. Same people, different problem

This distinction is critical.

Committee of 3 from 8

Order doesn't matter:

{}^8C_3=56.

President, VP, secretary from 8

Order/role matters:

{}^8P_3=336.

Same people. Different structure.

11. Fast decision test

Ask:

If I swap two selected objects, does the outcome change?

If yes:

\boxed{\text{Permutation}}

If no:

\boxed{\text{Combination}}

12. Combination symmetry

A useful identity:

\boxed{ \binom nr=\binom n{n-r} }

Why?

Choosing

r

objects to include is equivalent to choosing:

n-r

objects to exclude.

Example:

\binom{10}{3} = \binom{10}{7}.

13. Extreme combination values

\boxed{ \binom n0=1 }

There is exactly one way to choose nothing.

Also:

\boxed{ \binom nn=1 }

There is exactly one way to choose everything.

And:

\boxed{ \binom n1=n }

14. Example: choose 2

\binom n2 = \frac{n!}{2!(n-2)!}

so:

\boxed{ \binom n2= \frac{n(n-1)}2 }

This is the same formula that appeared for the number of edges in a complete undirected graph.

Nice connection to Maths 1.

15. Pascal identity

An important identity:

\boxed{ \binom nr = \binom{n-1}{r} + \binom{n-1}{r-1} }

Intuition: distinguish one special object.

Either:

it is not chosen
it is chosen

Those cases are disjoint and exhaustive.

16. Example of Pascal identity

\binom53 = \binom43+\binom42.

Numerically:

10=4+6.

Correct.

17. Pascal triangle

Combination numbers form Pascal's triangle:


text
        1
      1   1
    1   2   1
  1   3   3   1
1   4   6   4   1

Each interior number equals the sum of the two directly above it.

18. Sum of one row

For row corresponding to

n

\boxed{ \sum_{r=0}^{n} \binom nr = 2^n }

Why?

Every element of an

n

-element set is either:

selected
not selected

So total subsets:

2^n.

This reconnects to the power-set result from Maths 1.

19. Binomial theorem connection

The coefficients in:

(a+b)^n

are combinations:

\boxed{ (a+b)^n = \sum_{r=0}^{n} \binom nr a^{n-r}b^r }

Example:

(a+b)^3 = a^3+3a^2b+3ab^2+b^3.

Coefficients:

1,3,3,1.

20. Repetition allowed: ordered selections

Suppose you choose

r

items, each time from

n

possibilities, and repetition is allowed.

If order matters:

\boxed{ n^r }

Example: 4-digit PIN:

10^4.

21. Repetition forbidden: ordered selections

If repetition is not allowed and order matters:

\boxed{ {}^nP_r }

Example: 4 distinct digits chosen from 10:

{}^{10}P_4.

22. Repetition forbidden: unordered selections

If repetition is forbidden and order does not matter:

\boxed{ {}^nC_r }

Example: choose 4 students from 10:

\binom{10}{4}.

23. Core counting grid

Order matters?	Repetition?	Count
yes	yes	$n^r$
yes	no	${}^nP_r$
no	no	${}^nC_r$

The "no order + repetition allowed" case exists too, but it uses a different formula and may be beyond the immediate core depending on course coverage.

24. Combinations with repetition

If you choose

r

items from

n

categories, order does not matter, and repetition is allowed, the count is:

\boxed{ \binom{n+r-1}{r} }

This is often called stars and bars.

Treat it as supplementary unless emphasized in your lectures.

25. Stars and bars intuition

Suppose we need nonnegative integer solutions to:

x_1+x_2+x_3=5.

Represent 5 identical objects as:


text
*****

Use 2 separators:


text
**|*|**

meaning:

x_1=2,\quad x_2=1,\quad x_3=2.

There are:

5+3-1=7

positions containing:

5 stars
2 bars

So number of solutions:

\binom72.

26. Arrangements with repeated identical objects

Suppose there are:

n

objects with repetitions:

n_1,n_2,\dots,n_k

where:

n_1+\cdots+n_k=n.

Distinct permutations:

\boxed{ \frac{n!}{n_1!n_2!\cdots n_k!} }

27. Example: BANANA

BANANA has:

6

letters.

Counts:

A: 3
N: 2
B: 1

Distinct arrangements:

\frac{6!}{3!2!}

= \frac{720}{12}

\boxed{60}

28. Why divide by repeated factorials

If identical copies were artificially labeled, swapping them would produce fake "new" permutations.

We divide by all such internal rearrangements:

n_1!n_2!\cdots n_k!.

29. Circular permutations

For

n

distinct objects arranged around a circle, rotationally equivalent arrangements are usually treated as the same.

Then:

\boxed{ (n-1)! }

30. Why circular arrangements use $(n-1)!$

For linear arrangements:

n!.

But each circular arrangement can be rotated into:

n

linear descriptions.

Therefore:

\frac{n!}{n} = (n-1)!.

31. Example

6 people around a round table:

(6-1)! = 5! = 120.

32. Selection with mandatory members

Suppose a committee of 4 is chosen from 10 people, and Alice must be included.

Alice is fixed.

Choose the remaining:

3

members from:

9.

So:

\boxed{ \binom93 }

33. Selection excluding someone

Committee of 4 from 10, but Alice cannot be selected.

Then effectively choose:

4

from remaining:

9.

So:

\boxed{ \binom94 }

34. At least one special member

Suppose 4 people are chosen from 10, including 3 women and 7 men.

How many committees contain at least one woman?

Direct counting has several cases:

1 woman
2 women
3 women

Complement is easier.

Total committees:

\binom{10}{4}.

No women:

\binom74.

So:

\boxed{ \binom{10}{4}-\binom74 }

35. Exactly $k$ special members

Suppose choose 5 people from:

6 women
8 men

with exactly 2 women.

Choose women:

\binom62.

Choose men:

\binom83.

Multiply:

\boxed{ \binom62\binom83 }

Because both choices must happen.

36. Why multiply combinations here?

The choices are sequential independent stages:

choose women
choose men

Each resulting pair of selections creates one committee.

So use the multiplication principle.

37. At most / at least language

These phrases matter.

Exactly 2

Only:

2.

At least 2

2,3,4,\dots

At most 2

0,1,2.

A major source of mistakes is reading these casually.

38. Example: at most 2 women

Committee of 4 from 5 women and 6 men.

At most 2 women means:

0 women
1 woman
2 women

Count:

\binom50\binom64 + \binom51\binom63 + \binom52\binom62.

39. Block method for arrangements

Suppose 6 people line up and A/B must stand together.

Treat A/B as one block.

Then we have:

block AB
4 other people

So:

5!

block arrangements.

A and B can internally swap:

2!

Thus:

\boxed{ 5!\cdot2 }

40. Multiple blocks

Suppose:

A and B must be together
C and D must be together

among 6 people.

Treat:

[AB],[CD],E,F

as 4 objects.

Arrange blocks:

4!.

Internal orders:

2!\cdot2!.

Total:

\boxed{ 4!\cdot2\cdot2 }

41. "Not together"

Often:

\boxed{ \text{not together} = \text{all} - \text{together} }

For 6 people, A and B not together:

Total:

6!.

Together:

5!\cdot2.

Thus:

\boxed{ 6!-2(5!) }

42. Fixed positions

Suppose 7 people line up and A must stand at one end.

A has:

2

possible ends.

Remaining 6 people:

6!

arrangements.

Total:

\boxed{ 2\cdot6! }

43. A and B at the ends

If A and B must occupy the two ends:

Arrange A and B at ends:

2!

ways.

Arrange remaining:

(n-2)!

ways.

Total:

\boxed{ 2(n-2)! }

44. No two special objects adjacent

A useful gap method.

Suppose:

4 men
3 women
no two women adjacent

First arrange men:

4!.

This creates gaps:


text
_ M _ M _ M _ M _

Number of gaps:

5.

Choose 3 gaps for women:

\binom53.

Arrange 3 women:

3!.

Total:

\boxed{ 4!\binom53 3! }

45. Why gap method works

Placing at most one special object in each gap guarantees no two are adjacent.

This is a general restriction technique worth remembering.

46. Probability bridge

Suppose 5 cards are chosen from 52, with order irrelevant.

Total possible hands:

\boxed{ \binom{52}{5} }

This is why combinations are central to probability.

If every hand is equally likely:

P(E) = \frac{\text{favorable combinations}} {\binom{52}{5}}.

47. Example: exactly 2 special objects

Suppose a set has:

4 special items
6 ordinary items

Choose 3.

How many selections contain exactly 2 special items?

Choose:

2

from the 4 special:

\binom42.

Choose:

1

from the 6 ordinary:

\binom61.

Thus:

\boxed{ \binom42\binom61 }

48. Complement with combinations

Suppose we choose 3 people from 10 and want at least one of A or B.

Total:

\binom{10}{3}.

Committees containing neither A nor B:

\binom83.

So desired:

\boxed{ \binom{10}{3}-\binom83 }

49. Exactly one of A and B

Two disjoint cases:

A included, B excluded
B included, A excluded

For committee size 3 from 10:

Choose which one of A/B:

2

ways.

Then choose remaining 2 members from the other 8 people:

\binom82.

So:

\boxed{ 2\binom82 }

50. Both A and B included

For committee size 4 from 10:

Fix A and B.

Choose remaining:

2

from other:

8.

Count:

\boxed{ \binom82 }

51. Neither A nor B

Choose all 4 from remaining 8:

\boxed{ \binom84 }

These "both / exactly one / neither" patterns are common.

52. Permutation with restrictions example

How many 5-digit numbers can be formed using digits:

1,2,3,4,5

exactly once?

All digits are distinct and order matters:

5!=120.

53. Same problem with first digit restriction

How many start with an even digit?

Even first digit:

2\text{ or }4

so:

2

choices.

Remaining:

4!

orders.

Total:

2\cdot4!=48.

54. Same problem ending in odd digit

Odd choices:

1,3,5

so:

3

choices for final digit.

Remaining:

4!

arrangements.

Thus:

\boxed{72}

Common mistake: using permutation for a committee

Committee members have no roles unless stated.

So:

\binom nr

not:

{}^nP_r.

Common mistake: using combination for ranks

Gold, silver, bronze are ordered positions.

So:

{}^nP_3

not:

\binom n3.

Common mistake: dividing by

r!

twice

Combination already includes the:

r!

division.

Do not compute:

\binom nr/r!

again unless a separate symmetry genuinely requires it.

Common mistake: forgetting internal block arrangements

If A and B must be together, treating them as one block gives positions of the block but not internal order.

Usually multiply by:

2!

for:

AB

or:

BA.

Common mistake: cases overlap

If solving by cases, cases must ideally be mutually exclusive.

For example:

exactly 1 woman
exactly 2 women

do not overlap.

So counts can be added safely.

But:

at least 1 woman
at least 2 women

overlap heavily.

Adding them directly double-counts.

Common mistake: forgetting impossible cases

Suppose choose 5 people with exactly 4 women when only 3 women exist.

That case contributes:

0.

Always check feasibility before applying formulas.

61. Simplifying combinations efficiently

Example:

\binom{100}{2}.

Do not expand

100!

Use:

\binom n2 = \frac{n(n-1)}2.

So:

\binom{100}{2} = \frac{100\cdot99}{2} = 4950.

62. Another simplification

\binom{20}{18}

Use symmetry:

\binom{20}{18} = \binom{20}{2}.

Thus:

= 190.

Much easier.

63. Master decision tree


text
What am I counting?
│
├── Sequence / roles / ranks?
│      │
│      ├── repetition allowed → n^r
│      └── repetition forbidden → nPr
│
└── Group / committee / subset?
       │
       ├── repetition forbidden → nCr
       └── repetition allowed → stars-and-bars style

Then separately ask:

restrictions?
must include/exclude?
together/apart?
exactly/at least/at most?

64. Core formula sheet

Factorial

\boxed{ n!=n(n-1)\cdots1 }

Permutation

\boxed{ {}^nP_r = \frac{n!}{(n-r)!} }

Combination

\boxed{ {}^nC_r = \binom nr = \frac{n!}{r!(n-r)!} }

Relation

\boxed{ {}^nP_r = {}^nC_r\,r! }

Symmetry

\boxed{ \binom nr=\binom n{n-r} }

Repeated arrangements

\boxed{ \frac{n!}{n_1!n_2!\cdots n_k!} }

Circular permutation

\boxed{ (n-1)! }

65. Week 5 → Week 6 connection

Week 5 gave the fundamental counting principles:

\text{add} \quad\text{and}\quad \text{multiply}.

Week 6 packages recurring counting patterns into reusable formulas:

\boxed{ \text{ordered selection} \rightarrow {}^nP_r }

\boxed{ \text{unordered selection} \rightarrow {}^nC_r }

These become essential once probability begins.

66. What you should actually master

By the end of Stats 1 Week 6, you should be able to:

Decide whether order matters.
Compute permutations.
Compute combinations.
Explain why combinations divide by $r!$ .
Use: ${}^nP_r={}^nC_r\,r!.$
Use symmetry: $\binom nr=\binom n{n-r}.$
Solve committee and ranking problems.
Handle required/excluded members.
Handle exactly / at least / at most restrictions.
Use complement counting.
Count arrangements with repeated identical objects.
Solve basic together/not-together arrangements.
Use block and gap methods when appropriate.
Avoid overcounting.

If those are comfortable, Stats 1 Week 6 is under control.

Quick Recall & Flashcards

Test your active recall before proceeding to practice problems. Format:

Question :: Answer.

Week 6 Diagnostic: In how many ways can a committee of 3 members be selected from a group of 7 candidates? :: Answer: 35 — C(7, 3) = 7! / (3! * 4!) = (7 * 6 * 5) / (3 * 2 * 1) = 35.
Week 6 Diagnostic: In how many ways can 5 distinct books be arranged on a single shelf? :: Answer: 120 — P(5, 5) = 5! = 120.

Practice & Self-Check

Attempt these diagnostic questions to verify your operational understanding.

Question 1

In how many ways can a committee of 3 members be selected from a group of 7 candidates?

NAT

3 Unit Assessment

Question 2

In how many ways can 5 distinct books be arranged on a single shelf?

NAT

3 Unit Assessment