0.2.4 · Counting toolkit: combinations, inclusion–exclusion

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

Negate "every CS course is taken by Asha". from Lesson 0.2.3
How many possible relations are there on two domains of sizes 2 and 3? from Lesson 0.2.2
How many subsets of a 6-element set contain one particular element? from Lesson 0.2.1

1 · The Hook

GATE loves counting questions: "How many superkeys does this relation have?", "How many schedules of these two transactions are possible?", "How many keys can a B+ tree of height 3 hold?" Each is a counting problem in disguise. Three tools cover almost all of them: arrangements, choices and inclusion–exclusion.

2 · Predict First

A relation has 5 attributes. How many attribute groups of size 2 are there? And how many attribute groups contain attribute A or attribute B (or both)?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

Predict First — the answer

Groups of size 2: 10 (5 choose 2). Groups containing A or B: total 2⁵ = 32 groups; those containing neither A nor B are the 2³ = 8 groups built from the other three attributes. So 32 − 8 = 24. (Inclusion–exclusion gives the same: 16 + 16 − 8 = 24.)

Product rule and arrangements

If one choice can be made in m ways and a second, independent choice in n ways, both together can be made in m × n ways.

n! (n factorial) = n × (n − 1) × … × 1 is the number of ways to arrange n distinct items in order. 0! = 1. 3! = 6, 4! = 24, 5! = 120.

Combinations

C(n, k) ("n choose k") is the number of ways to choose k items from n when order does not matter:

C(n, k) = n! / (k! (n − k)!)

C(5, 2) = 10, C(4, 2) = 6, C(n, 0) = C(n, n) = 1, C(n, 1) = n, C(n, k) = C(n, n − k). The sum C(n, 0) + C(n, 1) + … + C(n, n) = 2ⁿ (all subsets, grouped by size).

Arranging with fixed internal order

Two transactions have 2 and 3 steps. Their steps can be interleaved, but each transaction's own steps must stay in order. Choose which 2 of the 5 positions belong to the first transaction: C(5, 2) = 10 ways. In general, interleavings of sequences of lengths m and n: C(m + n, m) = (m + n)! / (m! n!). (Used in Lesson 6.3.1.)

Inclusion–exclusion

Two sets: |A ∪ B| = |A| + |B| − |A ∩ B|.
Three sets: |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.

"Count the ones with A, the ones with B, …, subtract what you double-counted, add back what you removed too often."

The superkey-counting pattern (preview)

Attribute groups of a relation with n attributes that contain a given group X of k attributes: the other n − k attributes are free, so 2ⁿ⁻ᵏ groups. Groups containing X or Y: 2ⁿ⁻|X| + 2ⁿ⁻|Y| − 2ⁿ⁻|X ∪ Y|. Lesson 2.2.1 uses exactly this.

4 · Visual

Groups of attributes from {A, B, C, D, E}  (2^5 = 32 in all)

contain A          : A fixed in, 4 free  -> 2^4 = 16
contain B          : B fixed in, 4 free  -> 2^4 = 16
contain A and B    : both fixed, 3 free  -> 2^3 =  8
contain A or B     : 16 + 16 - 8         =      24
contain neither    : 32 - 24             =       8   (= 2^3, subsets of {C,D,E})

5 · Worked Examples

Example 1 Easy

Compute 4!, C(6, 2) and C(6, 4).

Solution

4! = 24. C(6, 2) = 6·5/2 = 15. C(6, 4) = C(6, 2) = 15.

Example 2 Medium

In how many ways can the operations of T1 (3 steps) and T2 (2 steps) be interleaved, keeping each transaction's own order?

Solution

C(5, 2) = 10.

Example 3 GATE

R has attributes A, B, C, D, E, F. How many attribute groups contain AB or CD (or both)?

Solution

Contain AB: 2⁴ = 16. Contain CD: 2⁴ = 16. Contain both (ABCD): 2² = 4. Total 16 + 16 − 4 = 28.

6 · GATE Traps

C(n, k) counts unordered choices; arrangements of k from n in order are n!/(n − k)!.
0! = 1, so C(n, 0) = 1.
In inclusion–exclusion for "X or Y", the overlap is "contains X ∪ Y", whose size uses |X ∪ Y|, not |X| + |Y|, when X and Y share attributes.
Interleavings of m and n steps: C(m + n, m), not (m + n)!.

7 · Memory Hook

"Choose = C, Arrange = !, Or = add then subtract the overlap."

8 · Connect the Dots

Lessons 0.2.1–0.2.3 gave sets, tuples and logic; this lesson added counting. The toolkit is complete. Next: the Chapter 0.2 Lock-in, the Phase 0 checkpoint, and then Phase 1, where we draw the first ER diagram.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · NAT · 1 mark(s) — Combinations

What is C(7, 3)?

Numerical answer: ________

Q2 · NAT · 2 mark(s) — Interleavings

T1 has 4 operations and T2 has 2. How many interleavings keep each transaction's own order?

Numerical answer: ________

Q3 · NAT · 2 mark(s) — Inclusion–exclusion

R has 5 attributes A, B, C, D, E. How many attribute groups contain A or B?

Numerical answer: ________

Q4 · NAT · 2 mark(s) — Inclusion–exclusion

R has 5 attributes A, B, C, D, E. How many attribute groups contain AB or BC?

Numerical answer: ________

Q5 · MCQ · 1 mark(s) — Factorial

In how many orders can 4 transactions run one after another (each runs completely before the next starts)?

(A) 10
(B) 24
(C) 16
(D) 4

10 · Rule Card

Product rule: m × n. n! arrangements; 0! = 1.
C(n, k) = n!/(k!(n − k)!); C(n, k) = C(n, n − k); Σₖ C(n, k) = 2ⁿ.
Interleavings of m and n ordered steps: C(m + n, m).
|A ∪ B| = |A| + |B| − |A ∩ B|; three sets: add singles, subtract pairs, add the triple.
Groups of n attributes containing a fixed group X: 2ⁿ⁻|X|.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

product rulefactorial n!combination C(n, k)interleavings C(m+n, m)inclusion–exclusion (2 and 3 sets)groups containing a fixed set 2ⁿ⁻ᵏ

12 · Answer Vault

Reveal answers when you’re ready

Recall Warm-up

Some CS course is not taken by Asha.
2⁶ = 64.
2⁵ = 32.