0
$\begingroup$

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) enter image description here

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:
    enter image description here
    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.

  • 0
    @joriki: I believe they're identical base on the input/output were given. Thanks a lot.2012-08-08

0 Answers 0