|
| |
|
|
A290131
|
|
Number of regions in a regular drawing of the complete bipartite graph K_{n,n}.
|
|
24
|
|
|
|
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
|
Chai Wah Wu, Table of n, a(n) for n = 1..10000
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.
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)
Eric Weisstein's World of Mathematics, Complete Bipartite Graph
|
|
|
FORMULA
|
a(n) = A115004(n-1) + (n-1)^2.
a(n) = 2*(n-1)^2 + Sum_{i=2..n-1} (n-i)*(2n-i)*phi(i). - Chai Wah Wu, Aug 16 2021
|
|
|
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
(Python)
from sympy import totient
def A290131(n): return 2*(n-1)**2 + sum(totient(i)*(n-i)*(2*n-i) for i in range(2, n)) # Chai Wah Wu, Aug 16 2021
|
|
|
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
|
| |
|
|
