조합론에서의 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\)를 골라 \..

Baekjoon Online Judge에는 유용한 문제 난이도 기능 solved.ac 가 있다. 내가 기여한 문제들의 풀이를 간략하게 써보려고 한다. 아마 Gold, Platinum이 주류가 될 것 같고, Diamond 이상은 개별 풀이 포스팅을 할 것 같다. 형식은 문제 번호 (내가 준 티어) 순이다. Gold / Platinum / Diamond 수준의 구분은 신경을 쓰지만, Gold I ~ V의 세부적인 분류는 문제를 푼 직후에 즉흥적으로 내린 경우가 더 많다. 참고 정도만 하자! BOJ 1762. 평면그래프와 삼각형 (Gold II) 불러오는 중입니다... BOJ 2026. 소풍 (Gold III) Last update 19.12.16. 더보기 Maximal clique problem의 결정 문제..

스코어보드는 여기서 볼 수 있다. 5, 6위팀과 페널티 4분이라는 근소한 차이로 전체 4등 / 90팀으로 대회를 마무리했다. 예선 본선 모두 4등이다. 팀원은 imeimi, TAMREF, jhhope1. A Bus With No Drivers 팀처럼 컴공과가 한 명밖에 없는 팀이다 ㅋㅋ 팀 전략, 사전 연습, 팀노트 즈홒(jhhope1)은 풀이를 내는 능력이 뛰어난 데 비해 아직 구현이 익숙하지 않았고, 나는 코딩이 빠른 편이지만 풀이를 잘 못 만들었다. imeimi는 단점이 없다. 그냥 이멘이다 ㅋㅋㅋ 그래서 즈홒은 코딩을 잡지 않았고, 내가 Soulless Coding Machine 역할을 하면서 즈홒과 이멘이 주는 풀이를 구현하는 위주의 전략을 사용했다. 레드코더 2 ~ 2.5명 정도가 팀에서 낼 ..

고등학생 때 확률과 통계에서, 빠르면 중학생 때 수학올림피아드에서 접하게 되는 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종 스털링 수의 조합적 의미를 깊게 다루지는 않는다. - 서술을 엄밀하게..

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\)이다. 엌ㅋㅋㅋㅋㅋ 좀 더 정상적인 예시로, ..