Introductory Combinatorics:The Basic Principle of Counting

What is combinatorics? It can be simply characterized as:

Combinatorics = The Art of counting

Combinatorics begins with

The Basic Principle of Counting: Suppose that two operations are to be performed. If operation 1 results in any one of $m$ possible outcomes and if for each outcome of operation 1 there are $n$ possible outcomes of operation 2, then together there are $mn$ possible outcomes of the two operations.

The Basic Principle of Counting is also called the Rule of Products. The principle assumes that the choice for operation 2 does not depend on the choice of operation 1.

Example. A lunch bar serves 5 different sandwiches and 3 different drinks. How many different lunches can a person order?

Solution. For each choice of a sandwich, there are three different choices of a drink. Hence there are $5\cdot 3=15$ possible orders.

Example. Let $A$ and $B$ be finite sets. Prove that $|A\times B|=|A|\cdot|B|$ where $|A|$ denotes the cardinality (i.e. the number of elements) of the set $A$.

Proof. Let $|A|=m$ and $|B|=n$. For each choice of elements in $A$ there are $n$ possible choices for the elements in $B$ to pair with. Since there are $m$ possible choices for the elements in $A$, the total number of all possible ordered pairs is $mn$, i.e. $|A\times B|=mn=|A|\cdot|B|$.

Example. A small community consists of 10 women, each of whom has 3 children. If one woman and one of her children are to be chosen as mother and child of the year, how many different choices are possible?

Solution. There are $10\times 3=30$ possible choices.

If more than two operations are to be performed, the basic principle can be generalized as follows.

The Generalized Basic Principle of Counting

If $r$ operations are to be performed in such a way that operation 1 results in $n_1$ possible outcomes, operation 2 results in $n_2$ possible outcomes, …, operation $r$ results in $n_r$ possible outcomes, then there is a total of $n_1\cdot n_2\cdots n_r$ possible outcomes of the $r$ operations.

Example. A person is to complete a true-false questionnaire. How many different ways are there to answer the questionnaire?

Solution. $\stackrel{10\ \mathrm{fold}}{\overbrace{2\cdot 2\cdots 2}}=2^{10}=1024$.

Example. A questionnaire contains 4 questions that have 2 possible answers and three questions with 5 possible answers. How many different answers are possible?

Solution. $2\cdot 2\cdot 2\cdot 2\cdot 5\cdot 5\cdot 5=2^4\cdot 5^3=2000$ different ways to answer the questionnaire.

Example. How many different 7-place license plates are possible if the first 3 places are to be occupied by letters and the final 4 by numbers?

Solution. $26\cdot 26\cdot 26\cdot 10\cdot 10\cdot 10\cdot 10=175,760,000$.

Example. In the above example, how many license plates would be possible if repetition among letters or numbers were prohibited?

Solution. $26\cdot 25\cdot 24\cdot 10\cdot 9\cdot 8\cdot 7=78,624,000$.

Theorem. (Power Set Cardinality Theorem) If $A$ is a finite set, then $|\wp(A)|=2^{|A|}$.

Proof. The proof boils down to counting how many different ways there are to determine subsets of $A$. Let $B$ be a subset of $A$. For each $x\in A$, there are two possibilities: either $x\in B$ or $x\not\in B$. Since $A$ has $n$ elements, there are $\stackrel{n\ \mathrm{fold}}{\overbrace{2\cdot 2\cdots 2}}=2^n$ different ways to determine subsets of $A$.

References: Not in particular order.

[1] Applied Discrete Structures, Al Doerr and Ken Levasseur. This book is available for free under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 United States License.

[2] A First Course in Probability, Sheldon Ross, 5th Edition, Prentice-Hall, 1998

Leave a Reply

Your email address will not be published. Required fields are marked *