Notes on Permutations and Combinations

6.1 Introduction

The chapter begins with a practical problem regarding a number lock with digits labeled from 0-9. The objective is to calculate potential sequences for unlocking the suitcase given a partial digit. This scenario emphasizes the need for counting techniques which will be discussed throughout the chapter.

6.2 Fundamental Principle of Counting

The Fundamental Principle of Counting illustrates that if one event can occur in m ways and a second event can occur in n ways, then the total ways the events can happen in succession is m x n. This principle can be extended to more than two events. For instance,

• Example: Mohan with 3 pants and 2 shirts has 3 x 2 = 6 combinations.
• Generalization: For r events, the count becomes m1 x m2 x ... x mr.

6.2.1 Examples

1. If an event can happen in 4 ways and another in 3 ways: 4 x 3 = 12.
2. The arrangement of items can be built upon this principle to calculate complex combinations without listing them.

6.3 Permutations

Definition

A permutation is defined as a specific arrangement of objects where order is important. If you need to find permutations of n objects taking r at a time without repetition, the formula is given as:

6.3.1 Permutations of Distinct Objects

• Theorem 1: Number of permutations of n different objects taken r at a time is denoted by

  P(n, r) = n! / (n - r)!

Example: Arranging 4 letters from the word ROSE. Without repetition, the count is 4! = 24.

6.3.2 Factorial Notation

Factorials are essential in permutations: n! = n x (n-1) x (n-2)...3 x 2 x 1. Special cases are defined with: 0! = 1.

6.3.3 Permutations with Repetition

When repetition is allowed:

• Theorem 2: Number of permutations of n objects taken r at a time is given by:

  P(n, r) = n^r

Example: Arranging 3 letters from the alphabet where letters can repeat results in 26^3.

6.3.4 Permutations with Non-Distinct Objects

To find permutations when some objects are indistinguishable:

• Theorem: Number of permutations of n objects, with p1 indistinguishable of one kind, p2 of another, ... is given by:

  n! / (p1! x p2! ...)

Example: Arranging letters in ALLAHABAD, calculate as 9! / (4! x 2!) = 7560.

6.4 Combinations

Combinations are selections where order does not matter. The formula for combinations of n different objects taken r at a time is:

• Theorem:

  C(n, r) = n! / (r!(n - r)!)

Example: Selecting 3 lawn tennis players from 5 indicates C(5, 3) = 10.

The relationship between combinations and permutations is critical:

• Theorem 5: nP = nC * r!
• This signifies a direct correlation for counting

Exercise and Applications

Multiple examples ranged from organizing items to forming teams, calculating handshakes, or finding distinct arrangements of words. Exercises reinforce the broader understanding of principles and their application in variable scenarios.

Historical Context

The chapter concludes with a historical overview of permutations and combinations tracing back to Jain mathematicians and other ancient scholars who laid the groundwork for these concepts in mathematics, culminating in formal recognition and formula derivation by figures like Jacob Bernoulli.

1. Fundamental Principle of Counting: If an event can occur in m ways followed by n ways, total ways is m × n.
2. Permutations: Arrangements where order matters; calculated as P(n, r) = n! / (n - r)!.
3. Factorial Notation: n! represents the product of all natural numbers up to n; 0! = 1.
4. Permutations with Repetition: When allowed, P(n, r) = n^r for arranging r items with n options.
5. Non-Distinct Permutations: Objects of the same kind reduce total arrangements via n! / (p1! p2! ...).
6. Combinations: The selections where order does not matter, given by C(n, r) = n! / (r!(n - r)!).
7. Relationship: nP = nC × r! relates permutations and combinations.
8. Historical Significance: Long history with contributions from various cultures including Bharat and ancient Greeks.
9. Basic exercises reinforce counting techniques applicable to real-world problems.
10. Emphasizes practical applications of permutations and combinations in statistics, probability, and everyday counting problems.