Go back to UGC NET COMUPTER SCIENCE

UNIT 1 — Counting, Mathematical Induction and Discrete Probability

(UGC NET)

(Counting • Pigeonhole Principle • Permutations • Combinations • Inclusion–Exclusion • Mathematical Induction • Probability • Bayes’ Theorem)

1. BASICS OF COUNTING — DEFINITIONS

Definition 1: Counting Principle (Product Rule)

If an action consists of k independent stages, and the stages can be performed in

$n_{1}, n_{2}, \dots, n_{k} ways respectively,$

then the total number of ways of performing the action is

$n_{1} \times n_{2} \times \dots \times n_{k} .$

Definition 2: Sum Rule (Addition Principle)

If an action can be performed in m ways or n ways, and the two sets of possibilities are mutually exclusive,

$Total ways = m + n .$

Definition 3: Factorial (n!)

For any positive integer n:

$n! = n (n - 1) (n - 2) \dots 1$

and by definition

$0! = 1.$

2. PERMUTATIONS — DEFINITIONS

Definition 4: Permutation

A permutation is an arrangement of objects in a specific order.

Definition 5: r-Permutation of n Objects

The number of ways to arrange r objects out of n:

$^{n} P_{r} = \frac{n!}{(n - r)!}$

Definition 6: Permutation with Repetition

If among n objects,

$n_{1}$ are alike,
$n_{2}$ are alike, etc.,

then number of distinct permutations:

$\frac{n!}{n_{1}! n_{2}! \dots}$

3. COMBINATIONS — DEFINITIONS

Definition 7: Combination

A combination is a selection of r objects from n objects where order does not matter.

Definition 8: r-Combination of n Objects

$^{n} C_{r} = \frac{n!}{r! (n - r)!}$

Key Relation

$^{n} P_{r} =^{n} C_{r} \cdot r!$

4. PIGEONHOLE PRINCIPLE — DEFINITIONS & STATEMENTS

Definition 9: Pigeonhole Principle (Basic)

If more than n objects are placed into n boxes, then at least one box contains more than one object.

Formal Statement:
If $n + 1$ objects are placed into $n$ boxes, at least one box contains ≥ 2 objects.

Definition 10: Generalized Pigeonhole Principle

If N objects are placed into k boxes, then at least one box contains

$⌈ \frac{N}{k} ⌉$

objects.

5. INCLUSION–EXCLUSION PRINCIPLE — STATEMENTS

Definition 11: Inclusion–Exclusion Principle (Two Sets)

For any two sets A and B,

$∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣ .$

Definition 12: Inclusion–Exclusion (Three Sets)

$∣ A \cup B \cup C ∣ = ∣ A ∣ + ∣ B ∣ + ∣ C ∣ - ∣ A \cap B ∣ - ∣ A \cap C ∣ - ∣ B \cap C ∣ + ∣ A \cap B \cap C ∣ .$

6. MATHEMATICAL INDUCTION — DEFINITIONS & STEPS

Definition 13: Principle of Mathematical Induction

Let $P (n)$ be a statement depending on a natural number n.
If:

Base Step: $P (1)$ is true.
Induction Step: $P (k) \Rightarrow P (k + 1)$ for all natural numbers k,

Then $P (n)$ is true for all natural numbers.

Definition 14: Strong Induction

A statement $P (n)$ is true for all natural numbers n if:

$P (1)$ is true.
Assuming all of $P (1), P (2), \dots, P (k)$ are true implies $P (k + 1)$ .

7. PROBABILITY — DEFINITIONS

Definition 15: Sample Space (S)

The set of all possible outcomes of an experiment.

Definition 16: Event (E)

Any subset of the sample space.

Definition 17: Probability of an Event

If all outcomes are equally likely:

$P (E) = \frac{∣ E ∣}{∣ S ∣}$

Definition 18: Complement of an Event

$P (E^{'}) = 1 - P (E)$

Definition 19: Conditional Probability

$P (A ∣ B) = \frac{P (A \cap B)}{P (B)}, P (B) > 0$

Definition 20: Independent Events

Two events A and B are independent if:

$P (A \cap B) = P (A) P (B)$

8. BAYES’ THEOREM — STATEMENT

Definition 21: Bayes’ Theorem

If $A_{1}, A_{2}, \dots, A_{n}$ form a partition of the sample space and B is any event with $P (B) > 0$ , then:

$P (A_{i} ∣ B) = \frac{P (B ∣ A_{i}) P (A_{i})}{\sum_{j = 1}^{n} P (B ∣ A_{j}) P (A_{j})}$

This theorem is used to reverse conditional probability.

Tag: Counting

UGC NETComputer Science Unit 1 – Counting, Mathematical Induction and Discrete Probability