0
$\begingroup$

Let $G=(V,E)$ a simple graph with $n$ vertices and exactly $m$ edges. The number of possible simple graphs with exactly $m$ edges is given by $\binom{\binom{n}{2}}{m}$, as every pair of vertices can be sampled in $m$ different ways.

Equivalently I was trying to understand whether by extending the reasoning is possible to compute the possible number of loopy-multigraphs (graphs with multiedges and self-loops) that have exactly $m$ edges. My intuition is that one should use combinations with repetitions instead of combinations as for the simple case, as they represent the number of ways to sample $y$ elements from a set of $x$ elements allowing for duplicates (i.e., with replacement, in our case multi-edges and self-loops) but disregarding different orderings (e.g. {2,1} = {1,2} as the graph is not directed). In our case the set has $n(n+1)/2$ elements and we sample it in $m$ possible ways.

Then, the total number of loopy-multigraphs with exactly $m$ edges should be given by:

$$\left(\!\!{\binom {n(n+1)/2}{m}}\!\!\right) = \binom{n(n+1)/2+m-1}{m}$$

but I'm not sure if this estimate is correct. Can someone help me figuring out if this is true? It seems that this result is not written in any paper nor book on graph theory and complex networks.

$\endgroup$

migrated from mathoverflow.net Oct 25 '16 at 11:27

This question came from our site for professional mathematicians.

  • $\begingroup$ Why $n^2$ elements, maybe $n(n+1)/2$? $\endgroup$ – Fedor Petrov Oct 25 '16 at 8:21
  • $\begingroup$ Sure, indeed you are correct! I just recounted it in a triangle graph with 3 nodes, there are 6 possible pairs counting each pair once considering self-loops. I just edited the question. $\endgroup$ – linello Oct 25 '16 at 8:32
  • 1
    $\begingroup$ You have $\binom{n}{2}$ edges, plus $n$ loops. Thus, number of such graphs is $\binom{ \binom{n}{2} + n}{m}$. It is a one-line proof, and is perhaps left as an easy exercise.... $\endgroup$ – Per Alexandersson Oct 25 '16 at 8:41
  • 1
    $\begingroup$ @PerAlexandersson but multiple edges are also allowed, so the answer is as in original post $\endgroup$ – Fedor Petrov Oct 25 '16 at 8:45
  • 1
    $\begingroup$ Instead of $N:=\binom{n+1}2$ we may consider arbitrary positive integers $N$. The question is about the number of functions $f:\{1\ \ldots\ N\}\rightarrow\{0\ 1\ \ldots\}$ such that $\sum f = m,\ $ where $m$ is an arbitrary non-negative integer $m$. (The tennis players would agree that the case of $m=0$ is lovely). $\endgroup$ – Włodzimierz Holsztyński Oct 25 '16 at 8:52
0
$\begingroup$

Here is an iteration in a general case.

Let $\ C(N\ m)\ $ be the number of functions $\ f:\{1\ \ldots\ N\}\rightarrow\{\ 0\ 1\ \ldots\ \}\ $ such that $\ \sum f=m,\ $ where $\ N\ $ and $\ m\ $ are a positive and a non-negative integer respectively.

Then

$$ C(N\ 0)\ =\ C(1\ m)\ =\ 1 $$

And, for $\ m>0,$

$$ C(N\ m) = \sum_{k=1}^{\min(m\ N)} \binom Nk\cdot C(k\,\ m\!-\!k) $$

EXAMPLE:

$$ C(4\ 2)\,\ =\,\ \binom 41\cdot C(1\ 3)\ +\ \binom 42\cdot C(2\ 0) \,\ =\,\ 10 $$

or

$$ C(2\ 4)\,\ =\,\ \binom 21\cdot C(1\ 3)\ +\ \binom 22\cdot C(2\ 2) \,\ =\,\ 2\ +\ C(2\ 2)\,\ =\,\ 2 +(2+1)\,\ =\,\ 5 $$

Enjoy :-)

$\endgroup$
  • $\begingroup$ Here $C$ represents binomial coefficients, right? $\endgroup$ – linello Oct 26 '16 at 14:27
  • $\begingroup$ @linello, I've defined C(N m) in my answer (see the first yellow field at the start). It is done by an inductive (recursive) definition. On the other hand, the binomial coefficient is standard $\ \binom mk$. $\endgroup$ – Włodzimierz Holsztyński Oct 26 '16 at 16:06

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.