편집토론기록

파 디 브루노의 공식

진술[편집 | 원본 편집]

파 디 브루노의 공식(Faà di Bruno's Formula)은 연쇄법칙(chain rule)을 고차 미분으로 일반화한 공식이다. 함수 [math]\displaystyle{ f }[/math]와 [math]\displaystyle{ g }[/math]가 미분가능한 일변수 함수이면 다음이 성립한다:

[math]\displaystyle{ \frac{\mathrm d ^n}{\mathrm dx^n} f(g(x)) = \sum_{\sum_{1\le j \le n} j\cdot m_j = n}\frac{n!}{m_1! m_2! \cdots m_n!} f^{(m_1 + \cdots + m_n)}(g(x)) \prod_{1\le j \le n} \left(\frac{g^{(j)}(x)}{j!} \right)^{m_j}. }[/math]

이를 Bell polynomial

[math]\displaystyle{ B_{n,k}(x_1, \cdots , x_{n-k+1} ) = \sum_{(j_1 , \cdots , j_{n-k+1})} \frac{n!}{j_1! j_2! \cdots j_{n-k+1}!} \prod_{i=1}^{n-k+1} \left(\frac{x_i}{i!}\right)^{j_i} }[/math]

where [math]\displaystyle{ j_1 + \cdots + j_{n-k+1} = k }[/math] and [math]\displaystyle{ j_1 + 2j_2 + \cdots + (n-k+1)j_{n-k+1} = n }[/math]을 이용하여 간단히(?) 나타내면

[math]\displaystyle{ \frac{\mathrm d ^n}{\mathrm dx^n} f(g(x)) = \sum_{k=1}^n f^{(k)} (g(x)) B_{n,k} \left( g'(x) , \cdots , g^{(n-k+1)}(x)\right) }[/math]

가 된다. 또한, 이를 '조합적'으로 나타내면 다음과 같다:

[math]\displaystyle{ \frac{\mathrm d ^n}{\mathrm dx^n} f(g(x)) = \sum_{\pi \in \Pi }f^{(|\pi|)}(g(x)) \prod_{B\in \pi} g^{(|B|)}(x). }[/math]

이때 [math]\displaystyle{ \pi }[/math]는 [math]\displaystyle{ \{1, \cdots, n\} }[/math]의 partition이며 [math]\displaystyle{ \Pi }[/math]는 그러한 [math]\displaystyle{ \pi }[/math]들의 집합이고, [math]\displaystyle{ B \in \pi }[/math]는 partition [math]\displaystyle{ \pi }[/math]의 한 'block'을 뜻하고, [math]\displaystyle{ \pi }[/math]의 cardinality는 'block'의 수, [math]\displaystyle{ B }[/math]의 cardinality는 'block' [math]\displaystyle{ B }[/math]의 size를 말한다.

위 식에서의 [math]\displaystyle{ f^{(\cdot)}(g(x)) \prod (g^{(\cdot)}(x))^\cdot }[/math]의 계수들(Faà di Bruno coefficients)

[math]\displaystyle{ \frac {n!}{m_1! m_2! \cdots 1!^{m_1} 2!^{m_2}\cdots} }[/math]

은 정수 [math]\displaystyle{ n }[/math]을

[math]\displaystyle{ n=\underbrace{1+\cdots+1}_{m_1} \,+\, \underbrace{2+\cdots+2}_{m_2} \,+\, \underbrace{3+\cdots+3}_{m_3}+\cdots }[/math]

으로 나누는 partition의 수이며, Bell polynomial에도 나타난다. 참고로, Bell polynomial은 통계학의 누적량(cumulant)과도 관계가 있다.

우리는 이 식을 이용하여 역함수의 [math]\displaystyle{ n }[/math]-계 도함수의 'linear recurrence'를 얻을 수 있다.

다변수 미적분으로의 확장[편집 | 원본 편집]

위의 [math]\displaystyle{ \pi, \; \Pi, \; B }[/math]의 정의를 그대로 가져와 쓰면, [math]\displaystyle{ y=u(x_1 , x_2 ,\cdots , x_n) }[/math]라고 할 때,

[math]\displaystyle{ \frac{\partial ^n}{\partial x_1 \cdots \partial x_n} f(y) = \sum_{\pi \in \Pi} f^{(|\pi|)}(y) \prod_{B\in\pi} \frac{\partial^{|B|}y}{\prod_{j\in B}\partial x_j} }[/math]

이다. 예를 들어 [math]\displaystyle{ n=3 }[/math]이라고 하면

[math]\displaystyle{ \begin{align}{\partial^3 \over \partial x_1\, \partial x_2\, \partial x_3}f(y) & = f'(y){\partial^3 y \over \partial x_1\, \partial x_2\, \partial x_3} \\ & + f''(y) \left( {\partial y \over \partial x_1} \cdot{\partial^2 y \over \partial x_2\, \partial x_3} +{\partial y \over \partial x_2} \cdot{\partial^2 y \over \partial x_1\, \partial x_3} + {\partial y \over \partial x_3} \cdot{\partial^2 y \over \partial x_1\, \partial x_2}\right) \\ & + f'''(y) {\partial y \over \partial x_1} \cdot{\partial y \over \partial x_2} \cdot{\partial y \over \partial x_3} \end{align} }[/math]

이다.

또한, 변수가 중복된 경우에는 다음과 같다:

[math]\displaystyle{ \partial_\tau f(y) = \sum_{\tau = \bigoplus m_i\tau_i} M f^{(|\tau|)} (y) \prod_{i} \partial_{\tau_i} y }[/math]

이때 [math]\displaystyle{ \tau= \{ \underbrace{1, \cdots , 1}_{k_1}, \cdots, \underbrace{n, \cdots , n}_{k_n}\} }[/math]는 multiset이며, [math]\displaystyle{ \partial_{\tau } = {\partial^{\sum k_i} \over \prod_i \partial x_i^{k_i}} }[/math]이고, [math]\displaystyle{ \bigoplus m_i\tau_i }[/math]는 multiset으로서의 합집합을 나타낸다. 이때 [math]\displaystyle{ m_i \tau_i = \underbrace{\tau_i \cup \cdots \cup \tau_i}_{m_i} }[/math]이고 [math]\displaystyle{ \bigoplus }[/math]은 [math]\displaystyle{ \tau_i }[/math]들이 모두 다름을 말한다. 또한 [math]\displaystyle{ |\tau| }[/math]는 [math]\displaystyle{ \tau = \bigoplus m_i\tau_i }[/math]로 쪼개었을 때의 partition의 수 [math]\displaystyle{ \sum m_i }[/math]를 말하며, multiplicity [math]\displaystyle{ M }[/math]는 [math]\displaystyle{ \tau }[/math]의 같은 수들을 모두 다르게 보았을 때와 같게 보았을 때의 비율을 말한다. 또한,

[math]\displaystyle{ M = \frac{\prod k_i !}{\prod \tau_i !!^{m_i} \prod m_i !} }[/math]

이 성립한다. 이때 !!는 주어진 multiset 안에서 같은 문자들을 다르게 보고 교환하여 같은 multiset을 만드는 방법의 수, 즉 [math]\displaystyle{ \tau!! = \prod k_i }[/math]를 말한다.

증명[편집 | 원본 편집]

우리는 다음의 두 가지 point에 집중할 것이다:

  • [math]\displaystyle{ \frac{\partial^n}{\partial x_1 \cdots \partial x_n} }[/math], 같은 변수들도 일단 index를 다르게 하고 미분했을 때의 식. 우변의 계수는 모두 1일 것이다.
  • 앞의 결과에서 동류항을 정리. 예를 들면, 만약 [math]\displaystyle{ n=3 }[/math]일 때 [math]\displaystyle{ x_2 = x_3 }[/math]이라면, 다음 두 항은 '중복도 2의' 한 항으로 합쳐지게 된다:
[math]\displaystyle{ \frac{\partial y}{\partial x_2}\frac{\partial^2 y}{\partial x_1\partial x_3} + \frac{\partial y}{\partial x_3}\frac{\partial^2 y}{\partial x_1\partial x_2} = 2\frac{\partial y}{\partial x_2}\frac{\partial^2 y}{\partial x_1\partial x_2}. }[/math]
이런 '중복된 항의 수'를 구하는 데 초점을 둔다.

먼저 다음의 [math]\displaystyle{ \{1, \cdots, n+1\} }[/math]의 partition을 만드는 inductive한 방법(algorithm)을 생각하자: [math]\displaystyle{ \pi_n }[/math]를 [math]\displaystyle{ \{1, \cdots, n\} }[/math]의 partition이라고 할 때,

  • [math]\displaystyle{ \pi_{n+1} = \pi_n \cup \{\{n+1\}\} }[/math],
  • [math]\displaystyle{ \pi_{n+1} = \pi_n \setminus \{B\} \cup \{B \cup \{n+1\}\} }[/math] for some [math]\displaystyle{ B\in \pi_n }[/math].

이 두 가지 방법으로 모든 [math]\displaystyle{ \{1, \cdots , n+1\} }[/math]의 partition을 만들 수 있음은 당연하다. 이제 다음을 귀납적으로 보이자:

[math]\displaystyle{ \frac{\partial ^n}{\partial x_1 \cdots \partial x_n} f(y) = \sum_{\pi} f^{(|\pi|)}(y) \prod_{B\in\pi} \frac{\partial^{|B|}y}{\prod_{j\in B}\partial x_j}. }[/math]

이때, [math]\displaystyle{ n\ge 0 }[/math]이다. 만약 [math]\displaystyle{ n=0 }[/math]이면, 다른 경우와 같이 [math]\displaystyle{ \pi }[/math]는 [math]\displaystyle{ \{1, \cdots, n\} }[/math]의 특정한 non-empty subset들을 모은 것인데 [math]\displaystyle{ \{1, \cdots , n \} = \emptyset }[/math] if [math]\displaystyle{ n=0 }[/math]에서 [math]\displaystyle{ \pi }[/math]는 아무 원소도 가질 수 없고, 즉 [math]\displaystyle{ \pi=\emptyset }[/math]으로 보는 것이 타당하다. 이에 따라 [math]\displaystyle{ n=0 }[/math]일 때에 [math]\displaystyle{ f(y) = f(y) }[/math]로 성립한다.

이제 다음 전개를 보자:

[math]\displaystyle{ \frac{\partial^{n+1}}{\partial x_1 \cdots \partial x_{n+1}} f(y) \\= \frac \partial {\partial x_{n+1}} \sum_{\pi} f^{(|\pi|)}(y) \prod_{B\in\pi} \frac{\partial^{|B|}y}{\prod_{j\in B}\partial x_j} \\= \sum_{\pi} \left[ f^{(|\pi|+1)}(y) \frac {\partial y} {\partial x_{n+1}} \cdot \prod_{B\in\pi} \frac{\partial^{|B|}y}{\prod_{j\in B}\partial x_j}+f^{(|\pi|)}(y) \frac {\partial y} {\partial x_{n+1}} \prod_{B\in\pi} \frac{\partial^{|B|}y}{\prod_{j\in B}\partial x_j}\right] \\= \sum_{\pi} \left[ f^{(|\pi|+1)}(y) \frac {\partial y} {\partial x_{n+1}} \cdot \prod_{B\in\pi} \frac{\partial^{|B|}y}{\prod_{j\in B}\partial x_j}+f^{(|\pi|)}(y) \sum_{B\in\pi} \left( \frac{\partial^{|B|+1}y}{\partial x_{n+1}\prod_{j\in B} \partial x_j} \cdot \prod_{B\ne C\in \pi}\frac{\partial^{|C|}y}{\prod_{j\in C} \partial x_j} \right)\right] }[/math]

여기서 각각의 partition [math]\displaystyle{ \pi }[/math]에 대해, 괄호 안의 두 항은 각각 inductively partition을 만드는 두 방법에 대응된다. 즉 위의 식은 [math]\displaystyle{ n+1 }[/math]에서의 모든 partition에 대한 sum이 되고, 즉 증명이 완료된다.

이제 중복된 경우의 중복도를 생각해보자. 일단 중복된 변수가 있을 때의 식이

[math]\displaystyle{ \partial_\tau f(y) = \sum_{\tau = \bigoplus m_i\tau_i} M f^{(|\tau|)} (y) \prod_{i} \partial_{\tau_i} y }[/math]

의 형태가 됨은 자명하다. 이제 [math]\displaystyle{ M }[/math]에 관한 식

[math]\displaystyle{ M = \frac{\prod k_i !}{\prod \tau_i !!^{m_i} \prod m_i !} }[/math]

만 증명하면 된다.

1부터 [math]\displaystyle{ n }[/math]까지의 수가 써진 타일이 있다고 생각해보자. [math]\displaystyle{ i }[/math] 타일은 [math]\displaystyle{ k_i }[/math] 개씩 있고, 즉 총 [math]\displaystyle{ \sum k_i }[/math] 개의 타일이 있다. 이를 모은 집합을 [math]\displaystyle{ \tau }[/math]라 하고, 이의 분할 [math]\displaystyle{ \tau = \bigoplus m_i \tau_i }[/math]를 상정하자. 이제 이 분할을 중복하여 만들 수 있는 수에 대해 생각해 보면, 먼저 [math]\displaystyle{ \tau }[/math]의 수들을 모두 permutation하면 [math]\displaystyle{ \prod k_i ! }[/math] 개의 중복도가 나오는데, 이를 각각의 block 안에서 같은 수들이 구별되지 않아서 생기는 중복도인 [math]\displaystyle{ \prod \tau_i!!^{m_i} }[/math]와 같은 block들이 구별되지 않아서 생기는 중복도인 [math]\displaystyle{ \prod m_i! }[/math]으로 나누어 주어야 한다. 이제 위의 M에 대한 식이 증명되었다.

참고문헌[편집 | 원본 편집]

각주