여러가지 수학 정리

따로 카테고리를 만들정도로 중요하거나 웰노운도 아니면서 다른 정리들과 연관되어있지도 않은 정리들을 그냥 모아놓은 페이지.. (그뭔씹?)

거듭제곱수의 합 / 파울하버의 공식 (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}} $
- 이렇게도 쓸수 있다고 한다
  - $ {\displaystyle \sum _{k=1}^{n}k^{p}={\frac {1}{p+1}}\left(B_{p+1}(n+1)-(-1)^{p+1}B_{p+1}\right)={\frac {1}{p+1}}\left(B_{p+1}(n+1)-B_{p+1}(1)\right).} $
- 하지만 이것을 계산하려면 베르누이 수를 계산해야 하고.. 이래저래 간단치가 않다
  - n번째 베르누이 수를 계산하는 알고리즘의 시간복잡도는 O(n^2log^2n)이라고 한다. (위키백과)
  - 정 안되면.. p의 최대 입력범위까지의 베르누이 수의 값들을 코드에 다 때려박아놓고 짜는 방법도 가능하긴 하다..오프라인 전처리!!
코드포스에 올라온 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)
- 관련 코드는 합 참고.
다른 접근 방법은, $\sum _{k=1}^{n}k^{p}= 1^p + 2^p + 3^p + \cdots + n^p$ 은 결국 n에 대한 (p+1)차식으로 표현된다는 것을 이용하는 방법이다.
- $f(x) = \sum _{k=1}^{x}k^{p}$ 라고 하면, f(1), f(2), …,f(p+2)의 값을 다 구한 다음에, 이걸 갖고 라그랑주 보간법을 사용해서 f(n)을 구해버릴수 있다.
- f(1), f(2), …,f(p+2)를 계산하는 것은 O(plogp)이다. 그리고 라그랑주 보간법을 적용하는 것은 O(p). 총 O(plogp)에 구할수 있다!!
- 라그랑주 보간법을 굳이 짜기 싫다면, 벌캠프-매시 알고리즘을 사용할수도 있다. k차 다항식은 항상 크기 k의 선형점화식으로 바꿀수 있기 때문이다. 하지만 이 방법은 점화식을 찾는데 O(p^2)이 걸리고, n번째 값을 찾는데에는 O(p^2logn)이 걸려서 효율적이지는 못하다.
결국, 쓰기 가장 편하면서 효율적인것은 라그랑주 보간법이다. 이 방법을 사용하자
관련 문제
- 합: p≤50, O(p^2) DP로도 순식간에 풀린다
- 거듭제곱의 합 1: p≤1000, O(p^2) DP로도 270ms 정도에 풀리긴 한다
- 27293: p≤100000, O(plogp)의 라그랑주 보간법을 써야만 8000ms대에 통과가능

프로베니우스의 동전 문제

coin problem, 프로베니우스의 동전 문제 - 레프네 약방
대충 핵심은
- P원짜리 동전과 Q원짜리 동전을 무한개 갖고 있고, P와 Q가 서로소라면, 두 동전을 이용해서 얼마를 초과하는 금액은 모두 만들수 있다.
- 그 '얼마', 즉 만들수 없는 최대 금액을 Frobenius number 라고 부르는데, 이 값은 PQ-P-Q 이다.
  - P,Q가 서로소가 아니면, 즉 gcd(P,Q)=g>1 이라면, g의 배수만 만들수 있다. (베주 항등식 참고)
  - 이때도 비슷한 논리를 적용하면, g*(P/g-1)*(Q/g-1) 이상의 g의 배수는 모두 만들수 있다.
원래 문제는 동전 n개에 대한 문제인데, n이 3 이상일때는 closed form으로 답이 안나온다.
관련 문제로는 쿨한 물건 구매나 설탕 배달가 있긴 한데, 사실 이걸 몰라도 충분히 효율적으로 풀수 있다..

Landau's Theorem

https://en.wikipedia.org/wiki/Tournament_(graph_theory)#Score_sequences_and_score_sets
n팀이 참가한 리그전의 결과가 각 팀의 승리수로 주어졌을때, 그게 valid한 결과인지 아닌지를 판별할수 있는 공식.
- 좀더 포멀하게는 토너먼트 그래프에서 각 노드의 outdegree의 시퀀스라고 표현할수도 있다.
모든 팀의 점수(=승리수)의 합이 C(n,2) 가 되어야 하는 것은 자명 (경기수 = 승리수여야 하니까)
여기에 추가로, 모든 i에 대해서 최하위 i팀의 점수의 합이 C(i,2) 이상이라면 valid한 결과이다.
이 정리를 이용하면 score sequence 의 validity를 O(n) 에 구할수 있다.
관련문제는 13560

Hertzsprung's problem

1~N까지의 숫자로 만들어지는 퍼뮤테이션 중에서 인접한 두 수의 차가 모두 2이상인 퍼뮤테이션의 갯수
다음 점화식으로 계산 가능 (https://oeis.org/A002464)
- If n = 0 or 1 then a(n) = 1; if n = 2 or 3 then a(n) = 0; otherwise a(n) = (n+1)*a(n-1) - (n-2)*a(n-2) - (n-5)*a(n-3) + (n-3)*a(n-4).
Hertzsprung's problem 에 좀더 자세히 설명.

Langford pairing

듀들리 랭퍼드가 1958년에 발표한 문제.
- 참고: Langford pairing, https://susam.net/blog/langford-pairing.html
1~N까지의 숫자들을 두번씩 사용해서 만든 시퀀스 중에서, 두개의 1 사이에는 숫자가 1개 있고, 두개의 2 사이에는 숫자가 2개 있고,.. 두개의 N사이에는 숫자가 N개 있는 시퀀스.
- 예를들면
  - N=3일때: 2,3,1,2,1,3
  - N=4일때: 4,1,3,1,2,4,3,2
관련 정리
- 수열의 존재 여부: n=4m 또는 n=4m+3 인 경우, 랭퍼드 수열이 존재한다 (필요충분조건)
  - 증명은, 홀수 인덱스에 들어갈 숫자의 갯수와, 짝수 인덱스에 들어갈 숫자의 갯수를 나눠서 세어보는 방식으로 필요조건을 증명하고. 충분조건은 아래 방식대로 구성적으로 해를 제시해서 증명한다
- 한개의 수열을 찾는 구성적인 방법
  - https://susam.net/blog/langford-pairing.html 참고
  - 코드로 옮기면
    - def langford_sequence(n): if n % 4 in (1, 2): raise ValueError('No Langford sequence exists.') x = (n + 3) // 4 a, b, c, d = 2 * x - 1, 4 * x - 2, 4 * x - 1, 4 * x p, q = range(1, a, 2), range(2, a, 2) r, s = range(a + 2, b, 2), range(a + 1, b, 2) l = [*reversed(s), *reversed(p), b, *p, c, *s] if n % 4 == 0: return l + [d, *reversed(r), *reversed(q), b, a, *q, c, *r, a, d] else: return l + [a, *reversed(r), *reversed(q), b, a, *q, c, *r]
- 해의 갯수
  - 갯수를 구하는 공식은 아직 없다. 현재까지 밝혀진 값들은 https://oeis.org/A014552에 있다.
Skolem sequence 는 거의 비슷한데 0부터 N-1까지의 숫자를 사용해서 만든 수열이다.
- 역시 N-1 이 4m 또는 4m+3일때만 존재한다.
- 한개의 해를 구하기 위해서는, N-1의 랭퍼드 수열을 만든 다음 0 0 을 끝에 붙여주기만 하면 된다.
관련 문제
- blobfacepalm

목차

여러가지 수학 정리

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

프로베니우스의 동전 문제

Landau's Theorem

Hertzsprung's problem

Langford pairing