Torsten Sillke, 1998-05-11 1-------4 Given a square with vertices 1, 2, 3, and 4. | \ / | Its diagonals are 13 and 24. | X | The internal crossing points are 'X'. | / \ | The segments are 12, 23, 34, 14, 1X, 2X, 3X, 4X. 2-------3 The regions (cells) are 12X, 23X, 34X, 41X. There are 8 triangles: 12X, 23X, 34X, 41X, 123, 234, 341, 412. Problem: Number of Triangles (convex n-gon) Given a convex n-gon with diagonals in general position. How many triangles are there? Problem: Number of Triangles (regular n-gon) (See [Som98]) Given a regular n-gon. Draw all diagonals. How many triangles can you count? Solution: --------- n triangles P(n) T(n) ------------------------------------- 3 1 1 0 4 8 8 0 5 35 35 0 6 110 111 1 7 287 287 0 8 632 644 12 9 1302 1302 0 10 2400 2430 30 11 4257 4257 0 12 6956 7084 128 13 11297 11297 0 14 17234 17381 147 15 25935 25935 0 16 37424 37688 264 triangles(n) = P(n) - T(n) where P(n) is the number of triangles for a convex n-gon in general position. This means there are no three diagonal through one point (except on the boundary). (There are no degenarate corners.) This number is easy to calculate as: P(n) = Binomial(n,3) + 4*Binomial(n,4) + 5*Binomial(n,5) + Binomial(n,6) = n*(n-1)*(n-2)*(n^3 + 18 n^2 - 43 n + 60)/720 The four terms count the triangles in the following manner [CoE76]: Binomial(n,3) : Number of trianges with 3 corners at the border. 4*Binomial(n,4) : Number of trianges with 2 corners at the border. 5*Binomial(n,5) : Number of trianges with 1 corners at the border. Binomial(n,6) : Number of trianges with 0 corners at the border. T(n) is the number of triple-crossings (this is the number of triples of diagonals which are concurrent) of the regular n-gon. It turns out that such concurrences cannot occur for n odd, and, except for obvious cases, can only occur for n divisible by 6. Among other interesting results, Bol [Bol36] finds values of n for which 4, 5, 6, and 7 diagonals are concurrent and shows that these are the only possibilities (with the center for exception). The function T(n) for n not divisible by 6 is: T(n) = 1/8*n*(n-2)*(n-7)*[2|n] + 3/4*n*[4|n]. where [k|n] is defined as 1 if k is a divisor of n and otherwise 0. The intersection points need not lie an any of lines of symmetry of the 2m-gon, e. g. for n=16 the triple intersection of (0,7),(1,12),(2,14). References: ----------- AlW78: Gerald I. Alexanderson, John E. Wetzel; Simple Partitions of Space, Mathematics Magazine 51:4 (Sep. 1978) 220-225 (plane sweeping method to count various types of regions produced by a given collection of planes. #cell = Binomial(n,0)+Binomial(n,1)+Binomial(n,2)+Binomial(n,3) 2Dim problem: n lines in general position dissect the plane #cell = Binomial(n,0)+Binomial(n,1)+Binomial(n,2) Euler's polyhedral formula f-e+v = 2 is used.) Ber73: Pierre Berloquin; 100 Jeux Geometriques, Paris 1973 (german; Mathematische Kopfspiele, Hugendubel, M\"unchen, 1983) - problem 9: How many different triangles has a 5-gon with all its diagonals? Ber79: Marie Berrondo; Les jeux mathematiques d'Eureka, Bordas, 1979, Paris (german: Eureka's mathematische Spiele, Hugendubel, M\"unchen, 1986) (german: Fallgruben f\"ur Kopf-F\"ussler, Fischer TB 8703, 1989) - chapter 4: problems 12 and 17. given n points in the plan in general position. #diagonals = Binomial(n,2) #crossing points = Binomial(#diagonals, 2) - 3 * Binomial(n,3) = Binomial(#diagonals, 2) - n * Binomial(n-1,2) = Binomial(n,2) * Binomial(n-2,2) / 2 not counting the n points themselves. Bol36: Gerrit Bol; Beantwoording van Prijsvraag no 17, Nieuw Arch. f. Wisk. (2) 18 (1936) 14-68 - concurrent diagonal of a regular n-gon - counting the number of regions - counting the number of segments - counting the number of interior points of any order Com74: Louis Comtet; Advanced Combinatorics, Reidel Publ. (1974) - Chapter: 1.Supplement and Excercises, Problem 8: Some enumeration problems related to convex polygons: Suppose that any three diagonals have no common point, then (1) the diagonals intersect each other in Binomial(n,4) interior points and in n(n-3)(n-4)(n-5)/12 exterior points. (2) the interior is divided into (n-1)(n-2)(n*n-3n+12)/24 convex regions and the whole plane into (n^4-6n^3+23n^2-26n+8)/8 regions. (5) there are n*(n-1)*(n-2)*(n^3 + 18 n^2 - 43 n + 60)/720 triangles in the interior such that every triangle-side is side or diagonal. (There is a Sign-Misprint: -43 is correct) CoG96: John H. Conway, Richard K. Guy; The Book on Numbers, Copernicus an imprint of Springer Verlag, 1996 (german: Zahlenzauber, Birkh\"auser, 1997) - Chapter 3: What comes next?, p 76-79 A cyclic convex n-gon in general position is divided by diagonals. Label the regions in the circle with at most 4 elem subsets of n-1. This gives an combinatorial interpretation of the formular 1+Binomial(n-1,1)+Binomial(n-1,2)+Binomial(n-1,3)+Binomial(n-1,4) CoE76: R. J. Cormier, R. B. Eggleton; Counting by corresponding, Mathematics Magazine 49 (1976) 181-186 (convex n-gon with diagonals in general position, how many triangles?) Dud31: Henry Ernest Dudeney; Puzzles and Curious Problems, London 1931, - p69, 164 How many different triangles has a 5-gon with all its diagonals? Eng98: Arthur Engel; Problem-solving strategies, Problem Books in Mathematics. New York, NY: Springer. x, 403 p. (1998) ISBN 0-387-98219-1/hbk Zbl 887.00002 - Chap. 5 Enumerative Combinatorics E9. Convex n-gons E9.a diagonals = Binomial(n,2) - n E9.b intersection points = Binomial(n,4) E9.c regions (general case) = 1 + Binomial(n,2) - n + Binomial(n,4) E9.d triangles (general case) = Binomial(n,3) + 4*Binomial(n,4) + 5*Binomial(n,5) + Binomial(n,6) Erd46: Paul Erd\"os; AMM 53 (Dec. 1946) 591 (problem E750 of Paul Erd\"os) AMM 54 (June 1947) 344 (solution to E750 by Norbert Kaufman and R. H. Koch) - how many crossing points can the diagonals of an convex n-gon have? Gal95: David Gale; Mathematical Entertainments, The Mathematical Intelligencer, 17:2 (1995) 37-39 - Configurations with Rational Angles = Langley's problem - rational quadrangles (the angle between any of the six sides is a rational multiple of Pi) - concurrent diagonal of a regular n-gon Gar79: Martin Gardner; Mathematical Circus, Alfred A. Knopf, New York 1979 (german: Mathematischer Zirkus, Ulstein, Berlin 1984) - chapter 14: Simplicity The number of regions R(n) in a chord dissected circle. (this is [Mos69]) HaM95: Heiko Harborth, I. Mengersen; Problem 77: Verbindungen ohne Kreuzung Math. Semesterberichte 42 (1995) 81-82 Hei62: H. Heineken; Regelm\"assige Vielecke und ihre Diagonalen, Enseignement Math. (2), ser. 8 (1962) 275-278 - proves that no three diagonals of a regular n-gon meet internally for n odd. Hem94: Heinrich Hemme; Die Sphinx, Vandenhoeck & Ruprecht, G\"ottingen 1994, ISBN 3-525-40735-1 - Problem 14: Kreissehnen The number of regions R(n) in a chord dissected circle. Shows R(n) is not 2**(n-1) and cites [Mos69]. Hon73: Ross Honsberger; Mathematical Gems I, The Dolciani Mathematical Expositions No. 1 The Mathematical Association of America, 1973 (german: Mathematische Edelsteine, Vieweg, Braunschweig, 1981) - Chapter: 9. A combinatorial problem A convex n-gon in general position is divided by diagonals. (1) Interior Regions = Binomial(n,4) + Binomial(n-1,2) (2) Interior Points = Binomial(n,4) The second method for (1) is the same as [Hon78 Problem 3] Hon78: Ross Honsberger; Mathematical Morsels, The Dolciani Mathematical Expositions No. 3 The Mathematical Association of America, 1978 (german: Gitter-Reste-W\"urfel, Vieweg, Braunschweig, 1984) - Problem 3: Regions in a circle Into how many regions is a circle divided if n points on its circumference are joined by chords with no three concurrent? interior regions = 1 + Binomial(n,2) + Binomial(n,4) - AMM 1973, E 2359 from T. C. Brown, Solution from Norman Bauman Kor72: Boris A. Kordemsky; The Moscow Puzzles, Scribners, 1972, (Edited by Martin Gardner) (german: K\"opfchen muss man haben, Urania Verlag, Leipzig, 19??) (german: K\"opfchen muss man haben, Aulis Verlag, K\"oln, 1982) - Chapter 1, Problem 5: Count! How many different triangles are there in the figure? (A regular 5-gon dissected by diagonals is shown.) Lan62: Harry Langman; Play Mathematics, 1962 - Chapter 7: Line problems problem 34: regular 10-gon Lar88: Mogens Esrom Larsen; Mathematical Gazette 72 (1988) 53 Problem 72A (convex n-gon with diagonals in general position, how many triangles?) Mot54: Geoffrey Mott-Smith; Mathematical Puzzles, for beginners and enthusiasts, Dover Publ., 1954 (1946 repr.), - Chapter X: Permutations and Combinations, Problem 162: How many Triangles? If every vertex of a regular octagon is connected with every other, how many triangles will be formed? (2.5 page analysis. number of corners at the boarder gives the 4 major cases.) Mos69: Leo Moser; in: Martin Gardner; Scientific American 221, Aug. 1969, 120-121 (problem) in: Martin Gardner; Scientific American 221, Sep. 1969, 245-246 (solution) - The number of regions R(n) in a chord dissected circle Noy96: M. Noy; A Short Solution of a Problem in Combinatorial Geometry, Mathematics Magazine 69:1 (Feb 1996) 52-53 - Into how many regions is a circle divided if n points on its circumference are joined by chords with no three concurrent? interior regions = 1 + Binomial(n,2) + Binomial(n,4) Interpretation: #chords = Binomial(n,2) #chord intersections = Binomial(n,4) Solution is the same as [Hon78 Problem 3]. PoR95: Bjorn Poonen and Michael Rubinstein The Number of Intersection Points Made by the Diagonals of a Regular Polygon, SIAM J. on Disc. Math. Vol. 11, No. 1 (Feb 1998), pp. 133-156. http://epubs.siam.org:80/sam-bin/dbq/article/28124 Note that Theorem 1 has a typographical error: in the second line, 232 should be replaced by 262. MSRI Preprint #1995-060, 25p Mathematical Sciences Research Institute, Berkeley, CA 94720-5070, USA http://www.msri.org/MSRI-preprints/author.html#P Rig80: J. F. Rigby; Multiple intersections of diagonals of regular polygons, and related topics, Geom. Dedicata 9 (1980) 207-238 - corrects a few misprints and omissions from [Bol36]. Sin99: David Singmaster; SOURCES IN RECREATIONAL MATHEMATICS, AN ANNOTATED BIBLIOGRAPHY 7th preliminary Edition, 1999, Section 5.X.1 COUNTING TRIANGLES Som98: Steven E. Sommars, Tim Sommars; The Number of Triangles Formed by Intersecting Diagonals of a Regular Polygon Journal of Integer Sequences, Vol. 1 (1998), Article 98.1.5 http://www.cs.uwaterloo.ca/journals/JIS/sommars/newtriangle.html Ste83: Hugo Steinhaus; Mathematical Snapshots, Oxford Univ. Press, 1983, 259-260 - poses the problem: no three diagonals of a regular n-gon meet internally for n prime. Shows the picture of a regular 23-gon. Tri85: Charles W. Trigg; Mathematical Quickies, Dover Publ., 1985, - Problem 32: Triangles in a circle If n points on the circumference of a circle are joined by straight lines in all possible ways, and no three of these lines meet at a single point inside the circle, find the number of triangles formed, all of whose vertices lie inside the circle. - Solution 32: Triangles in a circle Every set of six points on the circumference of the circle can be paired in one and only one way such that the three lines joining pairs will form an admissible triangle. Conversely, every admissible triangle has sides leading to six points on the circumference. Hence the number of admissible triangles is Binomial(n,6). -- Leo Moser, Math. Mag. 26 (March 1953) 226. - Problem 227: A particular isosceles triangle - Solution 227: A particular isosceles triangle (special Langley's problem) -- Math. Mag. 39 (Sept. 1966) 253. - Problem 268: Dissected Dodecagon a nontrivial tripple-crossing of diagonals Wet95: John E. Wetzel; Regular Dissections of an Infinite Strip, Discrete Math. 146 (Nov. 1995) 263-269 - Given m equally spaced points on a line in the plane and n equally spaced points on a parallel line, connect each other by a straingth line segment. Find the number of regions formed by the n*m line segments in the infinite strip between the parallel lines. References of Langley's problem and sums of roots of unity: ???78: - Langley's problem - Math. Gaz. 62 (1978) 174-183 CoJ76: J. H. Conway, A. J. Jones; Trigonometric Diophantic equations (On vanishing sums of roots of unity), Acta Arith. 30 (1976) 229-240 Hon76: Ross Honsberger; Mathematical Gems II, The Dolciani Mathematical Expositions No. 2 The Mathematical Association of America, 1976 (german: Mathematische Juwelen, Vieweg, Braunschweig, 1982) - Chapter: 2.3 shows solution of [Tho51] Kno94: C. Knop; Nine Solutions to One Problem, Quantum 4:5 (May/June 1994) 46-49, 60-61 Euc670: Oplossing 670, Euclides 72:2 (Oct 1996) 111 Man65: H. Mann; On linear relations between roots of unity, Mathematika 12 (1965) 107-117 Tho51: Thompson; AMM 58 (1951) 38, Problem E 913 Difference scheme: ------------------ P(n) = Binomial(n,3) + 4*Binomial(n,4) + 5*Binomial(n,5) + Binomial(n,6) P(n) is in Newton normal form. The coefficients (1,4,5,1) are the first diagonal of the following difference scheme. 0 1 2 3 4 5 6 7 8 9 10 -------------------------------------------------------------- 0 0 0 1 8 35 111 287 644 1302 2430 0 0 1 7 27 76 176 357 658 1128 0 1 6 20 49 100 181 301 470 1 5 14 29 51 81 120 169 4 9 15 22 30 39 49 5 6 7 8 9 10 1 1 1 1 1 The number of regions R(n) in a chord dissected circle [Hon78], [CoG96]. R(n) = 1 + Binomial(n,2) + Binomial(n,4) = 1+Binomial(n-1,1)+Binomial(n-1,2)+Binomial(n-1,3)+Binomial(n-1,4) 0 1 2 3 4 5 6 7 8 9 10 -------------------------------------------------------------- 1 1 2 4 8 16 31 57 99 163 256 0 1 2 4 8 15 26 42 64 93 1 1 2 4 7 11 16 22 29 0 1 2 3 4 5 6 7 1 1 1 1 1 1 1 -- mailto:Torsten.Sillke@uni-bielefeld.de http://www.mathematik.uni-bielefeld.de/~sillke/