|
| |
|
|
A276640
|
|
Triangle T(n, k) = the number of point-labeled 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
|
|
|
|
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
|
|
|
|
KEYWORD
|
nonn,tabf
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
