I saw this problem today:
In a round table there are 12 knights. Each pair of contiguous knights are enemies. How many different ways can 5 knights be chosen such that no pair of knights are enemies?
So I tried to count how many ways there are to pick 5 knights out of 12 and substract the number of ways 5 knights can be picked such that there is at least a pair of enemies. I think i did the second one wrong because I got a negative number. I figured maybe some abstraction woumd help, and I arrived at a generalization that is much more interesting:
Given a finite set $A$ of size $n$ and a symmetric relation $R$ in $A$, how many different subsets $B$ of size $k<n$ are there such that no pair of elements in $B$ are in $R$?
It is equivalent to counting how many subsets $B$ are there such that every pair of elements in $B$ are in $R^c$. In this case, the relation would be Enemies (It is symmetric) and $A$ the set of the 12 knights. I'd like some help on tackling the problem, and on working on the geralization. Thanks.
To rephrase, how many ways can we select five of the twelve knights at the table so that no two of them are seated in adjacent seats?
We first solve the problem for a line, then subtract those cases in which people at both ends of the line are selected to ensure that no two adjacent knights are selected when the ends of the line are joined to form a circle.
We arrange seven blue and five green balls so that no two green balls are adjacent. Place seven blue balls in a row. This creates eight spaces, six between successive blue balls and two at the ends of the row. $$\square \color{blue}{\bullet} \square \color{blue}{\bullet} \square \color{blue}{\bullet} \square \color{blue}{\bullet} \square \color{blue}{\bullet} \square \color{blue}{\bullet} \square \color{blue}{\bullet} \square$$ To ensure that no two green balls are adjacent, we must choose five of these eight spaces for the green balls, which can be done in $$\binom{8}{5}$$ ways.
However, we must exclude those arrangements in which both ends of the line are occupied by green balls since joining the ends of the lines together would form a circle in which two of the selected balls are adjacent. If both ends of the row are filled with green balls, we are left with six spaces in which we place a green ball. $$\color{green}{\bullet} \color{blue}{\bullet} \square \color{blue}{\bullet} \square \color{blue}{\bullet} \square \color{blue}{\bullet} \square \color{blue}{\bullet} \square \color{blue}{\bullet} \square \color{blue}{\bullet} \square \color{green}{\bullet}$$ To ensure the green balls are separated, we must choose three of these spaces, which can be done in $$\binom{6}{3}$$ ways.
Hence, the number of ways five knights can be selected from the twelve knights at the round table so that no two of them are adjacent is $$\binom{8}{5} - \binom{6}{3}$$
We begin by arranging $n - k$ blue and $k$ green balls in a row so that no two green balls are adjacent, then subtract those cases in which green balls occupy both ends of the row so that the green balls do not become adjacent when we join the ends of the row to form a circle.
Reasoning as before, placing $n - k$ blue balls in a row creates $n - k + 1$ spaces, $n - k - 1$ between the $k$ successive blue balls and two at the ends of the row. To ensure that no two green balls are adjacent, we must select $k$ of these $n - k + 1$ spaces, which can be done in $$\binom{n - k + 1}{k}$$ ways. Notice that this is zero when $k > n - k + 1$.
From these, we must exclude those cases in which green balls occupy both ends of the row. If green balls occupy both ends of the row, we are left with $n - k - 1$ spaces. To ensure that no two green balls are adjacent, we must choose $k - 2$ of these spaces for the remaining green balls, which can be done in $$\binom{n - k - 1}{k - 2}$$ ways.
Hence, the number of ways that $k$ objects can be selected from $n$ objects arranged in a circle so that no two of the $k$ objects are adjacent is $$\binom{n - k + 1}{k} - \binom{n - k - 1}{k - 2}$$