login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons 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}. 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

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 8 08:16 EST 2021. Contains 341942 sequences. (Running on oeis4.)