0
$\begingroup$

Consider a graph with $N$ nodes. We want to connect pairs of these nodes, resulting in active links, which are basically directed edges. An edge from $i$ to $j$ means that $i$ transmits data to $j$.

Three constraints have to be met:

  1. Nodes cannot receive $>1$ transmission.
  2. Nodes cannot send $>1$ transmission.
  3. Nodes cannot send and receive simultaneously.

A network state is a set of node pairs that transmit to one another. It's called feasible if all three constraints are met. So if you have 4 nodes $A,B,C,D$ and $A$ transmits to $B$ and $C$ transmits to $D$ then $S=\{\{A,B\},\{C,D\}\}$ is one feasible network state. $S=\{\{A,B\},\{B,C\}\}$ is not feasible because constraint 3 is violated.

Now I have a formula here that tells me how to calculate the number of feasible network states given $N$:

$|S|=\sum_{i=1}^{\lfloor N/2 \rfloor}\frac{N!}{(N-2i)!\cdot i!}$

I understand that there cannot be more than $i=\lfloor N/2 \rfloor$ active links, otherwise one of the three constraints will be violated.

But when I try to understand the formula, I get stuck at some point. Here's where:

Try it for $N=6$:

$i=1$: First pick any one out of $N=6$ nodes and connect it to any one of $N-1=5$ potential partners. You have $N(N-1)=6\cdot 5=30$ possibilities.

$i=2$: You have one active link already, so $2$ nodes are busy. Pick any one out of $N-2=4$ free nodes and connect it to any one of $N-3=3$ remaining nodes. You have $(N-2)(N-3)=4\cdot 3=12$ possibilities. Here you include pairs in both directions, e.g. $\{\{i,j\},\{j,i\}\}$ but we don't care about the ordering, so divide by 2 and you get $\frac{(N-2)(N-3)}{2}=6$ possibilities to find a second active link when there already is one. So multiply these $6$ with each possibility of choosing the first active link, and you have $N(N-1)\cdot\frac{(N-2)(N-3)}{2}=30\cdot 6=180$ ways of forming two active links.

Up to here my approach agrees with the formula. Now, for the last possible active link, things get messy:

$i=3$: You have two active links, so $4$ out of $6$ nodes are busy. There is exactly one possibility to form another pair. So I would say there are $180+1=181$ possibilities to form three active links here.

According to the formula there should be $120$ ways for $i=3$, however.

Does anyone know where my mistake is? Even intuitively I don't get it. If you have $180$ ways for $i=2$ how can there be fewer ways of forming a third active link. You already know there's $180$ ways that conform to the constraints, and there's exactly 2 free nodes. Connect the two, be done with it.

I am also interested in learning if this particular problem has a name.

$\endgroup$
  • $\begingroup$ One thing may be that you do care which order the pairs are taken, since $\{A, B\}$ is different from $\{B, A\}$ (or so I seem to understand). Also, networks where not all the nodes are connected are allowed. I think the $i$ index of the summation counts the number of pairs, and not the i-th pairing. $\endgroup$ – Riccardo Orlando Nov 2 '16 at 19:22
0
$\begingroup$

The index $i$ of the summation refers to the number of pairings in the network. Since not all of the nodes need to be connected, the formula counts all the network states with one active connection, then the states with two connections, and so on.

The number of states of a network with $i$ connections is the number of different ways $i$ ordered pairs can be extracted from the $N$ total elements.

For example, for $i=1$, we clearly have $N(N-1)$ possibilities.

For $i=2$, we have as before $N(N-1)$ options for a first pair, and then $(N-2)(N-3)$ options for the second. We don't care about the order of the pairs (even though we do care about the order of the elements within the pair), so we divide by two. Total: $$ \frac{N(N-1)(N-2)(N-3)}{2}=\frac{N!}{(N-4)!\cdot2}=\frac{N!}{(N-2i)!\cdot i!} $$

And this is the general formula: I know I didn't quite prove it, but the reasoning is rather straightforward.

And finally we add all these network counts, obtaining: $$ \sum _{i=1}^{\lfloor N/2 \rfloor} \frac{N!}{(N-2i)!\cdot i!} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.