COUNTING TECHNIQUES

Tags: #◇Computer Science #◇STT101A #◇Conceptual #◇Counting Techniques

---

◇Overview

Combinatorial Counting Techniques systematically determine the cardinality $|S|$ and $|E|$ of finite sample spaces without listing every outcome individually. Choosing the right formula depends on two classification questions: (1) Does order matter? and (2) Is sampling done with or without replacement?

◇Key Definitions

• Multinomial Coefficient (Permutations with Identical Items): The number of distinct arrangements of $n$ items consisting of $n_1$ identical of type 1, ..., $n_k$ identical of type $k$ is $\frac{n!}{n_1! n_2! \cdots n_k!}$.

◇Worked Example

Problem: How many distinct strings can be formed by rearranging all the letters of the word MISSISSIPPI?

Solution:

• Total letters $n = 11$: $1\text{ M}$, $4\text{ I}$'s, $4\text{ S}$'s, $2\text{ P}$'s.
• Distinct arrangements $= \frac{11!}{1! \, 4! \, 4! \, 2!} = \frac{39,916,800}{1 \times 24 \times 24 \times 2} = \frac{39,916,800}{1152} = 34,650$.

◇References & Navigation

• Previous Topic: ◇Mutually Exclusive Events
• Next Topic: ◇Fundamental Principle of Counting
• Related Notes: ◇Complement, ◇Counting by Cases