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

Author

Yavuz Oruc, Feb 08 2024

Keywords

• nonn

Comments

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.

Examples

			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.
		

Links

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

Crossrefs

Cf. A002727.

Programs

Mathematica

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}

Formula

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)