A290131 -id:A290131 - cp's OEIS frontend

A159065 Number of crossings in a regular drawing of the complete bipartite graph K(n,n).

0, 1, 7, 27, 65, 147, 261, 461, 737, 1143, 1637, 2349, 3217, 4401, 5769, 7457, 9433, 11945, 14753, 18235, 22173, 26771, 31801, 37813, 44449, 52161, 60489, 69955, 80289, 92203, 104941, 119493, 135261, 152705, 171205, 191649, 213473, 237877

Offset: 1

Stéphane Legendre, Apr 04 2009, Jul 11 2009

			For n = 3 draw vertically 3 points regularly spaced on the right, and 3 points regularly spaced on the left. Join the left and right points by straight lines. These lines cross at c(3) = 7 points.

Umberto Eco, Foucault's Pendulum. San Diego: Harcourt Brace Jovanovich, p. 473, 1989.
Athanasius Kircher (1601-1680). Ars Magna Sciendi, In XII Libros Digesta, qua nova et universali Methodo Per Artificiosum Combinationum contextum de omni re proposita plurimis et prope infinitis rationibus disputari, omniumque summaria quaedam cognitio comparari potest, Amstelodami, Apud Joannem Janssonium a Waesberge, et Viduam Elizei Weyerstraet, 1669, fol., pp. 482 (altra ed.: Amstelodami.(ut supra), 1671).

N. J. A. Sloane, Table of n, a(n) for n = 1..1000 [First 500 terms from Indranil Ghosh]
Lars Blomberg, Scott R. Shannon, and N. J. A. Sloane, Graphical Enumeration and Stained Glass Windows, 1: Rectangular Grids, (2020). Also arXiv:2009.07918.
M. Griffiths, Counting the regions in a regular drawing of K_{n,n}, J. Int. Seq. 13 (2010) # 10.8.5, Lemma 2.
S. 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

Cf. A000537, A115004, A114999, A290131, A331755.

A159065 := proc(n)
    local a,b,c ;
    c := 0 ;
    for a from 1 to n-1 do
    for b from 1 to n-1 do
        if igcd(a,b) = 1 then
            c := c+(n-a)*(n-b) ;
            if 2*a< n and 2*b < n then
                c := c-(n-2*a)*(n-2*b) ;
            end if;
        end if;
    end do:
    end do:
    c ;
end proc:
seq(A159065(n),n=1..30); # R. J. Mathar, Jul 20 2017

a[n_] := Module[{x, y, s1 = 0, s2 = 0}, For[x = 1, x <= n-1, x++, For[y = 1, y <= n-1, y++, If[GCD[x, y] == 1, s1 += (n-x)*(n-y); If[2*x <= n-1 && 2*y <= n-1, s2 += (n-2*x)*(n-2*y)]]]]; s1-s2]; Table[a[n], {n, 1, 40}] (* Jean-François Alcover, Jan 10 2014, translated from Joerg Arndt's PARI code *)

a(n) = {
    my(s1=0, s2=0);
    for (x=1, n-1,
        for (y=1, n-1,
            if ( gcd(x, y)==1,
                s1 += (n-x) * (n-y);
                if ( ( 2*x<=n-1) && (2*y<=n-1),
                    s2 += (n-2*x) * (n-2*y); );
             );
        );
    );
    return( s1 - s2 );
}
\\ Joerg Arndt, Oct 13 2013

s1:=0; s2:=0;
for a:=1 to n-1 do
   for b:=1 to n-1 do
      if gcd(a, b)=1 then
      begin
         s1:=s1+(n-a)*(n-b);
         if (2*a<=n-1) and (2*b<=n-1) then
            s2:=s2+(n-2*a)*(n-2*b);
      end;
a:=s1-s2;

from math import gcd
def a159065(n):
    c=0
    for a in range(1, n):
        for b in range(1, n):
            if gcd(a, b)==1:
                c+=(n - a)*(n - b)
                if 2*aIndranil Ghosh, Jul 20 2017

from sympy import totient
def A159065(n): return n-1 if n <= 2 else 2*n-3+3*sum(totient(i)*(n-i)*i for i in range(2,(n+1)//2)) + sum(totient(i)*(n-i)*(2*n-i) for i in range((n+1)//2,n)) # Chai Wah Wu, Aug 16 2021

a(n) = Sum((n-a)*(n-b); 1<=a

a(n) = (9/(8*Pi^2))*n^4 + O(n^3 log(n)). Asymptotic to (9/(2*Pi^2))*A000537(n-1).

For n > 2: a(n) = A115004(n-1)-(n-2)^2-2*Sum{n=2..floor((n-1)/2)} (n-2i)*(n-i)*phi(i) = 2n-3+3*Sum{n=2..floor((n-1)/2)}(n-i)*i*phi(i) + Sum_{n=floor((n+1)/2)..n-1} (n-i)*(2n-i)*phi(i). - Chai Wah Wu, Aug 16 2021

A355799 Number of vertices formed in a square by straight line segments when connecting the n-1 points between each corner that divide each edge into n equal parts to the n-1 points on the edge on the opposite side of the square.

Original entry on oeis.org

4, 9, 25, 93, 277, 597, 1405, 2421, 4357, 6661, 11261, 14593, 23625, 30121, 41453, 54477, 75985, 87677, 122433, 139461, 177965, 216017, 275733, 298805, 383497, 439909, 522473, 588597, 729501, 763149, 963573, 1045701, 1204481, 1361789, 1546309, 1657125, 2009113, 2166617, 2418733, 2602789

Offset: 1

Scott R. Shannon, Jul 17 2022

nonn

Scott R. Shannon, Image for n = 2.
Scott R. Shannon, Image for n = 3.
Scott R. Shannon, Image for n = 4.
Scott R. Shannon, Image for n = 5.
Scott R. Shannon, Image for n = 6.
Scott R. Shannon, Image for n = 7.
Scott R. Shannon, Image for n = 8.
Scott R. Shannon, Image for n = 16.

Cf. A355798 (regions), A355800 (edges), A355801 (k-gons), A255011 (all vertices), A290131, A331452, A335678.

a(n) = A355800(n) - A355798(n) + 1 by Euler's formula.

A355838 Number of regions formed in a square by straight line segments when connecting the n+1 points along each edge that divide it into n equal parts to the n+1 points on the edge on the opposite side of the square.

Original entry on oeis.org

4, 40, 184, 496, 1240, 2144, 4380, 6720, 10860, 15528, 24300, 30152, 46036, 57496, 75056, 96416, 129052, 148512, 198392, 225240, 279576, 336272, 415988, 453376, 565052, 648008, 754808, 848664, 1026040, 1085536, 1331532, 1452704, 1652684, 1862600, 2084888, 2247568, 2662092, 2887944, 3193744

Offset: 1

Scott R. Shannon, Jul 18 2022

nonn

This sequence is similar to A355798 but here the corner vertices of the square are also connected to points on the opposite edge.

Scott R. Shannon, Image for n = 2.
Scott R. Shannon, Image for n = 3.
Scott R. Shannon, Image for n = 4.
Scott R. Shannon, Image for n = 5.
Scott R. Shannon, Image for n = 6.
Scott R. Shannon, Image for n = 7.
Scott R. Shannon, Image for n = 8.
Scott R. Shannon, Image for n = 11.
Scott R. Shannon, Image for n = 16.

Cf. A355839 (vertices), A355840 (edges), A355841 (k-gons), A355798 (without corner vertices), A290131, A331452, A335678.

a(n) = A355840(n) - A355839(n) + 1 by Euler's formula.

A355800 Number of edges formed in a square by straight line segments when connecting the n-1 points between each corner that divide each edge into n equal parts to the n-1 points on the edge on the opposite side of the square.

Original entry on oeis.org

4, 12, 48, 196, 592, 1308, 2992, 5236, 9296, 14332, 23704, 31432, 49592, 64208, 87712, 115524, 158776, 186660, 255464, 295532, 374200, 455064, 574024, 632836, 800568, 923764, 1092672, 1238412, 1515912, 1613148, 2001200, 2191124, 2516016, 2847668, 3223968, 3485484, 4167304, 4523992, 5042336

Offset: 1

Scott R. Shannon, Jul 17 2022

nonn

See A355798 for images of the squares.

Cf. A355798 (regions), A355799 (vertices), A355801 (k-gons), A255011 (all vertices), A290131, A331452, A335678.

a(n) = A355798(n) + A355799(n) - 1 by Euler's formula.

A359694 Irregular table read by rows: T(n,k) is the number of k-gons, k>=3, in a regular drawing of a complete bipartite graph where the vertex positions on each part equal the Farey series of order n.

Original entry on oeis.org

2, 10, 2, 70, 24, 218, 160, 4, 1254, 1068, 148, 16, 2254, 2414, 252, 26, 10082, 11760, 1980, 266, 12, 21410, 25958, 5096, 648, 36, 4, 53422, 68208, 14360, 1980, 168, 20, 86986, 118922, 24028, 3056, 248, 12, 0, 2, 255678, 346676, 84344, 12774, 1132, 110, 4, 2, 365674, 493530, 119820, 18600, 1624, 112, 4

Offset: 1

Scott R. Shannon and N. J. A. Sloane, Jan 11 2023

The number of vertices along each edge is A005728(n). No formula is known.

See A359692 for other images of the graph.

			The table begins:
2;
10, 2;
70, 24;
218, 160, 4;
1254, 1068, 148, 16;
2254, 2414, 252, 26;
10082, 11760, 1980, 266, 12;
21410, 25958, 5096, 648, 36, 4;
53422, 68208, 14360, 1980, 168, 20;
86986, 118922, 24028, 3056, 248, 12, 0, 2;
255678, 346676, 84344, 12774, 1132, 110, 4, 2;
365674, 493530, 119820, 18600, 1624, 112, 4;
917478, 1244492, 334096, 57080, 5700, 478, 16, 4;
1335398, 1862666, 495536, 82642, 8096, 676, 24, 6;
2107042, 2989864, 788340, 128378, 12536, 932, 52, 4;
3195474, 4557430, 1230300, 205352, 20516, 1664, 80, 4;
.
.

Scott R. Shannon, Image for n = 7.
Eric Weisstein's World of Mathematics, Complete Bipartite Graph.
Wikipedia, Farey sequence.

Cf. A359690 (vertices), A359691 (crossings), A359692 (regions), A359693 (edges), A005728, A290131, A359653, A358886, A358882, A006842, A006843.

Sum of row n = A359692(n).

A334701 Consider the figure made up of a row of n adjacent congruent rectangles, with diagonals of all possible rectangles drawn; a(n) = number of interior vertices where exactly two lines cross.

Original entry on oeis.org

1, 6, 24, 54, 124, 214, 382, 598, 950, 1334, 1912, 2622, 3624, 4690, 6096, 7686, 9764, 12010, 14866, 18026, 21904, 25918, 30818, 36246, 42654, 49246, 57006, 65334, 75098, 85414, 97384, 110138, 124726, 139642, 156286, 174018, 194106, 214570, 237534, 261666, 288686, 316770, 348048, 380798, 416524, 452794, 492830

Offset: 1

Scott R. Shannon and N. J. A. Sloane, May 30 2020

nonn

It would be nice to have a formula or recurrence. - N. J. A. Sloane, Jun 22 2020

Lars Blomberg, Table of n, a(n) for n = 1..500
Lars Blomberg, Array (s,n) of the number of internal vertices where exactly s=2..501 lines cross in a figure made up of a row of n=1..500 adjacent congruent rectangles, with diagonals of all possible rectangles drawn. Rows are stored comma-separated.
Lars Blomberg, Scott R. Shannon, N. J. A. Sloane, Graphical Enumeration and Stained Glass Windows, 1: Rectangular Grids, (2020). Also arXiv:2009.07918.
Scott R. Shannon, Colored illustration showing regions for n=1
Scott R. Shannon, Images of vertices for n=1.
Scott R. Shannon, Colored illustration showing regions for n=2
Scott R. Shannon, Images of vertices for n=2.
Scott R. Shannon, Colored illustration showing regions for n=3
Scott R. Shannon, Images of vertices for n=3.
Scott R. Shannon, Colored illustration showing regions for n=4
Scott R. Shannon, Images of vertices for n=4.
Scott R. Shannon, Colored illustration showing regions for n=5
Scott R. Shannon, Images of vertices for n=5
Scott R. Shannon, Colored illustration showing regions for n=6
Scott R. Shannon, Images of vertices for n=6
Scott R. Shannon, Images of vertices for n=7
Scott R. Shannon, Images of vertices for n=8
Scott R. Shannon, Images of vertices for n=9.
Scott R. Shannon, Images of vertices for n=11.
Scott R. Shannon, Images of vertices for n=14.
Index entries for sequences related to stained glass windows

Column 4 of array in A333275.
Cf. A306302, A331755, A290131, A333274.
See also A115004, A331761.

Conjecture: As n -> oo, a(n) ~ C*n^4/Pi^2, where C is about 0.95 (compare A115004, A331761). - N. J. A. Sloane, Jul 03 2020

More terms from Lars Blomberg, Jun 17 2020

A355801 Irregular table read by rows: T(n,k) is the number of k-sided polygons, for k>=3, in a square when straight line segments connect the n-1 points between each corner that divide each edge into n equal parts to the n-1 points on the edge on the opposite side of the square.

Original entry on oeis.org

0, 1, 0, 4, 12, 12, 56, 32, 16, 156, 124, 24, 8, 0, 4, 384, 228, 72, 28, 716, 648, 144, 68, 8, 4, 1312, 1144, 240, 112, 8, 2244, 1912, 528, 256, 3528, 3072, 696, 360, 16, 5012, 5536, 1296, 524, 48, 28, 7696, 6596, 1960, 572, 16, 10340, 11448, 2968, 1028, 160, 24, 14520, 14428, 3872, 1156, 104, 8

Offset: 1

Scott R. Shannon, Jul 17 2022

Up to n = 50 the maximum sided k-gon created is the 8-gon. It is plausible this is the maximum sided k-gon for all n, although this is unknown.
See A355798 for more images of the square.
The keyword "look" is for the n = 10 image. - N. J. A. Sloane, Jul 21 2022

			The table begins:
0,     1;
0,     4;
12,    12;
56,    32,    16;
156,   124,   24,   8,    0,   4;
384,   228,   72,   28;
716,   648,   144,  68,   8,   4;
1312,  1144,  240,  112,  8;
2244,  1912,  528,  256;
3528,  3072,  696,  360,  16;
5012,  5536,  1296, 524,  48,  28;
7696,  6596,  1960, 572,  16;
10340, 11448, 2968, 1028, 160, 24;
14520, 14428, 3872, 1156, 104, 8;
19588, 19156, 5296, 2052, 160, 8;
25392, 26112, 7160, 2152, 208, 24;
31820, 37244, 9936, 3240, 488, 64;
.
.

Scott R. Shannon, Image for n = 10.

Cf. A355798 (regions), A355799 (vertices), A355800 (edges), A355801 (k-gons), A255011 (all vertices), A290131, A331452, A335678.

A290132 The number of edges in a graph induced by a regular drawing of K_{n,n}.

Original entry on oeis.org

1, 6, 24, 74, 170, 362, 642, 1110, 1766, 2706, 3894, 5558, 7602, 10326, 13562, 17510, 22178, 28006, 34634, 42722, 51922, 62570, 74450, 88462, 103994, 121862, 141482, 163610, 187886, 215578, 245430, 279198, 315958, 356390, 399830, 447542, 498626, 555278, 615698, 681206

Offset: 1

R. J. Mathar, Jul 20 2017

Chai Wah Wu, Table of n, a(n) for n = 1..10000
M. Griffiths, Counting the regions in a regular drawing of K_{n,n}, J. Int. Seq. 13 (2010) # 10.8.5, Table 2.

Cf. A159065, A290131.

A290132 := proc(n)
    2*n+A290131(n)+A159065(n)-1 ;
end proc:
seq(A290132(n),n=1..40);

b[n_] := Sum[(n-i+1)(n-j+1) Boole[GCD[i, j] == 1], {i, n}, {j, n}];
A290131[n_] := b[n-1] + (n-1)^2;
A159065[n_] := Module[{x, y, s1 = 0, s2 = 0}, For[x = 1, x <= n - 1, x++, For[y = 1, y <= n - 1, y++, If[GCD[x, y] == 1, s1 += (n - x)(n - y); If[2x <= n - 1 && 2y <= n - 1, s2 += (n - 2x)(n - 2y)]]]]; s1 - s2];
a[n_] := 2n + A290131[n] + A159065[n] - 1;
Table[a[n], {n, 1, 40}] (* Jean-François Alcover, May 24 2023, after Joerg Arndt in A159065 *)

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 a159065(n):
    c=0
    for a in range(1, n):
        for b in range(1, n):
            if gcd(a, b)==1:
                c+=(n - a)*(n - b)
                if 2*aIndranil Ghosh, Jul 20 2017

a(n) = 2*n + A290131(n) + A159065(n) - 1.

A355839 Number of vertices formed in a square by straight line segments when connecting the n+1 points along each edge that divide it into n equal parts to the n+1 points on the edge on the opposite side of the square.

Original entry on oeis.org

5, 25, 133, 357, 1013, 1637, 3761, 5561, 9313, 13065, 21689, 25357, 41553, 50157, 66005, 84897, 117793, 129841, 181717, 198857, 251189, 302293, 383161, 401073, 517193, 587041, 687765, 763425, 949869, 966249, 1234425, 1320913, 1512233, 1703657, 1912765, 2023569, 2475361, 2649813, 2934997

Offset: 1

Scott R. Shannon, Jul 18 2022

nonn

This sequence is similar to A355799 but here the corner vertices of the square are also connected to points on the opposite edge.

Scott R. Shannon, Image for n = 2.
Scott R. Shannon, Image for n = 3.
Scott R. Shannon, Image for n = 4.
Scott R. Shannon, Image for n = 5.
Scott R. Shannon, Image for n = 6.
Scott R. Shannon, Image for n = 11.

Cf. A355838 (regions), A355840 (edges), A355841 (k-gons), A355799 (without corner vertices), A290131, A331452, A335678.

a(n) = A355840(n) - A355838(n) + 1 by Euler's formula.

A355840 Number of edges formed in a square by straight line segments when connecting the n+1 points along each edge that divide it into n equal parts to the n+1 points on the edge on the opposite side of the square.

Original entry on oeis.org

8, 64, 316, 852, 2252, 3780, 8140, 12280, 20172, 28592, 45988, 55508, 87588, 107652, 141060, 181312, 246844, 278352, 380108, 424096, 530764, 638564, 799148, 854448, 1082244, 1235048, 1442572, 1612088, 1975908, 2051784, 2565956, 2773616, 3164916, 3566256, 3997652, 4271136, 5137452, 5537756

Offset: 1

Scott R. Shannon, Jul 18 2022

nonn

This sequence is similar to A355800 but here the corner vertices of the square are also connected to points on the opposite edge.

See A355838 for images of the squares.

Cf. A355838 (regions), A355839 (vertices), A355841 (k-gons), A355800 (without corner vertices), A290131, A331452, A335678.

a(n) = A355838(n) + A355839(n) - 1 by Euler's formula.

Previous Showing 11-20 of 28 results. Next

cp's OEIS Frontend

A159065 Number of crossings in a regular drawing of the complete bipartite graph K(n,n).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Pascal

Python

Python

Formula

A355799 Number of vertices formed in a square by straight line segments when connecting the n-1 points between each corner that divide each edge into n equal parts to the n-1 points on the edge on the opposite side of the square.

Views

Author

Keywords

Links

Crossrefs

Formula

A355838 Number of regions formed in a square by straight line segments when connecting the n+1 points along each edge that divide it into n equal parts to the n+1 points on the edge on the opposite side of the square.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A355800 Number of edges formed in a square by straight line segments when connecting the n-1 points between each corner that divide each edge into n equal parts to the n-1 points on the edge on the opposite side of the square.

Views

Author

Keywords

Comments

Crossrefs

Formula

A359694 Irregular table read by rows: T(n,k) is the number of k-gons, k>=3, in a regular drawing of a complete bipartite graph where the vertex positions on each part equal the Farey series of order n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A334701 Consider the figure made up of a row of n adjacent congruent rectangles, with diagonals of all possible rectangles drawn; a(n) = number of interior vertices where exactly two lines cross.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A355801 Irregular table read by rows: T(n,k) is the number of k-sided polygons, for k>=3, in a square when straight line segments connect the n-1 points between each corner that divide each edge into n equal parts to the n-1 points on the edge on the opposite side of the square.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A290132 The number of edges in a graph induced by a regular drawing of K_{n,n}.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A355839 Number of vertices formed in a square by straight line segments when connecting the n+1 points along each edge that divide it into n equal parts to the n+1 points on the edge on the opposite side of the square.

Views

Author

Keywords