Divided differences of inverse functions and partitions of a convex polygon

Floater, Michael; Lyche, Tom

doi:10.1090/S0025-5718-08-02144-3

Divided differences of inverse functions and partitions of a convex polygon
HTML articles powered by AMS MathViewer

by Michael S. Floater and Tom Lyche PDF

Math. Comp. 77 (2008), 2295-2308 Request permission

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

Carl de Boor, Divided differences, Surv. Approx. Theory 1 (2005), 46–69. MR 2221566
Nachum Dershowitz and Shmuel Zaks, Ordered trees and noncrossing partitions, Discrete Math. 62 (1986), no. 2, 215–218. MR 863045, DOI 10.1016/0012-365X(86)90120-2
C. F. Faà di Bruno, Note sur une nouvelle formule de calcul differentiel, Quarterly J. Pure Appl. Math, 1 (1857), 359–360.
A. Cayley, On the partition of a polygon, Proc. London Math. Soc. 22 (1890/91), 237–262.
Michael S. Floater and Tom Lyche, Two chain rules for divided differences and Faà di Bruno’s formula, Math. Comp. 76 (2007), no. 258, 867–877. MR 2291840, DOI 10.1090/S0025-5718-06-01916-8
Warren P. Johnson, The curious history of Faà di Bruno’s formula, Amer. Math. Monthly 109 (2002), no. 3, 217–234. MR 1903577, DOI 10.2307/2695352
W. P. Johnson, Combinatorics of higher derivatives of inverses, Amer. Math. Monthly 109 (2002), 273–277.
W. Kahan and R. J. Fateman, Symbolic computation of divided differences, ACM SIGSAM Bulletin 33 (1999), 7–28.
G. Kreweras, Sur les partitions non croisées d’un cycle, Discrete Math. 1 (1972), no. 4, 333–350 (French). MR 309747, DOI 10.1016/0012-365X(72)90041-6
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.
Tiberiu Popoviciu, Introduction à la théorie des différences divisées, Bull. Math. Soc. Roumaine Sci. 42 (1940), no. 1, 65–78 (French). MR 13171, DOI 10.1016/0016-0032(57)90875-x
Józef H. Przytycki and Adam S. Sikora, Polygon dissections and Euler, Fuss, Kirkman, and Cayley numbers, J. Combin. Theory Ser. A 92 (2000), no. 1, 68–76. MR 1783940, DOI 10.1006/jcta.1999.3042
Rodica Simion, Noncrossing partitions, Discrete Math. 217 (2000), no. 1-3, 367–409 (English, with English and French summaries). Formal power series and algebraic combinatorics (Vienna, 1997). MR 1766277, DOI 10.1016/S0012-365X(99)00273-3
Richard P. Stanley, Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, vol. 62, Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin. MR 1676282, DOI 10.1017/CBO9780511609589
J. F. Steffensen, Note on divided differences, Danske Vid. Selsk. Mat.-Fys. Medd. 17 (1939), no. 3, 12. MR 442, DOI 10.1016/0165-2125(93)90009-5
Xing-hua Wang and He-yu Wang, On the divided difference form of Faà di Bruno’s formula, J. Comput. Math. 24 (2006), no. 4, 553–560. MR 2239550