1Counting the number of solutions to the following equality:
$x_1 + \cdots + x_n = k$
where all $x_j$ and k belong to $\mathbb{N}$.
Stars and Bars:
$\binom{k+n-1}{k}$
2Counting number of solutions to the following equality:
$x_1 + \cdots + x_n = k$
where all $x_i > 0$.
E.g., $n = 3$ and $k = 5$.
Substitute $y_i + 1 = x_i$ in the equality:
$x_1 + x_2 + x_3 = 5$ with $x_i > 0 \equiv x_i \ge 1$
$(y_1 + 1) + (y_2 + 1) + (y_3 + 1) = 5$ with $y_i + 1 \ge 1$
$y_1 + y_2 + y_3 = y_i \ge 0$
Now we can use stars and bars as usual.
3Definition of a Composition of an Integer
Number of Compositions for an Arbitrary $n \in \mathbb{N}$
Sum of strictly positive integers summing to a given n.
The number of compositions is $2^{n-1}$ for any $n \in \mathbb{N}$.
4Counting the Number of Unit Paths from $\langle 0,0 \rangle$ to $\langle a , b \rangle$ in $\mathbb{N}^2$.
$\binom{a+b}{a}$
5Value of $\sum_{a+b=n} \binom{a+b}{a}$
$2^n$
6Catalan Numbers and Interpretation ITO Unit Paths
The nth Catalan number is computed as:
$\frac{1}{n+1} \binom{2n}{n}$
Its value tells us the number of unit paths from the origin to $\langle n , n \rangle$ which never above the line $y = x$.
7Counting the number of bijections between two (finite) sets A and B.
The number of functions $f : A \to B$ is $\lvert B \rvert ^ { \lvert A \rvert }$.
8Counting the number of injections between two (finite sets A and B).
Let $n = \lvert A \rvert$ and $m = \lvert B \rvert$.
Then, the number of injections $f : A \to B$ is:
$\frac{ m! }{ (m-n)! }$