카탈란 수(Catalan numbers) 공부하기

1. 카탈란 수 n = 0,1,2,3,...에 대하여 다음과 같은 수열 1,1,2,5,14,42,132,429,1430,4862,16796,58786,.... 0이상의 n에 대하여 카탈란 수 $C_{n}$는 다음과 같은 재귀적 관계를 만족한다. $$C_{0} = 1, C_{n} = \sum_{i = 1}^{n} C_{i-1}C_{n-i}$$ 이는 다음과 같이 정리할 수 있고 $$C_{0} = 1, C_{n} = \frac{2(2n-1)}{n+1}C_{n-1}$$ 점화식을 풀면 다음과 같이 일반항을 도출할 수 있다. $$C_{n} = \frac{1}{n+1} * \binom{2n}{n}$$  2. 응용 1) Dyck word n개의 X와 n개의 Y로 이루어진 문자열 중 처음부터 하나씩 셌을때 Y의 개수가 ..

• format_list_bulleted 조합론
• · 2025. 2. 25.
• textsms

여사건을 이용한 경우의 수1 - 특정 수를 포함하는 부분집합 구하는 법

20214번: Binary Seating (acmicpc.net)  두 강의실 0번과 1번에 n명의 학생이 1/2의 확률로 선택하여 입장할때,  1번 강의실에서 모든 시험이 끝날 때까지 걸리는 시간의 기댓값을 구하는 문제 걸리는 시간을 X라고 한다면...? 예를 들어 학생이 5명이고 각각 t = 1,4,5,2,3 만큼 시험을 보고 떠난다고 할때, 가능한 X = 1,2,3,4,5이다. 그러므로 E(X) = 1*P(X = 1) + 2*P(X = 2) + 3*P(X = 3) + 4*P(X = 4) + 5*P(X = 5) P(X = 1)은 어떻게 구할까? t = 1인 학생이 1번 강의실에 들어간 경우 (1) P(X = 2)는 어떻게 구할까? t = 2인 학생이 1번 강의실에 들어간 경우 (2) t = 1인 학생..

• format_list_bulleted 조합론
• · 2024. 8. 23.
• textsms

m면체 주사위 n개를 굴려서 나올 수 있는 경우의 수를 구하는 방법

3886번: Expected Allowance (acmicpc.net)  m면체 주사위 n개를 굴려서 나온 숫자의 합에 컷백 k를 뺀 값만큼 지폐를 받는다고 할 때, 받을 수 있는 지폐 수의 기댓값 이때, k 이하의 수가 나온다면 최소 1장은 받는다 예를 들어 6면체 주사위 2개를 굴리면? 가능한 숫자의 합은 1부터 12까지인데 모든 경우의 수는 36가지이고 숫자의 합이 2인 경우의 수는 (1,1)로 1가지 3인 경우의 수는 (1,2), (2,1)로 2가지 4인 경우의 수는 (1,3), (2,2), (3,1)로 3가지 k = 3이면 지폐를 1가지 받는 경우의 수는 숫자의 합이 2, 3, 4 3가지 경우에 가능하다. 따라서 지폐 1가지 받는 경우의 수는 1+2+3 = 6가지  그러면 먼저 m면체 주사위 n..

• format_list_bulleted 조합론
• · 2024. 8. 17.
• textsms

경기장 일렬 좌석에 앉을 때 사람을 지나치지 않고 전부 앉는 방법의 수

29313번: Стадион (acmicpc.net)  일렬로 된 N개의 좌석이 있는데 사람이 양쪽으로 들어가서 좌석에 앉을 수 있다고 할때,  어떤 사람이 이미 앉은 사람을 지나치지 않고 N명이 모두 앉는 방법의 수를 구하는 문제 예를 들어 3명이 앉는다고 해보면 이렇게 4가지가 있다    N개의 자리가 있을 때 _ _ _ _ _ _ ... 첫번째 자리에 먼저 앉으면 1 _ _ _ _ _ ... 나머지 N-1개의 자리는 고정적으로 2,3,4,5,6,... 으로 1가지 = N-1C0가지 결정된다 두번째 자리에 먼저 앉으면 _ 1 _ _ _ _ .... 1의 왼쪽 자리 _ 를 N-1명중 1명을 결정시키면 1의 오른쪽은 무조건 자동으로 결정되므로... N-1C1가지 왜냐하면 1의 왼쪽에 3을 앉히면 3 1 ..

• format_list_bulleted 조합론
• · 2024. 7. 26.
• textsms

다항식의 곱으로 구하는 복수순열1 - 주어진 개수의 알파벳들만으로 만들 수 있는 문자열의 개수

E - Alphabet Tiles (atcoder.jp) E - Alphabet TilesAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp  대문자 알파벳 A,B,C,..,Z의 개수가 주어질때, 이들로 만들 수 있는 길이 1부터 k까지 모든 문자열의 개수를 구하는 문제 길이가 s일때, 각각 A,B,C,...,Z 문자가 a1,a2,a3,...,a26개 있다고 한다면.. 이들을 일렬로 배열하는 복수순열의 개수와 같으므로,  $$\frac{(a1+a2+a3+...+a26)!}{a1!a2!...a26!} = \frac{s!}{a1!..

• format_list_bulleted 조합론
• · 2024. 6. 18.
• textsms

원형테이블에 앉은 n명의 사람 중 서로 인접하지 않은 k명의 사람을 뽑는 방법

1. 일렬로 앉은 경우 먼저 n명의 사람이 일렬로 앉아있다고 생각해보자. a1, a2, a3, ... , an이 일렬로 앉아있고, 여기서 서로 인접하지 않게 b1,b2,...,bk를 선택한다고 생각해보자.   b1,b2,...,bk가 서로 인접하지 않다는 것은 무슨 뜻일까? 먼저 선택한 k명 b1,b2,...,bk 사이의 선택받지 못한 x1,x2,x3,..,xk,xk+1에 대해, x1+x2+...+xk+1 = n-k이다. 왜냐하면 n명중 k명 b1,b2,..,bk를 선택하고 나서 남은 사람은 n-k명이니까    여기서 b1,b2,..,bk가 서로 인접하지 않을려면 그 사이에는 사람이 최소 1명이상 있어야한다. 즉, x2,x3,...,xk는 최소 1 이상이고 x1,xk+1은 0이상이다. 그러므로 구하고자 ..

• format_list_bulleted 조합론
• · 2024. 6. 7.
• textsms