Counting principles, permutations and combinations

Objectives and assumptions

Count a finite set of outcomes without listing every outcome. Decide whether choices form disjoint alternatives or successive stages; distinguish ordered arrangements from unordered selections; handle repetition, restrictions and overlaps; and justify a pigeonhole conclusion. Prerequisites: finite sets, multiplication, factorial notation and basic logic. All objects described as distinct really are distinguishable. Unless explicitly stated otherwise, rotations are different, positions are labeled and selection is without replacement. Recurrences, generating functions, advanced inclusion–exclusion and probability need further lessons.

The first step is to define one outcome precisely. A committee {A,B} is the same committee as {B,A}. A president–secretary assignment (A,B) is different from (B,A). Both tasks choose two people, but their sample spaces differ. A formula cannot decide this modeling question for you.

1. Sum rule and product rule

If a task is performed by exactly one of two mutually exclusive methods, with a outcomes of the first kind and b of the second, the total is a+b. For example, choose one elective from four mathematics electives or three computing electives, with no course in both lists: seven possibilities. If an item appears in both lists, simple addition double-counts it.

If a task consists of successive choices with a options for stage one and exactly b options for stage two for each first choice, there are ab outcomes. Three shirts and two trousers give six outfits. The second-stage choices need not be the same objects after each first choice, but their count must be b. Choosing an ordered pair of different students from five gives 5×4=20; the available second student depends on the first, yet four choices always remain.

If stage counts differ by branch, count each branch and add. Suppose a first symbol is A or B. After A, allow suffixes 0,1,2; after B, allow only 0,1. There are 3+2=5 strings, not 2×3. A choice tree exposes unequal branches and prevents a careless product.

2. Ordered arrangements

For n distinct objects, ordering all of them gives n!=n(n−1)…1 outcomes. Define 0!=1: there is one empty arrangement, so identities remain consistent. Choosing and ordering r of n distinct objects, without replacement, gives P(n,r)=n!/(n−r)! for integers 0≤r≤n. There are n choices for the first position, n−1 for the second, and n−r+1 for the last.

Worked example: award gold, silver and bronze to different people among seven participants. Positions are distinct and no person receives two awards, so P(7,3)=7×6×5=210. Dividing by 3! would forget which person received which award and would count a different task.

If repetition is allowed in r labeled positions and each position allows all n symbols, the count is n^r. Four-symbol strings over {A,B,C} number 3^4=81. A string is not automatically a decimal integer: leading zeros are allowed in a code unless a rule forbids them.

Worked example: form a three-digit decimal integer with no repeated digit. Hundreds has nine choices (1–9), tens then has nine (zero plus the eight unused nonzero digits), and units has eight. Total 9×9×8=648. Using 10×9×8 incorrectly permits a leading zero; using 9×8×7 incorrectly bans zero from every position.

3. Unordered selections

Choosing r objects from n distinct objects without replacement gives C(n,r)=n!/[r!(n−r)!]. Each unordered r-element subset appears r! times among ordered selections, once per ordering. Dividing by r! is justified because every selection has exactly that many orderings. For instance, choosing three committee members from seven gives 210/6=35.

C(n,0)=C(n,n)=1. Choosing nobody yields one empty selection, not zero selections. Also C(n,r)=C(n,n−r): choosing included objects uniquely determines the excluded ones. These facts are useful checks. For r outside 0…n there is no such subset; some counting conventions define C(n,r)=0 there, but the factorial expression above must not be applied to negative factorials.

If identical symbols repeat, blindly dividing by r! can fail. For arrangements of the multiset AABC, temporarily distinguish the two A copies. There are 4! labeled arrangements; swapping the two A labels produces the same visible string, giving 4!/2!=12 visible arrangements. This reasoning concerns indistinguishable copies, not selecting with replacement. We do not develop the full combinations-with-repetition formula here.

4. Restrictions: split into disjoint cases

Choose a three-person committee from four researchers and three designers, with at least one designer. Count the complement: all committees C(7,3)=35 minus committees with no designer C(4,3)=4. The answer is 31. “At least one” includes one, two and three designers; it is not “exactly one.”

Check by disjoint cases: exactly one designer gives C(3,1)C(4,2)=18; exactly two gives C(3,2)C(4,1)=12; exactly three gives C(3,3)C(4,0)=1. Sum 18+12+1=31. Every valid committee belongs to exactly one case. This agreement checks both methods and helps detect overlapping cases.

Complement counting requires a clearly specified universe: valid = all − invalid. If counting five-bit strings with at least one 1, all strings number 2^5=32 and only 00000 is invalid, leaving 31. For exactly two 1s, choose their two positions: C(5,2)=10. Multiplying that by 2^3 would be wrong because the remaining positions must all be 0.

5. Overlaps and inclusion–exclusion

For finite sets A and B, |A∪B|=|A|+|B|−|A∩B|. Count every object once by subtracting its duplicated count. If 18 learners study logic, 15 study algebra and 7 study both, then 26 study at least one. If the universe contains 40 learners, 40−26=14 study neither. The union count is not 33, and “neither” is not the same as “not both.”

For three sets, add single-set sizes, subtract all three pair intersections, then add the triple intersection once. An object in all three is counted 3−3+1=1 times. Pair-intersection counts include objects in the triple intersection unless the question explicitly says “only these two.” Keep those interpretations separate.

6. Pigeonhole principle

If N objects are assigned to k available boxes, where k≥1, some box contains at least ceil(N/k) objects. Boxes may actually be empty; “available” describes the k categories, not a requirement that each gets an object. To avoid ambiguity, think of k labeled boxes. If every box held at most ceil(N/k)−1, their total capacity would be less than N, a contradiction.

Example: among 13 objects placed into 4 boxes, some box has at least 4 objects. This guarantee is tight: occupancy 4,3,3,3 prevents a guarantee of 5. More generally, k(m−1)+1 objects force at least m in one of k boxes. This is an existence conclusion; it does not identify the box or say every box has m objects.

Solving checklist

Describe an outcome. Mark whether order matters, whether repetition is allowed and whether positions have different restrictions. Use products for equal-sized successive branches, sums for disjoint cases, and inclusion–exclusion for overlaps. For a restriction, compare direct counting with complement counting. Finally test a tiny version by enumeration and check that the answer is a nonnegative integer no larger than the unrestricted count.

7. Worked three-set inclusion–exclusion

Among 40 learners, let A, B and C be those who study three subjects. Suppose |A|=20, |B|=18, |C|=12, |A∩B|=8, |A∩C|=5, |B∩C|=4 and |A∩B∩C|=2. The pair-intersection counts include the learners in all three subjects.

Then |A∪B∪C|=20+18+12−8−5−4+2=35, so 5 study none. “Exactly A and B” has 8−2=6 learners, not 8. Exactly two subjects has (8−2)+(5−2)+(4−2)=11 learners. A second check uses disjoint regions: only A=20−8−5+2=9, only B=8 and only C=5; hence exactly one=22, exactly two=11 and all three=2, totaling 35.

This example shows why wording matters. “Both A and B” generally includes all three; “A and B but not C” excludes the triple intersection. Never reuse the same number for both meanings without checking the question.

Original practice: six single-correct MCQs

Original questions, not previous-year questions. Choose exactly one option.

C01. A code has three labeled positions, each allowing any of A,B,C,D, with repetition allowed. How many codes exist?

A. 12 B. 24 C. 64 D. 81

Answer: C

A: 4+4+4 uses addition for successive stages; a product is needed.

B: 4×3×2 wrongly forbids repetition.

C: Each of three positions has four choices, so 4^3=64.

D: 3^4 reverses the number of symbols and positions.

C02. How many three-digit decimal integers have no repeated digit?

A. 720 B. 648 C. 504 D. 900

Answer: B

A: 10×9×8 allows zero in the first position, which would not give a three-digit integer.

B: There are 9 nonzero first digits, 9 remaining second digits including zero, and 8 final choices: 648.

C: 9×8×7 wrongly excludes zero from every position.

D: 9×10×10=900 permits repeated digits.

C03. How many unordered three-person committees can be selected from seven distinct people?

A. 21 B. 210 C. 343 D. 35

Answer: D

A: C(7,2)=21 selects two people, not three.

B: P(7,3)=210 counts each committee in 3!=6 orders.

C: 7^3 permits repetition and distinguishes positions, neither of which applies.

D: C(7,3)=7×6×5/(3×2×1)=35; committee order does not matter.

C04. From four researchers and three designers, how many three-person committees contain at least one designer?

A. 31 B. 18 C. 34 D. 35

Answer: A

A: Subtract the four all-researcher committees from all 35 committees: 35−4=31.

B: 18 counts exactly one designer and misses committees with two or three.

C: 34 subtracts the all-designer committee, but that committee is allowed.

D: 35 includes the four committees containing no designer.

C05. In a group of 40, 18 study logic, 15 algebra and 7 both. How many study neither?

A. 7 B. 26 C. 14 D. 33

Answer: C

A: 40−18−15=7 subtracts the seven shared learners twice.

B: 26 is the union size, meaning at least one subject, not neither.

C: At least one totals 18+15−7=26; neither totals 40−26=14.

D: 33 adds the two counts without correcting overlap and does not count neither.

C06. What is the smallest number of objects that guarantees at least five in one of four boxes, for every placement?

A. 16 B. 17 C. 20 D. 5

Answer: B

A: Sixteen can be distributed 4,4,4,4, avoiding five in any box.

B: Four boxes hold at most 16 while each stays below five; the seventeenth forces five somewhere.

C: Twenty suffices but is not minimal; 17 already guarantees it.

D: Five objects can be distributed 2,1,1,1, so no box need contain five.

Source and scope

This introductory lesson aligns with Discrete Mathematics in Section 1 of the official GATE 2027 CS syllabus. It is not full-topic or full-syllabus coverage. The source establishes syllabus relevance; teaching examples and questions are original.

Official GATE 2027 CS syllabus (verified 2026-10-14).