GATE CS

Combinatorics

Counting

Counting is the art of finding how many objects have a given property without listing them: choosing, arranging, distributing and avoiding forbidden cases. It gives closed forms for the number of strings, subsets, functions, relations, matrices and lattice paths, and the sample-space sizes behind probability questions. A small set of rules and identities, applied with care about whether order matters and whether repetition is allowed, settles such questions.

6 previous-year questions · 6 solved · 6 practice questions

1. Basic rules, permutations and combinations

Sum rule. If a task can be done in one of two ways that cannot happen together (disjoint cases), with $m$ and $n$ outcomes respectively, there are $m + n$ outcomes. Product rule. If a task is done in two stages, with $m$ outcomes for the first and $n$ for the second whatever the first was, there are $m \cdot n$ outcomes. Most formulas below are built from these two rules.

Two questions decide the formula: does order matter (arrangement or selection), and is repetition allowed? Here $n$ is the number of distinct kinds available and $r$ the number of positions or picks. Conventions used throughout: $∣ A ∣$ is the number of elements of a finite set $A$ ; $[n] = {1, 2, \dots, n}$ ; $0! = 1$ ; and $(r n) = 0$ when $r > n$ or $r < 0$ .

Choose r from n distinct kinds	Repetition not allowed	Repetition allowed
Order matters (arrangements)	$P (n, r) = \frac{n !}{( n - r )!}$	$n^{r}$
Order does not matter (selections)	$(r n)$	$(r n + r - 1)$

PERMUTATIONS OF R FROM N DISTINCT OBJECTS

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

Ordered arrangements, no repetition, $0 \leq r \leq n$ . Also the number of injective functions from an $r$ -set to an $n$ -set.

COMBINATIONS

(r n) = \frac{n !}{r ! ( n - r )!} = (n - r n)

Unordered selections of $r$ from $n$ distinct objects, no repetition, $0 \leq r \leq n$ . Symmetry: choosing the ones taken is the same as choosing the ones left.

SELECTIONS WITH REPETITION

(r n + r - 1)

Unordered choice of $r$ items from $n$ kinds ( $n \geq 1$ ) when each kind may be taken any number of times (multisets of size $r$ ).

CIRCULAR ARRANGEMENTS

(n - 1)!

Seating $n \geq 1$ distinct people round a table when rotations count as the same arrangement (reflections counted as different). If reflections are also the same and $n \geq 3$ , divide by 2: $(n - 1)! /2$ .

Procedure for a counting question

Decide what is being built (a string, a subset, a function, a seating) and what makes two outcomes different.
Break the construction into stages; use the product rule across stages and the sum rule across disjoint cases.
For a restriction, either build so the restriction is respected, or count all and subtract the bad ones (complement).
Check with a tiny case (n = 2 or 3) by listing.

EXAM TIP

Place the restricted position first. For a number whose first digit cannot be 0, fill the first digit (9 ways), then the rest freely. Choosing a leading position last often forces awkward case splits.

2. Identical objects, multinomials and distributions

When some objects are identical, swapping them gives the same arrangement, so you divide out those swaps. For $n$ objects with $n_{1}$ of one kind, $n_{2}$ of another and so on, where $n_{1} + \dots + n_{k} = n$ , the count is the multinomial coefficient.

ARRANGEMENTS WITH IDENTICAL ITEMS (MULTINOMIAL COEFFICIENT)

\frac{n !}{n _{1} ! n _{2} ! \dots n _{k} !}

Distinct arrangements of $n$ objects of which $n_{i}$ are alike of type $i$ , $\sum n_{i} = n$ . It is also the number of ways to split $n$ distinct objects into labelled groups of sizes $n_{1}, \dots, n_{k}$ .

STARS AND BARS: NON-NEGATIVE SOLUTIONS

x_{1} + x_{2} + \dots + x_{k} = n, x_{i} \geq 0 \Rightarrow (k - 1 n + k - 1)

Number of integer solutions ( $k \geq 1$ ); equals the number of ways to put $n$ identical objects into $k$ distinct bins, empty bins allowed.

STARS AND BARS: POSITIVE SOLUTIONS

x_{1} + x_{2} + \dots + x_{k} = n, x_{i} \geq 1 \Rightarrow (k - 1 n - 1)

Every bin non-empty ( $n, k \geq 1$ ). For a lower bound $x_{i} \geq a_{i}$ , substitute $y_{i} = x_{i} - a_{i}$ and reduce $n$ by $\sum a_{i}$ .

STARS AND BARS WITH AN INEQUALITY

x_{1} + x_{2} + \dots + x_{k} \leq n, x_{i} \geq 0 \Rightarrow (k n + k)

Add a slack variable $x_{k + 1} = n - (x_{1} + \dots + x_{k}) \geq 0$ ; the equation now has $k + 1$ unknowns summing to $n$ .

For distinct objects, each object independently chooses a bin, so there are $k^{n}$ ways to place $n$ distinct objects into $k$ distinct bins. The number of ways to place them so that no bin is empty (onto functions) comes from inclusion-exclusion, covered in section 4. Dividing that by $k!$ gives the number of ways into $k$ identical non-empty bins, called the Stirling number of the second kind $S (n, k)$ .

STIRLING NUMBERS OF THE SECOND KIND

S (n, k) = k S (n - 1, k) + S (n - 1, k - 1), S (n, n) = 1, S (n, 1) = 1 (n \geq 1)

$S (n, k)$ = number of ways to split a set of $n$ distinct objects into $k$ non-empty unlabelled blocks. Conventions: $S (0, 0) = 1$ , $S (n, 0) = 0$ for $n \geq 1$ , $S (n, k) = 0$ for $k > n$ . Also $S (n, 2) = 2^{n - 1} - 1$ . Example values: $S (4, 2) = 7$ , $S (5, 2) = 15$ , $S (5, 3) = 25$ .

PARTITIONS OF AN INTEGER INTO EXACTLY K PARTS

p (n, k) = p (n - 1, k - 1) + p (n - k, k)

Number of ways to write $n$ as a sum of exactly $k$ positive integers with order ignored. Boundary values: $p (0, 0) = 1$ ; $p (n, k) = 0$ if $k > n$ , or if $n \geq 1$ and $k \leq 0$ . $p (n)$ is the total over all $k$ ; $p (1), \dots, p (7) = 1, 2, 3, 5, 7, 11, 15$ .

Objects	Bins	Rule	Count
$n$ distinct	$k$ distinct, empty allowed	each object picks a bin	$k^{n}$
$n$ distinct	$k$ distinct, none empty	onto functions	$k! S (n, k)$
$n$ identical	$k$ distinct, empty allowed	stars and bars	$(k - 1 n + k - 1)$
$n$ identical	$k$ distinct, none empty	stars and bars	$(k - 1 n - 1)$
$n$ distinct	$k$ identical, none empty	Stirling number	$S (n, k)$
$n$ distinct	$k$ identical, empty allowed	sum over non-empty bins used	$\sum_{j = 0}^{k} S (n, j)$
$n$ identical	$k$ identical, none empty	integer partitions	$p (n, k)$
$n$ identical	$k$ identical, empty allowed	partitions into at most $k$ parts	$p (n + k, k)$

WORKED EXAMPLE

How many distinct arrangements of the letters of ENGINEER have no two E's adjacent?

Solution

ENGINEER has 8 letters: E three times, N twice, and G, I, R once each.
Arrange the five non-E letters N, N, G, I, R first: $5! /2! = 60$ ways.
These five letters leave 6 gaps (including both ends). Put the three E's in three different gaps: $(3 6) = 20$ ways.
The E's are identical, so no further division is needed. Total $60 \times 20 = 1200$ .

Answer: 1200

EXAM TIP

Do not confuse the two stars-and-bars forms. With $x_{i} \geq 0$ the top of the binomial is $n + k - 1$ ; with $x_{i} \geq 1$ it is $n - 1$ . Test with $n = 2, k = 2$ : non-negative gives 3 solutions (0+2, 1+1, 2+0), positive gives 1.

3. The binomial theorem and identities

BINOMIAL THEOREM

(x + y)^{n} = k = 0 \sum n (k n) x^{n - k} y^{k}

For a non-negative integer $n$ . The coefficient of $x^{n - k} y^{k}$ is $(k n)$ ; there are $n + 1$ terms. In $(x_{1} + \dots + x_{k})^{n}$ the coefficient of $x_{1}^{n_{1}} \dots x_{k}^{n_{k}}$ , where $n_{1} + \dots + n_{k} = n$ , is $\frac{n !}{n _{1} ! \dots n _{k} !}$ .

PASCAL'S IDENTITY

(k n) = (k n - 1) + (k - 1 n - 1)

For $n \geq 1$ and $1 \leq k \leq n$ . Split the $k$ -subsets of an $n$ -set by whether they contain a chosen element.

SUM OF A ROW

k = 0 \sum n (k n) = 2^{n}, k = 0 \sum n (- 1)^{k} (k n) = 0 (n \geq 1)

Total number of subsets of an $n$ -set; from $x = y = 1$ and $x = 1, y = - 1$ . Hence even-size subsets and odd-size subsets each number $2^{n - 1}$ for $n \geq 1$ .

WEIGHTED ROW SUM

k = 0 \sum n k (k n) = n 2^{n - 1}

Follows from $k (k n) = n (k - 1 n - 1)$ (choose a committee, then its leader).

VANDERMONDE'S IDENTITY

k = 0 \sum r (k m) (r - k n) = (r m + n)

Choose $r$ from two groups of sizes $m$ and $n$ by how many come from the first (terms with $k > m$ or $r - k > n$ are 0). The case $m = n = r$ gives $\sum_{k} (k n)^{2} = (n 2 n)$ .

HOCKEY-STICK IDENTITY

i = r \sum n (r i) = (r + 1 n + 1)

For $0 \leq r \leq n$ . Sum down a diagonal of Pascal's triangle.

Within row $n$ the entries $(k n)$ rise strictly up to the middle and fall strictly after it. For even $n$ the single largest entry is $(n /2 n)$ ; for odd $n$ the two middle entries $(( n - 1 ) /2 n)$ and $(( n + 1 ) /2 n)$ are equal and both are the largest. Many identities have a combinatorial proof: count one set in two different ways.

EXAM TIP

To evaluate a sum like $\sum_{k = 0}^{n} (k n) 3^{k}$ , recognise the binomial theorem with $x = 1, y = 3$ : the value is $4^{n}$ . Putting numbers into $(x + y)^{n}$ is the fastest way to get such sums.

4. Inclusion-exclusion, derangements and the pigeonhole principle

INCLUSION-EXCLUSION

i = 1 ⋃ m A_{i} = i \sum ∣ A_{i} ∣ - i < j \sum ∣ A_{i} \cap A_{j} ∣ + i < j < l \sum ∣ A_{i} \cap A_{j} \cap A_{l} ∣ - \dots + (- 1)^{m + 1} ∣ A_{1} \cap \dots \cap A_{m} ∣

Counts elements with at least one of $m$ properties; for two sets, $∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣$ . The number with none of the properties is $∣ U ∣$ minus this value.

Use it in the complement form for restrictions: let $A_{i}$ be the set of objects that violate condition $i$ ; the good objects number $∣ U ∣ - ∣ ⋃ A_{i} ∣$ . When every $r$ -fold intersection has the same size by symmetry, each sum collapses to $(r m)$ times one term.

ONTO FUNCTIONS

# {onto f : [n] \to [k]} = j = 0 \sum k (- 1)^{j} (j k) (k - j)^{n}

Functions from an $n$ -set onto a $k$ -set; equals $k! S (n, k)$ and is $0$ if $n < k$ .

DERANGEMENTS

D_{n} = n! k = 0 \sum n \frac{( - 1 ) ^{k}}{k !}, D_{n} = (n - 1) (D_{n - 1} + D_{n - 2}) (n \geq 2)

Permutations of $n$ objects with no object in its original place. Convention $D_{0} = 1$ . Also $D_{n} = n D_{n - 1} + (- 1)^{n}$ , and for $n \geq 1$ , $D_{n}$ is the integer nearest to $n! / e$ . $D_{1} = 0, D_{2} = 1, D_{3} = 2, D_{4} = 9, D_{5} = 44, D_{6} = 265$ .

PERMUTATIONS WITH EXACTLY K FIXED POINTS

(k n) D_{n - k}

Choose which $k$ objects stay put, then derange the other $n - k$ (for $k = n$ this gives $D_{0} = 1$ , the identity).

PIGEONHOLE PRINCIPLE (GENERALISED)

If n objects go into k boxes, some box holds at least ⌈ \frac{n}{k} ⌉ .

For positive integers $n$ , $k$ . To guarantee at least $r$ objects in one of $k$ boxes you need $k (r - 1) + 1$ objects. It proves existence only; it does not construct the box.

WORKED EXAMPLE

Find the number of integer solutions of $x_{1} + x_{2} + x_{3} + x_{4} = 15$ with $0 \leq x_{i} \leq 6$ for every $i$ .

Solution

Without the upper bounds: $(3 15 + 3) = (3 18) = 816$ .
Let $A_{i}$ be the solutions with $x_{i} \geq 7$ . Put $y_{i} = x_{i} - 7$ : the sum becomes 8, giving $(3 11) = 165$ . There are 4 choices of $i$ , so $\sum ∣ A_{i} ∣ = 660$ .
Two variables $\geq 7$ : the sum becomes $15 - 14 = 1$ , giving $(3 4) = 4$ , for $(2 4) = 6$ pairs: total 24.
Three variables $\geq 7$ would need at least 21 > 15, so those terms are 0.
Good solutions $= 816 - 660 + 24 = 180$ .

Answer: 180

EXAM TIP

In a pigeonhole question work out the worst case first: fill every box to one below the target, then one more object forces the result. For 12 boxes and a target of 4 in one box, the worst case is $12 \times 3 = 36$ , so 37 objects are needed.

5. Strings, matrices, lattice paths and Catalan numbers

Many counting questions ask for the number of strings, functions, relations or matrices with a property. Reduce each to choosing positions or entries, as below. By the product rule, a string of length $n$ over an alphabet of $q$ symbols has $q^{n}$ possibilities in all. A relation on a set $A$ is a subset of $A \times A$ , so a relation on an $n$ -set is the same as an $n \times n$ 0/1 matrix.

Object	Count
Strings of length $n$ over $q$ symbols	$q^{n}$
Binary strings of length $n$ with exactly $k$ ones	$(k n)$
Subsets of an $n$ -set	$2^{n}$
Pairs $(A, B)$ of subsets of an $n$ -set with $A \subseteq B$	$3^{n}$
Functions from an $m$ -set to an $n$ -set	$n^{m}$
Injective functions from an $m$ -set to an $n$ -set	$P (n, m)$
Bijections between two $n$ -sets	$n!$
$n \times n$ binary matrices (relations on an $n$ -set)	$2^{n^{2}}$
Reflexive relations on an $n$ -set (also irreflexive)	$2^{n^{2} - n}$
Symmetric relations on an $n$ -set	$2^{n (n + 1) /2}$
Reflexive and symmetric relations on an $n$ -set	$2^{n (n - 1) /2}$
Antisymmetric relations on an $n$ -set	$2^{n} 3^{n (n - 1) /2}$
Asymmetric relations on an $n$ -set	$3^{n (n - 1) /2}$
Equivalence relations on an $n$ -set	Bell number $B_{n}$
$n \times n$ permutation matrices (one 1 in each row and column)	$n!$
$n \times n$ binary matrices with no all-zero row	$(2^{n} - 1)^{n}$

BELL NUMBERS

B_{n} = k = 0 \sum n S (n, k), B_{n + 1} = k = 0 \sum n (k n) B_{k}, B_{0}, \dots, B_{6} = 1, 1, 2, 5, 15, 52, 203

Number of partitions of an $n$ -set into non-empty blocks, which is also the number of equivalence relations on it (each relation corresponds to its set of equivalence classes).

LATTICE PATHS

(m m + n)

Shortest paths from $(0, 0)$ to $(m, n)$ using unit steps right and up: choose which $m$ of the $m + n$ steps are right. Forced points are handled by multiplying path counts of each leg.

CATALAN NUMBERS

C_{n} = \frac{1}{n + 1} (n 2 n) = (n 2 n) - (n + 1 2 n), C_{0}, \dots, C_{6} = 1, 1, 2, 5, 14, 42, 132

Paths from $(0, 0)$ to $(n, n)$ with right steps (along $x$ ) and up steps (along $y$ ) that never go above the line $y = x$ (touching allowed). Also: balanced bracket strings with $n$ pairs; unlabelled binary trees with $n$ nodes (left and right child distinguished); binary search trees on $n$ distinct keys; full binary trees with $n + 1$ leaves; ways to parenthesise a product of $n + 1$ factors; triangulations of a convex $(n + 2)$ -gon.

BINARY STRINGS WITH NO TWO CONSECUTIVE 1S

a_{n} = a_{n - 1} + a_{n - 2} (n \geq 3), a_{1} = 2, a_{2} = 3

Condition on the end: a valid string ending in 0 is any valid string of length $n - 1$ followed by 0; a valid string ending in 1 must end in 01, after any valid string of length $n - 2$ . Values: 2, 3, 5, 8, 13, 21, 34, 55 for $n = 1, \dots, 8$ ; $a_{n} = F_{n + 2}$ with $F_{1} = F_{2} = 1$ .

K-SUBSETS WITH NO TWO CONSECUTIVE ELEMENTS

(k n - k + 1)

Number of $k$ -element subsets of ${1, 2, \dots, n}$ with no two consecutive integers; equivalently binary strings of length $n$ with $k$ ones, no two adjacent (place the $k$ ones in the $n - k + 1$ gaps around the $n - k$ zeros).

The restricted-path count behind the Catalan formula uses reflection: paths from $(0, 0)$ to $(n, n)$ that go above $y = x$ touch the line $y = x + 1$ ; reflecting the part after the first touch in that line gives a one-to-one match with all paths to $(n - 1, n + 1)$ , which number $(n + 1 2 n)$ . Subtract them from all paths $(n 2 n)$ .

WORKED EXAMPLE

How many $3 \times 3$ binary matrices have exactly two 1s in every row and exactly two 1s in every column?

Solution

With only the row condition, each row is one of $(2 3) = 3$ patterns, so there would be $3^{3} = 27$ matrices.
Take the complement (swap 0 and 1). A matrix has exactly two 1s in every row and column if and only if its complement has exactly one 1 in every row and column.
A matrix with exactly one 1 in every row and column is a permutation matrix; there are $3! = 6$ of them.
Complementing is a one-to-one correspondence, so the answer is 6.

Answer: 6

EXAM TIP

The Catalan formula needs the path to stay on or below the diagonal (touching allowed). If the path may touch the diagonal only at its two ends, the count is $C_{n - 1}$ , not $C_{n}$ : the first step must be right and the last step up, and the part in between is a Catalan path of size $n - 1$ below the line $y = x - 1$ . The same number of paths lie strictly above the diagonal.

PREVIOUS-YEAR QUESTIONS

6 questions from the CS papers

Try each question first, then open the answer. We placed each question under a topic ourselves; the exam paper does not label topics.

See these papers in full: GATE CSE 2026 Set 1 · GATE CSE 2025 Set 1 · GATE CSE 2025 Set 2 · GATE CSE 2023 · GATE CSE 2022 · GATE CSE 2020

GATE 2026 CS1 Q.12

GATE 2026 · CS1Q.12 · 1 mark · MCQ

Consider $4 \times 4$ matrices with their elements from ${0, 1}$ . The number of such matrices with even number of $1$ s in every row and every column is

(A)
512
(B)
1025
(C)
1023
(D)
255

Answer and solution

GATE 2026 CS1 Q.12: answer and solution

See the question in the paper

Tap to open full size

GATE 2026 CS1 Q.12: answer and solution

GATE 2025 CS1 Q.30

GATE 2025 · CS1Q.30 · 1 mark · NAT

Let $S$ be the set of all ternary strings defined over the alphabet ${a, b, c}$ . Consider all strings in $S$ that contain at least one occurrence of two consecutive symbols, that is, "aa", "bb" or "cc". The number of such strings of length 5 that are possible is ______. (Answer in integer)

Answer and solution

GATE 2025 CS1 Q.30: answer and solution

See the question in the paper

Tap to open full size

GATE 2025 CS1 Q.30: answer and solution

GATE 2025 CS2 Q.64

GATE 2025 · CS2Q.64 · 2 marks · NAT

A quadratic polynomial $(x - α) (x - β)$ over complex numbers is said to be square invariant if $(x - α) (x - β) = (x - α^{2}) (x - β^{2})$ . Suppose from the set of all square invariant quadratic polynomials we choose one at random.

The probability that the roots of the chosen polynomial are equal is ______. (rounded off to one decimal place)

Answer and solution

GATE 2025 CS2 Q.64: answer and solution

See the question in the paper

Tap to open full size

GATE 2025 CS2 Q.64: answer and solution

GATE 2023 CS Q.48

GATE 2023 · CSQ.48 · 2 marks · MCQ

Let $U = {1, 2, \dots, n}$ , where $n$ is a large positive integer greater than 1000. Let $k$ be a positive integer less than $n$ . Let $A, B$ be subsets of $U$ with $∣ A ∣ = ∣ B ∣ = k$ and $A \cap B = \emptyset$ . We say that a permutation of $U$ separates $A$ from $B$ if one of the following is true.

All members of $A$ appear in the permutation before any of the members of $B$ .
All members of $B$ appear in the permutation before any of the members of $A$ .

How many permutations of $U$ separate $A$ from $B$ ?

(A)
$n!$
(B)
$(2 k n) (n - 2 k)!$
(C)
$(2 k n) (n - 2 k)! (k!)^{2}$
(D)
$2 (2 k n) (n - 2 k)! (k!)^{2}$

Answer and solution

GATE 2023 CS Q.48: answer and solution

See the question in the paper

Tap to open full size

GATE 2023 CS Q.48: answer and solution

GATE 2022 CS Q.32

GATE 2022 · CSQ.32 · 1 mark · NAT

The number of arrangements of six identical balls in three identical bins is ______.

Answer and solution

GATE 2022 CS Q.32: answer and solution

See the question in the paper

Tap to open full size

GATE 2022 CS Q.32: answer and solution

GATE 2020 CS Q.42

GATE 2020 · CSQ.42 · 2 marks · NAT

The number of permutations of the characters in LILAC so that no character appears in its original position, if the two L's are indistinguishable, is ______.

Answer and solution

GATE 2020 CS Q.42: answer and solution

See the question in the paper

Tap to open full size

GATE 2020 CS Q.42: answer and solution

OTHER EXAMS

ISRO: 1 question

From ISRO's Scientist/Engineer written test: ISRO CS 2025. They are not counted in the GATE numbers on this page.

ISRO CS 2025 Q.8

ISRO 2025 · CSQ.8 · 1 mark · MCQ

How many keys are needed for encrypted communication among 16 persons using AES encryption assuming unique key is used between any two persons:

(A)
120 keys
(B)
256 keys
(C)
32 keys
(D)
$2^{16}$ keys

Answer and solution

ISRO CS 2025 Q.8: answer and solution

See the question in the paper

Tap to open full size

ISRO CS 2025 Q.8: answer and solution

PRACTICE

6 questions to test yourself

PRACTICE 11 mark · MCQ

Five letters are written to five different people and the five addressed envelopes are prepared. The letters are put into the envelopes, one per envelope. In how many ways can exactly two letters land in their own correct envelopes?

(A)
20
(B)
30
(C)
45
(D)
44

Answer and solution

Answer: (A)

Choose the 2 letters that are correctly placed: $(2 5) = 10$ .
The other 3 letters must all be misplaced: $D_{3} = 2$ .
Total $10 \times 2 = 20$ .

PRACTICE 22 marks · NAT

A path goes from $(0, 0)$ to $(6, 6)$ using unit steps to the right or upward only. How many such paths never go above the line $y = x$ (touching the line is allowed)?

Answer and solution

Answer: $132$

This is the Catalan count for $n = 6$ .
$C_{6} = \frac{1}{7} (6 12) = \frac{924}{7} = 132$ .

PRACTICE 32 marks · MCQ

How many onto (surjective) functions are there from a set of 5 elements to a set of 3 elements?

(A)
243
(B)
150
(C)
120
(D)
60

Answer and solution

Answer: (B)

Use inclusion-exclusion over the elements of the codomain that are missed.
Number $= 3^{5} - (1 3) 2^{5} + (2 3) 1^{5} = 243 - 96 + 3 = 150$ .
Check: $3! S (5, 3) = 6 \times 25 = 150$ .

PRACTICE 42 marks · MSQ

For $n = 6$ , which of the following statements are true?

(A)
$\sum_{k = 0}^{6} (k 6) = 64$
(B)
$\sum_{k = 0}^{6} (k 6)^{2} = 924$
(C)
$\sum_{k = 0}^{6} k (k 6) = 192$
(D)
The number of subsets of a 6-element set with an even number of elements is 64

Answer and solution

Answer: (A), (B), (C)

A: the row sum is $2^{6} = 64$ , true.
B: $\sum_{k} (k 6)^{2} = (6 12) = 924$ , true.
C: $n 2^{n - 1} = 6 \times 32 = 192$ , true.
D: even-size subsets number $2^{5} = 32$ , not 64, so false.

PRACTICE 51 mark · NAT

What is the smallest number of people a group must have to be certain that at least 4 of them were born in the same calendar month?

Answer and solution

Answer: $37$

The months are 12 boxes; a target of 4 in one box.
Worst case: each of the 12 months has exactly 3 people, which is 36 people with no month reaching 4.
One more person forces some month to have 4: $12 \times 3 + 1 = 37$ , the formula $k (r - 1) + 1$ with $k = 12$ , $r = 4$ .

PRACTICE 62 marks · NAT

How many binary strings of length 8 contain no two consecutive 1s?

Answer and solution

Answer: $55$

Let $a_{n}$ be the count for length $n$ : $a_{1} = 2$ , $a_{2} = 3$ and $a_{n} = a_{n - 1} + a_{n - 2}$ .
$a_{3} = 5$ , $a_{4} = 8$ , $a_{5} = 13$ , $a_{6} = 21$ , $a_{7} = 34$ , $a_{8} = 55$ .

OFFICIAL GATE 2027 SYLLABUS WORDING

Copied from the GATE 2027 syllabus; see all 2027 syllabi.

GATE CS

Combinatorics: counting

Preparing in Kolkata? IAE Academy's course for GATE CSE.