Posts

Discrete Mathematics: Geometric Counting

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...
Post a Comment
Read more

Discrete Mathematics: Induction

Image
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 ...
Post a Comment
Read more

Discrete Mathematics: The Twelvefold Way

Image
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...
Post a Comment
Read more

Discrete Mathematics: Partitions

Image
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 \(...
Post a Comment
Read more

Discrete Mathematics: Injective and Surjective Functions

Image
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...
Post a Comment
Read more

Discrete Mathematics: Combinations With Repetition

Image
Combinations With Repetition How many combinations are there for \(N\) dice with \(S\) sides \(1, \ldots, S\)? Hint: Let \(X_1, \ldots, X_S\) represent the number of dice with each subscripted face value. Example. $N=3, S=6, \text{Die}_1 \leq \text{Die}_2 \leq \text{Die}_3$ \[ \boxed{\binom{N+S-1}{S-1}} \] How many combinations are there for \(N\) dice with \(S\) sides \(1, \ldots, S\) such that the face value \(1\) appears exactly \(K\) times? Hint: Let \(X_2, \ldots, X_S\) represent the number of dice with each subscripted face value. Example. $N=3, S=6, \text{Die}_1 \leq \text{Die}_2 \leq \text{Die}_3, K=1,2$ \[ \boxed{\binom{N-K+S-2}{S-2}} \] How many combinations are there for \(N\) dice with \(S\) sides \(1, \ldots, S\) such that the face value \(1\) appears at least \(K\) times? Hint: Let \(X_1, \ldots, X_S\) represent the number of dice with each subscripted face va...
Post a Comment
Read more

Discrete Mathematics: Combinations Without Repetition

Image
Combinations Without Repetition How many teams of $L$ people can be formed from $N$ people? Example. $N=4, L=0,1,2,3,4$ $$\boxed{\binom{N}{L}}$$ How many teams of $L$ people can be formed from $N$ people if a specific person $A$ must be on the team? Example. $N=4, L=1,2,3,4$ $$\boxed{\binom{N-1}{L-1}}$$ How many teams of $L$ people can be formed from $N$ people if a specific person $A$ cannot be on the team? Example. $N=4, L=0,1,2,3$ $$\boxed{\binom{N-1}{L}}$$ How many teams of $L$ people can be formed from $N$ people if a set of $K$ specific people must be on the team? Example. $N=4, L=2,3,4, K=2, \{A,B\}$ $$\boxed{ \binom{N-K}{L-K} }$$ How many teams of $L$ people can be formed from $N$ people if all $K$ specific people must not be on the team? Example. $N=4, L=2,3,4, K=2, \{A,B\}$ $$\boxed{ \binom{N-K}{L}}$$ How many teams of $L$ people ca...
Post a Comment
Read more