login
A117747
Number of different configurations of cycles (loops) in graphs containing directed and undirected links.
2
7, 15, 30, 74, 171, 444, 1138, 3048, 8175, 22427, 61686, 171630, 479411, 1347609, 3801522, 10768832, 30595671, 87190791, 249085662, 713268978, 2046679419, 5884137206, 16946037930, 48882597264, 141215566135, 408515830803, 1183284759846, 3431523892390
OFFSET
3,1
COMMENTS
Examples of such graphs are cellular gene regulatory networks and signal transduction networks.
a(n) is also the number of distinct planar embeddings of the n-helm and n-web graphs. - Eric W. Weisstein, May 21 2024
REFERENCES
Ma'ayan, A., Jenkins, S. L., Neves, S., Hasseldine, A., Grace, E., Dubin-Thaler, B., Eungdamrong, N. J., Weng, G., Ram, P. T., Rice, J. J., Kershenbaum, A., Stolovitzky, G. A., Blitzer, R. D. and Iyengar, R., Formation of regulatory patterns during signal propagation in a Mammalian cellular network. Science. 2005 Aug 12;309
LINKS
Eric Weisstein's World of Mathematics, Helm Graph.
Eric Weisstein's World of Mathematics, Planar Embedding.
Eric Weisstein's World of Mathematics, Web Graph.
FORMULA
a(n) = 3^(n/2)/3 + (1/(2*n))*Sum_{k=0..n-1} 3^gcd(n,k) if n is even;
a(n) = 3^((n-1)/2)/2 + (1/(2*n))*Sum_{k=0..n-1} 3^gcd(n,k) if n is odd.
a(n) ~ 3^n / (2*n).
EXAMPLE
a(3) = 1/6 *(3^3+3^1+3^1) + 3^(2/2) / 2 = 7.
a(4) = 1/8 * (3^4+3^1+3^2+3^1) + 3^(4/2) / 3 = 15.
The 7 cycles of length 3 are: --> 0 --> 0 --> 0, --> 0 <-- 0 --> 0, -0 --> 0 --> 0, -0 --> 0 <-- 0, -0 <-- 0 --> 0, -0-0 --> 0, -0-0-0.
PROG
(PARI) a(n)={if(n%2, 3^((n-1)/2)/2, 3^(n/2-1)) + sum(k=0, k=n-1, 3^gcd(n, k))/(2*n)} \\ Andrew Howroyd, Nov 07 2019
CROSSREFS
Cf. A000011.
Sequence in context: A139597 A210675 A293361 * A179882 A317510 A137196
KEYWORD
nonn
AUTHOR
Avi Ma'ayan (avi.maayan(AT)mssm.edu), Guillermo Cecchi, John Wagner, Ravi Rao, Azi Lipshtat, Ravi Iyengar and Gustavo Stolovitzky, Apr 28 2006
EXTENSIONS
Terms a(16) and beyond from Andrew Howroyd, Nov 07 2019
STATUS
approved