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\text{ ways respectively,}$$

then the total number of ways of performing the action is

$$n_1\times n_2\times \cdots \times n_k\mathrm{.}$$

---

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,

$$\text{Total ways}=m+n\mathrm{.}$$

---

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

$$\lceil \frac{N}{k}\rceil$$

objects.

---

---

5. INCLUSION–EXCLUSION PRINCIPLE — STATEMENTS

---

Definition 11: Inclusion–Exclusion Principle (Two Sets)

For any two sets A and B,

$$\mathrm{\mid }A\cup B\mathrm{\mid }=\mathrm{\mid }A\mathrm{\mid }+\mathrm{\mid }B\mathrm{\mid }-\mathrm{\mid }A\cap B\mathrm{\mid }\mathrm{.}$$

---

Definition 12: Inclusion–Exclusion (Three Sets)

$$\mathrm{\mid }A\cup B\cup C\mathrm{\mid }=\mathrm{\mid }A\mathrm{\mid }+\mathrm{\mid }B\mathrm{\mid }+\mathrm{\mid }C\mathrm{\mid }-\mathrm{\mid }A\cap B\mathrm{\mid }-\mathrm{\mid }A\cap C\mathrm{\mid }-\mathrm{\mid }B\cap C\mathrm{\mid }+\mathrm{\mid }A\cap B\cap C\mathrm{\mid }\mathrm{.}$$

---

---

6. MATHEMATICAL INDUCTION — DEFINITIONS & STEPS

---

Definition 13: Principle of Mathematical Induction

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

1. Base Step: $P(1)$ is true.

2. 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:

1. $P(1)$ is true.

2. 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{\mathrm{\mid }E\mathrm{\mid }}{\mathrm{\mid }S\mathrm{\mid }}$$

---

Definition 18: Complement of an Event

$$P(E^{\mathrm{\prime }})=1-P(E)$$

---

Definition 19: Conditional Probability

$$P(A\mid 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\mid B)=\frac{P(B\mid A_i)P(A_i)}{\sum _{j=1}^{n}P(B\mid A_j)P(A_j)}$$

This theorem is used to reverse conditional probability.