테페리넷

사용자 도구

사이트 도구

현재 위치: 테페리넷 » Problem Solving » 여러가지 수학 정리
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}} $
    • 이렇게도 쓸수 있다고 한다
      • $ {\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년에 발표한 문제.
  • 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]
    • 해의 갯수
  • Skolem sequence 는 거의 비슷한데 0부터 N-1까지의 숫자를 사용해서 만든 수열이다.
    • 역시 N-1 이 4m 또는 4m+3일때만 존재한다.
    • 한개의 해를 구하기 위해서는, N-1의 랭퍼드 수열을 만든 다음 0 0 을 끝에 붙여주기만 하면 된다.
  • 관련 문제

토론

댓글을 입력하세요:
S B X B H
 
ps/여러가지_수학_정리.txt · 마지막으로 수정됨: 2023/12/13 13:37 저자 teferi