# How many subsets of size k exist such that no pair of elements is $R$

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.

In a round table, there are $12$ knights. Each pair of contiguous knights are enemies. How many ways can $5$ knights be chosen so that no pair of knights are enemies?

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}$$

In how many ways can $k$ objects be selected from $n$ objects arranged in a circle if no two of the $k$ objects are adjacent.

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}$$

Think of your problem as a problem on a graph $G=(A,R)$ you are simply counting the number of independent sets in $G$ having size $k$. This is indeed an interesting problem, one that has a well established body of research around it. If you are not familiar with graph theory, I would highly recommend checking it out (happy to explain more).

• Please do, I'm a bit familiar with graph theory only because i've done competitive programming but nothing more. – Hyperbolic Marraquetoid Aug 24 '17 at 2:44
• No problem. For our purposes, a graph Consists of a set of vertices (in this case the set $A$) and a set of edges which consists of distinct two element subsets of $A$. Think of drawing a $|A|$ of dots on a piece of paper and giving each of them each a label corresponding to an element in A, and drawing a line between two dots if their corresponding labels are in a pair $R$. Your original Knight example gives you a "cycle" [link] en.m.wikipedia.org/wiki/Cycle_graph on 12 vertices. An independent set is just a st of dots (vertices) such that no two dots have a line between them. – mm8511 Aug 24 '17 at 2:53
• so we have an undirected cycle graph. How can I attack this problem? I'd also like to read more about the independent set problem, where can I read about it? – Hyperbolic Marraquetoid Aug 24 '17 at 2:56
• label the vertices of the 12-cycle in clockwise order from 1 to 12. It shouldn't be hard to convince yourself that the vertices with odd labels form an independent set of size 6. Similarly, the vertices with even labels form an independent set of size 6. In each of these sets there are 6 choose five ways to choose a subset of 5 vertices. This gives us 12 sets total. There are other ways to make independent sets, like (1,3,5,7,10), (2,4,6,8,11) etc... I don't know a simple closed formula for this – mm8511 Aug 24 '17 at 3:06
• You may try proving it by induction on the number of knights. For example, with $2k+2$ knights and choosing $k$ Non-enemies. For $k=1$ the answer is clearly 4, for $k=2$ you have 9 ways. Maybe $n^2$ is the pattern? I don't know. – mm8511 Aug 24 '17 at 3:15