A290131 Number of regions in a regular drawing of the complete bipartite graph K_{n,n}.

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

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

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: A019006 A363123 A168057 * A008911 A005719 A143126

Adjacent sequences: A290128 A290129 A290130 * A290132 A290133 A290134

Keyword

nonn,easy

Author

R. J. Mathar, Jul 20 2017

Status

approved