Encyclopedia of Integer Sequences - Formula

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?

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

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

• Interesting work. It helped me spot a typographical error in the page that you linked to, which I fixed. Thank you and (+1). – Marko Riedel Mar 6 '16 at 22:01
• @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. – jlroo Mar 7 '16 at 23:41