OFFSET
0,2
COMMENTS
a(n) = number of left-labeled (2,n)-bipartite graphs.
The bipartite graphs counted here arise as representations of certain types of calls in switching networks in which two callers can be in a call with an arbitrary number (n) of receivers, and where callers are distinguishable, but the receivers are not. In a more abstract setting, a left-labeled (2,n)-bipartite graph is a graph with two sets of non-overlapping vertices I and O, where |I| = 2, |O| = n, and the two vertices in I are considered different (distinguishable), whereas the n vertices in O are considered interchangeable (indistinguishable). The sequence gives the number of non-isomorphic graphs under these assumptions.
LINKS
A. Atmaca and A. Yavuz Oruc, On The Number Of Labeled Bipartite Graphs, arXiv:2402.08053 [math.CO], 2024.
Index entries for linear recurrences with constant coefficients, signature (3,-2,-2,3,-1).
FORMULA
a(n) = (2*n^3 + 15*n^2 + 58*n + 45/2 + (3/2)*(-1)^n)/24.
EXAMPLE
For n = 2, suppose that the left vertices are distinguishable and labeled a and b. The right vertices are indistinguishable but labeled d and e for notational convenience to describe the edges in the example bipartite graphs.
The nine left-labeled (2,2)-bipartite graphs are
(1) Empty bipartite graph (no edges)
(2) Place an edge between a and d
(3) Place an edge between b and d.
(4) Place an edge between a and d and an edge between a and e.
(5) Place an edge between b and d and an edge between b and e
(6) Place an edge between a and d and an edge between b and d
(7) Place an edge between a and d and an edge between b and e
(8) Place an edge between a and d and an edge between b and (d and e)
(9) Place an edge between a and (d and e) and an edge between b and (d and e).
The provided formula works out as: (2*2^3 + 15*2^2 + 58 * 2 + 22.5 + 1.5*(-1)^2)/24 = (16 + 60 + 116 + 24 )/24 = 216/24 = 9.
MATHEMATICA
an = Function[n, (2 n^3 + 15 n^2 + 58 n + 45/2 + (3/2) (-1)^n)/(24)] /@ Range[0, 999, 1];
LinearRecurrence[{3, -2, -2, 3, -1}, {1, 4, 9, 16, 26}, 51] (* Hugo Pfoertner, Feb 15 2024 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Yavuz Oruc, Feb 14 2024
EXTENSIONS
Edited by N. J. A. Sloane, Feb 19 2024 (simplified definition by referring to a classical sequence).
STATUS
approved