1
$\begingroup$

I am trying to reproduce the following sequence (https://oeis.org/A062734):

[1], [0, 1], [0, 0, 3, 1], [0, 0, 0, 16, 15, 6, 1], [0, 0, 0, 0, 125, 222, 205, 120, 45, 10, 1], ...

A062734: Triangular array T(n,k) giving number of connected graphs with n labeled nodes and k edges (n >= 1, 0 <= k <= n(n-1)/2).

Here is the Formula:

$$\sum_{n,k} T(n,k) \frac{x^n}{n!} y^{k} = 1 + \log\Bigg[\sum_{n=0,\infty} (1+y)^{\binom{n}{2}}*\frac{x^n}{n!} \Bigg]$$

Sum_{n,k} T(n,k) x^n/n! y^k = 1+log(Sum((1+y)^binomial(n, 2)*x^n/n!, n=0..infinity))

Essentially I just want to reproduce the list above but the part that I dont get is the $x,y$. Any hints on how to compute the formula above in a calculator/sage/python?

$\endgroup$
  • $\begingroup$ This has appeared several times at MSE. One link that I remember at this time is this MSE link. $\endgroup$ – Marko Riedel Mar 5 '16 at 21:22
2
$\begingroup$

Building on the great post of Marko Riedel MSE link of the same sequence. I wrote the equivalent python code of the maple code that Marko Riedel posted, here is the python code to generate A123527:

import math

class A123527:
    graphs = {}; count = {}; trees = {}

    def __init__(self,nodes,edges):
        self.nodes = nodes
        self.edges = edges

    def nCr(self,n,k):      
        key = (n, k)
        if key not in A123527.trees:
            if k > n:
                result = 0
            elif k == 0 or n == k:
                result = 1
            elif k == 1 or k == n - 1:
                result = n
            else:
                f = math.factorial
                result = int(f(n) / f(k) / f(n-k))
            A123527.trees[key] = result
        return A123527.trees[key]

    def ngraphs(self,n,k):
        if (n, k) not in A123527.graphs:
            A123527.graphs[(n, k)] = self.nCr(n * (n - 1) >> 1, k)
        return A123527.graphs[(n, k)]

    def T(self,n,k):
        if (n, k) in A123527.count:
            return A123527.count[(n, k)]
        if k == n - 1:
            result = int(n**(n - 2))
        if k == n*(n - 1)>>1:
            result = 1
        if k >= self.nCr(n-1,2)+1:
            result = self.nCr(self.nCr(n,2),k)
        else:
            p = n * (n - 1) >> 1
            result = self.nCr((n*(n-1)>>1),k)
            if k < p - n + 2:
                for i in range(1, n):
                    x = self.nCr(n - 1, i - 1)
                    y = min(i * (i - 1) >> 1, k)
                    for j in range(i - 1, y + 1):
                        result -= x* self.ngraphs(n - i, k - j)* self.T(i, j)
        A123527.count[(n, k)] = result
        return result

Output

res = A123527(20,22)
result = res.T(20,22)

result
Out: 2308679811324625848791040000L
$\endgroup$
  • $\begingroup$ Interesting work. It helped me spot a typographical error in the page that you linked to, which I fixed. Thank you and (+1). $\endgroup$ – Marko Riedel Mar 6 '16 at 22:01
  • $\begingroup$ @MarkoRiedel Your post was really helpful also introduced me to the maple code world. I am still working in improving this function/add comments to the code, will post new code soon. $\endgroup$ – jlroo Mar 7 '16 at 23:41

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.