Discrete Mathematics: Geometric Counting

Geometric Counting


  1. 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?

    2. $$ \boxed{\binom{M+1}{2}\binom{N+1}{2}} $$
  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?

    3. $$ \boxed{(M-A+1)(N-B+1)} $$
  3. 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?

    4. $$ \boxed{A(M-A+1)\cdot B(N-B+1)} $$
  4. 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?

    5. $$ \boxed{\sum_{k=1}^{\min(M,N)} (M-k+1)(N-k+1)} $$
  5. 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 intersection points are formed?

    6. $$ \boxed{\binom{N}{2}} $$
  6. If you draw $N$ straight lines in the plane, where no two lines are parallel and every pair intersects exactly once, and no three meet at the same point, how many line segments are created in total after cutting at intersections?

    7. $$ \boxed{N^2} $$
  7. 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 regions are formed?

    8. $$ \boxed{\frac{N(N+1)}{2} + 1} $$
  8. If you draw a convex polygon with $N$ vertices and draw all diagonals, assuming no three diagonals intersect at a single interior point, how many interior intersection points are formed?

    9. $$ \boxed{\binom{N}{4}} $$
  9. If you draw a convex polygon with $N$ vertices and draw all diagonals, assuming no three diagonals intersect at a single interior point, how many regions are formed inside the polygon?

    10. $$ \boxed{\frac{N^4 - 6N^3 + 23N^2 - 18N + 24}{24}} $$
  10. If you draw $N$ points on a circle and draw all chords between every pair of points, where no three chords intersect at the same interior point, how many interior intersection points are formed?

    11. $$ \boxed{\binom{N}{4}} $$
  11. If you draw $N$ points on a circle and draw all chords between every pair of points, where no three chords intersect at the same interior point, how many regions are formed inside the circle?

    12. $$ \boxed{\binom{N}{4} + \binom{N}{2} + 1} $$
  12. What is the maximum number of regions a circle can be divided into using $N$ straight line cuts?

    13. $$ \boxed{\frac{N(N+1)}{2} + 1} $$
  13. If $2N$ points are placed on a circle, how many ways are there to draw non-crossing chords between pairs of points so that every point is matched exactly once?

    14. $$ \boxed{ C_N = \frac{1}{N+1}\binom{2N}{N} } $$

Comments

Post a Comment

Popular posts from this blog

Discrete Mathematics: Permutations With Repetition

Image
Permutations With Repetition How many distinct strings with length \(L\) are there in a system with \(N\) digits \(0,\ldots,N-1\)? Example. $N=2, L=4$ Example. $N=3, L=3$ $$\boxed{N^L}$$ How many distinct strings with length \(L\) are there in a system with \(N\) digits \(0,\ldots,N-1\) without leading zero? Example. $N=2, L=4$ Example. $N=3, L=3$ $$\boxed{(N-1)N^{L-1}}$$ How many distinct strings with length \(L\) are there in a system with \(N\) digits \(0,\ldots,N-1\) where the digit \(1\) appears exactly \(K\) times? Example. $N=2, L=4, K=2$ Example. $N=3, L=3, K=1$ $$\boxed{\binom{L}{K}(N-1)^{L-K}}$$ How many distinct strings with length \(L\) are there in a system with \(N\) digits \(0,\ldots,N-1\) where the digit \(1\) appears at least \(K\) times? Example. $N=2, L=4, K=2$ Example. $N=3,L=3, K=1$ $$ \boxed{ \sum_{t=K}^{L} \bi...
Read more