|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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, 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
|
|
|
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
|
|
|
STATUS
|
approved
|
|
|
|