Faà di Bruno's formula

Faà di Bruno's formula is an identity in mathematics generalizing the chain rule to higher derivatives. It is named after Francesco Faà di Bruno (1855, 1857), although he was not the first to state or prove the formula. In 1800, more than 50 years before Faà di Bruno, the French mathematician Louis François Antoine Arbogast had stated the formula in a calculus textbook,[1] which is considered to be the first published reference on the subject.[2]

Perhaps the most well-known form of Faà di Bruno's formula says that

where the sum is over all -tuples of nonnegative integers satisfying the constraint

Sometimes, to give it a memorable pattern, it is written in a way in which the coefficients that have the combinatorial interpretation discussed below are less explicit:

Combining the terms with the same value of and noticing that has to be zero for leads to a somewhat simpler formula expressed in terms of Bell polynomials :

Combinatorial form

The formula has a "combinatorial" form:

where

  • runs through the set of all partitions of the set ,
  • "" means the variable runs through the list of all of the "blocks" of the partition , and
  • denotes the cardinality of the set (so that is the number of blocks in the partition and is the size of the block ).

Example

The following is a concrete explanation of the combinatorial form for the case.

The pattern is:

The factor corresponds to the partition 2 + 1 + 1 of the integer 4, in the obvious way. The factor that goes with it corresponds to the fact that there are three summands in that partition. The coefficient 6 that goes with those factors corresponds to the fact that there are exactly six partitions of a set of four members that break it into one part of size 2 and two parts of size 1.

Similarly, the factor in the third line corresponds to the partition 2 + 2 of the integer 4, (4, because we are finding the fourth derivative), while corresponds to the fact that there are two summands (2 + 2) in that partition. The coefficient 3 corresponds to the fact that there are ways of partitioning 4 objects into groups of 2. The same concept applies to the others.

A memorizable scheme is as follows:

Variations

Multivariate version

Let . Then the following identity holds regardless of whether the variables are all distinct, or all identical, or partitioned into several distinguishable classes of indistinguishable variables (if it seems opaque, see the very concrete example below):[3]

where (as above)

  • runs through the set of all partitions of the set ,
  • "" means the variable runs through the list of all of the "blocks" of the partition , and
  • denotes the cardinality of the set (so that is the number of blocks in the partition and

is the size of the block ).

More general versions hold for cases where the all functions are vector- and even Banach-space-valued. In this case one needs to consider the Fréchet derivative or Gateaux derivative.

Example

The five terms in the following expression correspond in the obvious way to the five partitions of the set , and in each case the order of the derivative of is the number of parts in the partition:

If the three variables are indistinguishable from each other, then three of the five terms above are also indistinguishable from each other, and then we have the classic one-variable formula.

Formal power series version

Suppose and are formal power series and .

Then the composition is again a formal power series,

where and the other coefficient for can be expressed as a sum over compositions of or as an equivalent sum over integer partitions of :

where

is the set of compositions of with denoting the number of parts,

or

where

is the set of partitions of into parts, in frequency-of-parts form.

The first form is obtained by picking out the coefficient of in "by inspection", and the second form is then obtained by collecting like terms, or alternatively, by applying the multinomial theorem.

The special case , gives the exponential formula. The special case , gives an expression for the reciprocal of the formal power series in the case .

Stanley[4] gives a version for exponential power series. In the formal power series

we have the th derivative at 0:

This should not be construed as the value of a function, since these series are purely formal; there is no such thing as convergence or divergence in this context.

If

and

and

then the coefficient (which would be the th derivative of evaluated at 0 if we were dealing with convergent series rather than formal power series) is given by

where runs through the set of all partitions of the set and are the blocks of the partition , and is the number of members of the th block, for .

This version of the formula is particularly well suited to the purposes of combinatorics.

We can also write with respect to the notation above

where are Bell polynomials.

A special case

If , then all of the derivatives of are the same and are a factor common to every term:

where is the nth complete exponential Bell polynomial.

In case is a cumulant-generating function, then is a moment-generating function, and the polynomial in various derivatives of is the polynomial that expresses the moments as functions of the cumulants.

See also

Notes

  1. ^ (Arbogast 1800).
  2. ^ According to Craik (2005, pp. 120–122): see also the analysis of Arbogast's work by Johnson (2002, p. 230).
  3. ^ Hardy, Michael (2006). "Combinatorics of Partial Derivatives". Electronic Journal of Combinatorics. 13 (1): R1. doi:10.37236/1027. S2CID 478066.
  4. ^ See the "compositional formula" in Chapter 5 of Stanley, Richard P. (1999) [1997]. Enumerative Combinatorics. Cambridge University Press. ISBN 978-0-521-55309-4.

References

Historical surveys and essays

Research works

Read other articles:

Иеремиил День памяти 8 ноября  Медиафайлы на Викискладе Иеремии́л (др.-евр. ‏ירחמיאל‏‎ — «высота Божия», «возвышение к Богу», Иерахмиил; Рамиил), в христианской и иудаистской ангелологии один из архангелов. Упоминается в неканонической ветхозаветной третьей...

جزء من سلسلة مقالات حولالاقتصاد الكُلِّيُّ مفاهيم رئيسة طلب إجمالي عرض إجمالي دورة أعمال انكماش مالي صدمة طلب تخفيض معدل التضخم طلب فعال توقع تكيفي توقعات رشيدة أزمة مالية نمو اقتصادي تضخم اقتصادي سعر الفائدة مصيدة سيولة مقاييس الدخل القومي والناتج ناتج محلي إجمالي الدخل

قرية فنذخ  - قرية -  تقسيم إداري البلد  اليمن المحافظة محافظة صنعاء المديرية مديرية بني حشيش العزلة عزلة عضران السكان التعداد السكاني 2004 السكان 1٬120   • الذكور 580   • الإناث 540   • عدد الأسر 109   • عدد المساكن 118 معلومات أخرى التوقيت توقيت اليمن (+3 غرينيتش)...

Railway station in Gujarat, India Ahmedabad JunctionAmdavad Junction Express train and Passenger train stationGeneral informationLocationKalupur, Ahmedabad, Gujarat IndiaCoordinates23°01′35″N 72°36′07″E / 23.026265°N 72.601902°E / 23.026265; 72.601902Elevation52.500 metres (172.24 ft)Owned byIndian RailwaysOperated byWestern RailwaysLine(s)Ahmedabad–Mumbai main line,Ahmedabad–Delhi main line,Ahmedabad–Surendranagar line,Ahmedabad–Gandhidha...

American Music Awards (AMAs) adalah acara penghargaan musik tahunan Amerika, umumnya diadakan pada musim gugur, dibentuk oleh Dick Clark pada tahun 1973 untuk ABC ketika kontrak jaringan untuk menayangkan Grammy Awards berakhir.Dari tahun 1973 hingga 2005, baik pemenang maupun nominasi dipilih oleh anggota industri musik, berdasarkan kinerja komersial, seperti penjualan dan pemutaran. Sejak tahun 2006, pemenang telah ditentukan oleh jajak pendapat publik dan penggemar, yang dapat memilih mela...

Campeonato Nacional AFP PlanVital Erstaustragung 1933 Hierarchie 1. Liga Mannschaften 16 Aktueller Meister CSD Colo-Colo (33. Titel) Rekordsieger CSD Colo-Colo (33) Rekordspieler Chilene Adolfo Nef (625) Rekordtorschütze Chilene Francisco Valdés (224) Aktuelle Saison 2023 Website www.anfp.cl Qualifikation für Copa LibertadoresCopa SudamericanaSupercopa de Chile Region Chile ChileVorlage:InfoboxFußballwettbwerb/Wartung/Kartenformat ↓ Primera B Die Primera Divisi�...

G20

Forum of 19 countries along with EU and AU For other uses, see G20 (disambiguation). G20Group of TwentyAll leaders at the 2021 G20 Summit in Rome, Italy.  Member countries of the G20   Countries represented through the membership of the European Union   Countries represented through the membership of the African Union   Countries permanently invited (Spain)Formation26 September 1999 (24 years ago) (1999-09-26)2008 (2008) (heads-of-sta...

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada Mei 2016. Aloysius SuwardiLahir(1951-06-21)21 Juni 1951Sukoharjo, Jawa TengahPekerjaanMusikusTahun aktif1974 - sekarang Aloysius Suwardi (lahir 21 Juni 1951) adalah musikus berkebangsaan Indonesia. Bidang yang digeluti dia adalah etnomusikologi, utamanya karawi...

  關於寂静岭系列的首部游戏,請見寂静岭 (游戏)。關於2006年改编电影,請見寂静岭 (电影)。 沉默之丘类型生存恐怖遊戲开发商科樂美 (Team Silent)Creature LabsClimax StudiosDouble Helix GamesVatra Games(英语:Vatra Games)WayForward Technologies(英语:WayForward)小島製作发行商科樂美主创外山圭一郎(日语:外山圭一郎)音乐山岡晃 (1999–2009)Daniel Licht(英语:Daniel Licht) (2012)Ludvig Fo...

Concerto Hi Antares, welcome etcetera. I saw you at Honda Concerto and agree with you 100%. Be aware that you may not revert another user too frequently, see WP:3RR. I will report the other guy if he reverts again. Best,  Mr.choppers | ✎  13:40, 16 March 2023 (UTC)Reply[reply] Also, edit summaries like this are unacceptable. If you find yourself getting that heated step away from the article for a time, rather than make personal attacks. ScottishFinnishRadish (talk) 16:50, 17 March 2023...

Basketball player selection This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (May 2016) (Learn how and when to remove this template message) 1987 NBA draftGeneral informationSportBasketballDate(s)June 22, 1987LocationFelt Forum (New York City, New York)Network(s)TBS SuperstationOverview161 total selections in 7 roundsLeagueNBAFirst selectionDavid Robinson ...

موقع حيز الاشعة تحت الحمراء infrared في طيف الموجات الكهرومغناطيسية. مطيافية الأشعة تحت الحمراء أو علم الأطياف ما تحت الحمراء (بالإنجليزية: Infrared spectroscopy)‏: هو أحد فروع علم الأطياف الذي يتعامل مع المنطقة تحت الحمراء من الطيف الكهرومغناطيسي. ويشمل مجموعة من التقنيات، وأشهرها مطي...

2009 film directed by Benny Boom This article is about the film. For other uses, see Next day air (disambiguation). Next Day AirTheatrical release posterDirected byBenny BoomWritten byBlair CobbsProduced byScott AronsonInny ClemonsMichael WilliamsStarring Donald Faison Mike Epps Wood Harris Omari Hardwick Darius McCrary Cisco Reyes Mos Def Yasmin Deliz CinematographyDavid A. ArmstrongEdited byDavid ChecelMusic byThe ElementsProductioncompaniesA-Mark Entertainment Melee Entertainment Next Day ...

Social movement in Malaysia Fiesta Feminista in Kota Kinabalu, Sabah Part of a series onFeminism History Feminist history History of feminism Women's history American British Canadian German Waves First Second Third Fourth Timelines Women's suffrage Muslim countries US Other women's rights Women's suffrage by country Austria Australia Canada Colombia India Japan Kuwait Liechtenstein New Zealand Spain Second Republic Francoist Switzerland United Kingdom Cayman Islands Wales United States state...

Hindu Temple in Uttarakhand, India Not to be confused with the city Joshimath. Jyotir MathJyotir Math entrance gateFormation500 BC (approx)FounderAdi ShankaraTypeReligiousLocationJoshimath, UttarakhandFirst ShankaracharyaTotakacharyaPresent ShankaracharyaSwami Avimukteshwaranand Saraswati Uttarāmnāya Śrī Jyotish Pītham or Jyotir Math is one amongst the four cardinal pīthams established by the philosopher-saint Śrī Ādi Śaṅkara to preserve and propagate Hinduism and Advaita Vedānta...

Radio station in Box Elder, South DakotaKXMZBox Elder, South DakotaBroadcast areaRapid City, South DakotaFrequency102.7 MHzBrandingHits 102.7ProgrammingFormatHot adult contemporaryOwnershipOwnerHouston Haugo(Haugo Broadcasting, Inc.)HistoryFirst air dateMarch 12, 2008Technical informationFacility ID164109ClassC2ERP50,000 wattsHAAT137 meters (449 feet)LinksWebcastListen liveWebsitewww.hits1027.com KXMZ (102.7 FM, Hits 102.7) is a radio station serving the city of Rapid City, South Dakota and o...

1985–1987 political scandal in the U.S. Iran-Contra affairPart of the Cold War and the Iran–Iraq WarReagan (far right) meets with (left to right) Secretary of Defense Caspar Weinberger, Secretary of State George Shultz, Attorney General Ed Meese, and Chief of Staff Donald Regan in the Oval OfficeDate20 August 1985 (1985-08-20) – 4 March 1987 (1987-03-04)Also known asMcFarlane affair (in Iran), Iran–Contra scandal, Iran–ContraParticipantsReagan administr...

Anthology of comics by Art Spiegelman BreakdownsCover to the first editionCreatorArt SpiegelmanDate1977Publisher Bélier Press Press Pantheon Books Breakdowns is a collected volume of underground comic strips by American cartoonist Art Spiegelman. The book is made up of strips dating to before Spiegelman started planning his graphic novel Maus, but includes the strip Maus which presaged the graphic novel, and Prisoner on the Hell Planet which is reproduced in Maus. The original edition of 197...

Kolkata Metro's Purple Line metro station Behala Chowrastaবেহালা চৌরাস্তাKolkata Metro stationBehala Chowrasta metro station gate CGeneral informationLocationDiamond Harbour Rd, Behala Chowrasta, Kolkata, West Bengal 700008IndiaCoordinates22°29′15″N 88°18′48″E / 22.487529°N 88.313426°E / 22.487529; 88.313426Owned byMetro Railway, KolkataKolkata Metro Rail CorporationOperated byKolkata MetroLine(s)Purple LinePlatformsSide platform...

American reality television series Kell on EarthGenreReality televisionStarringKelly CutroneCountry of originUnited StatesOriginal languageEnglishNo. of seasons1No. of episodes8ProductionExecutive producers Billy Taylor Dan Cutforth Jane Lipsitz Kelly Cutrone ProducerMagical Elves ProductionsRunning time44 minutesOriginal releaseNetworkBravoReleaseFebruary 1 (2010-02-01) –March 29, 2010 (2010-03-29) Kell on Earth is an American reality television series starring Kelly Cutrone...