레프네 약방

레프네 약방

  • 분류 전체보기 (136)
    • 알고리즘 문풀 (59)
      • AtCoder 연습 (6)
      • BOJ 연습 (24)
      • Codeforces Problemset 연습 (4)
      • Others (25)
    • 수학 이론 (38)
      • 정수론 (10)
      • 미적분학 (3)
      • 추상대수학 (11)
      • 선형대수학 (2)
      • 이산수학 (9)
      • 경시 테크닉 (3)
    • 수학 문풀 (20)
      • 경시 (내 풀이) (5)
      • 경시 (남의 풀이) (2)
      • 대입 스타일 (4)
      • 기타 (9)
    • CS 이론 (7)
      • 자료구조 (2)
      • 알고리즘 (5)
    • 통계학 (1)
      • 2019-1 일반통계학 (1)
    • 물리학 이론 (3)
      • 전자기학 (1)
      • 양자역학 (2)
    • 화학 이론 (3)
      • 물리화학 (3)
      • 계산화학 (0)
    • Misc. (0)
      • Computational Number Theory (0)
  • 홈
  • 태그
  • 미디어로그
  • 위치로그
  • 방명록
RSS 피드
로그인
로그아웃 글쓰기 관리

레프네 약방

컨텐츠 검색

태그

현대대수학 열역학 IMO 대수학 함수방정식 수학문풀 수학 Codeforces 화학 물리화학 물리 조합론 정수론 Russian Code Cup AOPS 그래프이론 더블카운팅 ps-hell Problem Solving 경시수학

최근글

댓글

공지사항

아카이브

수학 이론(38)

  • Cayley's theorem in Combinatorics

    2019.12.11
  • 스털링 수와 다항식 기저 변환

    2019.09.17
  • Pentagonal Number Theorem

    2019.09.16
  • lcm(1, 2, ... , n)의 크기

    2019.09.04
  • Ore's theorem & Palmer's algorithm

    2019.08.17
  • Bessel's Correction (Revised)

    2019.03.27
Cayley's theorem in Combinatorics

조합론에서의 Cayley's theorem은 완전그래프 \(K_{n}\)의 서로 다른 spanning tree가 \(n^{n-2}\)개라는 정리이다. 일반적으로는 그 쓰임보다도 아름다운 증명에 가치를 둔다. Functional graph를 알고 있다는 전제 하에 글을 작성했다. Reference : Miklos Bona - [A Walk through Combinatorics] cf : \([n] := \{1,\dots,n\}.\) Proof (By A. Joyal) \(K_{n}\)의 spanning tree의 개수를 \(t_{n}\)이라고 두고, \(n^{2}t_{n} = n^{n}\)임을 보인다. Definition. 정점 \(n \ge 1\)개의 트리 \(T\)에서 정점 \(a, b\)를 골라 \..

2019. 12. 11. 04:21
스털링 수와 다항식 기저 변환

고등학생 때 확률과 통계에서, 빠르면 중학생 때 수학올림피아드에서 접하게 되는 Stirling number \(S(n,k)\)에는 항상 제 2종 이라는 수식어가 붙는다. 교과서에서 보이지도 않는 제 1종 스털링 수가 뭐기에 더 쓸모가 많은 \(S(n,k)\)를 "제 2종"이라고 이름붙인 걸까? Notations & Preliminaries - \([n]\)은 양의 정수 집합 \(\{1,2,\cdots,n\}\)을 의미한다. - Falling factorial \(\displaystyle (x)_{k} := x(x-1)\cdots(x-k+1) = k! \cdot \begin{pmatrix}x\\k\end{pmatrix}\). - 제 2종 스털링 수의 조합적 의미를 깊게 다루지는 않는다. - 서술을 엄밀하게..

2019. 9. 17. 16:48
Pentagonal Number Theorem

Pentagonal Number Theorem은 분할수 \(p(n)\)을 \(\mathcal{O}(n^{1.5})\)에 구할 수 있게 해주는 멋진 점화식이다. BOJ 문제는 모르고, Project Euler 78번 으로 연습해볼 수 있다. koosaga님이 추천해주신 꿀이 뚝뚝 떨어지는 왕기초 연습문제도 Codeforces에 있다. 생성함수에 대한 기본적인 지식을 전제한다. 이탤릭체로 표기된 용어는 임의로 지어낸 용어로, 공식적인 용어와 다를 수 있다. 분할수와 그 생성함수 자연수 \(n \ge 0\)의 분할수 \(p(n)\)이란, 합이 \(n\)이 되는 단조 감소하는 자연수열(분할)의 개수를 말한다. 물론 빈 수열의 합은 0이기 때문에 \(p(0) = 1\)이다. 엌ㅋㅋㅋㅋㅋ 좀 더 정상적인 예시로, ..

2019. 9. 16. 07:00
lcm(1, 2, ... , n)의 크기

이 포스팅에서 다룰 것은 AKS primality test에 사용하는 lemma 중 하나로, \(n \ge 7\)에 대해 \(\ell_{n} := \mathrm{lcm}(1,2, ... , n) \ge 2^{n}\)이 성립한다는 것이다. 사실 Prime Number Theorem에 의해서 \(\ell_{n} \sim e^{n}\)이 성립하기 때문에, 충분히 큰 \(n\)에 대해서는 자명히 성립하는 부등식이다. 다만 PNT가 좀 overkill이기도 하고, 기왕 non-analytical한 증명이 있으니 이야기해보도록 하자. 증명은 다음의 글에서 가져왔다. https://math.stackexchange.com/questions/851328/textlcm1-2-3-ldots-n-geq-2n-for-n-ge..

2019. 9. 4. 11:50
Ore's theorem & Palmer's algorithm

Ore's theorem은 그래프에 해밀턴 회로가 존재할 조건과 관련된 정리이다. Statement를 바로 쓰면 다음과 같다. \(n \ge 3\)개의 정점으로 구성된 단순그래프 \(G\)에서, 모든 비인접(non-adjacent) 정점 \(x, y\)에 대해 \(\deg x + \deg y \ge n\)이 성립하면, \(G\)에는 해밀턴 회로가 존재한다. 여담으로 좀 더 강한 조건인 Dirac's theorem (모든 정점의 차수가 \(n/2\) 이상)도 있는데, 딱히 Ore's theorem 증명에 비해 쉬운지는 잘 모르겠다. 스포일러 방지선 Step 1. \(G\) is connected 두 정점 \(x\), \(y\)가 이미 인접(adjacent)한 경우에는 상관이 없다. \(x\)와 \(y\)가..

2019. 8. 17. 02:07
Bessel's Correction (Revised)

2019.03.27 Revised. 원본: 2017.09.10 표본분산 \(S^2\)는 \(\frac{1}{n-1}\sum_{k=1}^{n}(\bar{X}-X_k)^2\)로 정의된다. 그런데 분모의 꺼림칙한 \(n-1\)은 일반적으로 '자유도'(degree of freedom)라는 개념으로 설명하는데, 대략 "평균 \(\bar{X}\)는 이미 정해져 있으니까(?) 자유롭게 결정할 수 있는 변수의 개수는 \(n-1\)개 밖에 없어!" 같은 뉘앙스로 설명한다. 근데 이 설명이 도저히 납득이 가지 않는다. 사실 자유도를 이용한 설명은 다분히 작위적인 느낌이 든다. '자유도'라는 개념을 "자유롭게 결정할 수 있는 변수의 개수"와 같은 의미로 사용하는 경우를 본 적이 없다. 애초에 통계학적으로 의미가 있는지조차도..

2019. 3. 27. 14:25
1 2 3 4 ··· 7
Tistory Blog (here) Naver Blog
© 2018 T-Story. All right reserved.