A117747 Number of different configurations of cycles (loops) in graphs containing directed and undirected links.

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

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

Keywords

• nonn

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

Examples

			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.
		

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

• Andrew Howroyd, Table of n, a(n) for n = 3..500
• Avi Ma'ayan, C program to produce sequence
• Eric Weisstein's World of Mathematics, Helm Graph.
• Eric Weisstein's World of Mathematics, Planar Embedding.
• Eric Weisstein's World of Mathematics, Web Graph.

Crossrefs

Cf. A000011.

Programs

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

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

Extensions

Terms a(16) and beyond from Andrew Howroyd, Nov 07 2019