Mathematics Blog

Geometric Counting An $M \times N$ grid of squares is formed by horizontal and vertical grid lines. How many total rectangles can be formed using these grid lines? $$ \boxed{\binom{M+1}{2}\binom{N+1}{2}} $$ An $M \times N$ grid of squares is formed by horizontal and vertical grid lines. How many rectangles of exactly size $A \times B$ can be formed? $$ \boxed{(M-A+1)(N-B+1)} $$ An $M \times N$ grid of squares is formed by horizontal and vertical grid lines. A square in row $A$ and column $B$ (counted from the bottom-left corner) is fixed. How many rectangles contain this fixed square? $$ \boxed{A(M-A+1)\cdot B(N-B+1)} $$ An $M \times N$ grid of squares is formed by horizontal and vertical grid lines. How many squares can be formed using these grid lines? $$ \boxed{\sum_{k=1}^{\min(M,N)} (M-k+1)(N-k+1)} $$ If you draw $N$ straight lines in the plane, where no two lines are parallel and no three meet at the same point, how many intersec...

Induction Prove each of the following statements using mathematical induction. Triangular Numbers (Sum of First \(n\) Positive Integers): \[ 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2} \] Example. $N=4$ Sum of Odd Numbers: \[ 1 + 3 + 5 + \cdots + (2n-1) = n^2 \] Sum of First \(n\) Square Numbers: \[ 1^2 + 2^2 + 3^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6} \] Tetrahedral Numbers (Sum of First $n$ Triangular Numbers): \[ 1 + 3 + 6 + 10 + \cdots + \frac{n(n+1)}{2} = \frac{n(n+1)(n+2)}{6} \] Sum of First \(n\) Cubes: \[ 1^3 + 2^3 + 3^3 + \cdots + n^3 = \left(\frac{n(n+1)}{2}\right)^2 \] Geometric Series Partial Sum: \[ \sum_{k=0}^{n-1} ar^k = \frac{a(1-r^n)}{1-r}, \quad r \ne 1 \] Cardinality of the Power Set: \[ |P(A)| = 2^{|A|} \] Pascal's Identity: \[ \binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}, \quad n \ge 0,\; 1 \le k \le n \] Hockey-Stick Identity: \[ \sum_{k=r}^n \binom{k}{r} = \binom{n+1}{r+1}, \quad n ...

The Twelvefold Way How many functions are there from a set with $N$ distinct elements to a set with $K$ distinct elements? Example. $N=2, K=3$ Example. $N=3, K=2$ \[ \boxed{K^N} \] How many injective functions are there from a set with $N$ distinct elements to a set with $K$ distinct elements? Example. $N=2, K=3$ \[ \boxed{ \begin{cases} \dfrac{K!}{(K-N)!} & N \le K \\ 0 & N > K \end{cases} } \] How many surjective functions are there from a set with $N$ distinct elements to a set with $K$ distinct elements? Example. $N=3, K=2$ \[ \boxed{ \begin{cases} K!\,S(N,K) & N \ge K \\ 0 & N How many bijective functions are there from a set with $N$ distinct elements to a set with $K$ distinct elements? Example. $N=3, K=3$ \[ \boxed{ \begin{cases} N! & N = K \\ 0 & N \ne K \end{cases} } \] How many functions are there from a set with $N$ indistingu...

Partitions How many ways are there to partition a set $S$ with $N$ elements into 2 nonempty subsets $S_1$ and $S_2$ such that $S_1 \cup S_2 = S$? Example. $N=5$ \[ \boxed{S(N,2) = 2^{N-1} - 1} \] How many ways are there to partition a set $S$ with $N$ elements into $2$ nonempty subsets $S_1$ and $S_2$ such that $S_1 \cup S_2 = S$ and neither subset is allowed to be a singleton? Example. $N=5$ \[ \boxed{2^{N-1} - N - 1} \] How many ways are there to partition a set $S$ with $N$ elements into 3 nonempty subsets $S_1, S_2,$ and $S_3$ such that $S_1 \cup S_2 \cup S_3 = S$? Hint: Use the Inclusion-Exclusion Principle $$ \left| \bigcap_{i=0}^{K} A_i^c \right| = |T| - \sum_{i=0}^{K} |A_i| $$ $$ + \sum_{0 \le i_1 where \(T\) is the set of all ways of assigning each element of the \(N\)-element set to one of the subsets \(S_1,S_2,\) or \(S_3\), and \(A_i\) is the set of assignments in which the \(...

Injective and Surjective Functions Prove each of the following statements. \(|X|\le |Y|\) if and only if there exists an injective function $f:X\to Y$. Hint: Proceed by contradiction, and apply the Pigeonhole Principle. If \(g\circ f: X \to Z\) is injective, then \(f: X \to Y\) is injective. Hint: Prove the contrapositive. A function \(f:X\to Y\) is injective if and only if, for any functions \(g,h:W\to X\), if \(f\circ g=f\circ h\), then \(g=h\). Hint: Prove the contrapositive. Define trivial functions \(g,h:W\to X\) such that \(f\) must be injective. If \(f:X\to Y\) is injective and \(A,B \subseteq X\), then \[ f(A \cap B)=f(A)\cap f(B) \] If \(f:X\to Y\) is injective and \(A \subseteq X\), then \[ f^{-1}(f(A))=A \] \(f:X\to Y\) is injective if and only if \(f\) has a left inverse \(g:Y\to X\) such that \[ g\circ f=\mathrm{id}_X \] where \(\mathrm{id}_X(x)=x\) for all \(x...