User:IssaRice/Summary of counting techniques: Difference between revisions

Latest revision as of 02:38, 14 August 2019

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}, \dots, a_{k}) : a_{1}, \dots, a_{k} \in A}$	$n^{k}$
	${{a_{1}, \dots, a_{k}} : a_{1}, \dots, a_{k} \in A}$	$\sum_{i = 1}^{k} (\binom{n}{i})$
	${f : A \to N ∣ \sum_{a \in A} f (a) = k}$ (multisets with cardinality $k$ )
	${{a_{1}, \dots, a_{n}} : a_{1}, \dots, 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}, \dots, a_{k}) : a_{1}, \dots, a_{k} \in A and all a_{i} distinct}$	$P (n, k) = \frac{n!}{(n - k)!} = n (n - 1) \dots (n - (k + 1))$
	${(a_{1}, \dots, a_{n}) : a_{1}, \dots, a_{n} \in A and all a_{i} distinct}$	$P (n, n) = n!$
	${{a_{1}, \dots, a_{k}} : a_{1}, \dots, a_{k} \in A and all a_{i} distinct}$	$(\binom{n}{k}) = P (n, k) / (k!) = \frac{n!}{k! (n - k)!}$
	${(a, b) : a \in A and b \in B}$	$n m$
	${{a, b} : a \in A and b \in B}$

@@ Line 4: / Line 4: @@
 ! Description !! Set representing counting problem !! number of ways to count
 |-
-| || <math>\{(a_1, \ldots, a_k) : a_1,\ldots, a_k \in A\}</math> || <math>n^k</math>
+| Pick <math>k</math> things from <math>A</math> with replacement || <math>\{(a_1, \ldots, a_k) : a_1,\ldots, a_k \in A\}</math> || <math>n^k</math>
 |-
 | || <math>\{\{a_1, \ldots, a_k\} : a_1,\ldots, a_k \in A\}</math> || <math>\sum_{i=1}^k \binom n i</math>
 |-
-| || <math>\{\{a_1, \ldots, a_n\} : a_1,\ldots, a_n \in A\}</math> || <math>\sum_{i=1}^n \binom n i = 2^n - 1</math>
+| || <math display="inline">\{ f : A \to \mathbf N \mid \sum_{a \in A} f(a) = k\}</math> (multisets with cardinality <math>k</math>) ||
+|-
+| || <math>\{\{a_1, \ldots, a_n\} : a_1,\ldots, a_n \in A\}</math> || <math>\sum_{i=1}^n \binom n i = 2^n - 1</math> (a quick way to see this identity is that we want the power set without the empty set)
 |-
 | || <math>\{(a_1, \ldots, a_k) : a_1,\ldots, a_k \in A \text{ and all }a_i\text{ distinct}\}</math> || <math>P(n,k) = \frac{n!}{(n-k)!} = n(n-1)\cdots (n-(k+1))</math>
@@ Line 18: / Line 20: @@
 | || <math>\{(a,b) : a \in A \text{ and } b \in B\}</math> || <math>nm</math>
 |-
-| ||
+| ||  <math>\{\{a,b\} : a \in A \text{ and } b \in B\}</math> ||
 |}