Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Divided differences of inverse functions and partitions of a convex polygon


Authors: Michael S. Floater and Tom Lyche
Journal: Math. Comp. 77 (2008), 2295-2308
MSC (2000): Primary 05A17, 05A18, 26A06, 26A24, 41A05, 65D05
DOI: https://doi.org/10.1090/S0025-5718-08-02144-3
Published electronically: June 2, 2008
MathSciNet review: 2429886
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We derive a formula for an $ n$-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 $ n+1$ vertices. The formula provides a numerically stable method of computing divided differences of $ k$-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 [Enhancements On Off] (What's this?)

  • 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: https://doi.org/10.1090/S0025-5718-08-02144-3
Keywords: Divided differences, inverse functions, polygon partitions.
Received by editor(s): June 29, 2007
Published electronically: June 2, 2008
Article copyright: © Copyright 2008 American Mathematical Society

American Mathematical Society