cp's OEIS Frontend

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

%I A370081 #24 Feb 25 2024 10:41:52
%S A370081 1,8,25,60,129,256,484,872,1512,2532,4110,6484,9975,14992,22065,31860,
%T A370081 45207,63126,86868,117934,158130,209600,274874,356916,459189,585694,
%U A370081 741053,930566,1160285,1437090,1768784,2164158,2633108,3186722,3837386,4598894,5486579,6517410,7710149
%N A370081 Number of left-labeled (3,n)-bipartite graphs.
%C A370081 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.
%H A370081 Yavuz Oruc, <a href="/A370081/b370081.txt">Table of n, a(n) for n = 0..50</a>
%H A370081 A. Atmaca and A. Yavuz Oruc, <a href="https://arxiv.org/abs/2402.08053">On The Number Of Labeled Bipartite Graphs</a>, arXiv:2402.08053 [math.CO], 2024.
%F A370081 Let
%F A370081   ct1(n) = binomial(n+7,7) + ((n+4)*(2*n^4 + 32*n^3 + 172*n^2 + 352*n + 15*(-1)^n + 225))/320,
%F A370081   ct2(n) = (4*n^3 + 30*n^2 + 68*n - 3 + 3*(-1)^n)/24,
%F A370081 and
%F A370081   f(n) = 0            if n mod 3 = 0
%F A370081        = 2/81         if n mod 3 = 1
%F A370081        = n/27 + 13/81 if n mod 3 = 2
%F A370081 Then
%F A370081   a(n) = (1/6)*(ct1(n) + (n^3+12*n^2+45*n+54)/27)+ct2(n)-f(n)
%e A370081 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:
%e A370081 (1) Empty bipartite graph (no edges)
%e A370081 (2) Place an edge between a and d.
%e A370081 (3) Place an edge between b and d.
%e A370081 (4) Place an edge between c and d.
%e A370081 (5) Place an edge between a and d, and b and d.
%e A370081 (6) Place an edge between a and d, and c and d.
%e A370081 (7) Place an edge between b and d, and c and d.
%e A370081 (8) Place an edge between a and d, b and d, and c and d.
%e A370081 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.
%t A370081 ct1[n_] :=
%t A370081   Binomial[n+7,7]+(3*(n+4)*(2*n^4+32*n^3+172*n^2+352*n+15*(-1)^n+225))/960;
%t A370081 ct2[n_] := (4*n^3+30*n^2+68*n-3+3*(-1)^n)/24;
%t A370081 B3rmod0 = Function[n,(1/6)(ct1[n] + (n^3 + 12*n^2 + 45*n + 54)/27)+ct2[n]] /@Range[0,50,3];
%t A370081 B3rmod1 = Function[n,(1/6)(ct1[n] + (n^3 + 12*n^2 + 45*n + 50)/27)+ct2[n]] /@Range[1,50,3];
%t A370081 B3rmod2 = Function[n,(1/6)(ct1[n] + (n^3 + 12*n^2 + 39*n + 28)/27)+ct2[n]] /@Range[2,50,3];
%t A370081 B3r = {B3rmod0, B3rmod1, B3rmod2}~Flatten~{2, 1}
%Y A370081 Cf. A002727.
%K A370081 nonn
%O A370081 0,2
%A A370081 _Yavuz Oruc_, Feb 08 2024