라그랑주 역함수 정리(Lagrange Inversion Theorem)

라그랑주 역함수 정리(Lagrange Inversion Theorem)

---

📘 카탈란 수열 시리즈

• 🌱 카탈란(Catalan) 수열 - 카탈란 수열이란게 뭔데?
• 🔢 카탈란 수열의 일반항 구하기: 조합으로 구하기
• 🧮 카탈란 수열의 점화식 구하기
• 📐 카탈란수의 응용: n+2각형에서 삼각형으로 분할하기
• 🧪 카탈란 수열의 일반항을 생성함수로 구해보자 (1)
• 🧰 이항정리를 이항급수로 확장하기
• 🔍 카탈란 수열의 일반항을 생성함수로 구해보자 (2)
• 🔄 라그랑주 역함수 정리 (Lagrange Inversion Theorem)
• 🧠 번외: 카탈란 수를 선형대수로 풀 수 있다고?

---

 

1. 라그랑주 역함수 정리(Lagrange Inversion Theorem)

'라그랑주 역함수 정리' 용어자체가 생소하신 분들이 많으실거라 생각합니다.

혹여는 'Inversion'을 '역함수'라고 안보고 그냥 '반전'이라고 번역해서 '라그랑주 반전 정리'라고도 쓰이더군요.

그러나 '라그랑주'는 아주 다들 친숙하실테죠?

지구과학이나 물리에서 나오는 '라그랑주 점'도 이 분 이름이고 말이죠...

살면서 한번은 듣게되는 이름 중 하나가 아닐까 싶습니다.

아 물론 사람이구요, 위대한 인물이시죠.

[뭐 라플라스, 푸리에, 뉴턴, 오일러, 가우스 뭐 이런사람들 있잖아요... 심지어 저번 포스팅의 코시곱도 코시라는 사람이름이에요..]

 

뭐 사실 이 포스팅을 쓰는 순간조차도 저는 저 라그랑주 역함수 정리의 전체 형상을 모릅니다.

그저 그 정리의 결과로써 도출되는 내용과 그걸 어떻게 사용할 수 있는지 정도만 어렴풋하게 알고있는 수준입니다만,

제가 이걸 왜 포스팅에 쓰게 되었냐면,

이 정리를 이용하면 진짜 아주 쉽게 비선형 점화식을 가진 수열을 풀 수 있거든요.

라그랑주 역함수 정리는 결과적으로 '어떤 함수의 역함수를 멱급수로 전개했을 때, 각 항의 계수를 직접 계산할 수 있도록 해주는 정리'입니다.

 

 

2. 카탈란 수열의 생성함수에의 적용

바로 얼마전까지 진짜 온몸을 비틀어가며 간신히 생성함수로부터 이항급수를 통해 카탈란수의 일반항을 구했었는데요(누가 시키지도 않았었지만..)

이때, 생성함수가 자기자신을 포함한 '암시적'인 형태로 나왔었죠.(여기서 말하는 명시적vs암시적 함수라는 뜻은 f(x)=x처럼 깔끔하게 x로 정의되는 함수가 '명시적 함수', f(x) = xg(f(x))처럼 f(x)자체가 자신을 포함한 구조로 정의되는 함수가 '암시적 함수'라고 합니다)

물론 간단한 조작으로 이걸 다시 명시적 함수로 바꾼뒤 그 뒤를 진행했지만,

여기서 바로 라그랑주 역함수 정리를 이용하면

'암시적으로 정의된 함수의 생성함수를 "역함수로 본 다음" 그 멱급수 전개를 추출'하게 됩니다.

즉, $ C(x) $가 무엇인지 바로 찾는게 아니라,

우리가 구하려는 생성함수 C(x)가 어떤 함수 F의 역함수라고 보고 F(C(x)) = x 꼴로 놓는다면, 역함수 정리를 통해 C(x)를 추출할 수 있다는 것이죠.

다시말해,

$ xC(x)^2 - C(x) + 1 = 0 $에서 오히려

$ x = \frac{C(x) - 1}{C(x)^2} $ 꼴로 놓고

$ x = F(C(x)) $ 이런 식으로 본 다음에, 역함수를 취해

$ F^{-1}(x) = C(x) $로 만듧니다.

여기서 어떤 함수 $ F(x) $의 역함수 $ F^{-1}(x) = C(x) $를 멱급수로 전개했을 때, 그 항의 계수 $ C_n  $​을 직접 계산할 수 있게 해주는 정리가 바로 라그랑주 역함수 정리입니다.

(※ 생성함수의 멱급수 전개와 계수의 의미는 https://omnil.tistory.com/226, https://omnil.tistory.com/227에서 자세히 다뤘으니, 궁금하신 분은 그쪽을 참고해주세요!)

뭐, 결국 C(x)를 역함수로 보고, 이 역함수를 멱급수로 전개했을 때 특정 항의 계수를 알 수 있다는거죠.

그냥 원래 저희가 구하고 싶던거 구하는겁니다.

 

 

3. 형태는 어떻게 생겼는데?

라그랑주 역함수 정리는 다음과 같은 모양을 가졌습니다.

$ [x^n]f^{-1}(x) = \frac{1}{n}[t^{n-1}]\left(\frac{t}{f(t)}\right)^n \qquad (f(0) = 0, f'(0) \neq 0) $

여기서 대괄호 안에 있는 부분은 '거듭제곱이 n인 항을 찾겠다'는 뜻입니다.

(좀 더 자세하게는, $ [x^n]f(x) $란 표기는 멱급수 $f(x)=\sum a_kx^k $ 중 $a_n$을 의미합니다.)

말로 설명해보자면 "역함수의 $x^n$의 계수는 $\left(\frac{t}{f(t)}\right)^n$의 $t^{n-1}$의 계수를 n으로 나눈 값과 같다." 입니다.

그냥 정의자체가 이래요. 그리고 진짜로 풀면 답이 나오는게 신기하죠.

 

 

4. 라그랑주 역함수 정리의 다른 형태

그런데, 위와 같은 형식(standard form)에서는 계산을 하기가 조금 애매한 사항이 많습니다.

역함수가 분석적으로 존재하고 전개가 단순한 경우에는 저 형태도 굉장히 잘 작동하지만, 조합적 구조(재귀적 생성)를 가진 함수는

- $\frac{t}{f(t)}$ 자체가 복잡한 유리함수가 되기 쉽고
- 그것을 n제곱하면 차수가 급격히 상승하고
- 원하는 $ t^{n-1} $ 항이 존재하지 않거나, 매우 뒤에 등장하는 경우가 많기 때문에

저 형식을 사용하기 어려워지죠.

 

그러면 아예 답이 없냐고 하면, 식 자체를 재귀적 생성 형태(자기자신을 포함하는 형태)로 변형시키면 됩니다.(다르게 변형한 라그랑주 역함수 정리도 많습니다)

[[아래와 같은 변형을 Lagrange-Bürmann formula[라그랑주 뷔르만 공식]이라고 합니다.]]

$ y = x \cdot \phi (y) $

형태로 변형시키면, 이 변형에 해당하는 라그랑주 역함수 정리는

$ [x^n]y(x) = \frac{1}{n}[t^{n-1}]\phi(t)^n $

가 됩니다.

 

 

5. 역함수 정리의 변형 형태로 풀어보는 카탈란 수열

카탈란 수열을 예로 들어볼께요.

카탈란 수열의 생성함수는

$ C(x) = xC(x)^2 +1 $

이와 같고, 이를

$ y = x \cdot \phi(y) $ 형태로 바꾸면

$ C(x) - 1 = x \cdot C(x)^2 $ 과 같이 바꿀 수 있습니다. 여기서 바로 $ y = C(x)-1 $로 치환합니다.

그러면

$ y = x(y+1)^2 $처럼 정리가되고, 이는 바로 $ y = x \cdot \phi(y) $의 형태가 됩니다.

여기서 바로 역함수 정리를 적용하면

$ [x^n]y(x) = \frac{1}{n}[t^{n-1}]\phi(t)^n $

$ [x^n](C(x)-1) = \frac{1}{n}[t^{n-1}](t+1)^{2n} \quad (n \ge 1) $

이렇게 정리가 되겠죠?

여기서 $ C(x)-1 $의 의미는 생성함수에서 상수항을 제거한 조건(tail truncation)인데요, 말그대로 카탈란 수열의 재귀적 항들만 보겠다는 의미가 됩니다.

그래서 $ C_0 $를 따로 정의해줘야합니다. 식 자체도 n이 분모에 있기때문에 1부터 정의가 되니까 n=0인 상황은 따로 정의해줘야죠.

그리고 $ x^n $의 계수는 멱급수 정의에서 $ C_n $이었으므로, $ C_n $을 알고싶다면, $ x^n $의 계수를 찾으면 됩니다.

 

6. 구한 식으로 n = 2 계산해보기

그럼 간단하게 $ n=2 $인 상황을 봅시다. $ C_2 $값은 이미 2라는걸 저희는 알고있죠?

$ [x^2](C(x)-1) = \frac{1}{2}[t^1](t+1)^4 $

이렇게 식이 정리가 되겠고, 네제곱에서 지수가 1인 항의 계수는 이항정리에서 $ {_4} C_1 $이므로, 4가 되죠?

그러면

$ C_2 = \frac{1}{2} \cdot 4 = 2 $

오.. 바로 딱 나왔네요

 

7. 라그랑주 역함수 정리 식으로 일반항 구하기

그럼 이걸로 일반항도 유도할 수 있을까요? 뭔가 특정 수를 넣어주는 대신 주어진 그대로 n에대해 풀면 되지 않을까요?

이제 우항만 살펴봅시다

$ \frac{1}{n}[t^{n-1}](t+1)^{2n} $

여기서 2n승의 (1+x)에서 n-1승 항의 계수는

$ {_{2n}} C_{n-1} $이겠네요?

그럼 우항을 정리하면

$ \frac{1}{n}{_{2n}} C_{n-1} $

하나의 식이 나왔군요! 근데 어째 항상 저희가 보던 식의 모습이랑 조금 다릅니다?

그럼 식 변형을 한번 해볼까요?

일단 조합 공식은 다음과 같습니다.

$ {_n}C_r = \frac{n!}{r!(n-r)!} $

$ {_{2n}}C_{n-1} = \frac{(2n)!}{(n-1)!(2n-(n-1))!} = \frac{(2n)!}{(n-1)!(n+1))!} $

자, 여기서 $ \frac{1}{n} $까지 포함해서 식을 다시쓰면

$ \frac{(2n)!}{(n-1)!(n+1))! \cdot n} $

$ = \frac{(2n)!}{n!(n+1))!} \quad \because (n-1)! \cdot n = n! $

$ = \frac{(2n)!}{n!n! \cdot (n+1)} \quad \because (n+1)! = n! \cdot (n+1) $

$ = {_{2n}}C_n $

결국,

$ C_n = \frac{1}{n}{_{2n}} C_{n-1} = \frac{1}{n+1}{_{2n}}C_n = \frac{1}{n+1}\binom{2n}{n} $

으로 정리가 되면서, 일반항이 풀립니다.

그러나 여기서 $ n=0 $인 경우는 예외로 두었기 때문에 엄밀하게는 구간을 나눠서

$ C_n = \begin{cases} \frac{1}{n+1}\binom{2n}{n} \quad n \ge 1 \\ 1 \qquad n = 0 \end{cases} $

이렇게 보아야하지만, 식이 정리되면서 일반항이 n=0인 것까지 포함을 할 수 있게 되면서

$ C_n = \frac{1}{n+1}\binom{2n}{n} $이라는 일반항을 라그랑주 역함수 정리로 유도할 수 있었습니다.

 

8. 결론

사실 뭔가 빙빙 돌아왔지만, 개념만 알고있으면 공식을 통해 특정 항의 계수를 바로 알아내거나 심지어는 아주 빠르게 일반항을 뽑아낼 수 있는 강력한 공식이 바로 라그랑주 역함수 정리입니다.