6
$\begingroup$

Let $n,k$ be integers such that $n - 1 \le k \le {n \choose 2}$. Let $T(n, k)$ be the number of connected, simple graphs without self-loops on $n$ labelled vertices having exactly $k$ edges. Can we give an expression for $T(n,k)$ in terms of $T(m,h)$ for $m < n$ or $h < k$ (that is, a recursive formula)?

$T(n, k)$ is sequence A123527 on the OEIS: http://oeis.org/A123527.

Variations on this question have been asked before on this site (for instance: here), but I wasn't able to piece together a recursive formula from their answers. My motivation is to write a program that computes it for small $n$, for which a recursive formula can be used.

So far I've noticed that a few base cases are easy to compute. In fact, if $k = n - 1$ then $T(n, k)$ is counting the number of trees on $n$ vertices, which, by Cayley's formula, is $$T(n, n - 1) = n ^ {n - 2}\text{,}$$ while if $k \ge {n - 1 \choose 2} + 1$ then every graph is surely connected, therefore $$T(n, k) = {{n \choose 2} \choose k}\text{.}$$

$\endgroup$
7
  • $\begingroup$ This doesn't answer your question, but the formula $\sum_{n,k} T(n,k) \frac{x^n}{n!} y^k = 1+\ln\left( \sum_{n \ge 0} (1+y)^\binom{n}{2} \frac{x^n}{n!} \right)$ from A062734 might help. The Mathematica code on A062734 computes the sequence by looking at the coefficients of the Taylor series of the RHS about $x=0$. $\endgroup$ – Snowball Dec 3 '14 at 17:45
  • $\begingroup$ That's still interesting — I'm asking for a recursive formula only because I don't think there's a chance of a simple closed formula, but any computable formula will do. $\endgroup$ – Jacopo Notarstefano Dec 3 '14 at 19:46
  • $\begingroup$ I suggest the first chapter of Harary & Palmer, Graphical Enumeration. $\endgroup$ – Marko Riedel Dec 3 '14 at 22:24
  • 2
    $\begingroup$ There is a recurrence that you may want to refine at this MSE link. $\endgroup$ – Marko Riedel Dec 4 '14 at 1:21
  • 1
    $\begingroup$ Can you elaborate on how exactly that recurrence is computed? The notation is a little strange to me. $\endgroup$ – gct Dec 17 '14 at 14:18
2
$\begingroup$

I know I am late but I had the same question and came up with following recurrence. I hope this helps somebody who comes across this.

def numberOfedges(n,k):
    t = combination(n,2)
    ret = combination(t,k)
    if k < combination(n - 1,2) + 1:
        for i in range(1,n):
            ni = combination(n - 1, i - 1) 
            x = combination(i,2)
            for j in range(i - 1, min(x,k) + 1): 
                ret -= ni * combination(combination(n - i,2),k - j) * numberOfedges(i, j) 
    return ret
$\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.