

A276640


Triangle T(n, k) = the number of pointlabeled graphs with n points and k edges, no points isolated, no edges isolated. By rows, 0 <= n, ceiling(2*n/3) <= k <= binomial(n, 2).


2



1, 3, 1, 16, 15, 6, 1, 125, 222, 205, 120, 45, 10, 1, 90, 1356, 3670, 5700, 6165, 4945, 2997, 1365, 455, 105, 15, 1, 1680, 18942, 69450, 156870, 258160, 331506, 343140, 290745, 202755, 116175, 54257, 20349, 5985, 1330, 210, 21, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

In an incidence matrix for a graph of this kind, with n columns and k rows, each row has 2 ones (since it is a graph), the rows are distinct (since it is not a multigraph), no column is all zeros (since there are no isolated points), and the columns are distinct (since there are no isolated edges). The transpose of such a matrix, and only such, is an incidence matrix of a covering of a set of k elements (called points) by n distinct nonempty subsets (called blocks) such that every point belongs to exactly 2 blocks, and every 2 blocks have at most 1 point of intersection (for if 2 points each belong to both of 2 blocks, then those 2 blocks are all the blocks that either of those 2 points belong to, so the columns for those 2 points in the matrix are equal). Referring all these matrices to canonical ordered sets of n and k points, the number of matrices for each covering by blocks of these kinds is the factorial of the number of blocks. (Since the rows are distinct, every permutation of the blocks as row indices gives a different matrix.) Hence the number of these graphs, with k blocks on n points, T(n, k), is related to the number of those covers, A060052, by T(n, k) * k! = A060052(k, n) * n!.


LINKS

David Pasino, Table of n, a(n) for n = 1..491


FORMULA

T(n, k) = Sum{s=0..min(floor(n/2), k)} binomial(n, 2*s) * ((2*s)! / (2^s * s!)) * (1)^s * A276639(n  2*s, k  s). (This is the inverse relationship of A276639 in terms of T. A276639(n, k) counts graphs with no isolated points, n points, k edges. The summation range of s, the role of s in the arguments (n  2s, k  s) of the T or A function being summed, and the coefficient function of s, are the same in the relationship going either way, except that the factor (1)^s is absent when the function being summed is this T. The coefficient, without the 1, is the number of ways to choose 2s points among the n and group them into s pairs to be s isolated edges. A graph with no isolated points is a graph with some number s of isolated edges and a graph on the complement of the union of those with no isolated edges and no isolated points. That the inverse relationship is almost the same was found empirically for small values of n (leaving k as k), and once found, was readily proved.)


EXAMPLE

The triangle T(n, k) begins:
n\k 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 0 0 3 1 0 0 0 0 0 0 0 0 0 0 0
4 0 0 0 16 15 6 1 0 0 0 0 0 0 0 0
5 0 0 0 0 125 222 205 120 45 10 1 0 0 0 0
6 0 0 0 0 90 1356 3670 5700 6165 4945 2997 1365 455 105 15


CROSSREFS

Cf. A059443, A060052.
Sequence in context: A264902 A156653 A048159 * A123527 A288265 A096611
Adjacent sequences: A276637 A276638 A276639 * A276641 A276642 A276643


KEYWORD

nonn,tabf


AUTHOR

David Pasino, Sep 08 2016


STATUS

approved



