A370307 a(n) = A002623(n) + n.

1, 4, 9, 16, 26, 39, 56, 77, 103, 134, 171, 214, 264, 321, 386, 459, 541, 632, 733, 844, 966, 1099, 1244, 1401, 1571, 1754, 1951, 2162, 2388, 2629, 2886, 3159, 3449, 3756, 4081, 4424, 4786, 5167, 5568, 5989, 6431, 6894, 7379, 7886, 8416, 8969, 9546, 10147, 10773, 11424, 12101

Offset: 0

Author

Yavuz Oruc, Feb 14 2024

Keywords

• nonn

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.

Examples

			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.
		

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).

Crossrefs

Cf. A002623.

Programs

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 *)

Formula

a(n) = (2*n^3 + 15*n^2 + 58*n + 45/2 + (3/2)*(-1)^n)/24.

Extensions

Edited by N. J. A. Sloane, Feb 19 2024 (simplified definition by referring to a classical sequence).