User:IssaRice/Summary of counting techniques

Let $A$ be a set with $n$ elements, and let $B$ be a set with $m$ elements.

Description	Set representing counting problem	number of ways to count
Pick $k$ things from $A$ with replacement	$\{(a_{1},\ldots ,a_{k}):a_{1},\ldots ,a_{k}\in A\}$	$n^{k}$
	$\{\{a_{1},\ldots ,a_{k}\}:a_{1},\ldots ,a_{k}\in A\}$	$\sum _{i=1}^{k}{\binom {n}{i}}$
	${\textstyle \{f:A\to \mathbf {N} \mid \sum _{a\in A}f(a)=k\}}$ (multisets with cardinality $k$)
	$\{\{a_{1},\ldots ,a_{n}\}:a_{1},\ldots ,a_{n}\in A\}$	$\sum _{i=1}^{n}{\binom {n}{i}}=2^{n}-1$ (a quick way to see this identity is that we want the power set without the empty set)
	$\{(a_{1},\ldots ,a_{k}):a_{1},\ldots ,a_{k}\in A{\text{ and all }}a_{i}{\text{ distinct}}\}$	$P(n,k)={\frac {n!}{(n-k)!}}=n(n-1)\cdots (n-(k+1))$
	$\{(a_{1},\ldots ,a_{n}):a_{1},\ldots ,a_{n}\in A{\text{ and all }}a_{i}{\text{ distinct}}\}$	$P(n,n)=n!$
	$\{\{a_{1},\ldots ,a_{k}\}:a_{1},\ldots ,a_{k}\in A{\text{ and all }}a_{i}{\text{ distinct}}\}$	${\binom {n}{k}}=P(n,k)/(k!)={\frac {n!}{k!(n-k)!}}$
	$\{(a,b):a\in A{\text{ and }}b\in B\}$	$nm$
	$\{\{a,b\}:a\in A{\text{ and }}b\in B\}$