Chapter 7 Permutations and Combinations (Concepts)

Fundamental Principle of Counting

Permutations and Combinations are mathematical concepts that deal with counting possible arrangements and selections of objects from a set. The foundation of these topics lies in the basic rules of counting, collectively known as the Fundamental Principle of Counting (FPC).

The FPC helps us determine the total number of outcomes for a complex event by breaking it down into simpler events or decisions. It consists of two main principles: the Multiplication Principle and the Addition Principle.

Multiplication Principle

The Multiplication Principle applies when a task is performed in a sequence of stages or steps. It is used to find the total number of outcomes when events happen one after another (using the keyword "AND").

Principle: If a first task can be performed in $n_1$ ways, and a second task can be performed in $n_2$ ways, then the total number of ways to perform the first task AND the second task is the product:

Examples of the Multiplication Principle

Example A: Creating an Outfit

A person has 3 different shirts and 4 different pairs of pants. How many different outfits can they create?

To create an outfit, the person must choose a shirt AND choose a pair of pants.

• Number of ways to choose a shirt = 3.
• Number of ways to choose pants = 4.

By the Multiplication Principle, the total number of outfits is:

Example B: Forming a Code (Without Repetition)

How many 4-letter codes can be formed using the first 10 letters of the alphabet if no letter can be repeated?

We have four positions to fill:

• 1st position: 10 choices.
• 2nd position: 9 choices (one letter is used).
• 3rd position: 8 choices (two letters are used).
• 4th position: 7 choices (three letters are used).

Total codes = $10 \times 9 \times 8 \times 7 = 5040$.

Example C: Forming a Number (With Repetition)

How many 3-digit numbers can be formed using the digits 0, 1, 2, 3, 4, 5 if repetition is allowed?

We have three positions to fill: Hundreds, Tens, and Units.

• Hundreds place: 5 choices (cannot be 0).
• Tens place: 6 choices (0 is now allowed, repetition is okay).
• Units place: 6 choices.

Total 3-digit numbers = $5 \times 6 \times 6 = 180$.

Addition Principle

The Addition Principle applies when we have a choice between two or more mutually exclusive options. It is used to find the total number of outcomes when we can do one task OR another (using the keyword "OR").

Principle: If a task can be performed in $n_1$ ways, and another, mutually exclusive task can be performed in $n_2$ ways, then the total number of ways to perform either the first task OR the second task is the sum:

Examples of the Addition Principle

Example D: Choosing a Class Representative

A class has 15 boys and 12 girls. In how many ways can one student be selected as a representative?

The representative can be a boy OR a girl. These two choices are mutually exclusive.

• Number of ways to choose a boy = 15.
• Number of ways to choose a girl = 12.

By the Addition Principle, the total number of ways to choose a representative is:

Example E: Choosing a Mode of Transport

A person can travel from city A to city B by one of 3 buses or by one of 2 trains. In how many ways can they travel from A to B?

The person can travel by bus OR by train. The choices are mutually exclusive.

• Number of ways to travel by bus = 3.
• Number of ways to travel by train = 2.

Total ways = $3 + 2 = 5$.

Combining the Principles

Many counting problems require using both principles together.

Example F: Choosing a President and Vice-President

From a group of 6 boys and 8 girls, a President and a Vice-President are to be selected such that one is a boy and the other is a girl.

This problem has two mutually exclusive cases (Addition Principle), and each case involves a sequence of choices (Multiplication Principle).

• Case 1: President is a Boy AND Vice-President is a Girl.

  Number of ways = (Ways to choose a boy) $\times$ (Ways to choose a girl) = $6 \times 8 = 48$.

• Case 2: President is a Girl AND Vice-President is a Boy.

  Number of ways = (Ways to choose a girl) $\times$ (Ways to choose a boy) = $8 \times 6 = 48$.

The final selection can be from Case 1 OR Case 2. Since these cases are mutually exclusive, we add their outcomes:

Factorial Notation

In the realm of counting arrangements and selections, we frequently encounter the product of a sequence of decreasing positive integers. To simplify the representation of such products, we use factorial notation. This notation is fundamental to the formulas for permutations and combinations.

Definition of Factorial

For any positive integer $n$, the factorial of $n$, denoted by $n!$ (read as "n factorial"), is defined as the product of all positive integers from 1 up to $n$.

Let's calculate the factorials for the first few positive integers:

Recursive Relation

From the definition of $n!$, we can see a relationship between the factorial of $n$ and the factorial of $n-1$.

This gives us the very useful recursive relation:

This relation allows us to break down larger factorials, which is key to simplifying expressions. For example, $10! = 10 \times 9!$.

Factorial of Zero

The definition of factorial applies to positive integers. To make the recursive relation $n! = n \times (n-1)!$ consistent for the case when $n=1$, we need to define a value for $0!$.

Let's use the recursive formula with $n=1$:

Since we know that $1! = 1$, the equation becomes:

For this to be true, $0!$ must be equal to 1. Therefore, by definition:

This definition is crucial for the formulas of permutations and combinations to work correctly in all cases.

Usage and Properties

$n!$ represents the number of ways to arrange $n$ distinct objects in a sequence (a permutation of $n$ objects).

Factorial notation is defined only for non-negative integers ($0, 1, 2, 3, \dots$). It is not defined for negative integers or fractions.

Answer:

Answer:

Permutations

In combinatorics, we often need to count the number of ways to arrange objects. Permutations are arrangements where the order of the objects matters. Each unique sequence or ordering of a set of objects is called a permutation.

Definition of a Permutation

A permutation is an arrangement of a set of objects in a definite, specific order. The key idea is that changing the order creates a new, distinct permutation.

For example, consider three distinct letters: A, B, and C. If we arrange all of them, the possible permutations are:

ABC, ACB, BAC, BCA, CAB, CBA

There are 6 distinct arrangements, so there are 6 permutations of these three letters.

Often, we are interested in arranging only a smaller group of items taken from a larger set. A permutation of $n$ distinct objects taken $r$ at a time is an ordered arrangement of $r$ objects chosen from the set of $n$.

Notation for Permutations

The number of permutations of $n$ distinct objects taken $r$ at a time is represented by the following standard notations:

• $P(n, r)$
• $^nP_r$
• $P_r^n$

All these symbols mean the same thing and are read as "the number of permutations of n objects taken r at a time". The conditions for this notation are:

• The $n$ objects must be distinct.
• $0 \le r \le n$.

If we try to arrange more objects than we have (i.e., if $r > n$), it's impossible. In this case, $^nP_r = 0$.

In the next section, we will derive the formula for calculating $^nP_r$ using the Fundamental Principle of Counting.

Permutations when all Objects are Different

In various mathematical applications, especially in probability and arrangement-based problems, we encounter scenarios where we need to determine the total number of ways to order a subset of objects. When all objects in the initial set are distinct, the counting process depends heavily on whether an object can be reused or not.

Case I: Permutations when Repetition is Not Allowed

This is the standard case where once an object is selected for a position, it cannot be used again for any subsequent position. We use the Fundamental Principle of Counting to derive the formula.

Derivation of the Formula for $^nP_r$

Imagine we have a set of $n$ distinct objects and we want to arrange $r$ of them in a sequence. This is equivalent to filling $r$ empty slots or positions using the $n$ available objects, without repetition.

We can determine the number of options for each position sequentially:

• For the 1st position: We have $n$ distinct objects to choose from, so there are $n$ options.
• For the 2nd position: One object has been used, leaving $n-1$ objects. So there are $n-1$ options.
• For the 3rd position: Two objects have been used, leaving $n-2$ objects. So there are $n-2$ options.
• ...
• For the r-th position: We have already used $r-1$ objects, leaving $n - (r-1) = n - r + 1$ objects. So there are $n - r + 1$ options.

By the Fundamental Principle of Multiplication, the total number of ways to fill all $r$ positions is the product of the number of choices at each step:

$^nP_r = n \times (n-1) \times (n-2) \times \dots \times (n - r + 1)$

To express this formula more compactly using factorials, we multiply and divide by $(n-r)!$:

The numerator is now the product of all integers from $n$ down to 1, which is $n!$. The denominator is $(n-r)!$. This gives us the standard formula for permutations:

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

This formula is valid for $0 \le r \le n$.

Arranging All $n$ Objects

A special and very common case is when we arrange all $n$ distinct objects. This means we are taking $n$ objects at a time, so $r=n$. Substituting $r=n$ into the formula:

Since we define $0! = 1$, the result is:

$^nP_n = n!$

This means the number of ways to arrange $n$ distinct items in a row is simply $n!$.

Case II: Permutations when Repetition is Allowed

In this scenario, an object can be used any number of times. This is common in problems involving digital locks, phone numbers, or passwords.

Derivation

Again, consider filling $r$ vacant slots with $n$ distinct objects.

1. The first slot $S_1$ can be filled in $n$ ways.

2. Since repetition is allowed, the object used in $S_1$ is still available. Thus, the second slot $S_2$ can also be filled in $n$ ways.

3. Similarly, every subsequent slot up to the $r^{th}$ slot can be filled in $n$ ways.

By the Multiplication Principle:

Total Permutations $= n \times n \times n \times \dots \text{ (up to } r \text{ times)}$

Total Permutations $= n^r$

Comparison Summary

Answer:

Answer:

Answer:

Permutations when not all Objects are Distinct

In the previous section, we discussed permutations of distinct objects. However, we often encounter problems where we need to arrange objects, and some of these objects are identical. When objects are identical, swapping them among themselves does not create a new, visibly distinct arrangement. This reduces the total number of unique permutations.

Formula for Permutations with Repetition

Suppose we have a collection of $n$ objects in total. Let there be $k$ different types of objects, with $p_1$ identical objects of the first type, $p_2$ identical objects of the second type, ..., and $p_k$ identical objects of the $k$-th type. The total number of objects is $n = p_1 + p_2 + \dots + p_k$.

The number of distinct permutations (arrangements) of these $n$ objects is given by the formula:

Number of permutations $= \frac{n!}{p_1! \cdot p_2! \cdot \dots \cdot p_k!}$

Here, $n$ is the total number of items, and $p_1, p_2, \dots$ are the counts of each group of identical items.

Intuition behind the Formula

Let's understand why we divide. Consider the word "TEE".

If the two 'E's were distinct (say, $E_1$ and $E_2$), we would have 3 distinct objects: T, $E_1$, $E_2$. The number of arrangements would be $3! = 6$.

$T E_1 E_2$, $T E_2 E_1$, $E_1 T E_2$, $E_2 T E_1$, $E_1 E_2 T$, $E_2 E_1 T$

Now, let's make the 'E's identical again ($E_1=E_2=E$). Look at the arrangements:

• $T E_1 E_2$ and $T E_2 E_1$ both become TEE.
• $E_1 T E_2$ and $E_2 T E_1$ both become ETE.
• $E_1 E_2 T$ and $E_2 E_1 T$ both become EET.

For every unique arrangement, we have counted it $2! = 2$ times because there are $2!$ ways to arrange the two 'E's. To correct for this overcounting, we divide the initial total ($3!$) by the factorial of the count of the repeated letter ($2!$).

This same logic applies no matter how many groups of repeated objects there are. We divide by the factorial of the count for each group to eliminate the overcounting from rearranging identical items.

Answer:

Circular Permutations

Circular permutations involve arranging objects around a closed loop, like people sitting at a round dining table or beads in a necklace. The key difference from linear permutations is that in a circle, there is no "fixed" starting or ending point. Rotating the entire arrangement does not create a new permutation.

Case 1: Arrangements of $n$ Distinct Objects

To arrange $n$ people at a round table, we first "fix" the position of one person to create a reference point. Once one person is fixed, the remaining $(n-1)$ positions behave like a linear arrangement.

Circular Permutations $= (n-1)!$

Case 2: Arrangements where Direction doesn't matter (Necklaces / Garlands)

In a garland of flowers or a necklace of beads, the arrangement looks the same whether we look at it from the front or flip it over. This means Clockwise and Anti-clockwise arrangements are identical.

Garland Permutations $= \frac{(n-1)!}{2}$

Comparison Table

Answer:

Answer:

Combinations

While permutations focus on the arrangement or order of objects, combinations deal with the selection or grouping of objects where the order of selection does not matter. In many real-world scenarios, we are interested in choosing a subset of items from a larger collection without regard to the order in which they are picked.

Definition of a Combination

A combination is a selection of a set of objects from a larger group of objects, where the order of selection is not important. A combination is essentially a subset of the original set. When we talk about combinations, we are concerned with who or what is in the group, not the sequence in which they were placed there.

For example, if you have a group of three friends, A, B, and C, and you need to choose two of them to form a team, the team consisting of {A, B} is the same as the team {B, A}. The order in which you picked them does not change the final team. The distinct combinations of choosing 2 friends from 3 are:

{A, B}, {A, C}, {B, C}

There are only 3 distinct combinations.

Distinction between Permutations and Combinations

The fundamental difference between permutations and combinations lies in the concept of order. When we deal with permutations, the sequence or arrangement is of primary importance. However, in combinations, we are only concerned with the selection of objects, regardless of how they are placed.

To identify which concept to apply in a given problem, one must ask: "Does the outcome change if I change the order of the selected items?"

• If Yes, it is a Permutation (e.g., a 4-digit ATM PIN; $1234$ is different from $4321$).
• If No, it is a Combination (e.g., selecting 2 fruits for a juice; Mango and Orange is the same as Orange and Mango).

Comparison Table

The Relationship Between Permutations and Combinations

The concepts of permutations and combinations are not isolated; they are deeply interconnected through the logic of selection and arrangement. A permutation can be viewed as a multi-stage process where we first select a group of items and then arrange them in a specific order.

To understand this relationship, consider the act of forming a word from a set of letters. If we want to arrange $r$ letters out of $n$ available letters, we must first choose which $r$ letters to use (Combination) and then determine their positions (Permutation).

The Two-Step Logic

We can mathematically define the relationship by breaking down the formation of a permutation into two distinct steps:

Step 1: Selection (Combination)

First, we select $r$ objects from $n$ distinct objects. The number of ways to perform this selection is denoted by $^nC_r$. At this stage, the order of the selected items does not matter.

Step 2: Arrangement (Factorial)

Once the $r$ objects are selected, they can be arranged among themselves in $r!$ different ways. This is because the first position can be filled in $r$ ways, the second in $(r-1)$ ways, and so on.

By the Fundamental Principle of Multiplication, the total number of permutations ($^nP_r$) is the product of the number of ways to complete Step 1 and Step 2.

$^nP_r = \ $$^nC_r \times r!$

Visualizing the Relationship

Consider 3 objects $\{A, B, C\}$. Suppose we want to select and arrange 2 objects ($n=3, r=2$).

This table confirms that the number of permutations is always $r!$ times the number of combinations. Specifically, $^3P_2 = \ $$^3C_2 \times 2!$.

Key Deductions

From the relationship $^nC_r = \frac{^nP_r}{r!}$, we can observe several important properties:

1. Inequality: Since $r! \ge 1$ for all $r \ge 0$, it follows that $^nP_r \ge \ $$^nC_r$. The number of ways to arrange objects will always be greater than or equal to the number of ways to simply select them.

2. Equality Case: $^nP_r = \ $$^nC_r$ only when $r! = 1$, which occurs when $r = 0$ or $r = 1$.

3. Symmetry: The number of ways to select $r$ objects is identical to the number of ways to reject $(n-r)$ objects. This is known as the restricted selection principle.

Combinations when all Objects are Different

Having understood the distinction between permutations (where order matters) and combinations (where order does not matter), we now focus on the mathematical derivation of the combination formula. This is specifically for cases where we select a group of items from a set where every individual object is distinct and unique.

Derivation of the Formula for $^nC_r$

The logic of combinations is built upon the logic of permutations. As established earlier, forming a permutation is a two-step process: first selecting the items and then arranging them. The relationship is expressed as:

This formula states that the number of ways to arrange $r$ items ($^nP_r$) is equal to the number of ways to first choose the group of $r$ items ($^nC_r$) and then arrange those $r$ items in $r!$ ways. To isolate the number of selections ($^nC_r$), we rearrange the equation:

From our study of permutations, we know that:

By substituting the expression for $^nP_r$ from equation (ii) into equation (i), we get:

On simplifying the fraction, we arrive at the Standard Formula for Combinations:

In many advanced texts and competitive exams, the notation $\binom{n}{r}$ is used interchangeably with $^nC_r$. It is read as "n choose r".

Important Properties and Special Cases

Understanding these properties can significantly reduce calculation time during exams:

1. Choosing Zero Items

When we choose no items from a set of $n$ objects, we are essentially selecting the "empty set". Mathematically:

2. Choosing All Items

There is only one way to select all $n$ objects from a set of $n$ objects (by taking the whole group).

3. Symmetry Property (Complementary Selection)

Choosing $r$ items to be part of a group is logically the same as choosing $n-r$ items to be left out. This is a very powerful property for calculation.

For example, if you are asked to calculate $^{100}C_{98}$, it is much easier to calculate $^{100}C_{100-98} = \ $$ ^{100}C_2$.

4. Equality of Two Combinations

If two combinations of the same set of $n$ objects are equal, such that:

Then, there are only two possibilities:

1. Either $a = b$ (The selections are identical).
2. Or $a + b = n$ (One is the complement of the other, based on Property 3).

5. Pascal's Rule (Addition Property)

This is a fundamental recurrence relation in combinations, often visualized in Pascal's Triangle. It states:

$^nC_r + \ ^nC_{r-1} = \ ^{n+1}C_r$

Total and Restricted Selections

6. Total Number of Combinations (Selection of At Least One)

Finding the number of ways to select one or more items from $n$ different items means we could select 1 item, or 2 items, or 3 items, ..., up to $n$ items.

Derivation: Each of the $n$ distinct items has 2 choices: either it is selected or it is not. Total ways to form any subset = $2 \times 2 \times \dots$ ($n$ times) = $2^n$. This includes the case where no item is selected ($^nC_0 = 1$). To find "at least one", we subtract this case:

Ways to select at least one $= 2^n - 1$

7. Particular Things Always Occurring

If we must select $r$ objects from $n$ distinct objects such that $p$ particular objects always occur:

Combination: Since $p$ items are already fixed in the selection, we only need to choose the remaining $(r-p)$ items from the remaining $(n-p)$ items.

Number of Combinations $= \ ^{n-p}C_{r-p}$

Permutation: To find the arrangements, we multiply the selection by the number of ways to arrange all $r$ items.

Number of Permutations $= \ ^{n-p}C_{r-p} \times r!$

8. Particular Things Never Occurring

If we must select $r$ objects from $n$ distinct objects such that $p$ particular objects never occur:

Combination: We must exclude the $p$ items from our total pool. Thus, we select $r$ items from the remaining $(n-p)$ items.

Number of Combinations $= \ ^{n-p}C_{r}$

Permutation: We multiply the above selection by $r!$ to arrange them.

Number of Permutations $= \ ^{n-p}C_{r} \times r!$

Selection from Alike (Identical) Objects

9. Selections with Multiple Groups of Alike Objects

If there are $(p + q + r)$ things, where $p$ things are alike (of one kind), $q$ things are alike (of second kind), and $r$ things are alike (of third kind), the number of non-empty selections is:

Logic: Out of $p$ alike things, we may take 0, 1, 2, ..., $p$ things. This provides $(p+1)$ ways. Similarly, there are $(q+1)$ ways for the $q$ group and $(r+1)$ ways for the $r$ group. We subtract 1 to exclude the case where 0 items are picked from all groups.

Total Ways $= (p+1)(q+1)(r+1) - 1$

10. Selections with Alike and Different Objects

If there are $(p + q + r)$ things, where $p$ items are alike, $q$ items are alike, and the remaining $r$ items are all different:

Logic: The alike groups give $(p+1)$ and $(q+1)$ options. For the $r$ different items, each item can either be selected or not (2 choices each), leading to $2 \times 2 \times \dots$ ($r$ times) $= 2^r$ ways.

Total Ways $= (p+1)(q+1) \cdot 2^r - 1$

Answer:

Answer:

Answer:

Answer:

Answer:

Answer:

Important Results on Combinations

The formula for combinations, $^nC_r = \frac{n!}{r!(n-r)!}$, gives rise to several important identities and properties. These results are not just theoretical curiosities; they provide powerful shortcuts for solving complex counting problems and are fundamental to topics like the Binomial Theorem and Probability.

Property 1: The Symmetry Property

This is one of the most frequently used properties of combinations. It states that the number of ways to choose $r$ objects from a set of $n$ is the same as the number of ways to choose $(n-r)$ objects from that set.

$$^nC_r = \ ^nC_{n-r}$$

Combinatorial Proof (Intuitive Explanation)

Imagine you have $n$ distinct items. The act of choosing $r$ items to take with you is logically equivalent to choosing $(n-r)$ items to leave behind. For every group of $r$ items you select, you are simultaneously defining a group of $(n-r)$ items that you are not selecting. Therefore, the number of ways to perform these two actions must be identical.

Algebraic Proof

We start with the right side of the equation, $^nC_{n-r}$, and show that it simplifies to the formula for $^nC_r$.

Simplify the second term in the denominator: $n - (n - r) = n - n + r = r$.

By the commutative property of multiplication ($a \times b = b \times a$), this is the same as the formula for $^nC_r$.

Answer:

Property 2: Pascal's Identity

This identity relates combinations of size $n$ to combinations of size $n+1$. It is the fundamental algebraic rule used to construct Pascal's Triangle.

$$^nC_r + \ ^nC_{r-1} = \ ^{n+1}C_r$$

Combinatorial Proof (Intuitive Explanation)

Suppose we want to form a committee of $r$ members from a group of $(n+1)$ people. The total number of ways to do this is $^{n+1}C_r$.

Now, consider one specific person in the group, say, "Aman". Every possible committee we form will either include Aman or it will not. These two scenarios are mutually exclusive and exhaustive.

• Case 1: The committee includes Aman.

  Since Aman is already chosen, we only need to choose the remaining $(r-1)$ members from the remaining $n$ people. This can be done in $^nC_{r-1}$ ways.

• Case 2: The committee does NOT include Aman.

  Since Aman is excluded, we must choose all $r$ members from the other $n$ people. This can be done in $^nC_r$ ways.

By the Addition Principle, the total number of ways to form the committee is the sum of these two cases.

$$^{n+1}C_r = \ ^nC_r + \ ^nC_{r-1}$$

Derivation (Proof)

To Prove: $^nC_r + \ ^nC_{r-1} = \ ^{n+1}C_r$

Proof:

We start with the Left Hand Side (L.H.S.) of the equation and apply the factorial definition of combinations, which is $^nC_r = \frac{n!}{r!(n-r)!}$.

Simplify the denominator of the second term:

L.H.S. $= \frac{n!}{r!(n-r)!} + \frac{n!}{(r-1)!(n-r+1)!}$

To add these two fractions, we need a common denominator. We observe the following relationships between the factorial terms:

• $r! = r \times (r-1)!$
• $(n-r+1)! = (n-r+1) \times (n-r)!$

Now, let us rewrite the denominators using these relationships to make them identical:

Take the common factor $\frac{n!}{(r-1)!(n-r)!}$ outside the bracket:

Calculate the sum inside the brackets by taking the L.C.M.:

Simplify the numerator inside the bracket (the $-r$ and $+r$ cancel out):

Now, group the terms in the numerator and the denominator together:

Using the property $(k+1) \cdot k! = (k+1)!$, we can combine the terms:

The above expression is exactly the definition of $^{n+1}C_r$.

Hence Proved.

Property 3: Sum of All Combinations

The sum of all combinations for a given $n$, ranging from choosing 0 items to choosing all $n$ items, is equal to $2^n$.

$$^nC_0 + \ ^nC_1 + \ ^nC_2 + \dots + \ ^nC_n = \sum\limits_{r=0}^{n} \ ^nC_r = 2^n$$

Combinatorial Proof (Intuitive Explanation)

Consider a set containing $n$ distinct elements. The total number of subsets of this set can be found by considering each element one by one. For each element, there are 2 choices: either it is included in the subset or it is excluded.

• For element 1: 2 choices
• For element 2: 2 choices
• ...
• For element $n$: 2 choices

By the Multiplication Principle, the total number of possible subsets is $2 \times 2 \times \dots \times 2$ ($n$ times), which equals $2^n$.

Alternatively, we can count the subsets by their size. The number of subsets of size 0 is $^nC_0$, size 1 is $^nC_1$, and so on. Summing these individual counts must equal the total number of subsets ($2^n$).

Answer:

Division into Groups

A significant application of combinations is the division of a set of distinct objects into several groups. We must distinguish between two types of problems: Division (where we just form piles or groups) and Distribution (where those groups are given to specific persons or entities).

1. Division into Unequal Groups

In the study of Combinatorics, the concept of partitioning a set into groups is fundamental. When we deal with distinct objects, the way we partition them depends heavily on whether the final groups are simply "piles" (Division) or are being assigned to specific "entities" (Distribution).

Case A: Division into Unequal Groups

Consider a scenario where we have a total of $(m + n)$ distinct objects. We want to divide these into two separate groups, one containing $m$ objects and the other containing $n$ objects, where $m \neq n$.

The Logical Derivation

1. First Step: We select $m$ objects from the total $(m+n)$ objects to form the first group.

2. Second Step: After selecting $m$ objects, we are left with $(m+n) - m = n$ objects. These remaining $n$ objects must form the second group. The number of ways to select $n$ objects from $n$ is simply 1.

3. Total Ways: According to the Fundamental Principle of Multiplication, the total number of ways to perform this division is the product of these two steps:

By expanding the combination formula $^nC_r = \frac{n!}{r!(n-r)!}$, we get:

On simplifying the denominator, we arrive at the standard result:

Note: Since $m \neq n$, the groups are already distinct by their size. For example, a group of 10 items and a group of 2 items are naturally different, so there is no risk of overcounting the groups themselves.

Case B: Distribution among Distinct Persons

Distribution differs from division because the identity of the recipient matters. If we take the two groups formed in Case A and give them to two people, say Amit and Sumit, we introduce an additional layer of arrangement.

The Arrangement Factor

Once the two groups (one of size $m$ and one of size $n$) are formed, they can be handed out in the following ways:

1. Group $m$ goes to Amit, and Group $n$ goes to Sumit.
2. Group $n$ goes to Amit, and Group $m$ goes to Sumit.

This represents the permutation of the 2 groups among 2 people, which is $2!$ ways.

Final Formula for Distribution

The total number of ways to distribute $(m+n)$ things to two persons such that one gets $m$ and the other gets $n$ is:

Answer:

2. Division of $(m + n + p)$ things into Three Unequal Groups

Extending the logic of two groups, we now look at the partitioning of $(m + n + p)$ distinct objects into three separate groups. For these formulas to hold in their simplest form, we assume that the group sizes are unequal ($m \neq n \neq p$).

Case A: Division into groups of size $m, n,$ and $p$

When we "divide" objects into groups, we are simply creating three nameless collections (piles) of items. The order in which these piles are placed on a table does not matter.

Derivation of the Formula

1. Selection for the first group: Out of the total $(m + n + p)$ objects, we select $m$ objects.

2. Selection for the second group: We are now left with $(n + p)$ objects. From these, we select $n$ objects.

3. Selection for the third group: Only $p$ objects remain. There is only 1 way to form the final group ($^pC_p = 1$).

By the Fundamental Principle of Multiplication, the total number of ways to divide the items is:

Substituting the factorial expansion:

On canceling $(n+p)!$ from the numerator and denominator, we get:

Case B: Distribution among Three Distinct Persons

In competitive exams, "distribution" implies that the identity of the person receiving the group is important. If we give these three groups to three different people (say A, B, and C), the problem changes from a simple selection to an arrangement.

The Logic of Arrangement

Once the three unequal piles are created, they can be distributed among three persons in $3!$ ways. For example, person A could receive the group of size $m$, or $n$, or $p$.

Answer:

3. Division into Equal Groups

A critical point of confusion in combinatorics arises when dividing objects into groups of equal size. When the sizes of the groups are identical, the groups themselves become indistinguishable unless they are assigned to specific people or positions.

Case A: Division of $2m$ things into two equal groups

Suppose we have $2m$ distinct objects and we want to divide them into two groups, each containing $m$ objects. In this case, the groups are "nameless" (just two piles on a table).

The Logic of Overcounting

If we use the standard formula for unequal groups, we would calculate $^{(2m)}C_m$. However, let us look at an example with 4 distinct objects $\{A, B, C, D\}$ divided into two groups of 2:

• Selection 1: $\{A, B\}$ and $\{C, D\}$
• Selection 2: $\{C, D\}$ and $\{A, B\}$

In "Division" (creating piles), these two selections result in the exact same two piles. Since there are 2 equal groups, every unique division is counted $2!$ times in the $^{(2m)}C_m$ calculation.

Derivation

Expanding the combination formula:

Case B: Distribution of $2m$ things among two distinct persons

When the same $2m$ objects are distributed among two distinct persons (for example, Arjun and Bhaskar), the groups are no longer indistinguishable because the recipient's identity acts as a label.

The Reintroduction of Arrangement

Giving $\{A, B\}$ to Arjun and $\{C, D\}$ to Bhaskar is different from giving $\{C, D\}$ to Arjun and $\{A, B\}$ to Bhaskar. Therefore, we multiply the division formula by $2!$ to account for the arrangement between the two people.

Answer:

4. Division and Distribution of $3m$ things into Three Equal Groups

When partitioning $3m$ distinct objects into three equal groups of size $m$ each, the concept of indistinguishable groups becomes even more critical. In competitive exams, identifying whether the groups are "nameless piles" or are being "assigned to specific entities" is the key to choosing the correct formula.

Case A: Division into Three Equal Groups

In this scenario, we are simply dividing $3m$ objects into three heaps, each containing $m$ objects. Since the sizes of all three heaps are identical and the heaps themselves have no specific names or recipients, the order in which the heaps are formed does not matter.

The Logic of Adjustment

If we simply used the formula for unequal groups ($m, n, p$), we would calculate the number of ways as:

However, because the three groups are of equal size, any specific partition of objects is counted $3!$ times (all possible permutations of the three identical-looking heaps). To find the number of unique divisions, we must divide by $3!$.

Standard Formula

Case B: Distribution among Three Distinct Persons

When these three equal groups are distributed among three distinct persons (for example, Amit, Binay, and Chitra), the groups are no longer indistinguishable. The recipient's name acts as a unique label for each group.

Reintroducing the Permutation

Since the three persons can be arranged in $3!$ ways to receive the three prepared heaps, we multiply the division formula by $3!$. This cancels out the adjustment factor used in the division step.

Answer:

Answer:

Summary Table for Division and Distribution

To master problems related to partitioning objects in competitive exams, it is essential to have a quick reference for all the formulas derived. The fundamental difference lies in whether we are just creating piles (Division) or assigning those piles to distinct entities (Distribution).

The following table summarizes the number of ways to divide and distribute distinct objects under various conditions:

Key Points to Remember

1. Identical Group Sizes

Whenever you see equal group sizes in a "Division" problem, you must divide by the factorial of the number of equal groups to avoid overcounting indistinguishable sets. For example, if there are 4 equal groups, divide the result by $4!$.

2. Distribution to Persons

In "Distribution" problems involving distinct people (like distributing 12 mangoes to 3 children: Ram, Shyam, and Mohan), the identity of the person makes the groups distinct. Hence, the "equal group" adjustment factor is cancelled out by multiplying by the permutation of the people.

3. The Selection Approach

For unequal groups, the formula $\frac{(m+n)!}{m!n!}$ is mathematically identical to $^{(m+n)}C_m$. You can always solve these by step-by-step selection if you forget the general formula.

Distribution of Identical Objects into Distinct Groups

In previous sections, we discussed the distribution of distinct objects. However, when the objects are identical (like identical coins, marbles, or sweets), the logic changes significantly. In this case, it doesn't matter which object a person gets; only how many objects they receive matters.

This concept is also widely known as the "Stars and Bars" method in combinatorics and is frequently used to find the number of non-negative or positive integer solutions to linear equations.

1. Distribution of Identical Objects (Non-Negative Integers)

In examinations, the problem of distributing identical objects among distinct persons is a frequent theme. The core of this concept lies in the fact that since the objects are identical, we do not care which object is given to whom; we only care about the quantity each person receives.

This is equivalent to finding the number of non-negative integer solutions to the linear equation:

The "Stars and Bars" Visualization

To understand the derivation, let us use a visual analogy. Suppose we have $n$ identical items, which we represent as "Stars" ($*$), and we want to distribute them among $r$ distinct people.

1. Why $r-1$ Dividers?

To divide a single row of objects into $r$ separate compartments, we need exactly $r-1$ separators or "Bars" ($|$).

• To make 2 groups, we need 1 bar: $(* * | * * *)$
• To make 3 groups, we need 2 bars: $(* | * * | * *)$
• To make $r$ groups, we need $r-1$ bars.

2. The Total Arrangement

When we lay out all the $n$ stars and the $r-1$ bars in a single line, every unique arrangement of these symbols represents a unique distribution. For example, if $n=5$ and $r=3$ (so we use 2 bars):

The total number of positions in this line is the sum of the stars and the bars:

Mathematical Derivation

We have a total of $n+r-1$ positions. Out of these, we need to choose $r-1$ positions to place our bars. The remaining $n$ positions will automatically be filled by stars.

Step 1: Using Permutation of Alike Objects

The number of ways to arrange $n+r-1$ objects where $n$ are identical (stars) and $r-1$ are identical (bars) is given by:

Step 2: Conversion to Combination Formula

From the definition of combinations ($^nC_r = \frac{n!}{r!(n-r)!}$), we can see that the expression in above equation is exactly the same as:

By the symmetry property of combinations ($^nC_r = \ ^nC_{n-r}$), this can also be written as:

Numerical Application

Answer:

2. Distribution of Identical Objects (Positive Integers)

When distributing identical objects among distinct persons with the constraint that no person is left empty-handed, we are looking for the number of positive integer solutions. This is a restricted version of the "Stars and Bars" problem where each person must receive $x_i \ge 1$.

Mathematically, this corresponds to finding the number of solutions for:

Method 1: The Gap Method (Visual Derivation)

Consider $n$ identical objects arranged in a horizontal row. Since the objects are identical, they create spaces or gaps between them.

1. Identifying the Gaps

If there are $n$ objects, the number of internal gaps between them is $n-1$. For example, if $n=4$ stars, the gaps are represented by the spaces between them:

2. Placing the Dividers

To divide these $n$ objects into $r$ distinct groups such that each group contains at least one object, we must place $r-1$ dividers into these internal gaps. Because we are only choosing from internal gaps and placing only one divider per gap, we ensure that:

• No group is empty (since dividers aren't at the ends).
• No two dividers are in the same place (so no group in between them is empty).

3. The Formula

Out of the $n-1$ available gaps, we choose $r-1$ gaps to place our dividers.

Method 2: Reduction to Case 1 (Algebraic Derivation)

This method converts the "at least one" problem into a "zero or more" problem (non-negative solutions), which we solved previously using the $\ ^{n+r-1}C_{r-1}$ formula.

Step 1: Satisfying the Initial Condition

To ensure every person gets at least one object, we pre-distribute 1 object to each of the $r$ persons.

Step 2: Distributing the Remainder

The remaining $n-r$ identical objects can now be distributed among the $r$ persons in any manner (each can get 0, 1, or more of the remaining items). We apply the non-negative distribution formula $\ ^{N+r-1}C_{r-1}$ where $N = n-r$.

On simplifying the terms within the combination:

Answer:

Answer:

Comparison Table

The following table provides a quick reference to distinguish between the two primary cases of distributing $n$ identical objects among $r$ distinct persons:

Key Observations for Problem Solving

1. Logical Transformation

The "At least one" case is logically a subset of the "Zero or more" case. If you have $n$ items and must give at least 1 to each of the $r$ people, you are essentially reducing your pool of available items to $n-r$.

2. Constraint Identification

Always look for keywords in the problem statement:

• "May get none", "Non-negative integers", "Each can get any number": Use $^ {n+r-1}C_{r-1}$.
• "Each gets at least one", "Positive integers", "No group is empty": Use $^ {n-1}C_{r-1}$.