..

Two problems involving Geometry in Combinatorics

Problem 1

Let P be a convex n-gon, where n >= 6. Find the number of triangles formed by any 3 vertices of P that are pairwise nonadjacent in P.

Solution

Out of n points, let us fix a point A in P. There are n ways to select such a point. Now let us select the remaining two points B and C from P such that they are not adjacent to A. There are (n - 3) remaining points we can select B and C from. Which gives us:

Number of ways of selecting B and C after point A has been selected = (n−32)\binom{n - 3}{2}

Now out of (n−32)\binom{n - 3}{2}, we are also counting points where B and C are adjacent to each other. We need to substract this number from (n−32)\binom{n - 3}{2}. If we consider both B and C as one point together, since that is the only way they can be adjacent to each other, we have (n−41)=(n−4)\binom{n - 4}{1} = (n - 4) ways where both B and C are adjacent to each other after an arbitrary point A has been selected. So we now have,

n((n−32)−(n−4))n(\binom{n - 3}{2} - (n - 4 ))

And since each point will be counted thrice in this process. We have final answer:

n3((n−32)−(n−4))\frac{n}{3}(\binom{n - 3}{2} - (n - 4 ))

Problem 2

Simpler, but interesting variant of the above problem which can be solved using combinatorics. For a convex n-gon, where n >= 4. Find an expression which expresses the number of diagonals connecting any two vertices.

Solution

To form a diagonal, we need any two points which are not adjacent to each other, and we can simply connect them together to form a diagonal. If there are n points given to us, we can select 2 points in the following number of ways:

(n2)\binom{n}{2}

But this also counts lines connecting two points which form the convex n-gon itself. We need to subtract that from the previous expression, and we have our answer as:

(n2)−n\binom{n}{2} - n

Problem 3

Determine the probability that the string “UNIVERSITY” appears as a contiguous block in a sequence of 15 random draws from the set {A,B,C,...,Z}\{A, B, C, ..., Z\}, where each draw is made independently with replacement

Solution

  • The sequence consists of n=15 n = 15 characters.
  • The string “UNIVERSITY” has length m=10 m = 10 .
  • Each position in the sequence is drawn independently from a set of 26 letters.
  • There are 6 possible starting positions for “UNIVERSITY” in the sequence.

At any fixed starting position, the probability that the next 10 letters match “UNIVERSITY” exactly is:

(126)10\left(\frac{1}{26}\right)^{10}

Since there are 6 possible starting positions, it can be expressed as:

P("UNIVERSITY" appears)≈6×(126)10P(\text{"UNIVERSITY" appears}) \approx 6 \times \left(\frac{1}{26}\right)^{10} =62610= \frac{6}{26^{10}}