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
    This is related: http://math.stackexchange.com/questions/179452 (but not a duplicate, since $k$ there is the maximal degree of a vertex, whereas here it's the total number of edges).2012-08-08
  • 0
    I do not understand what you mean by "There will never be a group with 3 connections". Does $n=3$ and all possible connections not defy this statement, or am I understanding the problem wrong?2012-08-08
  • 0
    @utdiscant: Your comment makes me wonder whether $k$ is actually intended to have the same meaning as in the question I linked to, after all. That would make sense of the example, which is confusing since it says "$3$ people and $2$ connections" but then lists both $k=1$ and $k=2$ as possibilities. Chan, could you please comment on this?2012-08-08
  • 0
    @joriki: Sorry for the confusion, I meant to say if $n = 3, k = 2$ then we need to list all possibilities for both $n = 3, k = 1$ and $n = 3, k = 2$2012-08-08
  • 0
    @Chan: That's very confusing indeed. You should use different variable names for these two variables. Also, if I understand correctly, $k$ is not the total number of connections, but the maximal number of connections per person? If so, a) this should be brought out more clearly in the question, and b) could you then confirm that this is a duplicate of the question I linked to above?2012-08-08
  • 0
    @utdiscant: I've just read the other question, it's very similar to mine. Let me borrow some words from the other topic to explain it: It meant we can't have any vertex of degree > 3.2012-08-08
  • 0
    @Chan: If you believe it's only similar and not identical, please point out the differences.2012-08-08
  • 0
    @joriki: I believe they're identical base on the input/output were given. Thanks a lot.2012-08-08

0 Answers 0