Possible Duplicate:
Enumerate certain special configurations - combinatorics.
Problems: Given $n$ people stand in a circle, and $k$ connections between them. Count the number of ways these $n$ poeple can form $k$ connections. A configuration is considered distinct if and only if they differ in the either the number of connections or the people who are connected. For example, with 3 people and 2 connections we have 4 ways:
- $k = 1: (p_1, p_2)p_3$ or $(p_1, p_3)p2$ or $p_1(p_2, p_3)$
- $k = 2: (p_1, p_2, p_3)$ to form a triangle of 2 connections
Further, the number of connections between a pair must be the same, i.e. if $p_1, p_2, p_3 \ldots p_4$ are connected, they must have the same number of connections. Finally, the connection cannot cross each other, so if we have $n = 4, k = 2$, then the following configuration is invalid: $(p_1, p_3), (p_2, p_4)$ assuming $p1 \rightarrow p_2 \rightarrow p_3 \rightarrow p_4 \rightarrow p_1$. (see picture)
In short, we have to count all number of ways to form those connections with from 1 to $k$ where $1 \leq k \leq n$. Here are some of my observations:
- $k = 1$: there is $\dbinom{n}{2}$ ways
There will never be a group with 3 connections, and my argument to this statement is as following:
Assuming there are already 2-connections, now there is no way we can add another people to form a 3-connections because he/she must stand in one of those quadrants which obviously yield a cross which is invalid.$k = 2, (n \geq 3)$ then the most obvious choices is $(n - 3 + 1)$ ways to form a loop. The other ways is to pick a 1-connection for one pair, and one for the others.
- $k = 3:$ which depends upon on the previous two cases, i.e. $3 = 1 + 1 + 1 = 1 + 2$
What I'm trying to do is to find a general formula for this counting problem without referring to the previous 2 cases. However, I really don't know if this is possible and I'm not so confident on previous reasoning either. So any idea or suggestion would be greatly appreciated.