Combinatorics, Permutations & Elementary Probability
“Factorial arrangements, circular permutations, derangements, stars and bars, and dice/coin/card probability.”
1.Systematic Combinatorial Counting Strategies
§ 2.1.Counting problems in GATE Aptitude reward disciplined partitioning:
1. The Tie Method (Together): To arrange items where certain elements must always appear together, bundle them into a single super-element.
2. The Gap Method (Never Together): To ensure no two restricted elements are adjacent, first arrange the unrestricted elements, then place the restricted elements into the empty slots (gaps) created between them.
3. Derangements Formula: The number of permutations of n elements such that no element appears in its original position is given by:
D_n = n! * Sum_{k=0}^n [ (-1)^k / k! ]
For large n, D_n / n! approaches 1/e ≈ 0.3678.
Memorize the first 5 derangement values directly for instant GATE answers: D_1 = 0, D_2 = 1, D_3 = 2, D_4 = 9, D_5 = 44.
2. Worked Problem: Gap Method for Non-Adjacent Seating
Do not subtract adjacent pairs from total without accounting for triple overlaps.
Problem [Original Practice Problem · Modeled on GATE Pattern]:
In how many ways can 5 computer science professors and 4 data science professors sit in a single row such that no two data science professors sit next to each other?
Step 1: Arrange the unrestricted group (5 CS professors) in a row:
Number of ways = 5! = 120 ways.
Step 2: Identify the gaps created by 5 professors:
_ CS1 _ CS2 _ CS3 _ CS4 _ CS5 _
There are 5 + 1 = 6 available gaps.
Step 3: Select and arrange the 4 Data Science professors into the 6 gaps:
Number of ways to choose 4 gaps and arrange = 6P4 = 6! / (6 - 4)! = 6 5 4 * 3 = 360 ways.
Step 4: Apply multiplication principle:
Total ways = 5! 6P4 = 120 360 = 43,200 ways.
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.
Curated for clarity, rigorous numerical solving, and semester excellence:
GATE-specific aptitude coverage with past-paper question patterns.
Systematic aptitude preparation with exam-pattern questions.