경우의 수/공식

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!)]

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

2019년 7월 가형 27번/나형 16번[8]

2020학년도 3월 고2 29번

2016학년도 10월 가형 26번

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

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

풀이 [펼치기·접기]

----
이 문제는 구슬의 종류가 두 가지가 아닌 세 가지이기 때문에 더욱 어렵다. 특히 (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개가 모두 이웃하는 경우를 두 번 센 것이다.[11] 따라서 이 경우의 수를 다시금 한 번 빼 주어야 한다. 검은 구슬 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)][13]
• [math(D_n = {\rm round}\left(\dfrac{n!}{e}\right))][14]
• 원순열
• 서로 다른 [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})][15]
• 중복조합(중복집합계수)
• [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)][16]
• [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)][17]
• 집합의 분할
• [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))]