Yavuz Oruc - cp's OEIS frontend

User: Yavuz Oruc

Yavuz Oruc has authored 2 sequences.

A370081 Number of left-labeled (3,n)-bipartite graphs.

1, 8, 25, 60, 129, 256, 484, 872, 1512, 2532, 4110, 6484, 9975, 14992, 22065, 31860, 45207, 63126, 86868, 117934, 158130, 209600, 274874, 356916, 459189, 585694, 741053, 930566, 1160285, 1437090, 1768784, 2164158, 2633108, 3186722, 3837386, 4598894, 5486579, 6517410, 7710149

Offset: 0

Yavuz Oruc, Feb 08 2024

nonn

a(n) = number of left-labeled (3,n)-bipartite graphs. The bipartite graphs counted here arise as representations of certain types of calls in switching networks in which three 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 (3,n)-bipartite graph is a graph with two sets of non-overlapping vertices I and O, where |I| = 3, |O| = n, and the vertices in I are considered different (distinguishable) up to subsets, whereas the n vertices in O are considered entirely interchangeable (indistinguishable). The sequence gives the number of non-isomorphic graphs under these assumptions.

			For n = 1, a(1) = 8 and there are 8 left-labeled (3,1)-bipartite graphs. Suppose the left vertices are labeled a, b, c and the right vertex is labeled d. The left-labeled (3,1)-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 c and d.
(5) Place an edge between a and d, and b and d.
(6) Place an edge between a and d, and c and d.
(7) Place an edge between b and d, and c and d.
(8) Place an edge between a and d, b and d, and c and d.
For n = 2, a(2) = 25 and there are 25 left-labeled (3,2)-bipartite graphs. These left-labeled (3,2)-bipartite graphs are listed in the publication that is given in the reference section.

Yavuz Oruc, Table of n, a(n) for n = 0..50
A. Atmaca and A. Yavuz Oruc, On The Number Of Labeled Bipartite Graphs, arXiv:2402.08053 [math.CO], 2024.

Cf. A002727.

ct1[n_] :=
  Binomial[n+7,7]+(3*(n+4)*(2*n^4+32*n^3+172*n^2+352*n+15*(-1)^n+225))/960;
ct2[n_] := (4*n^3+30*n^2+68*n-3+3*(-1)^n)/24;
B3rmod0 = Function[n,(1/6)(ct1[n] + (n^3 + 12*n^2 + 45*n + 54)/27)+ct2[n]] /@Range[0,50,3];
B3rmod1 = Function[n,(1/6)(ct1[n] + (n^3 + 12*n^2 + 45*n + 50)/27)+ct2[n]] /@Range[1,50,3];
B3rmod2 = Function[n,(1/6)(ct1[n] + (n^3 + 12*n^2 + 39*n + 28)/27)+ct2[n]] /@Range[2,50,3];
B3r = {B3rmod0, B3rmod1, B3rmod2}~Flatten~{2, 1}

Let
  ct1(n) = binomial(n+7,7) + ((n+4)*(2*n^4 + 32*n^3 + 172*n^2 + 352*n + 15*(-1)^n + 225))/320,
  ct2(n) = (4*n^3 + 30*n^2 + 68*n - 3 + 3*(-1)^n)/24,
and
  f(n) = 0            if n mod 3 = 0
       = 2/81         if n mod 3 = 1
       = n/27 + 13/81 if n mod 3 = 2
Then
  a(n) = (1/6)*(ct1(n) + (n^3+12*n^2+45*n+54)/27)+ct2(n)-f(n)

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

Original entry on oeis.org

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

Yavuz Oruc, Feb 14 2024

nonn

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.

			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.

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

Cf. A002623.

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

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

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

cp's OEIS Frontend

User: Yavuz Oruc

A370081 Number of left-labeled (3,n)-bipartite graphs.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula