A255192 Triangle of number of connected subgraphs of K(n,n) with m edges.

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.

Links

Table of n, a(n) for n=1..39.

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

Adjacent sequences: A255189 A255190 A255191 * A255193 A255194 A255195

Keyword

nonn,tabf

Author

Thomas Dybdahl Ahle, Feb 16 2015

Status

approved