Permutations and Combinations

Introduction to Permutations and Combinations

Permutations and Combinations are foundational branches of combinatorics used to count the number of possible outcomes or arrangements without needing to list every possibility manually.

The core distinction between the two lies in a single question: Does the order matter?

• Permutations (Order Matters):A permutation is an ordered arrangement of objects where changing the sequence produces a completely different outcome ($AB \neq BA$). Common examples include entering a security PIN, podium finishes in a race, or assigning distinct roles like President and Secretary.
  • Formula: The number of ways to arrange $r$ elements from $n$ distinct objects is given by: $$P(n, r) = \frac{n!}{(n – r)!}$$
• Combinations (Order Does Not Matter):A combination is a selection or grouping of items where the sequence does not change the result ($AB = BA$). Examples include picking ingredients for a recipe, dealing a hand of cards, or choosing members for an equal-standing committee.
  • Formula: The number of ways to select $r$ elements from $n$ distinct objects is given by: $$\binom{n}{r} = C(n, r) = \frac{n!}{r!(n – r)!}$$

Together, these principles—alongside factorial algebra—provide the foundation for solving complex problems involving group distributions, circular arrangements, probability, and number theory.

Explore Contents

• Notation of Factorial & its Algebra
• Permutations
• Combinations
• Lesson
• Questions & Answers

Notation of Factorial & its Algebra

Why This Matters

Factorials are the backbone of counting problems, combinatorics, and probability. Whether you are finding the number of ways to arrange books on a shelf or selecting a team from a larger group, factorial notation gives you the algebraic shorthand needed to compute permutations and combinations efficiently.

Core Concepts

Definition of Factorial Notation

For any natural number $n$, the factorial of $n$, denoted by the symbol $n!$, is the product of all positive integers less than or equal to $n$.

$$n! = n \times (n – 1) \times (n – 2) \times \dots \times 3 \times 2 \times 1$$

Key properties and definitions include:

• Base case: By convention and mathematical definition, $0! = 1$.
• Recursive form: For any positive integer $n \ge 1$, $n! = n \times (n – 1)!$.
• Domain: Factorials are defined for non-negative integers ($0, 1, 2, 3, \dots$). Negative numbers and non-integers do not have standard factorials.

Values of the first few factorials:

• $0! = 1$
• $1! = 1$
• $2! = 2 \times 1 = 2$
• $3! = 3 \times 2 \times 1 = 6$
• $4! = 4 \times 3 \times 2 \times 1 = 24$
• $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$

Algebraic Simplification of Factorials

When evaluating algebraic expressions involving factorials, avoid expanding every term completely into numbers. Instead, expand the larger factorial until it matches the smaller factorial, allowing common terms to cancel out cleanly.

Key algebraic techniques:

• Ratio of factorials: $\frac{n!}{(n – r)!} = n(n – 1)(n – 2)\dots(n – r + 1)$
• Factoring common factorials: Factor out the smallest factorial term from sums or differences before simplifying. For example, $(n + 1)! – n! = n!(n + 1 – 1) = n \cdot n!$.
• Common denominator: To add or subtract fractions with factorial denominators like $\frac{1}{6!} + \frac{1}{7!}$, convert the smaller denominator to the larger by multiplying numerator and denominator by the missing integer factor.

Worked Examples

Now let’s apply the algebraic properties of factorials to simplify fractions and solve factorial equations.

Example 1: Simplifying Factorial Quotients Evaluate the numerical value of $\frac{8!}{5! \times 3!}$.

1.Identify the largest factorial in the denominator:

The denominator contains $5!$ and $3!$. Expand the numerator $8!$ down to $5!$ so they can be canceled directly.

$$8! = 8 \times 7 \times 6 \times 5!$$

2.Substitute and cancel common factorials:

Replace $8!$ in the fraction:

$$\frac{8 \times 7 \times 6 \times 5!}{5! \times 3!} = \frac{8 \times 7 \times 6}{3!}$$

3.Evaluate the remaining terms:

Expand $3! = 3 \times 2 \times 1 = 6$.

$$\frac{8 \times 7 \times 6}{6} = 8 \times 7 = 56$$

Example 2: Solving an Equation with Factorial Denominators Find the value of $x$ if $\frac{1}{8!} + \frac{1}{9!} = \frac{x}{10!}$.

1.Clear denominators by multiplying by the largest factorial:

Multiply every term in the equation by $10!$:

$$\frac{10!}{8!} + \frac{10!}{9!} = x$$

2.Expand and reduce each term individually:

Expand $10!$ relative to each denominator:

$$\frac{10!}{8!} = \frac{10 \times 9 \times 8!}{8!} = 10 \times 9 = 90$$

$$\frac{10!}{9!} = \frac{10 \times 9!}{9!} = 10$$

3.Sum the resulting integers to find x:

Combine the simplified terms:

$$x = 90 + 10 = 100$$

Permutations

Why This Matters

Understanding permutations is essential whenever you need to arrange items where order dictates the outcome. Whether you are generating secure passwords, scheduling race lineups, or assigning specific committee roles, distinguishing when the sequence matters ensures you count possibilities accurately without duplicate or missing configurations.

Core Concepts

Defining a Permutation

A permutation is an ordered arrangement of a set of distinct objects. Unlike collections where grouping alone is sufficient, in a permutation, changing the order of the exact same elements produces an entirely distinct outcome.

When selecting and arranging $r$ unique elements from a total set of $n$ elements, the number of possible permutations is determined by the formula:

$$P(n, r) = \frac{n!}{(n – r)!}$$

Where:

• $n!$ ($n$ factorial) is the product of all positive integers up to $n$ ($n \times (n – 1) \times \dots \times 1$).
• $(n – r)!$ cancels out the choices that are not selected.
• When arranging all $n$ items ($r = n$), $P(n, n) = n!$.

Identifying When Order Matters

The fundamental test to identify a permutation scenario is: Does swapping two items create a different result?

• Order matters (Permutation):
  • Awarding 1st, 2nd, and 3rd place medals in a sprint. (Alice winning Gold and Bob winning Silver is completely different from Bob winning Gold and Alice winning Silver.)
  • Setting a numerical passcode or PIN. The sequence 1-2-3-4 will unlock a vault, whereas 4-3-2-1 will fail.
  • Assigning distinct officer positions (President, Vice President, Treasurer) within an organization.
• Order does not matter (Combination):
  • Choosing 3 fruits to blend into a single smoothie bowl.
  • Selecting a general 3-person delegate committee where everyone shares equal standing.
  • Dealing a 5-card poker hand.

Worked Examples

Now let’s put the concept of order and the permutation formula into practice — here is how to break down and solve real-world arrangement problems.

Example 1: Running for Specific Officer Roles A student council club has 8 eligible candidates. In how many ways can the positions of President, Vice President, and Secretary be filled?

1.Determine if order matters:

Because each role (President, Vice President, Secretary) carries distinct duties and status, assigning Person A to President and Person B to Secretary is different from vice versa. Order matters, so this is a permutation.

2.Identify n and r:

The total pool of candidates is $n = 8$, and the number of specific roles to fill is $r = 3$.

3.Apply the permutation formula:

Substitute $n = 8$ and $r = 3$ into $P(n, r) = \frac{n!}{(n – r)!}$:

$$P(8, 3) = \frac{8!}{(8 – 3)!} = \frac{8!}{5!}$$

$$P(8, 3) = \frac{8 \times 7 \times 6 \times 5!}{5!} = 8 \times 7 \times 6 = 336$$

There are 336 distinct ways to assign the three positions.

Example 2: Creating a 4-Digit Security Code A security gate requires a 4-digit code using the digits 1 through 9, where no digit can be repeated. How many unique codes can be formed?

1.Confirm order dependency:

A security pin depends entirely on the sequence in which the digits are entered (e.g., 1234 is not the same code as 4321). Therefore, this is a permutation problem.

2.Identify pool size and code length:

The digits 1 through 9 provide $n = 9$ available choices. The code requires $r = 4$ non-repeating digits.

3.Calculate total arrangements:

Use the permutation formula:

$$P(9, 4) = \frac{9!}{(9 – 4)!} = \frac{9!}{5!} = 9 \times 8 \times 7 \times 6 = 3,024$$

A total of 3,024 unique access codes can be set.

Combinations and the Role of Order

Why This Matters

Understanding combinations allows you to count groupings when the sequence or order of elements does not matter. Distinguishing combinations from permutations prevents counting errors across probability calculations, data analysis, and competitive exams.

Core Concepts

What Is a Combination?

A combination is a selection of items from a collection such that the order of selection does not matter. If you are forming a committee of 3 people from a group of 10, choosing Alice, Bob, and Charlie produces the exact same committee as choosing Charlie, Alice, and Bob.

The number of combinations of $n$ distinct objects taken $r$ at a time is denoted by $C(n, r)$, $_nC_r$, or $\binom{n}{r}$, and calculated as:

$$\binom{n}{r} = \frac{n!}{r!(n – r)!}$$

Combinations vs. Permutations

The key distinction between a permutation and a combination comes down to a single question: Does order matter?

• Permutations (Order Matters): Arrangements, rankings, podium finishes, secret codes, and assigned positions (e.g., President vs. Vice President). Changing the sequence creates a distinct outcome ($AB \neq BA$).
• Combinations (Order Does Not Matter): Unordered subsets, hands of cards, committees of equal status, and ingredient selections. Changing the sequence produces the identical group ($AB = BA$).

Because order does not matter in combinations, each distinct group of $r$ elements can be arranged in $r!$ different ways. Dividing the number of permutations $P(n, r)$ by $r!$ eliminates these duplicate orderings:

$$\binom{n}{r} = \frac{P(n, r)}{r!}$$

Worked Examples

Now let’s apply the distinction between permutations and combinations to identify which method to use and calculate the total number of outcomes.

Example 1: Class Project Committee A teacher wants to choose a team of 3 students from a group of 8 candidates to present a project. How many different teams can be selected?

1.Determine if order matters:

All 3 students have the same role on the team. Choosing students A, B, and C is identical to choosing C, B, and A. Because order does not matter, this is a combination problem where $n = 8$ and $r = 3$.

2.Set up the combination formula:

Apply the formula $\binom{n}{r} = \frac{n!}{r!(n – r)!}$:

$$\binom{8}{3} = \frac{8!}{3!(8 – 3)!} = \frac{8!}{3! \times 5!}$$

3.Simplify and evaluate:

Expand the numerator until $5!$ cancels:

$$\binom{8}{3} = \frac{8 \times 7 \times 6 \times 5!}{(3 \times 2 \times 1) \times 5!} = \frac{8 \times 7 \times 6}{6} = 56$$

There are 56 possible teams.

Example 2: Selecting Officers vs. Selecting Members A club has 6 members. How does selecting an Executive Board (President and Vice President) differ from selecting a 2-person cleanup committee?

1.Analyze the Executive Board (Permutation):

The roles are distinct; selecting Member A as President and Member B as Vice President is different from selecting Member B as President and Member A as Vice President. Order matters:

$$P(6, 2) = \frac{6!}{(6 – 2)!} = 6 \times 5 = 30 \text{ outcomes}$$

2.Analyze the Cleanup Committee (Combination):

Both members share identical duties. Selecting Member A and Member B creates the exact same cleanup pair as Member B and Member A. Order does not matter:

$$\binom{6}{2} = \frac{6!}{2!(6 – 2)!} = \frac{6 \times 5}{2 \times 1} = 15 \text{ outcomes}$$

3.Compare the relationship:

Notice that $P(6, 2) = \binom{6}{2} \times 2!$. The combination count divides out the $2!$ internal orderings between the two chosen members.

Let Start The Following Lesson

1. Formation of Groups & Their Distribution

Why This Matters

Dividing objects into smaller collections is one of the most tested ideas in Permutations and Combinations, frequently appearing in competitive exams like JEE Main and Advanced. Grasping whether groups are distinct or identical, and whether items are merely partitioned or actively distributed to recipients, prevents double-counting and off-by-a-factor errors.

Core Concepts

Division into Unequal Groups

When partitioning $(m + n)$ distinct objects into two groups containing $m$ and $n$ items respectively (where $m \neq n$):

1. Choose $m$ items out of the total $(m + n)$ items to form the first group: $\binom{m+n}{m}$.
2. The remaining $n$ items automatically form the second group: $\binom{n}{n} = 1$.

Expanding using factorials:

$$\binom{m+n}{m} = \frac{(m+n)!}{m! \, ((m+n)-m)!} = \frac{(m+n)!}{m! \, n!}$$

Because $m \neq n$, the two groups are inherently distinct by their sizes. Order of selection does not matter, and no division by symmetry factors (like $2!$) is needed.

Partitioning vs. Distribution

A common pitfall is conflating the grouping (division) of items with the distribution of those groups to people or labeled locations.

When handing two unequal groups to two distinct people, Group 1 can go to either person, giving $2!$ ways to assign them.

Worked Examples

Now let’s apply the group formation and distribution principles to concrete problems with distinct items.

Example 1: Dividing Books into Unequal Bundles

Find the number of ways to divide 10 distinct books into two bundles containing 7 and 3 books respectively.

1.Identify group sizes and total items:

Total items: $10$

Group sizes: $m = 7$, $n = 3$

Since $7 \neq 3$, this is a division into unequal groups.

2.Select items for the first group:

Choose 7 books out of 10:

$$\binom{10}{7} = \frac{10!}{7! \, 3!}$$

3.Evaluate the total combinations:

Calculate the numerical value:

$$\frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 10 \times 3 \times 4 = 120\text{ ways}$$

Example 2: Grouping and Distributing to People

In how many ways can 9 different toys be divided into two groups of 4 and 5 toys, and then distributed between Alice and Bob?

1.Form the two groups (Division):

Choose 4 toys out of 9 to make the first group:

$$\binom{9}{4} = \frac{9!}{4! \, 5!} = \frac{9 \times 8 \times 7 \times 6}{4 \times 3 \times 2 \times 1} = 126\text{ ways}$$

2.Distribute the bundles (Permutation):

Alice and Bob are 2 distinct recipients. The 2 unequal packets can be assigned in $2!$ ways.

3.Compute the total ways:

Multiply division ways by distribution ways:

$$126 \times 2! = 126 \times 2 = 252\text{ ways}$$

Review what you’ve learned

Check your learning on this topic with a quick quiz. Score at least 80% to unlock a new strength.

2. Total Number of Combinations

Why This Matters

Counting all possible subsets from a collection of distinct items appears constantly in probability, computer science, and combinatorics. Instead of summing individual combination terms one by one, using the total combinations formula lets you evaluate every possible selection—including the common condition of selecting “at least one”—in a single step.

Core Concepts

Binary Choice Model and the $2^n$ Principle

When you have $n$ distinct items, forming any group comes down to an independent binary decision for each individual item: either you include it, or you leave it out.

• Two choices per item: For each item $i$, there are $2$ possible choices (Selected or Not Selected).
• Multiplication rule: Across $n$ distinct items, the total number of subsets is:
  $$2 \times 2 \times \cdots \times 2 = 2^n$$
• Connection to combinations: This identity mirrors the binomial expansion sum:
  $$\binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \cdots + \binom{n}{n} = 2^n$$

The “At Least One” Condition ($2^n – 1$)

Most real-world problems require picking at least one item, meaning an empty selection is not allowed.

• Excluding the empty set: The subset where every item is rejected corresponds to $\binom{n}{0} = 1$.
• Formula for selecting at least one: Subtracting this single empty scenario from the total $2^n$ possibilities gives:
  $$\text{Total valid ways} = 2^n – 1$$
• Alternative view: This directly computes:
  $$\binom{n}{1} + \binom{n}{2} + \dots + \binom{n}{n} = 2^n – 1$$

Worked Examples

Now let’s put the $2^n – 1$ formula to work—here’s how to apply what you just learned to common counting scenarios.

Example 1: Inviting Guests to a Dinner Party A host has 6 distinct friends and decides to invite at least one of them to dinner. In how many different ways can the host choose the guest list?

1.Identify the number of distinct items:

There are 6 distinct friends, so $n = 6$.

2.Determine the unrestricted total selections:

Each friend can either be invited or not invited. The total number of subsets is $2^6 = 64$.

3.Exclude the case where no one is invited:

The condition specifies inviting “at least one” friend. Subtract the single case where 0 friends are invited:

$$2^6 – 1 = 64 – 1 = 63$$

There are 63 possible guest selections.

Example 2: Forming a Subject Study Group with Specific Restrictions A student is choosing which subjects to study tonight out of 5 distinct subjects: Math, Physics, Chemistry, Biology, and English. If they must choose at least one subject, but Math must always be included, how many combinations are possible?

1.Fix the required item:

Math must be selected, so there is only 1 choice for Math.

2.Count choices for remaining items:

There are $5 – 1 = 4$ remaining subjects. For each of these 4 subjects, the student can either include it or omit it:

$$2^4 = 16$$

3.Check the ‘at least one’ condition:

Because Math is guaranteed to be in the group, the group can never be empty. Thus, we do not subtract 1:

$$\text{Total ways} = 1 \times 2^4 = 16$$

There are 16 valid subject selections.

3. Combination of Things Which Are NOT All Different

Why This Matters

In standard combinatorics, choosing items from a distinct set relies on formulas like $\binom{n}{r}$, where identity matters. However, real-world problems often involve indistinguishable objects—such as identical coins, marbles, or repetitive letters in a word—where standard formulas fail and overcount possibilities. Mastering selections of identical items simplifies complex counting problems into straightforward partition and case-counting techniques.

Core Concepts

Selections from a Group of Identical Items

When all $n$ available items are identical, selecting $r$ items does not depend on which items you pick, because no item can be distinguished from another. Any two groups of size $r$ are completely identical.

• Rule for Fixed $r$: The number of ways to select $r$ items from $n$ identical items ($0 \le r \le n$) is exactly 1.
• Total Number of Selections (Any Size): You can choose 0 items, 1 item, 2 items, …, or up to $n$ items. Since each choice of quantity offers exactly 1 way, the total number of ways to select any number of items from $n$ identical items is:
  $$n + 1$$
• At Least One Item: If you must select at least one item ($r \ge 1$), there are $(n + 1) – 1 = n$ ways (choosing 1, 2, …, or $n$ items).

Selections from Multiple Groups of Identical and Distinct Items

When a collection contains several sets of identical items alongside unique items, selection choices operate independently across groups.

If a collection contains:

• $p$ identical items of type 1
• $q$ identical items of type 2
• $r$ identical items of type 3
• $k$ distinct items

The total number of ways to make a selection (choosing zero or more of each) is:

$$(p + 1)(q + 1)(r + 1) \cdot 2^k$$

If you must select at least one item overall, subtract the 1 null case where zero items are chosen from all groups:

$$(p + 1)(q + 1)(r + 1) \cdot 2^k – 1$$

Worked Examples

Now let’s apply these selection rules to solve typical problems involving identical items and mixed collections.

Example 1: Selections from Multiple Identical Sets

Find the total number of ways to select at least one fruit from a basket containing 4 identical apples, 5 identical bananas, and 3 identical oranges.

1.Determine choices for each fruit type:

For the 4 identical apples, you can choose 0, 1, 2, 3, or 4 apples (5 choices).

For the 5 identical bananas, you can choose 0, 1, 2, 3, 4, or 5 bananas (6 choices).

For the 3 identical oranges, you can choose 0, 1, 2, or 3 oranges (4 choices).

2.Calculate the product of independent choices:

Multiply the independent options for all three types:

$$5 \times 6 \times 4 = 120\text{ total combinations}$$

3.Exclude the empty selection:

Subtract the 1 case where 0 apples, 0 bananas, and 0 oranges are picked:

$$120 – 1 = 119\text{ ways}$$

Example 2: Combining Identical and Distinct Items

A bag contains 3 identical blue marbles, 2 identical green marbles, and 4 completely distinct red marbles. In how many ways can a person choose at least one marble?

1.Count options for identical items:

Blue marbles (3 identical): choose 0, 1, 2, or 3 $\rightarrow 3 + 1 = 4$ options.

Green marbles (2 identical): choose 0, 1, or 2 $\rightarrow 2 + 1 = 3$ options.

2.Count options for distinct items:

Each of the 4 distinct red marbles can either be included or excluded independently:

$$2^4 = 16\text{ options}$$

3.Multiply and subtract the empty selection:

Combine all independent selections and remove the case where nothing is picked:

$$(4 \times 3 \times 16) – 1 = 192 – 1 = 191\text{ ways}$$

4. Problems Based on Number Theory

Why This Matters

Finding the divisors of large numbers by manual listing quickly becomes impractical. By treating divisor selection as an application of the fundamental counting principle, prime factorization allows you to compute the exact number of divisors of any integer instantly. This concept forms the backbone of algebraic number theory, cryptography, and competitive combinatorics problems.

Core Concepts

Prime Factorization and Divisors

The Fundamental Theorem of Arithmetic states that every integer $N > 1$ can be expressed uniquely (up to order) as a product of prime powers:

$$N = p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}$$

where $p_1, p_2, \dots, p_k$ are distinct positive prime numbers and each exponent $a_i \ge 1$ is an integer.

Any positive divisor $d$ of $N$ must be built solely from these same prime factors. Consequently, $d$ takes the form:

$$d = p_1^{b_1} \cdot p_2^{b_2} \cdots p_k^{b_k}$$

where each exponent $b_i$ is an integer constrained by:

$$0 \le b_i \le a_i$$

The Combinatorial Multiplier Rule

Because the power of each prime factor chosen for $d$ is independent of the others, finding the total number of divisors is an application of the multiplication rule of counting:

• For prime factor $p_1$, the exponent $b_1$ can be any integer from $0$ up to $a_1$, yielding $a_1 + 1$ choices.
• For prime factor $p_2$, the exponent $b_2$ can be any integer from $0$ up to $a_2$, yielding $a_2 + 1$ choices.
• In general, for prime factor $p_i$, there are $a_i + 1$ possible choices.

Multiplying the independent choices together gives the total number of positive divisors, denoted by $d(N)$ or $\tau(N)$:

$$d(N) = (a_1 + 1)(a_2 + 1)\cdots(a_k + 1)$$

Worked Examples

Now let’s apply this counting technique to concrete numbers, observing how prime factorization leads directly to the divisor count.

Example 1: Divisors of a Standard Composite Number Find the total number of positive divisors of $N = 360$.

1.Find the prime factorization:

Break down 360 into prime factors:

360 = 36 * 10 = (2² * 3²) * (2 * 5) = 2³ * 3² * 5¹

2.Identify the exponents of each prime:

The distinct prime factors are 2, 3, and 5.

The corresponding exponents are:

a₁ = 3, a₂ = 2, a₃ = 1

3.Add 1 to each exponent and multiply:

Apply the divisor formula:

d(360) = (3 + 1)(2 + 1)(1 + 1) = 4 * 3 * 2 = 24

Therefore, 360 has 24 positive divisors.

Example 2: Divisors of an Expression with Composite Bases Find the total number of positive divisors of $N = 12^3 \cdot 15^2$.

1.Reduce all bases to prime factors:

Neither 12 nor 15 is prime, so first decompose each base:

12 = 2² * 3

15 = 3 * 5

2.Consolidate powers of identical primes:

Substitute and combine exponents using standard exponent rules:

N = (2² * 3)³ * (3 * 5)² = (2⁶ * 3³) * (3² * 5²) = 2⁶ * 3⁵ * 5²

3.Calculate the divisor product:

The exponents for the prime bases 2, 3, and 5 are 6, 5, and 2.

d(N) = (6 + 1)(5 + 1)(2 + 1) = 7 * 6 * 3 = 126

Thus, N has 126 positive divisors.

5. Permutation of Alike Objects Taken All at a Time

Why This Matters

When arranging distinct objects, every swap creates a new order. But in real-world scenarios—such as unscrambling words with repeated letters, scheduling shifts with identical tasks, or routing through grid paths—identical items create duplicate arrangements. Understanding permutations of alike objects lets you eliminate redundant overcounts systematically.

Core Concepts

The General Formula

If there are $n$ total objects where $p$ objects are indistinguishable of one kind, $q$ objects are indistinguishable of another kind, and $r$ objects are indistinguishable of a third kind (such that $p + q + r \le n$), the number of distinct permutations of all $n$ objects taken together is:

$$\frac{n!}{p! \, q! \, r!}$$

• Total arrangements without restrictions: $n!$ treats all items as if they were unique.
• Correcting overcounts: Because the $p$ identical items can be permuted among themselves in $p!$ ways without changing the visual arrangement, we divide by $p!$. The same logic applies independently to $q!$ and $r!$.

Handling Remaining Distinct Objects

Any items that appear only once have an individual count of $1$. Since $1! = 1$, they do not alter the denominator.

• If all $n$ items are unique, the formula simplifies to $\frac{n!}{1! \times 1! \times \dots} = n!$.
• If all $n$ items are identical to one another, the formula yields $\frac{n!}{n!} = 1$.

Worked Examples

Now let’s apply the multiset permutation formula to real problems by breaking down the counting process step by step.

Example 1: Arranging the Letters of “BALLOON” Find the number of distinct arrangements of all the letters in the word BALLOON.

1.Count total and repeated elements:

The word has 7 letters in total ($n = 7$).

Count the frequency of each letter:

• B: 1
• A: 1
• L: 2 ($p = 2$)
• O: 2 ($q = 2$)
• N: 1

2.Set up the formula:

Divide the factorial of the total count by the factorials of the repeated counts:

$$\text{Arrangements} = \frac{7!}{2! \, 2!}$$

3.Calculate the final result:

Expand and simplify:

$$\frac{5040}{2 \times 2} = \frac{5040}{4} = 1260$$

Example 2: Arranging Colored Flags on a Pole How many distinct vertical signals can be made using 3 identical red flags, 2 identical blue flags, and 4 identical green flags displayed in a single line?

1.Identify values of n, p, q, and r:

• Total flags: $n = 3 + 2 + 4 = 9$
• Red flags: $p = 3$
• Blue flags: $q = 2$
• Green flags: $r = 4$

2.Apply the permutation formula:

$$\text{Arrangements} = \frac{9!}{3! \, 2! \, 4!}$$

3.Simplify the fraction:

Cancel out $4!$ first to make calculation easier:

$$\frac{9 \times 8 \times 7 \times 6 \times 5 \times 4!}{(3 \times 2 \times 1) \times (2 \times 1) \times 4!} = \frac{9 \times 8 \times 7 \times 6 \times 5}{6 \times 2}$$

$$\frac{15120}{12} = 1260$$

6. Circular Permutation

Why This Matters

Arranging items in a straight line depends heavily on which item occupies the first position, but sitting around a round table removes any fixed beginning or end. Circular permutation allows you to count distinct relative arrangements without overcounting identical configurations caused merely by rotating the circle. Mastering this concept is essential for solving standard combinatorics problems involving roundtables, necklaces, and cyclical sequences.

Core Concepts

Linear Versus Circular Arrangements

When arranging $n$ distinct objects in a straight line, there are $n!$ possible permutations because each slot from left to right is unique. However, in a circular arrangement, shifting every element one position clockwise or counterclockwise does not change their relative positions—it represents the exact same cyclic order.

• Rotational Symmetry: For any arrangement of $n$ distinct objects around a circle, rotating every object produces $n$ indistinguishable arrangements.
• Fixing a Reference Point: To avoid counting duplicates, fix one object in an arbitrary position to act as an anchor. The remaining $n – 1$ objects can then be arranged linearly relative to that anchor.
• The Formula: The number of circular permutations of $n$ distinct items is:$$(n – 1)!$$

Clockwise Versus Counterclockwise Distinctions

In seating arrangements around a table, sitting to someone’s left is fundamentally different from sitting to their right, so clockwise and counterclockwise orders are treated as distinct.

However, in objects like necklaces, key rings, or bracelets, flipping the entire object over turns a clockwise order into a counterclockwise order.

• When Orientations Are Distinct (e.g., People at a Table):$$P_{\text{circ}} = (n – 1)!$$
• When Orientations Are Indistinguishable (e.g., Beads on a Ring): Flipping the circle makes opposite rotational directions identical, halving the total count:$$P_{\text{ring}} = \frac{(n – 1)!}{2}$$

Worked Examples

Now let’s apply the circular permutation formulas to both seating arrangements and reversible physical objects.

Example 1: Roundtable Seating Arrangement

Find the number of ways 6 delegates can sit around a circular conference table.

1.Identify the total number of items:

There are $n = 6$ distinct delegates seated around a circle where left and right orientations are distinct.

2.Apply the circular permutation formula:

Fix one delegate in place to break the rotational symmetry. The remaining $6 – 1 = 5$ delegates can be arranged in $(6 – 1)!$ ways.

3.Calculate the final value:

Compute $5!$:

$$5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$$

There are 120 distinct seating arrangements.

Example 2: Arranging Beads on a Key Ring

How many distinct ways can 8 differently colored beads be threaded onto a key ring?

1.Determine symmetry type:

A key ring can be flipped over, which makes clockwise and counterclockwise arrangements identical.

2.Select the appropriate formula:

Use the formula for reversible circular permutations:

$$\frac{(n – 1)!}{2}$$

Here, $n = 8$.

3.Compute the result:

Evaluate $\frac{(8 – 1)!}{2} = \frac{7!}{2}$:

$$\frac{5040}{2} = 2520$$

There are 2,520 distinct arrangements.

7. Geometric Problems: Lines Formed by Points

Why This Matters

Understanding geometric problems in combinatorics bridges the gap between abstract counting and spatial intuition. Whether designing circuit traces between microchip pins or establishing direct communication paths across a network of nodes, determining the number of unique connections relies on choosing subsets of points under geometric constraints.

Core Concepts

The Two-Point Principle

In Euclidean geometry, any two distinct points determine exactly one straight line. When choosing points to form lines, the order of selection does not matter—joining point A to point B yields the exact same line as joining point B to point A. Therefore, this is purely a combination problem rather than a permutation problem.

If you have $n$ coplanar points where no three points lie on the same straight line (non-collinear):

• Every unique pair of points creates a unique straight line.
• The total number of straight lines is given by the combination formula:

$$\binom{n}{2} = \frac{n(n – 1)}{2}$$

Collinearity and Deductions

When three or more points lie on a single line (collinear points), the general formula overcounts.

If a set of $m$ points out of the total $n$ points are collinear:

• Any pair chosen from those $m$ points produces the same identical line instead of $\binom{m}{2}$ distinct lines.
• To correct the count, subtract all the redundant lines $\binom{m}{2}$ and add back the single line that passes through all $m$ collinear points:

$$\text{Total Lines} = \binom{n}{2} – \binom{m}{2} + 1$$

Worked Examples

Now let’s apply the combination formula and collinearity correction to standard geometric configuration problems.

Example 1: Fully Non-Collinear Points Find the number of unique straight lines that can be formed by joining 8 points in a plane, given that no three points are collinear.

1.Identify the parameters:

The total number of points is $n = 8$. Since no three points are collinear, every pair determines a distinct line without overlap.

2.Apply the combination formula:

Compute the number of 2-point combinations:

$$\binom{8}{2} = \frac{8 \times 7}{2 \times 1} = 28$$

3.Conclude the result:

There are 28 unique straight lines formed by joining the 8 points.

Example 2: Accounting for a Collinear Subset A plane contains 10 points. Exactly 4 of these points lie on the same straight line, while no other combination of three points is collinear. How many distinct straight lines can be formed?

1.Calculate total unconstrained lines:

Assume all $n = 10$ points were non-collinear:

$$\binom{10}{2} = \frac{10 \times 9}{2} = 45$$

2.Determine overcounted lines from the collinear set:

The 4 collinear points would individually form:

$$\binom{4}{2} = \frac{4 \times 3}{2} = 6 \text{ lines}$$

However, these 4 points all lie along just 1 common line.

3.Apply the deduction and adjustment:

Subtract the 6 overcounted lines and add back the 1 shared line:

$$\text{Total Lines} = 45 – 6 + 1 = 40$$

8. Distribution of Alike Objects

Why This Matters

When allocating identical resources—like server requests across processors, budget credits across projects, or identical prizes among contestants—order does not matter, but distinct recipients do. Mastering the Stars and Bars technique transforms these potentially overwhelming counting problems into standard combinations, bypassing tedious case-by-case casework.

Core Concepts

Stars and Bars for Non-Negative Distributions

Suppose you want to distribute $n$ identical objects among $r$ distinct recipients where any recipient may receive zero objects ($x_i \ge 0$). This is equivalent to finding the number of non-negative integer solutions to:

$$x_1 + x_2 + \dots + x_r = n$$

To divide $n$ identical objects (“stars”) into $r$ bins, you only need $r – 1$ dividers (“bars”).

• Arranging $n$ stars and $r – 1$ bars creates a total of $n + r – 1$ slots.
• Choosing where to place the $r – 1$ dividers uniquely determines how many objects each person receives.

The total number of non-negative distributions is given by:

$$\binom{n + r – 1}{r – 1} = \binom{n + r – 1}{n}$$

Handling Positive Distributions (At Least One Each)

Often, constraints require that each recipient receives at least one object ($x_i \ge 1$ for all $i$). Instead of memorizing a separate formula, you can convert this to the standard formula using substitution:

• Pre-allocation approach: Give each of the $r$ recipients 1 object first. That leaves $n – r$ identical objects to distribute freely among the $r$ recipients.
• Applying the base formula with $n – r$ objects yields:

$$\binom{(n – r) + r – 1}{r – 1} = \binom{n – 1}{r – 1}$$

Worked Examples

Connecting the stars and bars formula to concrete distribution problems reveals how quickly constraints can be handled using variable substitutions.

Example 1: Distributing Identical Candies (Allowing Zero) Find the number of ways to distribute 10 identical candies among 3 children if any child can receive zero or more candies.

1.Identify parameters:

Here, the number of identical objects is $n = 10$, and the number of distinct recipients is $r = 3$. The problem allows $x_i \ge 0$.

2.Apply the Stars and Bars formula:

Substitute $n = 10$ and $r = 3$ into $\binom{n + r – 1}{r – 1}$:

$$\binom{10 + 3 – 1}{3 – 1} = \binom{12}{2}$$

3.Calculate the final combinations:

Evaluate the binomial coefficient:

$$\binom{12}{2} = \frac{12 \times 11}{2 \times 1} = 66$$

There are 66 ways to distribute the candies.

Example 2: Positive Integer Solutions (At Least One Object) Find the number of positive integer solutions to $x_1 + x_2 + x_3 + x_4 = 12$, where $x_i \ge 1$.

1.Define new non-negative variables:

Let $y_i = x_i – 1$ so that $y_i \ge 0$. Substitute $x_i = y_i + 1$ into the equation:

$$(y_1 + 1) + (y_2 + 1) + (y_3 + 1) + (y_4 + 1) = 12 \implies y_1 + y_2 + y_3 + y_4 = 8$$

2.Identify effective parameters:

We now have $n’ = 8$ remaining objects to distribute among $r = 4$ bins with non-negative constraints ($y_i \ge 0$).

3.Compute using the base formula:

Substitute $n’ = 8$ and $r = 4$:

$$\binom{8 + 4 – 1}{4 – 1} = \binom{11}{3} = \frac{11 \times 10 \times 9}{3 \times 2 \times 1} = 165$$

There are 165 positive integer solutions.

9. Understanding Derangements

Why This Matters

A derangement is a permutation of a set of items where no element appears in its original, designated position. Whether you are analyzing cryptographic shuffling algorithms, calculating the exact probability that nobody gets their own gift in a Secret Santa exchange, or verifying randomized testing protocols, derangements provide the mathematical framework to count complete rearrangements without fixed points.

Core Concepts

What Is a Derangement?

Consider an ordered set of elements $(1, 2, 3, \dots, n)$. A permutation $\sigma$ of this set is called a derangement if:

$$\sigma(i) \neq i \quad \text{for every } i \in \{1, 2, \dots, n\}$$

Any position where $\sigma(i) = i$ is known as a fixed point. Therefore, a derangement is simply a permutation with zero fixed points. The total number of derangements of an $n$-element set is denoted by $!n$ or $D_n$ (sometimes called the subfactorial of $n$).

For small sets:

• For $n = 1$: There is no way to move the single element out of position 1. Thus, $!1 = 0$.
• For $n = 2$: The only valid rearrangement of $(1, 2)$ is $(2, 1)$. Thus, $!2 = 1$.
• For $n = 3$: From the 6 total permutations of $(1, 2, 3)$, only $(2, 3, 1)$ and $(3, 1, 2)$ leave no element in place. Thus, $!3 = 2$.

The Derangement Formula

Using the Principle of Inclusion-Exclusion (PIE), we subtract permutations that fix at least one element, add back those that fix at least two, and continue alternating:

$$!n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!} = n! \left( 1 – \frac{1}{1!} + \frac{1}{2!} – \frac{1}{3!} + \dots + \frac{(-1)^n}{n!} \right)$$

This formula leads to two key insights:

1. Recurrence Relation: Derangements can also be computed recursively:$$!n = (n – 1)(!(n – 1) + !(n – 2))$$
2. Convergence to $1/e$: As $n$ grows large, the alternating sum inside the parentheses approaches the Taylor series expansion for $e^{-1} = 1/e \approx 0.3679$. This means the probability that a random permutation is a derangement rapidly approaches roughly 36.8%, regardless of how large $n$ becomes.

Worked Examples

Now let’s put the derangement formula and recurrence to work with concrete problem setups.

Example 1: The Four-Letter Envelope Mix-Up A clerk has 4 addressed letters and 4 corresponding envelopes. In how many ways can the clerk place every letter into an incorrect envelope?

1.Identify the parameters:

Each letter has one correct matching envelope. A situation where every letter goes to the wrong envelope is a complete derangement of $n = 4$ items.

2.Apply the inclusion-exclusion formula:

Evaluate $!4$ using the subfactorial expansion:

$$!4 = 4! \left( \frac{1}{0!} – \frac{1}{1!} + \frac{1}{2!} – \frac{1}{3!} + \frac{1}{4!} \right)$$

3.Simplify the terms:

Compute the intermediate arithmetic:

• $1 – 1 = 0$
• $\frac{1}{2} – \frac{1}{6} + \frac{1}{24} = \frac{12 – 4 + 1}{24} = \frac{9}{24}$
• $!4 = 24 \times \frac{9}{24} = 9$There are 9 ways to misplace all four letters.

Example 2: Computing Derangements via Recurrence Find the number of derangements for $n = 5$ using the recurrence relation $!n = (n – 1)(!(n – 1) + !(n – 2))$.

1.List known base cases:

Recall the values for smaller sets:

• $!1 = 0$
• $!2 = 1$
• $!3 = 2$
• $!4 = 9$

2.Substitute values into the recurrence:

For $n = 5$, the formula becomes:

$$!5 = (5 – 1)(!4 + !3)$$

$$!5 = 4 \times (9 + 2)$$

3.Calculate the final result:

Multiply out the terms:

$$!5 = 4 \times 11 = 44$$

There are 44 derangements of 5 items.

Permutations & Combinations Questions & Answers

Question 1 (JEE Main / NDA Style: Alike Objects & Letter Arrangement)

Question:

All the letters of the word $\text{BALLOON}$ are arranged in all possible ways. How many distinct words can be formed such that the two $\text{L}$’s never appear together?

• (A) $1260$
• (B) $900$
• (C) $360$
• (D) $540$

Correct Answer: (B) 900

1. Total Arrangements without restriction:
   The word $\text{BALLOON}$ contains $7$ letters where $\text{L}$ appears $2$ times, $\text{O}$ appears $2$ times, and $\text{B, A, N}$ appear $1$ time each:
   $$\text{Total} = \frac{7!}{2! \, 2!} = \frac{5040}{4} = 1260 \text{ arrangements[cite: 6]}$$
2. Arrangements where the two $\text{L}$’s ARE together (Tie-together / String Method):
   Treat the two $\text{L}$’s as a single block $[\text{LL}]$.
   Now we arrange 6 units: $[\text{LL}], \text{B}, \text{A}, \text{O}, \text{O}, \text{N}$, with two identical $\text{O}$’s:
   $$\text{Together} = \frac{6!}{2!} = \frac{720}{2} = 360$$
3. Arrangements where the two $\text{L}$’s are NOT together:
   $$\text{Result} = \text{Total} – \text{Together} = 1260 – 360 = 900$$

Question 2 (JEE Main / Advanced Style: Grouping & Distribution)

Question:

In how many ways can $9$ distinct toys be divided into two groups of $4$ toys and $5$ toys, and then distributed between two children, Alice and Bob?

• (A) $\frac{9!}{4! \, 5!}$
• (B) $\frac{9!}{4! \, 5!} \times 2$
• (C) $\frac{9!}{2! \, 4! \, 5!}$
• (D) $\frac{9!}{(4!)^2}$

Correct Answer: (B)

1. Division/Partition into Unequal Groups:
   When dividing $(m + n)$ distinct objects into groups of size $m$ and $n$ ($m \neq n$), the number of ways to partition them into unlabelled piles is:
   $$\frac{(m + n)!}{m! \, n!} = \frac{9!}{4! \, 5!} = \binom{9}{4} = 126 \text{ ways[cite: 1]}$$
2. Distribution to Specific People:
   Since the groups are unequal in size ($4 \neq 5$), they are inherently distinct. Distributing these two distinct bundles between two specific recipients (Alice and Bob) gives $2!$ ways[cite: 1]:
   $$\text{Total Ways} = \frac{9!}{4! \, 5!} \times 2! = 126 \times 2 = 252 \text{ ways[cite: 1]}$$

Question 3 (CAT / JEE Main Style: Derangements)

Question:

A courier clerk has $5$ addressed letters and $5$ corresponding stamped envelopes. In how many ways can the clerk place the letters such that exactly one letter goes into its correct envelope and the remaining $4$ letters go into incorrect envelopes?

• (A) $9$
• (B) $44$
• (C) $45$
• (D) $120$

Correct Answer: (C) 45

1. Choose which letter is placed correctly:
   Select $1$ correct letter out of $5$:
   $$\binom{5}{1} = 5 \text{ ways}$$
2. Derange the remaining 4 letters ($!4$):
   The remaining $4$ letters must all go into wrong envelopes (a complete derangement of $4$ items):
   $$!4 = 4! \left( 1 – \frac{1}{1!} + \frac{1}{2!} – \frac{1}{3!} + \frac{1}{4!} \right) = 24 \left( \frac{1}{2} – \frac{1}{6} + \frac{1}{24} \right) = 12 – 4 + 1 = 9 \text{[cite: 9]}$$
3. Total Ways:
   $$\text{Total} = \binom{5}{1} \times !4 = 5 \times 9 = 45$$

Question 4 (JEE Main / Advanced Style: Stars & Bars / Alike Distributions)

Question:

Find the number of positive integer solutions to the equation:

$$x_1 + x_2 + x_3 + x_4 = 12, \quad \text{where } x_i \ge 1 \text{ for each } i \in \{1, 2, 3, 4\} \text{[cite: 12]}$$

• (A) $\binom{15}{3} = 455$
• (B) $\binom{11}{3} = 165$
• (C) $\binom{12}{4} = 495$
• (D) $\binom{11}{4} = 330$

Correct Answer: (B) 165

1. Using the Stars and Bars Method:
   For distributing $n$ identical units among $r$ variables where each variable must be positive ($x_i \ge 1$), the formula is:
   $$\binom{n – 1}{r – 1} \text{[cite: 12]}$$
2. Calculation:
   Here, $n = 12$ and $r = 4$[cite: 12]:
   $$\binom{12 – 1}{4 – 1} = \binom{11}{3} = \frac{11 \times 10 \times 9}{3 \times 2 \times 1} = 165 \text{[cite: 12]}$$ (Equivalently, giving $1$ unit to each variable first leaves $12 – 4 = 8$ units to distribute freely: $\binom{8 + 4 – 1}{4 – 1} = \binom{11}{3} = 165$)[cite: 12].

Question 5 (CAT / Number Theory & Combinatorics Style: Divisors)

Question:

Find the total number of positive even divisors of the number $N = 360$.

• (A) $24$
• (B) $18$
• (C) $16$
• (D) $12$

Correct Answer: (B) 18

1. Prime Factorization of $N = 360$:
   $$360 = 2^3 \times 3^2 \times 5^1$$
2. Condition for Even Divisors:
   A divisor $d = 2^a \cdot 3^b \cdot 5^c$ is even if and only if the exponent of $2$ is at least $1$ ($a \in \{1, 2, 3\}$, meaning $3$ choices).
   • Choices for $a$: $3$ choices ($1, 2,$ or $3$)
   • Choices for $b$: $2 + 1 = 3$ choices ($0, 1,$ or $2$)
   • Choices for $c$: $1 + 1 = 2$ choices ($0$ or $1$)
3. Total Even Divisors:
   $$\text{Even Divisors} = 3 \times 3 \times 2 = 18$$ (Note: Total divisors = $(3+1)(2+1)(1+1) = 24$. Odd divisors correspond to $a = 0 \implies 1 \times 3 \times 2 = 6$. Thus, $24 – 6 = 18$.)

Question 6 (JEE Main Style: Circular Permutation & Constraints)

Question:

In how many ways can $4$ Indian delegates and $4$ US delegates sit around a round conference table such that no two Indian delegates sit together?

• (A) $144$
• (B) $576$
• (C) $720$
• (D) $2880$

Correct Answer: (A) 144

1. Use the Gap Method:
   First, seat the $4$ US delegates around the circular table.
   The number of ways to seat $n = 4$ people in a circle is:
   $$(4 – 1)! = 3! = 6 \text{ ways[cite: 8]}$$
2. Seating the Indian Delegates into Gaps:
   Between the $4$ seated US delegates around the circle, there are exactly $4$ distinct gaps created.
   Since the US delegates are already seated, these $4$ gaps are now distinct, distinguishable positions.
   The $4$ Indian delegates can be arranged in these $4$ gaps in:
   $$4! = 24 \text{ ways}$$
3. Total Arrangements:$$\text{Total} = 3! \times 4! = 6 \times 24 = 144$$

Question 7 (JEE Main / NDA Style: Geometric Counting with Collinear Points)

Question:

There are $12$ points in a plane, out of which exactly $5$ points are collinear and no other three points lie on the same straight line. Find the total number of distinct triangles that can be formed by joining these points as vertices.

• (A) $220$
• (B) $210$
• (C) $211$
• (D) $200$

Correct Answer: (B) 210

1. Total Triangles from Unrestricted Points:
   Choosing any $3$ points from $12$ gives:

$$\binom{12}{3} = \frac{12 \times 11 \times 10}{3 \times 2 \times 1} = 220$$

2. Deduct Triangles from Collinear Points:
   Any $3$ points chosen from the $5$ collinear points will lie on a single straight line and fail to form a triangle:

$$\binom{5}{3} = \binom{5}{2} = \frac{5 \times 4}{2 \times 1} = 10$$

3. Total Valid Triangles:
   Unlike lines (where you add back $+1$ for the single straight line), points on a line produce zero triangles.

$$\text{Triangles} = \binom{12}{3} – \binom{5}{3} = 220 – 10 = 210$$

Question 8 (JEE Main / Advanced Style: Selections from Mixed Groups)

Question:

A fruit basket contains $4$ identical apples, $5$ identical bananas, $3$ identical oranges, and $4$ completely distinct mangoes. In how many ways can a person select at least one fruit from the basket?

• (A) $1919$
• (B) $1920$
• (C) $120$
• (D) $960$

Correct Answer: (A) 1919

1. Choices for Identical Items:

• For $4$ identical apples: can pick $0, 1, 2, 3,$ or $4$ $\implies 4 + 1 = 5$ choices.
• For $5$ identical bananas: $5 + 1 = 6$ choices.
• For $3$ identical oranges: $3 + 1 = 4$ choices.

2. Choices for Distinct Items:

• For the $4$ distinct mangoes, each mango has $2$ independent choices (selected or not):

$$2^4 = 16 \text{ choices[cite: 1, 13]}$$

3. At Least One Fruit Condition:
   Using the formula $(p + 1)(q + 1)(r + 1) \cdot 2^k – 1$:

$$\text{Total Ways} = (4 + 1)(5 + 1)(3 + 1) \times 2^4 – 1 \text{[cite: 1]}$$

$$\text{Total Ways} = 5 \times 6 \times 4 \times 16 – 1 = 120 \times 16 – 1 = 1920 – 1 = 1919$$

Question 9 (CAT / JEE Style: Exponent of a Prime in $n!$ — Legendre’s Formula)

Question:

Find the number of consecutive zeros at the end of $100!$.

• (A) $20$
• (B) $24$
• (C) $25$
• (D) $28$

Correct Answer: (B) 24

1. Concept:
   The number of terminal zeros in $N!$ equals the highest power of $10$ dividing $N!$, which is determined by the exponent of prime $5$ (since factors of $2$ are far more abundant).
2. Legendre’s Formula for Prime $p = 5$ in $100!$:
   $$E_5(100!) = \left\lfloor \frac{100}{5} \right\rfloor + \left\lfloor \frac{100}{5^2} \right\rfloor + \left\lfloor \frac{100}{5^3} \right\rfloor + \dots$$

$$E_5(100!) = 20 + 4 + 0 = 24$$

3. Conclusion:
   There are exactly $24$ trailing zeros.

Question 10 (JEE / NDA Style: Circular Permutation with Reversible Symmetry)

Question:

How many distinct ways can $8$ differently colored, distinct beads be threaded onto a key ring (or necklace)?

• (A) $5040$
• (B) $2520$
• (C) $40320$
• (D) $720$

Correct Answer: (B) 2520

1. Circular Symmetry:
   Arranging $n$ distinct objects in a circle fixes $1$ reference anchor, giving $(n – 1)!$ arrangements.
2. Reversibility (Clockwise vs. Counterclockwise):
   For a necklace or key ring, flipping the ring over makes clockwise and counterclockwise arrangements visually identical:

$$P_{\text{ring}} = \frac{(n – 1)!}{2} \text{[cite: 4]}$$

For $n = 8$ beads:

$$\text{Ways} = \frac{(8 – 1)!}{2} = \frac{7!}{2} = \frac{5040}{2} = 2520$$

Question 11 (CAT / JEE Main Style: Non-Negative Integer Solutions with Upper Bound)

Question:

Find the number of non-negative integer solutions to:

$$x_1 + x_2 + x_3 = 10, \quad \text{such that } 0 \le x_1 \le 4 \text{ and } x_2, x_3 \ge 0 \text{[cite: 12]}$$

• (A) $40$
• (B) $45$
• (C) $66$
• (D) $21$

Correct Answer: (A) 40

1. Total Non-Negative Solutions without restriction on $x_1$:
   Using Stars and Bars $\binom{n + r – 1}{r – 1}$ for $n = 10, r = 3$:

$$\text{Total} = \binom{10 + 3 – 1}{3 – 1} = \binom{12}{2} = \frac{12 \times 11}{2} = 66 \text{[cite: 12]}$$

2. Subtract Solutions where $x_1 \ge 5$ (Violating the condition):
   Substitute $x_1 = y_1 + 5$ where $y_1 \ge 0$:

$$(y_1 + 5) + x_2 + x_3 = 10 \implies y_1 + x_2 + x_3 = 5$$

The number of non-negative solutions is:

$$\binom{5 + 3 – 1}{3 – 1} = \binom{7}{2} = \frac{7 \times 6}{2} = 21$$

3. Valid Solutions:
   $$\text{Valid} = 66 – 21 = 40$$

Question 12 (JEE Advanced Style: Combinations with Specific Inclusions/Exclusions)

Question:

A student council must select a delegation of $5$ members from a group of $7$ boys and $5$ girls. If the delegation must contain at least one girl, in how many ways can the committee be formed?

• (A) $771$
• (B) $792$
• (C) $750$
• (D) $720$

Correct Answer: (A) 771

1. Total Ways to Choose Any 5 Members:
   Total members available = $7 + 5 = 12$.

$$\text{Total} = \binom{12}{5} = \frac{12 \times 11 \times 10 \times 9 \times 8}{5 \times 4 \times 3 \times 2 \times 1} = 792$$

2. Complement Rule (Delegations with NO Girls / All Boys):
   Choosing all $5$ members strictly from the $7$ boys:

$$\binom{7}{5} = \binom{7}{2} = \frac{7 \times 6}{2 \times 1} = 21$$

3. At Least One Girl:
   $$\text{Result} = \text{Total} – \text{All Boys} = 792 – 21 = 771$$