login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 13 17:59 EDT 2022. Contains 356107 sequences. (Running on oeis4.)