사용자 도구

사이트 도구


ps:여러가지_수학_정리

여러가지 수학 정리

거듭제곱수의 합 / 파울하버의 공식 (Faulhaber's Formula)

  • $\sum _{k=1}^{n}k^{p}= 1^p + 2^p + 3^p + \cdots + n^p$ 을 구하는 방법.
    • n이 p보다 많이 큰 경우만 생각해보자. n이 작으면 그냥 각각 항을 계산해서 푸는 O(nlogp)방법으로 처리될거 같다.
  • 대충 p=3 까지는 일반식이 잘 알려져있다.
    • $ 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2} = \frac{n^2 + n}{2} $
    • $ {\displaystyle 1^{2}+2^{2}+3^{2}+\cdots +n^{2}={\frac {n(n+1)(2n+1)}{6}}={\frac {2n^{3}+3n^{2}+n}{6}}} $
    • $ {\displaystyle 1^{3}+2^{3}+3^{3}+\cdots +n^{3}=\left[{\frac {n(n+1)}{2}}\right]^{2}={\frac {n^{4}+2n^{3}+n^{2}}{4}}} $
  • 그 이상의 p에 대해서도 일반 공식은 존재한다. 이것은 파울하버의 공식 (Faulhaber's formula) 으로 구할 수 있다. 위키 링크에 있는 식을 그대로 옮겨적으면 이렇게 된다
    • $ {\displaystyle \sum _{k=1}^{n}k^{p}={1 \over p+1}\sum _{j=0}^{p}{p+1 \choose j}B_{j}n^{p+1-j}} $
    • 하지만 이것을 계산하려면 베르누이 수를 계산해야 하고.. 이래저래 간단치가 않다
  • 코드포스에 올라온 adamant의 Counting sums of powers 글에 따르면, 이걸 풀기 위해서 베르누이 수를 이해하고 기억할 필요 없이, 그냥 생성함수를 이용해서 계산하면 된다고 한다. FFT를 잘 쓰고 어찌저찌 하면 O(plogp)에 계산 가능하다는것 같다는데 제대로 이해는 못했다.
    • 이 방법을 몰라도 아래의 방법으로 구할 수가 있기는 하지만, 응용 문제를 풀기 위해서는 이 방법을 이해할 필요가 있을것 같긴 하다..
  • 이 방법으로 구하는 것보다는 시간복잡도가 비효율적이지만, 좀 더 이해하기 쉬운 방법은 파울하버의 공식 위키 페이지 구석에 언급된 Pascal's identity 를 이용하는 것이다
    • $ {\displaystyle {\begin{aligned}(n+1)^{k+1}-1&=\sum _{m=1}^{n}\left((m+1)^{k+1}-m^{k+1}\right)\\&=\sum _{p=0}^{k}{\binom {k+1}{p}}(1^{p}+2^{p}+\dots +n^{p}).\end{aligned}}} $
    • 여기서 $ S(p) = 1^{p}+2^{p}+\dots +n^{p} $ 이라 하면,
    • $ S(k) = \frac{(n+1)^{k+1}-1-\sum _{p=0}^{k-1}{\binom {k+1}{p}}S(p)}{k+1} $ 로 쓸수 있다.
    • S(p)를 구하기 위해서는 DP를 이용해서 S(1),S(2), …, S(p)까지 차례로 구해 나가면 된다. 시간 복잡도는 O(p^2)
  • 관련 문제는 . 코드도 링크를 참고.

토론

댓글을 입력하세요:
Y M V H​ R
 
ps/여러가지_수학_정리.txt · 마지막으로 수정됨: 2021/05/31 02:08 저자 teferi