|
|
A290131
|
|
Number of regions in a regular drawing of the complete bipartite graph K_{n,n}.
|
|
16
|
|
|
0, 2, 12, 40, 96, 204, 368, 634, 1012, 1544, 2236, 3186, 4360, 5898, 7764, 10022, 12712, 16026, 19844, 24448, 29708, 35756, 42604, 50602, 59496, 69650, 80940, 93600, 107540, 123316, 140428, 159642, 180632, 203618, 228556, 255822, 285080, 317326, 352020, 389498
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
LINKS
|
Table of n, a(n) for n=1..40.
Martin Griffiths, Counting the regions in a regular drawing of K_{n,n}, J. Int. Seq. 13 (2010) # 10.8.5. See Lemma 2 and Table 1.
Stéphane Legendre, The Number of Crossings in a Regular Drawing of the Complete Bipartite Graph, J. Integer Seqs., Vol. 12, 2009.
Eric Weisstein's World of Mathematics, Complete Bipartite Graph
|
|
FORMULA
|
a(n) = A115004(n-1) + (n-1)^2.
|
|
MAPLE
|
A115004 := proc(n)
local a, b, r ;
r := 0 ;
for a from 1 to n do
for b from 1 to n do
if igcd(a, b) = 1 then
r := r+(n+1-a)*(n+1-b);
end if;
end do:
end do:
r ;
end proc:
A290131 := proc(n)
A115004(n-1)+(n-1)^2 ;
end proc:
seq(A290131(n), n=1..30) ;
|
|
MATHEMATICA
|
z[n_] := Sum[(n - i + 1)(n - j + 1) Boole[GCD[i, j] == 1], {i, n}, {j, n}];
a[n_] := z[n - 1] + (n - 1)^2;
Array[a, 40] (* Jean-François Alcover, Mar 24 2020 *)
|
|
PROG
|
(Python)
from math import gcd
def a115004(n):
r=0
for a in range(1, n + 1):
for b in range(1, n + 1):
if gcd(a, b)==1:r+=(n + 1 - a)*(n + 1 - b)
return r
def a(n): return a115004(n - 1) + (n - 1)**2
print([a(n) for n in range(1, 51)]) # Indranil Ghosh, Jul 20 2017, after Maple code
|
|
CROSSREFS
|
Cf. A115004, A159065, A290132, A331754.
For K_n see A007569, A007678, A135563.
The following eight sequences are all essentially the same. The simplest is A115004(n), which we denote by z(n). Then A088658(n) = 4*z(n-1); A114043(n) = 2*z(n-1)+2*n^2-2*n+1; A114146(n) = 2*A114043(n); A115005(n) = z(n-1)+n*(n-1); A141255(n) = 2*z(n-1)+2*n*(n-1); A290131(n) = z(n-1)+(n-1)^2; A306302(n) = z(n)+n^2+2*n. - N. J. A. Sloane, Feb 04 2020
Sequence in context: A086602 A019006 A168057 * A008911 A005719 A143126
Adjacent sequences: A290128 A290129 A290130 * A290132 A290133 A290134
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
R. J. Mathar, Jul 20 2017
|
|
STATUS
|
approved
|
|
|
|