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