|
Divided differences of inverse functions and partitions of a convex polygon
Author(s):
Michael
S.
Floater;
Tom
Lyche.
Journal:
Math. Comp.
77
(2008),
2295-2308.
MSC (2000):
Primary 05A17, 05A18, 26A06, 26A24, 41A05, 65D05
Posted:
June 2, 2008
Retrieve article in:
PDF DVI PostScript
Abstract |
References |
Similar articles |
Additional information
Abstract:
We derive a formula for an  -th order divided difference of the inverse of a function. The formula has a simple and surprising structure: it is a sum over partitions of a convex polygon with  vertices. The formula provides a numerically stable method of computing divided differences of  -th roots. It also provides a new way of enumerating all partitions of a convex polygon of a certain type, i.e., with a specified number of triangles, quadrilaterals, and so on, which includes Catalan numbers as a special case.
References:
-
- 1.
- C. de Boor, Divided differences, Surveys in approximation theory 1 (2005), 46-69. MR 2221566 (2006k:41001)
- 2.
- N. Dershowitz and S. Zaks, Ordered trees and noncrossing partitions, Discrete Math. 62 (1986), 215-218. MR 863045 (88c:05008)
- 3.
- C. F. Faà di Bruno, Note sur une nouvelle formule de calcul differentiel, Quarterly J. Pure Appl. Math, 1 (1857), 359-360.
- 4.
- A. Cayley, On the partition of a polygon, Proc. London Math. Soc. 22 (1890/91), 237-262.
- 5.
- M. S. Floater and T. Lyche, Two chain rules for divided differences and Faà di Bruno's formula, Math. Comp. 76 (2007), 867-877. MR 2291840
- 6.
- W. P. Johnson, The curious history of Faà di Bruno's formula, Amer. Math. Monthly 109 (2002), 217-234. MR 1903577 (2003d:01019)
- 7.
- W. P. Johnson, Combinatorics of higher derivatives of inverses, Amer. Math. Monthly 109 (2002), 273-277.
- 8.
- W. Kahan and R. J. Fateman, Symbolic computation of divided differences, ACM SIGSAM Bulletin 33 (1999), 7-28.
- 9.
- G. Kreweras, Sur les partitions non croisées d'un cycle, Discrete Mathematics 1 (1972), 333-350. MR 0309747 (46:8852)
- 10.
- T. Popoviciu, Sur quelques propriétés des fonctions d'une ou de deux variables reélles, dissertation, presented at the Faculté des Sciences de Paris, published by Institutul de Arte Grafice ``Ardealul'' (Cluj, Romania), 1933.
- 11.
- T. Popoviciu, Introduction à la théorie des différences divisées, Bull. Math. Soc. Roumaine Sciences 42 (1940), 65-78. MR 0013171 (7:117a)
- 12.
- J. H. Przytycki and A. S. Sikora, Polygon dissections and Euler, Fuss, Kirkman, and Cayley numbers, Journal of Combinatorial Theory, Series A 92 (2000), 68-76. MR 1783940 (2001g:05005)
- 13.
- R. Simion, Noncrossing partitions, Discrete Mathematics 217 (2000), 367-409. MR 1766277 (2001g:05011)
- 14.
- R. P. Stanley, Enumerative combinatorics, Vol. 2, Cambridge University Press, 1999. MR 1676282 (2000k:05026)
- 15.
- J. F. Steffensen, Note on divided differences, Danske Vid. Selsk. Math.-Fys. Medd. 17 (1939), 1-12. MR 0000442 (1:75a)
- 16.
- X. Wang and H. Wang, On the divided difference form of Faà di Bruno's formula, J. Comp. Math. 24 (2006), 553-560. MR 2239550 (2007a:65015)
Similar Articles:
Retrieve articles in Mathematics of Computation
with MSC
(2000):
05A17, 05A18, 26A06, 26A24, 41A05, 65D05
Retrieve articles in all Journals with MSC
(2000):
05A17, 05A18, 26A06, 26A24, 41A05, 65D05
Additional Information:
Michael
S.
Floater
Affiliation:
Centre of Mathematics for Applications, Department of Informatics, University of Oslo, P.O. Box 1053, Blindern, 0316 Oslo, Norway
Tom
Lyche
Affiliation:
Centre of Mathematics for Applications, Department of Informatics, University of Oslo, P.O. Box 1053, Blindern, 0316 Oslo, Norway
DOI:
10.1090/S0025-5718-08-02144-3
PII:
S 0025-5718(08)02144-3
Keywords:
Divided differences,
inverse functions,
polygon partitions.
Received by editor(s):
June 29, 2007
Posted:
June 2, 2008
Copyright of article:
Copyright
2008,
American Mathematical Society
|
Comments: webmaster@ams.org