Формула Фаа-ди-Бруно является обобщением формулы дифференцирования сложной функции на производные более высоких порядков. Она была названа в честь итальянского математика и священника Франческо Фаа-ди-Бруно, благодаря которому она стала известна (примерно в 1855 году), хотя реально первооткрывателем этой формулы является Луи Франсуа Антони Арбогаст, который более чем за 50 лет до Фаа ди Бруно сделал первые публикации[1] на эту тему.
Возможно, наиболее известна формула Фаа ди Бруно в следующем виде:
где сумма по всем кортежам длины n из неотрицательных целых чисел (m1, …, mn), удовлетворяющих ограничению
Иногда, для лучшего запоминания, формула записывается в виде
однако это снижает очевидность комбинаторной интерпретации.
Суммируя члены с фиксированным значением m1 + m2 + … + mn = k и заметив, что mj должен быть равен нулю при j > n − k + 1, можно прийти к несколько более простой формуле, выраженной через полиномы БеллаBn,k(x1, …, xn−k+1):
Комбинаторный вид формулы может первоначально показаться сложным, поэтому рассмотрим конкретный случай:
Все действия выполняются по следующем образцу:
Множитель очевидным образом соответствует разбиению 2 + 1 + 1 числа 4 (порядок производной). Его сомножитель показывает, что имеется 3 слагаемых в этом разбиении. Наконец, коэффициент 6 означает, что существует ровно 6 разбиений множества из 4 элементов, в которых одна часть содержит два элемента и две части — по одному.
По аналогии, множитель в третьей строке соответствует разбиению 2 + 2 числа 4, а указывает на то, что в этом разбиении должно быть 2 слагаемых . Коэффициент 3 говорит, что есть только способа разбить 4 элемента на группы размера 2.
Остальные члены формулы интерпретируется аналогично.