경우의 수/공식

1. 개요

2. 계산 방식에 따른 분류

• 순열
• 서로 다른 사람 [math(n)]명을 일렬로 배열: [math(n!)]
• 서로 다른 사람 [math(n)]명을 원형으로 배열[2]: [math((n-1)!)]
• 일렬로 나열된 서로 같은 상자 [math(n)]개에 서로 다른 공 [math(r)]개를 이웃하지 않도록 넣기: [math({}_{n-r+1}{\rm P}_r)]
• 정의역의 원소가 [math(r)]개이고 공역의 원소가 [math(n)]개인 일대일함수의 개수: [math({}_n{\rm P}_r)]
• 정의역의 원소가 [math(r)]개이고 공역의 원소가 [math(n)]개인 일대일대응의 개수: [math(n!=r!)]
• 같은 것이 있는 순열
• [math((a+b)^n)]의 전개식에서 [math(a^rb^{n-r})]의 계수: [math(\dfrac{n!}{r!(n-r)!}={}_n{\rm C}_r)]
• 알파벳을 배열할 때 특정 문자들의 순서 또는 특정 문자의 위치가 미리 정해질 때의 경우의 수
• 조합
• 서로 다른 사람 [math(n)]명 중 [math(r)]명을 선택: [math({}_n{\rm C}_r)]
• [math((a+b)^n)]의 전개식에서 [math(a^rb^{n-r})]의 계수: [math(\dfrac{n!}{r!(n-r)!}={}_n{\rm C}_r)]
• 마름모가 가로로 [math(m)]개, 세로로 [math(n)]개 배열된 경우 좌하단 점에서 우상단 점까지 이동하는 최단거리의 경우의 수: [math(\dfrac{(m+n)!}{m!n!}={}_{m+n}{\rm C}_m={}_{m+n}{\rm C}_n)]
• 일렬로 나열된 서로 같은 상자 [math(n)]개에 서로 같은 공 [math(r)]개를 이웃하지 않도록 넣기: [math({}_{n-r+1}{\rm C}_r)]
• 정의역의 원소가 [math(r)]개이고 공역의 원소가 [math(n)]개인 강단조증가함수/강단조감소함수의 개수: [math({}_n{\rm C}_r)]
• 자연수 [math(x_1,\,x_2,\,\cdots,\,r,\,n)]에 대하여 [math(0<x_1<x_2<\cdots<x_r\leq n)]을 만족시키는 순서쌍 [math((x_1,\,x_2,\,\cdots,\,x_r))]의 개수: [math({}_n{\rm C}_r)]
• 중복순열
• 서로 다른 상자 [math(n)]개에 서로 다른 공 [math(r)]개를 넣기: [math({}_n\Pi_r=n^r)]
• 정의역의 원소가 [math(n)]개이고 공역의 원소가 [math(r)]개인 함수의 개수: [math(r^n)]
• 중복조합
• 서로 다른 상자 [math(n)]개에 서로 같은 공 [math(r)]개를 넣기: [math({}_n{\rm H}_r)]
• [math(x_1+x_2+\cdots+x_n=r)]의 음이 아닌 정수해의 개수: [math({}_n{\rm H}_r)]
• 일렬로 나열된 서로 같은 상자 [math(n)]개에 서로 같은 공 [math(r)]개를 이웃하지 않도록 넣기: [math({}_{r+1}{\rm H}_{n-2r+1})]
• 정의역의 원소가 [math(r)]개이고 공역의 원소가 [math(n)]개인 단조증가함수/단조감소함수의 개수: [math({}_n{\rm H}_r)]
• 자연수 [math(x_1,\,x_2,\,\cdots,\,r,\,n)]에 대하여 [math(0\leq x_1\leq x_2\leq\cdots\leq x_r\leq n)]을 만족시키는 순서쌍 [math((x_1,\,x_2,\,\cdots,\,x_r))]의 개수: [math({}_n{\rm H}_r)]
• 자연수의 분할
• 서로 같은 상자 [math(n)]개에 서로 같은 공 [math(k)]개를 넣기: [math(P(n,\,k))]
• 집합의 분할
• 서로 같은 상자 [math(n)]개에 서로 다른 공 [math(k)]개를 넣기(빈 상자가 없을 때): [math(S(n,\,k))]

3. 모델에 따른 분류

3.1. 함수의 개수

• 전체 함수: [math({}_n\Pi_r=n^r)]

• 일대일함수: [math({}_n{\rm P}_r)]

• 일대일대응: [math(n!=r!)]

• 강단조증가함수/강단조감소함수: [math({}_n{\rm C}_r)]

• 단조증가함수/단조감소함수: [math({}_n{\rm H}_r)]

3.1.1. 수열의 개수

3.2. 부등호

• 자연수 [math(x_1,\,x_2,\,\cdots,\,r,\,n)]에 대하여 [math(0<x_1<x_2<\cdots<x_r\leq n)]을 만족시키는 순서쌍 [math((x_1,\,x_2,\,\cdots,\,x_r))]의 개수: [math({}_n{\rm C}_r)]
• 자연수 [math(x_1,\,x_2,\,\cdots,\,r,\,n)]에 대하여 [math(0\leq x_1\leq x_2\leq\cdots\leq x_r\leq n)]을 만족시키는 순서쌍 [math((x_1,\,x_2,\,\cdots,\,x_r))]의 개수: [math({}_n{\rm H}_r)]

• 자연수 [math(x_1,\,x_2,\,\cdots,\,r,\,n)]에 대하여 [math(n\geq x_1>x_2>\cdots>x_r>0)]을 만족시키는 순서쌍 [math((x_1,\,x_2,\,\cdots,\,x_r))]의 개수: [math({}_n{\rm C}_r)]
• 자연수 [math(x_1,\,x_2,\,\cdots,\,r,\,n)]에 대하여 [math(n\geq x_1\geq x_2\geq\cdots\geq x_r\geq0)]을 만족시키는 순서쌍 [math((x_1,\,x_2,\,\cdots,\,x_r))]의 개수: [math({}_n{\rm H}_r)]

3.3. 상자에 공 넣기

• 같은 상자에 같은 공 넣기(자연수의 분할)

• 같은 상자에 다른 공 넣기(집합의 분할)

• 다른 상자에 같은 공 넣기(중복조합)

• 다른 상자에 다른 공 넣기(중복순열)

3.4. 이웃하지 않게 배열하기

• 같은 상자에 같은 공 넣기: [math({}_{n-r+1}{\rm C}_r={}_{r+1}{\rm H}_{n-2r+1})]
• 같은 상자에 다른 공 넣기: [math({}_{n-r+1}{\rm P}_r={}_{n-r+1}{\rm C}_r\times r!={}_{r+1}{\rm H}_{n-2r+1}\times r!)]
• 다른 상자에 같은 공 넣기: [math({}_{n-r+1}{\rm C}_r\times n!={}_{r+1}{\rm H}_{n-2r+1}\times n!)]
• 다른 상자에 다른 공 넣기: [math({}_{n-r+1}{\rm P}_r\times n!={}_{n-r+1}{\rm C}_r\times n!\times r!={}_{r+1}{\rm H}_{n-2r+1}\times n!\times r!)]

증명 [펼치기·접기]

----
이는 두 가지 방법으로 증명할 수 있다. 이때, 같은 상자에 같은 공 넣기의 경우의 수를 먼저 유도한 뒤, 상자와 공이 구별되는 경우 어떻게 경우의 수가 달라지는지를 검토하자.

[1] 공을 넣지 않는 상자를 먼저 배열하기


위 그림과 같이 전체 상자 [math(n)]개 중 공을 넣는 상자 [math(r)]개를 미리 빼서 하나씩 공을 넣어 놓자. 이때 남게 되는, 공을 넣지 않는 상자 [math((n-r))]개를 일렬로 배열한 뒤, 이 상자들 사이와 양 끝에 공을 넣는 상자들을 한 자리에 하나씩만 배치하면, 공을 넣는 상자들끼리 이웃하지 않는다. 한 자리에 공을 넣는 상자들을 두 개 이상 배치한다는 것은 곧 그들끼리 이웃한다는 뜻이기 때문이다. 공을 넣는 상자들을 배치할 수 있는 자리는 위 그림에서 V자로 표시되어 있으며, 개수는 상자보다 하나가 많은 [math((n-r+1))]개이다.

상자를 한 자리에 하나씩만 배치하므로 경우의 수는 중복을 허용하지 않는 조합으로 계산해야 한다. 즉, 경우의 수는 [math({}_{n-r+1}{\rm C}_r)]이다.

[2] 공을 넣는 상자를 먼저 배열하기


위 그림과 같이 전체 상자 [math(n)]개 중 공을 넣지 않는 상자(이하 적색 상자) [math((n-r))]개를 미리 빼 놓자. 이때 남게 되는 공을 넣는 상자(이하 녹색 상자) [math(r)]개를 일렬로 배열한 뒤 상자들 사이에 적색 상자를 하나씩 끼워 넣어 녹색 상자끼리 이웃하는 일을 방지하자. 여기에서 끼워 넣는 적색 상자의 개수는, 녹색 상자의 개수보다 하나가 적은 [math((r-1))]개이다.


그러면 적색 상자는 [math((n-r))]개에서 [math((r-1))]개를 뺀 [math((n-2r+1))]개가 남게 되며, 이제 이 상자들을 앞서 적색 상자와 녹색 상자를 교대로 배열한 곳에 추가로 배열해야 한다. 남은 적색 상자가 들어갈 수 있는 서로 다른 자리는 위 그림과 같이 양 끝과 각 적색 상자 바로 옆이므로 총 [math((r+1))]개이다. 적색 상자는 공을 넣지 않는 상자이므로, 적색 상자끼리는 어떻게 배열하든지 경우가 구별되지 않는다. 따라서 '적색 상자의 바로 옆'만 고려해야 하지, '적색 상자의 왼쪽' 또는 '적색 상자의 오른쪽'을 고려해서는 안 된다.

한편, 위 증명 방법과는 달리 적색 상자를 같은 자리에 두 개 이상 추가해도 된다. 공을 넣지 않는 상자끼리는 이웃해도 상관없기 때문이다. 따라서 경우의 수는 중복을 허용하는 중복조합으로 계산해야 한다. 즉, 경우의 수는 [math({}_{r+1}{\rm H}_{n-2r+1})]이다.

어떤 방식으로 공식을 유도하든 다음과 같이 값은 같다.

[math(\begin{aligned}{}_{r+1}{\rm H}_{n-2r+1}&={}_{(r+1)+(n-2r+1)-1}{\rm C}_{n-2r+1}\\&={}_{n-r+1}{\rm C}_{n-2r+1}\\&={}_{n-r+1}{\rm C}_{(n-r+1)-(n-2r+1)}\\&={}_{n-r+1}{\rm C}_r\end{aligned})]

한편, [math(r=0)]이면 상자에 공을 아예 넣지 않는 경우 단 하나만 존재하므로 경우의 수는 [math(1)]이다. 이 경우 공이 구별되는지의 여부는 중요하지 않게 된다. 대수적으로도, 위 공식에 [math(r=0)]을 대입하면 다음과 같이 모두 [math(1)]이 나온다.

[math(\begin{aligned}{}_{n-r+1}{\rm C}_r&={}_{n+1}{\rm C}_0=1\\\\{}_{n-r+1}{\rm C}_r\times r!&={}_{n+1}{\rm C}_0\times0!=1\times1\\&={}_{n-r+1}{\rm P}_r={}_{n+1}{\rm P}_0\\&=1\end{aligned})]

그런데 이는 이웃하지 않게 배열하는 경우의 수가 존재하는, 곧 [math(1)] 이상일 때에만 해당한다. 어떨 때 경우의 수가 [math(0)]이 되는지 알아보자.


위 그림과 같이 총 상자의 개수가 [math(1)]개, [math(3)]개, [math(5)]개, [math(7)]개일 때, 녹색 상자의 개수의 최댓값은 각각 [math(1)]개, [math(2)]개, [math(3)]개, [math(4)]개가 된다. 총 상자의 개수가 [math(2)]개, [math(4)]개, [math(6)]개, [math(8)]개인 경우는 [math(1)]개, [math(3)]개, [math(5)]개, [math(7)]인 경우에서 왼쪽 끝 또는 오른쪽 끝에 녹색 상자를 배치하면 이웃하지 않게 넣을 수 있는 공의 개수의 최댓값이 역시 각각 [math(1)]개, [math(2)]개, [math(3)]개, [math(4)]개가 됨을 확인할 수 있다. 이를 표로 나타내면 다음과 같다.

총 상자 개수	넣을 수 있는 공 개수
[math(1,\,2)]	[math(1)]
[math(3,\,4)]	[math(2)]
[math(5,\,6)]	[math(3)]
[math(7,\,8)]	[math(4)]
[math(\vdots)]	[math(\vdots)]
[math(n)]	[math(r=\left\lfloor\dfrac{n+1}2\right\rfloor)]
[math(\therefore r\leq\dfrac{n+1}2)]

따라서 [math(n-2r+1\geq0)]이어야 이웃하지 않게 배열하는 경우의 수가 존재한다. 만약 [math(n-2r+1<0)]이면 녹색 상자의 개수가 너무 많아서 어떻게 배열하더라도 녹색 상자끼리 이웃하는 곳이 생겨버린다. 곧, 이웃하지 않게 배열하는 경우의 수가 0이다. 그러므로 공식을 더욱 정확히 쓰면 다음과 같다.

[math(\begin{cases}{}_{n-r+1}{\rm C}_r\;\textsf{or}\;{}_{r+1}{\rm H}_{n-2r+1}&\qquad\quad(n-2r+1\geq0)\\0&\qquad\quad(n-2r+1<0)\end{cases})]

공식의 [math({}_{n-r+1}{\rm C}_r)]에서 [math(n-r+1)]은 [math(1)] 이상이어야 하는데, [math(r\geq 0)]이므로 [math(n-2r+1<n-r+1<0)]이 성립하고, 이 경우 이 공식을 사용할 수조차 없는 것이다. 요컨대 이 공식은 경우의 수가 하나라도 존재함을 전제하고 유도한 것이므로, 이에 해당하지 않는 경우는 그 자체로 논외로서 경우의 수를 [math(0)]으로 구한다고 생각할 수 있다.

이제 상자와 공이 구별될 때 경우의 수가 어떻게 변하는지 알아보자. 상자가 모두 구별되면 공을 같은 위치에 배열하더라도 상자가 어디에 놓이느냐에 따라 다른 경우가 된다. 상자 [math(n)]개를 일렬로 늘어놓는 경우의 수는 [math(n!)]이므로 위 공식에 [math(n!)]을 곱하면 된다. 또한 공이 구별되면 공이 들어가는 상자의 위치가 같더라도 들어가는 공이 무엇이느냐에 따라 다른 경우가 된다. 각 상자에 들어가는 공을 결정하는 경우의 수는 [math(r!)]이므로 위 공식에 [math(r!)]을 곱하면 된다. 따라서 상자와 공이 모두 구별되면 [math(n!)]과 [math(r!)]을 모두 곱하면 된다. 이 말을 그림으로 쉽게 이해해 보자.


위 그림은 같은 상자 [math(7)]개와 같은 공 [math(3)]개에 대하여 한 상자에 공을 하나씩 넣되 공을 넣은 상자끼리 이웃하지 않게 배열하는 경우 [math(10)]가지를 모두 나타낸 것이다. 공식은 [math({}_{7-3+1}{\rm C}_3=10)]으로 성립하며, 흑색 사각형은 공을 넣은 상자, 백색 사각형은 공을 넣지 않은 상자를 의미한다.

여기에서 상자 [math(7)]개가 모두 구별된다고 하자. 상자가 구별된다는 의미에서 각 상자에 [math(\rm A)]부터 [math(\rm G)]까지의 이름을 붙이면 다음과 같은 일이 발생한다.


즉, 앞서 도출된 [math(10)]가지의 경우들에 대하여 경우 하나하나마다 상자를 배열하는 방식이 [math(7!)]가지씩 존재하는 것이다. 위 그림의 왼쪽 위의 경우를 보면, 공은 언제나 왼쪽에서 첫 번째, 세 번째, 다섯 번째 상자에 들어가지만 그 상자들은 각각 [math(\rm A)], [math(\rm C)], [math(\rm E)]가 될 수도, [math(\rm G)], [math(\rm E)], [math(\rm C)]가 될 수도 있는 것이다. 상자가 구별되지 않던 상황에서는 일어나지 않던 일이다. 이와 같이 각 경우마다 상자를 배열하는 방식이 [math(7!)]가지씩 존재하므로 경우의 수는 [math(10\times 7!)]이 된다.

이번에는 공 [math(3)]개가 모두 구별된다고 하자. 공이 구별된다는 의미에서 각 상자에 [math(\rm a)]부터 [math(\rm c)]까지의 이름을 붙이면 다음과 같은 일이 발생한다.


즉, 앞서 도출된 [math(10)]가지의 경우들에 대하여 경우 하나하나마다 공을 넣는 방식이 [math(3!)]가지씩 존재하는 것이다. 위 그림의 왼쪽 위의 경우를 보면, 공은 언제나 왼쪽에서 첫 번째, 세 번째, 다섯 번째 상자에 들어가지만 그 공들은 각각 [math(\rm a)], [math(\rm b)], [math(\rm c)]가 될 수도, [math(\rm c)], [math(\rm b)], [math(\rm a)]가 될 수도 있는 것이다. 공이 구별되지 않던 상황에서는 일어나지 않던 일이다. 이와 같이 각 경우마다 공을 넣는 방식이 [math(3!)]가지씩 존재하므로 경우의 수는 [math(10\times 3!)]이 된다.

상자와 공이 모두 구별되는 경우는 위 두 현상이 동시에 일어나는 것이므로 경우의 수는 [math(10\times7!\times3!)]이 된다.

이를 일반화하여 정리하면 다음과 같다.


상자와 공이 구별되든 구별되지 않든, 공을 넣는 상자들이 각각 왼쪽에서 몇 번째에 위치하는지(이하 상자들의 '상대적 위치')에 따라 경우가 갈리는 것은 공통이므로 이를 경우의 수를 구할 때 일차적으로 고려하여야 한다. 이는 앞서 밝혔듯이 [math({}_{n-r+1}{\rm C}_r)]이다. 여기에서 상자가 구별되면 상자의 상대적 위치는 같더라도 어느 자리에 어느 상자가 위치하는지에 따라 경우가 갈리며, 각 상대적 위치마다 상자를 배열하는 가짓수는 [math(n!)]이므로 이를 곱해 주어야 한다. 공의 경우에도 마찬가지의 이유로 공이 구별될 때는 [math(r!)]을 곱해 주어야 한다. 결국 상대적 위치, 상자의 배열(상자가 구별될 때만), 공의 배열(공이 구별될 때만)에서 각각 하나를 선택하여 조합하면 최종적인 경우 하나가 만들어진다고 볼 수 있다. 그렇기 때문에 곱의 법칙에 따라 각 수를 곱하여 경우의 수를 계산하는 것이다.

3.4.1. 성질

증명 [펼치기·접기]

----
우선 [math(n)]개의 상자에 왼쪽부터 [math(1)]부터 [math(n)]까지의 번호를 붙이자. 이때, 구하고자 하는 경우의 수 [math(N(n,\,r))]은 맨 오른쪽 상자 [math(n)]에[8] 공을 넣는 경우와 넣지 않는 경우로 나누어 구할 수 있다.

상자 [math(n)]에 공을 넣으면 이와 이웃하는 상자 [math(n-1)]에는 공을 넣을 수 없으므로 [math(1)]부터 [math(n-2)]까지의 상자에 서로 이웃하지 않게 나머지 [math((r-1))]개의 공을 넣어야 한다. 이 경우의 수는 다음과 같다.

[math(N(n-2,\,r-1))]

상자 [math(n)]에 공을 넣지 않으면 [math(1)]부터 [math(n-1)]까지의 상자에 서로 이웃하지 않게 [math(r)]개의 공을 넣어야 한다. 이 경우의 수는 다음과 같다.

[math(N(n-1,\,r))]

따라서 다음과 같은 귀납적 관계가 성립한다.

[math(N(n,\,r)=N(n-2,\,r-1)+N(n-1,\,r))]

이와 같은 방법을 계속 적용하면 다음이 성립한다.

[math(\begin{aligned}N(n,\,r)&=N(n-2,\,r-1)+N(n-1,\,r)\\&=N(n-2,\,r-1)+N(n-3,\,r-1)+N(n-2,\,r)\\&=N(n-2,\,r-1)+\cdots+N(2r-3,\,r-1)+N(2r-2,\,r)\end{aligned})]

이때 [math(N(2r-1,\,r)=1)]이고 [math(N(2r-2,\,r)=0)]이다. 다시 말해서 [math(n\leq2r-2)]일 때 [math(N(n,\,r)=0)]이 되므로 이 이상 식을 조작할 필요는 없다. 따라서 다음이 성립한다.

[math(\begin{aligned}N(n,\,r)&=N(n-2,\,r-1)+N(n-3,\,r-1)+\cdots+N(2r-3,\,r-1)\\&=\displaystyle\sum_{k=2r-3}^{n-2}N(k,\,r-1)\end{aligned})]

---

예제 [펼치기·접기]

----

2010학년도 9월 가형/나형 10번

앞서 밝힌 사실에 따라 (가)에는 [math(7)]이 들어간다. 또한 (나)가 있는 식은 [math(k)]장의 카드에서 수가 연속되지 않는 카드 [math(2)]장을 선택하는 경우의 수를 구하는 식이다. 이때 [math((k-1))]은 수가 연속하는 카드 [math(2)]장을 뽑는 경우의 수가 되므로, (나)에는 아무 조건 없이 [math(k)]장의 카드 중 [math(2)]장을 선택하는 모든 경우의 수가 들어가야 한다. 즉, (나)에는 [math({}_k{\rm C}_2)]가 들어간다. 마지막 (다)에 들어갈 값은 앞서 구한 공식을 사용하면

[math(N(9,\,3)={}_{9-3+1}{\rm C}_3={}_7{\rm C}_3=35)]

가 된다. 따라서 정답은 ①이다. 한편 앞서 밝힌 성질

[math(N(n,\,r)=\displaystyle\sum_{k=2r-3}^{n-2}N(k,\,r-1))]

에 [math(n=9)] 및 [math(r=3)]을 대입하면 문제에 나온 식

[math(N(9,\,3)=\displaystyle\sum_{k=3}^7N(k,\,2))]

가 됨도 확인할 수 있다.

3.4.2. 예제 및 오개념: '같다'와 '다르다'의 의미

2019학년도 7월 가형 27번/나형 16번[9]

2020학년도 3월 고2 29번

2016학년도 10월 가형 26번

3.4.3. 심화 예제: 세 종류의 대상을 배열하기

2023년 도쿄대학 본고사 문과 3번/이과 2번[11]

풀이 [펼치기·접기]

----
이 문제는 구슬의 종류가 두 가지가 아닌 세 가지이기 때문에 더욱 어렵다. 특히 (2)는 빨간 구슬뿐만 아니라 검은 구슬까지 이웃하지 않아야 하기 때문에 복잡하다. 먼저 (1)을 풀어 보자.

빨간 구슬끼리 이웃하지 않게 하려면, 빨간 구슬을 배열한 다음 그 사이에 나머지 구슬을 넣어 보는 방법이 있고, 나머지 구슬을 먼저 배열해 놓고 그 사이와 양쪽 끝에 빨간 구슬을 끼워넣는 방법이 있다. 이중에서 간단한 것은 단연코 후자이다. 전자의 경우 빨간 구슬 4개 사이에 나머지 구슬 3개를 넣고, 그 다음 마지막으로 남은 구슬들을 또 배열하는 경우의 수를 따지기가 매우 복잡하기 때문이다. 이는 구슬의 종류가 3개이기 때문으로, 빨간 구슬 이외에는 검은 구슬과 흰 구슬이 있어서 어떤 구슬을 얼마나 빨간 구슬 사이에 넣는지도 고려하는 것이 매우 복잡한 것이다. 따라서 후자의 방법으로 풀어 보자.

먼저 검은 구슬 3개와 흰 구슬 5개를 먼저 배열해 놓는 가짓수는

[math(\dfrac{8!}{3!5!}={}_8{\rm C}_3)]

이며, 빨간 구슬이 들어갈 수 있는 자리는 이 8개의 구슬 사이의 7개의 자리와 양쪽 끝 2개의 자리이므로 총 9개이다. 따라서 9개의 자리 중에서 빨간 구슬 4개가 들어갈 자리 4개를 고르면 된다. 따라서 빨간 구슬끼리 이웃하지 않게 배열하는 경우의 수는 다음과 같다.

[math({}_8{\rm C}_3\times{}_9{\rm C}_4)]

이 과정을 시행하여 만들어지는 경우 중 하나를 그림으로 나타내면 다음과 같다.


또한 12개의 구슬을 배열하는 전체 경우의 수는

[math(\dfrac{12!}{3!4!5!})]

이므로 구하는 확률 [math(p)]는 다음과 같다.

[math(p=\dfrac{{}_8{\rm C}_3\times{}_9{\rm C}_4}{12!/(3!4!5!)}=\dfrac{14}{55})]

이제 (2)를 풀어 보자. 조건부확률의 정의에 따라 다음이 성립한다.

[math(\begin{aligned}q&=\dfrac{\textsf{\footnotesize 빨간 구슬끼리 그리고 검은 구슬끼리 이웃하지 않을 확률}}{\textsf{\footnotesize 빨간 구슬끼리 이웃하지 않을 확률}(=p)}\\&=\dfrac{\textsf{\footnotesize 빨간 구슬끼리 그리고 검은 구슬끼리 이웃하지 않는 경우의 수}}{\textsf{\footnotesize 빨간 구슬끼리 이웃하지 않는 경우의 수}(={}_8{\rm C}_3\times{}_9{\rm C}_4)}\end{aligned})]

따라서 빨간 구슬끼리뿐만 아니라 검은 구슬끼리도 이웃하지 않는 경우의 수를 구하면 된다. 이를 계산할 때는 여사건을 이용하면 편리하다. 즉, 다음과 같이 [math(q)]의 값을 구하는 것이다.

[math(\begin{aligned}q&=\dfrac{\textsf{\footnotesize 빨간 구슬끼리 그리고 검은 구슬끼리 이웃하지 않는 경우의 수}}{\textsf{\footnotesize 빨간 구슬끼리 이웃하지 않는 경우의 수}}\\&=1-\dfrac{\textsf{\footnotesize 빨간 구슬끼리 이웃하지 않고 적어도 두 검은 구슬이 이웃하는 경우의 수}}{\textsf{\footnotesize 빨간 구슬끼리 이웃하지 않는 경우의 수}(={}_8{\rm C}_3\times{}_9{\rm C}_4)}\end{aligned})]

따라서 빨간 구슬끼리 이웃하지 않고 적어도 두 검은 구슬이 이웃하는 경우의 수를 구하자. 이번에도 검은 구슬과 흰 구슬을 먼저 배열하고 나중에 빨간 구슬을 배열해 보자. 이웃하는 검은 구슬 2개를 한 덩어리로 묶어 마치 별개의 하나의 공처럼 생각하면 이 공 1개와 검은 구슬 1개와 흰 구슬 5개를 배열하는 셈이 된다. 그 경우의 수는

[math(\dfrac{7!}{1!1!5!})]

이고 이 7개의 구슬 사이와 양쪽 끝에 있는 8개의 자리에 빨간 구슬 4개를 넣는 경우의 수는 [math({}_8{\rm C}_4)]이므로 이때의 경우의 수는 다음과 같다.

[math(\dfrac{7!}{1!1!5!}\times{}_8{\rm C}_4)]

그러나 이는 검은 구슬 3개가 모두 이웃하는 경우를 두 번 센 것이다.[12] 따라서 이 경우의 수를 다시금 한 번 빼 주어야 한다. 검은 구슬 3개를 한 덩어리로 묶어 마치 별개의 하나의 공처럼 생각하면 이 공 1개와 흰 구슬 5개를 배열하는 셈이 된다. 그 경우의 수는

[math(\dfrac{6!}{1!5!})]

이고 이 6개의 구슬 사이와 양쪽 끝에 있는 7개의 자리에 빨간 구슬 4개를 넣는 경우의 수는 [math({}_7{\rm C}_4)]이므로 이때의 경우의 수는 다음과 같다.

[math(\dfrac{6!}{1!5!}\times{}_7{\rm C}_4)]

따라서 최종적인 빨간 구슬끼리 이웃하지 않고 적어도 두 검은 구슬이 이웃하는 경우의 수는 다음과 같다.

[math(\dfrac{7!}{1!1!5!}\times{}_8{\rm C}_4-\dfrac{6!}{1!5!}\times{}_7{\rm C}_4)]

따라서 구하는 확률 [math(q)]는 다음과 같다.

[math(\begin{aligned}q&=1-\dfrac{\dfrac{7!}{1!1!5!}\times{}_8{\rm C}_4-\dfrac{6!}{1!5!}\times{}_7{\rm C}_4}{{}_8{\rm C}_3\times{}_9{\rm C}_4}\\&=1-\dfrac{65}{168}=\dfrac{103}{168}\end{aligned})]

3.5. 이항정리

3.6. 최단거리로 가는 방법

4. 공식 일람

• 순열(하강 계승)
• [math({}_n{\rm P}_r = n^{\underline r} = (n)_r = r! \dbinom{n}{r}=r!\cdot{}_n{\rm C}_r=\dfrac{n!}{(n-r)!})]
• [math({}_n{\rm P}_1=1,\,{}_n{\rm P}_n=n!)]
• [math({}_n{\rm P}_r=n\cdot{}_{n-1}{\rm P}_{r-1}={}_{n-1}{\rm P}_r+r\cdot{}_{n-1}{\rm P}_{r-1})]
• [math(r>1)]일 때, [math({}_n{\rm P}_r=(n-r+1)\cdot{}_n{\rm P}_{r-1})]
• 상승 계승
• [math(n^{\overline r} = n^{(r)} =r! \left(\!\!\dbinom{n}{r}\!\!\right) = r!\cdot{}_n{\rm H}_r =\dfrac{(n+r-1)!}{(n-1)!})]
• 같은 것이 있는 순열
• [math(a_1)]이 [math(\rm P_1)]개, [math(a_2)]가 [math(\rm P_2)]개, [math(\cdots\cdots)], [math(a_n)]이 [math({\rm P}_n)]개이면 [math(\frac{\displaystyle \left( \sum_{k=1}^n {\rm P}_k \right)!}{\displaystyle \prod_{k=1}^n \left( {\rm P}_k ! \right)} = \dfrac{({\rm P}_1 +{\rm P}_2 +\cdots +{\rm P}_n)!}{{\rm P}_1! \times {\rm P}_2! \times \cdots \times {\rm P}_n!})]
• 염주순열
• [math(n)]개의 서로 다른 구슬로 염주를 만드는 경우의 수는 [math(\left\lceil\dfrac{(n-1)!}2\right\rceil)]
• 완전순열(준계승)
• 사람 [math(n)]명이 [math(n)]개의 모자 중 하나를 쓸 때 자기 것을 쓰지 않는 경우의 수는 [math(\displaystyle D_n=\, !n = n¡ = \sum_{k=2}^n{}_n{\rm P}_{n-k}\left(-1\right)^k(n\geq2))]
• 점화식: [math(D_n=(n-1)\left(D_{n-1}+D_{n-2}\right)(n\geq 3))]
• [math(D_1=0,\,D_2=1,\,D_3=2,\,D_4=9,\,D_5=44)][14]
• [math(D_n = {\rm round}\left(\dfrac{n!}{e}\right))][15]
• 원순열
• 서로 다른 [math(n)]개의 공을 원형으로 배열하는 경우의 수는 [math((n-1)!)]
• 조합(이항계수)
• [math({}_n{\rm C}_r= \dbinom{n}{r} = \dfrac{n^{\underline r}}{r!} = \dfrac{(n)_r}{r!} = \dfrac{{}_n{\rm P}_r}{r!} = \dfrac{n!}{(n-r)!r!})]
• [math({}_n{\rm C}_0={}_n{\rm C}_n=1)]
• [math({}_n{\rm C}_1={}_n{\rm C}_{n-1}=n)]
• [math({}_n{\rm C}_r={}_n{\rm C}_{n-r})]
• [math({}_n{\rm C}_r=\dfrac{n}r\times{}_{n-1}{\rm C}_{r-1}\;(r\neq0))]
• [math(n\neq 1)]이면 [math({}_n{\rm C}_0<{}_n{\rm C}_1<{}_n{\rm C}_2<\cdots<{}_n{\rm C}_{\lfloor n/2\rfloor}={}_n{\rm C}_{\lceil n/2\rceil}>\cdots>{}_n{\rm C}_{n-2}>{}_n{\rm C}_{n-1}>{}_n{\rm C}_n)]
• [math(n=1)]이면 [math({}_1{\rm C}_0={}_1{\rm C}_1={}_1{\rm C}_{\lfloor1/2\rfloor}={}_1{\rm C}_{\lceil1/2\rceil})]
• 중복순열(거듭제곱)
• [math({}_n\Pi_r=n^r)]
• 중복순열의 합(파울하버의 공식): [math(\displaystyle \sum_{k=1}^n k^c = \sum_{k=0}^c \frac{(-1)^k}{c+1} \binom{c+1}k B_k n^{c+1-k})][16]
• 중복조합(중복집합계수)
• [math({}_n{\rm H}_r= \left(\!\!\dbinom{n}{r}\!\!\right) = M(n,\,r) = \dfrac{n^{\overline r}}{r!} = \dfrac{n^{(r)}}{r!} = {}_{n+r-1}{\rm C}_r={}_{n+r-1}{\rm C}_{n-1} = \dfrac{(n+r-1)!}{(n-1)! r!})]
• [math({}_n{\rm H}_r>{}_n{\rm C}_r\;(n\geq2))]
• [math({}_n{\rm H}_1={}_n{\rm C}_1=n,\,{}_n{\rm H}_0={}_n{\rm C}_0=1)]
• 등차수열의 합
• 서로 다른 2개의 문자에 대하여 음이 아닌 정수이고, [math(a+b=<n-1)]일 때, [math(\dfrac{n(n+1)}{2})]가 성립한다.
• 서로 다른 3개의 문자에 대하여 음이 아닌 정수이고, [math(a+b+c=<n-1)]일 때, [math(\dfrac{n(n+1)(2n+1)}{12}+\dfrac{n(n+1)}{4})]가 성립한다.
• 서로 다른 4개의 문자에 대하여 음이 아닌 정수이고, [math(a+b+c+d=<n-1)]일 때, [math(\dfrac{1}{6}(\dfrac{n(n+1)}{2})^2+\dfrac{n(n+1)(2n+1)}{12}+\dfrac{n(n+1)}{6})]이 성립한다.
• 이웃하지 않는 경우의 수
• 다른 상자 [math(n)]개에 같은 공 [math(r)]개 넣기: [math({}_{n-r+1}{\rm C}_r={}_{r+1}{\rm H}_{n-2r+1})]
• 다른 상자 [math(n)]개에 다른 공 [math(r)]개 넣기: [math({}_{n-r+1}{\rm P}_r={}_{n-r+1}{\rm C}_r\times r!={}_{r+1}{\rm H}_{n-2r+1}\times r!)]
• 자연수의 분할
• [math(P(n,\,k)=\displaystyle\sum_{i=1}^kP(n,\,i)=P(n-1,\,k-1)+P(n-k,\,k))]
• [math(P(n,\,1)=1)]
• [math(P(n,\,2)=\left\lfloor\dfrac{n}2\right\rfloor)][17]
• [math(P(n,\,3)={\rm round}\biggl(\dfrac{n^2}{12}\biggr) = \left\lfloor\dfrac{n^2}{12}+\dfrac12\right\rfloor=\left\lfloor\dfrac{n^2+6}{12}\right\rfloor)][18]
• 집합의 분할
• [math(S(n,\,k)= \begin{Bmatrix} n \\ k \end{Bmatrix} = \displaystyle\frac1{k!}\sum_{r=0}^k(-1)^{k-r}{}_k{\rm C}_rr^n)]
• [math(S(n,\,k)=S(n-1,\,k-1)+kS(n-1,\,k))]
• [math(S(n,\,1)=S(n,\,n)=1)]
• [math(S(n,\,2)=\dfrac{2^n-2}{2!}=2^{n-1}-1)]
• [math(S(n,\,3)=\dfrac{3^n-3\cdot2^n+3}{3!}=\dfrac{3^{n-1}-2^n+1}2)]
• [math(S(n,\,n-1)={}_n{\rm C}_2)]
• 오일러 수
• [math(A(n,\,k)= E(n,\,k)= \left<\begin{matrix} n \\ k \end{matrix}\right> = \displaystyle\sum_{r=0}^{k} (-1)^r \binom{n+1}{r}(k-r+1)^n)]
• 최단거리의 길이(택시 노름)
• [math(\left\|\bold{x}\right\|_1 = |x_1| + |x_2| + \cdots + |x_n| = \displaystyle\sum_{k=1}^{n} {|x_k|})]
• 한 번에 한 계단 또는 두 계단만 오를 수 있는 계단 [math(n)]개를 오르는 경우의 수(피보나치 수열): [math(F_{n+1})]
• [math(F_n=\dfrac1{\sqrt5}\left\{\left(\dfrac{1+\sqrt5}2\right)^n-\left(\dfrac{1-\sqrt5}2\right)^n\right\})]
• [math(F_n=F_{n-1}+F_{n-2}\;(n\geq3),\;F_1=F_2=1)]

4.1. 상보적 관계

• [math(n^{\underline r} = (-1)^r (-n)^{\overline r} \Leftrightarrow n^{\overline r} = (-1)^r (-n)^{\underline r})]
• [math(\dbinom{n}{r} = (-1)^r \left(\!\!\dbinom{-n}{r}\!\!\right) \Leftrightarrow \left(\!\!\dbinom{n}{r}\!\!\right) = (-1)^r \dbinom{-n}{r})]
• [math(n^{\underline r} \xrightleftharpoons[×r!]{÷r!}\dbinom{n}{r})], [math(n^{\overline r} \xrightleftharpoons[×r!]{÷r!}\left(\!\!\dbinom{n}{r}\!\!\right))]