login
A370081
Number of left-labeled (3,n)-bipartite graphs.
1
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,2
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.
LINKS
A. Atmaca and A. Yavuz Oruc, On The Number Of Labeled Bipartite Graphs, arXiv:2402.08053 [math.CO], 2024.
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)
EXAMPLE
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.
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}
CROSSREFS
Cf. A002727.
Sequence in context: A004640 A250321 A011924 * A346522 A244834 A169831
KEYWORD
nonn
AUTHOR
Yavuz Oruc, Feb 08 2024
STATUS
approved