login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 13 16:36 EDT 2021. Contains 342936 sequences. (Running on oeis4.)