login
A255192
Triangle of number of connected subgraphs of K(n,n) with m edges.
1
1, 4, 1, 81, 78, 36, 9, 1, 4096, 8424, 9552, 7464, 4272, 1812, 560, 120, 16, 1, 390625, 1359640, 2696200, 3880300, 4394600, 4059000, 3111140, 1994150, 1070150, 478800, 176900, 53120, 12650, 2300, 300, 25, 1, 60466176, 314452800, 939988800, 2075760000
OFFSET
1,2
COMMENTS
m ranges from 2n-1 to n^2.
First column is A068087.
FORMULA
Sum(k>=0, T(n,k)*(-1)^k ) = A136126(2*n-1,n-1) = A092552(n+1), alternating row sums.
EXAMPLE
Triangle begins:
----|------------------------------------------------------------
n\m | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
----|------------------------------------------------------------
1 | 1
2 | - - 4 1
3 | - - - - 81 78 36 9 1
4 | - - - - - - 4096 8424 9552 7464 4272 1812 560 120 16 1
PROG
(Python)
from math import comb as binomial
def f(x, a, b, k):
if b == k == 0:
return 1
if b == 0 or k == 0:
return 0
if x == a:
return sum(binomial(a, n) * f(x, x, b - 1, k - n) for n in range(1, a + 1))
return sum(binomial(b, n) * f(x, x, n, k2) * f(n, b, a - x, k - k2)
for n in range(1, b + 1) for k2 in range(0, k + 1) )
def a(n, m):
return f(1, n, n, m)
for n in range(1, 5):
print([a(n, m) for m in range(1, n * n + 1)])
CROSSREFS
Cf. A005333 (row sums?).
Sequence in context: A114917 A100864 A295178 * A299582 A211341 A280620
KEYWORD
nonn,tabf
AUTHOR
Thomas Dybdahl Ahle, Feb 16 2015
STATUS
approved