7
$\begingroup$

I am trying to find the relation between the number of nodes and the number of connections possible. So if there are $0$ nodes, that means $0$ connections possible, $1$ node still means $0$ connections possible, $2$ nodes $1$ connection possible, $3$ nodes $3$ connection and so on. How can I find the relation between $n$ nodes and the number of possible connections ?

$\endgroup$

closed as off-topic by Mike Pierce, JonMark Perry, Shailesh, user91500, Claude Leibovici Aug 8 '16 at 7:29

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Mike Pierce, Shailesh, Claude Leibovici
If this question can be reworded to fit the rules in the help center, please edit the question.

14
$\begingroup$

the sequence is $a_0,a_1,a_2\dots$ with $a_n=\frac{n(n-1)}{2}$

$\endgroup$
  • $\begingroup$ Great! Thanks. It helped! $\endgroup$ – freerunner Aug 7 '16 at 19:41
8
$\begingroup$

Let $a_n$ be the number of connections for $n$ nodes.

For $n > 0$, we have $a_n = a_{n-1} + n-1$ because among the $a_n$ connections, there are $n-1$ of them that connect to the $n^{th}$ node while $a_{n-1}$ of them didn't.

Rewrite above expression as $a_k - a_{k-1} = k-1$. Start summing both sides from $k = 1$ to $n$, we get

$$a_n - a_0 = \sum_{k=1}^n (k-1) = \sum_{k=1}^n \frac{k(k-1)-(k-1)(k-2)}{2} = \frac{n(n-1)}{2}$$

Together with $a_0 = 0$, we find $a_n = \frac{n(n-1)}{2}$ for $n > 0$.
Since this is trivially true at $n = 0$, we have $a_n = \frac{n(n-1)}{2}$ in general.

$\endgroup$
6
$\begingroup$

Hint: If you have graph on $n$ nodes, an edge in the graph corresponds to a choice of $2$ of these nodes (the $2$ which the edge connects). Hence the number of possible edges in the graph is the number of ways you can choose $2$ nodes. Can you continue from here?

$\endgroup$
  • $\begingroup$ Yep. I can now :) $\endgroup$ – freerunner Aug 7 '16 at 19:41
  • $\begingroup$ Great - glad I could help :) $\endgroup$ – Zestylemonzi Aug 7 '16 at 19:45
  • $\begingroup$ Just stumbled across your hint again. You meant something like this, right? n! / ((n - 2)! * 2!) $\endgroup$ – freerunner Feb 8 at 15:22
1
$\begingroup$

$a_n - a_{n-1} = n-2 \implies a_n = n-2 + n-3 +....+1 = ...$

$\endgroup$

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