경우의 수/공식 (덤프버전으로 되돌리기)

[[분류:확률론]][[분류:이산수학]][[분류:대학수학능력시험]]
[include(틀:상위 문서, top1=경우의 수)]
[include(틀:이산수학)]
[목차]
== 개요 ==
[[경우의 수]]에 관한 공식과 모델을 설명하는 문서이다. 이를 이해하는 일은 중고등학교 수학 교육과정에서 매우 중요한 것으로 취급되는데, 이러한 모델들을 이용한 문제를 내기 때문에 그에 맞는 계산을 진행해야 하기 때문이다. 또한, 해당 내용과 관련된 [[평가원]]이나 [[교육청]]의 고교 수능형 기출 문제[* 수학영역 [[확률과 통계]] 과목과 연관이 깊다.]를 예제로 실었다.

== 계산 방식에 따른 분류 ==
 * '''[[순열]]'''
  * 서로 다른 사람 [math(n)]명을 일렬로 배열: [math(n!)]
  * 서로 다른 사람 [math(n)]명을 [[원순열|원형으로 배열]][* 회전하여 일치하는 것은 같은 것으로 봄]: [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))]

== 모델에 따른 분류 ==
##추가 예정

=== [[함수]]의 개수 ===
조건에 맞는 함수의 개수를 여러 계산으로 구할 수 있다. [[정의역]] [math(X)]의 원소의 개수를 [math(r)], [[공역]] [math(Y)]의 원소의 개수를 [math(n)]이라 하고 정의역과 공역이 모두 유한집합일 때, 다음이 성립한다.

 * '''전체 함수''': [math({}_n\Pi_r=n^r)]
정의역의 원소도, 공역의 원소도 서로 구별되며 정의역의 원소는 공역의 원소에 각각 독립적으로 대응하기 때문에 '''[[중복순열]]'''을 사용한다.
 * '''일대일함수''': [math({}_n{\rm P}_r)]
일대일함수는 공역의 원소 하나에 둘 이상의 정의역의 원소가 대응해서는 안 된다. 따라서 처음에는 정의역의 원소 [math(x_1)]이 대응할 수 있는 치역의 원소가 [math(n)]개이지만 바로 다음에는 [math((n-1))]개, [math((n-2))]개... 식으로 하나씩 줄어든다. 그러므로 '''[[순열]]'''을 사용한다.
 * '''일대일대응''': [math(n!=r!)]
일대일대응은 정의역과 치역의 원소의 개수가 동일한 일대일함수이므로 [math(n=r)]이다. 따라서 [math({}_n{\rm P}_r={}_r{\rm P}_r={}_n{\rm P}_n=n!=r!)]이 성립한다.
 * '''강단조증가함수/강단조감소함수''': [math({}_n{\rm C}_r)]
정의역의 임의의 두 원소 [math(a)], [math(b)]에 대하여, 각각 [math(\boldsymbol{a<b})]'''이면''' [math(\boldsymbol{f(a)<f(b)})]'''인 함수''' 그리고 [math(\boldsymbol{a<b})]'''이면''' [math(\boldsymbol{f(a)>f(b)})]'''인 함수'''를 말한다. 공역의 원소 [math(n)]개 중에서, 정의역의 원소 [math(r)]개에 대응할 원소 [math(r)]개를 임의로 뽑고 나면, 전자이든 후자이든 해당 조건을 만족시키는 '''유일한''' 함수가 자연스럽게 만들어진다. 따라서 그저 [math(n)]개에서 [math(r)]개를 뽑는 경우의 수를 구하는 것과 같으므로 '''[[조합]]'''을 사용한다.
 * '''단조증가함수/단조감소함수''': [math({}_n{\rm H}_r)]
정의역의 임의의 두 원소 [math(a)], [math(b)]에 대하여, 각각 [math(\boldsymbol{a<b})]'''이면 [math(\boldsymbol{f(a)\leq f(b)})]인 함수''' 그리고 [math(\boldsymbol{a<b})]'''이면 [math(\boldsymbol{f(a)\geq f(b)})]인 함수'''를 말한다. 바로 위 경우와 달리 서로 다른 정의역의 원소에 서로 같은 함숫값이 대응해도 된다. 곧, 중복을 허용하여 원소를 뽑고 나면 전자이든 후자이든 해당 조건을 만족시키는 '''유일한''' 함수가 자연스럽게 만들어진다. 따라서 그저 [math(n)]개에서 [math(r)]개를 중복을 허용하여 뽑는 경우의 수를 구하는 것과 같으므로 '''[[중복조합]]'''을 사용한다.

이를 응용하면 '''강단조증가/감소함수가 아닌 단조증가/감소함수의 개수'''[* 곧, 서로 다른 정의역의 원소에 같은 함숫값이 대응하는 경우가 적어도 한 번 있는 증가/감소함수의 개수]도 구할 수 있는데, 이는 다름 아닌 [math({}_n{\rm H}_r-{}_n{\rm C}_r)]이다. 먼저 모든 증가/감소함수의 개수([math({}_n{\rm H}_r)])를 구한 뒤, 서로 다른 정의역의 원소에 같은 함숫값이 대응하는 경우가 없는 증가/감소함수 즉, 강단조증가/강단조감소함수의 개수([math({}_n{\rm C}_r)])를 빼면 된다.

==== [[수열]]의 개수 ====
외전판으로 주로 각 항의 계수가 자연수라는 조건이 붙으며, 수열의 합을 이용하는 문제가 주로 등장한다.
예를 들어, 일반항이 3차 다항식으로 이루어져 있고 모든 항의 계수가 자연수이며, 제 4항부터 6항까지의 합이 945라고 한다면 [math((\dfrac{6(6+1)}{2})^2-(\dfrac{3(3+1)}{2})^2=405, \dfrac{6(6+1)(12+1)}{6}-\dfrac{3(3+1)(6+1)}{6}=77,  \dfrac{6(6+1)}{2}-\dfrac{3(3+1)}{2}=15, 6-3=3)]이니 [math(405a+77b+15c+3d=945)]를 만족시키는 자연수 [math(a, b, c, d)]를 구하면 된다.
=== [[부등호]] ===
 * 자연수 [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(1)]부터 [math(n)]까지의 자연수 중에서 [math(r)]개의 수를 뽑는 것을 나타내고 있지만, 꼭 그럴 필요 없이 '''서로 다른 [math(\boldsymbol n)]개의 수에서 [math(\boldsymbol r)]개를 뽑는 상황'''이면 동일한 공식이 성립한다는 뜻이다. 서로 다른 [math(n)]개의 수 중 [math(r)]개를 뽑고 나면 크기순으로 자연스럽게 [math(x_1)]부터 [math(x_r)]까지의 값이 정해지므로, 전자의 경우 그저 '''[[조합]]'''으로 계산하면 된다. 후자의 경우 [math(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)]
=== 상자에 공 넣기 ===
상자에 공을 넣는 상황을 모델로 하여, 여러 가지 경우의 수를 비교하며 설명할 수 있다. 대표적인 것을 표로 정리하면 다음과 같다.

||<tablealign=center><table bgcolor=#ffffff,#000000><bgcolor=#D7D7D7,#555555><width=33%> '''[math(\boldsymbol n)]개의 상자[br][math(\boldsymbol r)]개 또는[br][math(\boldsymbol k)]개의 공''' ||<-2><width=33%> '''서로 같은 상자''' ||<width=33%> '''서로 다른 상자''' ||
||<|2> '''서로 같은 공''' ||<-2> '''[[자연수의 분할]]''' ||<bgcolor=#f5f5f5,#555555> '''[[중복조합]]''' ||
||<-2> [math(P(n,\,k))] ||<bgcolor=#f5f5f5,#555555> [math({}_n{\rm H}_r)] ||
||<|2> '''서로 다른 공''' ||<-2> '''[[집합의 분할]]''' ||<bgcolor=#f5f5f5,#555555> '''[[중복순열]]''' ||
||<-2> [math(S(n,\,k))] ||<bgcolor=#f5f5f5,#555555> [math({}_n\Pi_r)], [math(n^r)] ||
||<-4> ||
||<-2><width=50%> '''빈 상자 비허용''' ||<-2><bgcolor=#f5f5f5,#555555><width=50%> '''빈 상자 허용''' ||

 * '''같은 상자에 같은 공 넣기([[자연수의 분할]])'''
경우의 수를 [math(P(n,\,k))]로 표기하는 [[자연수의 분할]]은 분할된 수들의 순서를 고려하지 않는다. 예를 들어 [math(6)]을 세 개의 수로 분할하는 경우 중 하나인 [math((1,\,2,\,3))]은 [math((2,\,3,\,1))]이나 [math((3,\,2,\,1))] 등과 다른 것이 아니며, 이것들은 모두 '[math(6)]을 [math(1)], [math(2)], [math(3)] 세 개의 수로 분할한 경우'로서 뜻하는 바가 완전히 같다. 또한, 공 6개를 '''같은''' 상자 3개에 '1개, 2개, 3개'로 배분하든 '2개, 3개, 1개'로 배분하든 다르지 않게 되려면 공끼리도 서로 구별이 되지 않아야 한다. 따라서 자연수의 분할은 '''같은''' 상자에 '''같은''' 공 넣기로 볼 수 있다.

한편, [math(P(n,\,k))]는 근본적으로 [math(k)]개의 수로 분할하는 경우의 수를 뜻하므로 이를 '상자에 공 넣기'로 생각할 때 빈 상자가 없어야 함은 물론이다. 예를 들어 [math(k)]개의 상자에 공을 담는데 한 개의 상자가 빈다면 이는 [math(P(n,\,k))]가 아닌 [math(P(n,\,k-1))]을 뜻하는 것이기 때문이다.

 * '''같은 상자에 다른 공 넣기([[집합의 분할]])'''
경우의 수를 [[제2종 스털링 수|[math(S(n,\,k))]]][* [math(\begin{Bmatrix} n \\ k \end{Bmatrix})]로 표기하기도 한다.]로 표기하는 [[집합의 분할]]은 분할된 원소들끼리 이루는 각 집합들의 순서를 고려하지 않는다. 예를 들어 집합 [math(\{1,\,2,\,3,\,4\})]를 세 개의 집합으로 분할하는 경우 중 하나인 [math((\{1,\,2\},\,\{3\},\,\{4\}))]는 [math((\{3\},\,\{4\},\,\{1,\,2\}))]나 [math((\{4\},\,\{3\},\,\{1,\,2\}))] 등과 다른 것이 아니며, 이것들은 모두 '[math(\{1,\,2,\,3,\,4\})]를 [math(\{1,\,2\})], [math(\{3\})], [math(\{4\})] 세 개의 집합으로 분할한 경우'로서 뜻하는 바가 완전히 같다.

그러나 집합의 분할에서는 각 집합에 들어가는 원소가 다르면 다른 집합이기에 다른 경우로 본다. 곧, 원소가 4개인 집합을 원소가 각각 2개, 1개, 1개인 집합으로 분류하는 경우는 모두 같은 것이 아니다. 예를 들어 [math((\{1,\,2\},\,\{3\},\,\{4\}))]와 [math((\{1,\,3\},\,\{2\},\,\{4\}))]는 분할된 원소의 개수는 2개, 1개, 1개로 같지만 서로 다른 집합으로 분할했으므로 서로 다른 경우이다. 요컨대 원소를 담는 추상적인 개념으로서의 '집합'은 그 자체로 서로 구별이 되지 않지만, '원소'끼리는 서로 구별이 되므로 원소를 여러 '집합'에 담는 순간 본질적으로는 '원소'에 의하여 경우가 구별되는 것이다.[* 이 말이 잘 이해가 되지 않는다면 이렇게 생각해 보자. 위에서 예로 든 [math(\{1,\,2,\,3,\,4\})]를 세 집합으로 분할하기 위하여 '''똑같은''' 중괄호 세 개([math(\{\})], [math(\{\})], [math(\{\})])를 준비하는 것이다. 이 자체로는 세 개의 중괄호가 구별이 되지 않는다. 그런데 여기에 구체적인 원소를 담는 순간, [math((\{1,\,2\},\,\{3\},\,\{4\}))]와 같이 원소끼리는 구별이 되므로 원소를 담은 뒤에야 비로소 집합끼리 구별이 되는 것이다. 그런데 이는 집합 그 자체가 구별이 가능하기 때문이 아니라 본질적으로 구별이 가능한 원소를 집합에 담았기 때문이라고 할 수 있다.] 따라서 집합의 분할은 '''같은''' 상자에 '''다른''' 공 넣기로 볼 수 있다.

한편, [math(S(n,\,k))]는 근본적으로 [math(k)]개의 수로 분할하는 경우의 수를 뜻하므로 이를 '상자에 공 넣기'로 생각할 때 빈 상자가 없어야 함은 물론이다. 예를 들어 [math(k)]개의 상자에 공을 담는데 한 개의 상자가 빈다면 이는 [math(S(n,\,k))]가 아닌 [math(S(n,\,k-1))]을 뜻하는 것이기 때문이다.

 * '''다른 상자에 같은 공 넣기([[중복조합]])'''
경우의 수를 [math({}_n{\rm H}_r)][* 표준 표기는 [math(\left(\!\!\dbinom{n}{r}\!\!\right))] 또는 [math(\dfrac{n^{\overline r}}{r!})]]로 표기하는 [[중복조합]]은 뽑은 대상들의 순서를 고려하지 않는다. 예를 들어 3개의 수 [math((1,\,2,\,3))]에서 4개를 중복을 허용하여 뽑는 경우 중 하나인 [math((1,\,1,\,2,\,3))]은 [math((1,\,2,\,1,\,3))]이나 [math((3,\,1,\,2,\,1))] 등과 다른 것이 아니며, 이것들은 모두 '[math((1,\,2,\,3))]에서 4개를 중복을 허용하여 뽑는 경우'로서 뜻하는 바가 완전히 같다.

그러나 중복조합에서는 각 대상을 뽑은 횟수가 같더라도 뽑은 대상이 다르면 다른 경우로 본다. 곧, 3개의 수 [math((1,\,2,\,3))]에서 4개를 중복을 허용하여 뽑는 경우는 모두 같은 것이 아니다. 예를 들어 [math((1,\,1,\,2,\,3))]과 [math((2,\,2,\,1,\,3))]은 각 대상을 뽑은 횟수는 둘 다 2회, 1회, 1회로 같지만 2회를 뽑은 대상이 다르기 때문에 다른 경우로 취급하는 것이다.
 
상자가 다르고 공이 같으면, 자체로는 구별되지 않는 공을 구별이 가능한 상자에 넣는 순간 그 상자로서 공들을 구별할 수 있게 된다. 앞서 설명한 집합의 분할과는 정반대인 것이다. 따라서 서로 다른 상자에 번호를 매긴 뒤 '공을 상자에 넣기'를 '공에 번호 쓰기'로 바꾸어 생각할 수 있다. 예를 들어 상자 [math(1)], [math(2)], [math(3)] 세 개에 공 네 개를 차례대로 1개, 3개, 0개를 넣었다면 이는 공 네 개에 각각 [math((1,\,2,\,2,\,2))]를 쓰는 것과 같다. 이렇게 생각하면 이는 중복조합의 개념과 일치하며, 중복조합은 '''다른''' 상자에 '''같은''' 공 넣기로 볼 수 있다.

한편, [math({}_n{\rm H}_r)]의 계산에는 [math(n)]개의 대상에서 [math(r)]개를 뽑을 때 '중복을 허용'하는 전제만이 있을 뿐이지 '모든 수를 적어도 한 번' 뽑는다는 전제는 없으므로 이를 '상자에 공 넣기'로 생각할 때 '모든 상자에 적어도 한 번' 공을 넣어야 할 필요가 없다고 할 수 있다. 곧, 빈 상자가 있어도 되는 것이다.

 * '''다른 상자에 다른 공 넣기([[중복순열]])'''
경우의 수를 [math({}_n\Pi_r)] 또는 [math(n^r)][* [math({}_n\Pi_r)]는 한국과 일본에서만 통용되며, 이외의 곳에서는 용례가 없다. 오직 [math(n^r)]만을 쓴다.]으로 표기하는 [[중복순열]]은 뽑은 대상들을 구별하면서 순서를 고려한다. 예를 들어 4개의 수 [math((1,\,2,\,3,\,4))]에서 3개를 뽑는 경우 중 하나인 [math((1,\,2,\,3))]은 [math((2,\,3,\,1))]이나 [math((3,\,2,\,1))] 등과 모두 다르다. 뽑은 수 자체는 같지만 순서가 다르면 다른 경우로 취급하는 것이다. 이 '순서'란 '상자에 공 넣기'로 생각할 때 곧 '상자'가 구별 가능하다는 뜻이다. 또한 [math((1,\,2,\,3))]은 [math((1,\,2,\,4))]나 [math((2,\,3,\,4))] 등과 모두 다르다. 뽑은 수의 개수는 같지만 뽑은 수가 다르면 다른 경우로 취급하는 것이다. 이 '뽑은 수'란 '상자에 공 넣기'로 생각할 때 곧 '공'이 구별 가능하다는 것이다. 다시 말해서 상자에도 [math(1,\,2,\,3,\,4)]처럼, 공에도 [math(1,\,2,\,3)]처럼 번호가 매겨져 있어서 구별이 가능하다. 따라서 중복순열은 '''다른''' 상자에 '''다른''' 공 넣기로 볼 수 있다.

한편, [math({}_n\Pi_r)]의 계산에는 [math(n)]개의 대상에서 [math(r)]개를 뽑을 때 '모든 수를 적어도 한 번' 뽑는다는 전제는 없으므로 이를 '상자에 공 넣기'로 생각할 때 '모든 상자에 적어도 한 번' 공을 넣어야 할 필요가 없다고 할 수 있다. 곧, 빈 상자가 있어도 되는 것이다.

=== 이웃하지 않게 배열하기 ===
상자를 일렬로 배열한 뒤, 한 상자에는 한 공만 넣고 공을 넣은 상자끼리 이웃하지 않는 경우의 수를 구해 보자. 상자의 개수를 [math(n)], 공의 개수를 [math(r)]라 하면 다음이 성립한다.

 * '''같은 상자에 같은 공 넣기''': [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={}_{n-r+1}{\rm C}_r\times n!\times r!={}_{r+1}{\rm H}_{n-2r+1}\times n!\times r!)]

즉, 같은 상자에 같은 공 넣기가 가장 기본으로 그 공식은 [math({}_{n-r+1}{\rm C}_r={}_{r+1}{\rm H}_{n-2r+1})]이며, 여기에서 상자가 구별되면 [math(n!)]을, 공이 구별되면 [math(r!)]을 곱하는 식이다.

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

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

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

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

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

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

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

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

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

{{{#!wiki style="text-align: center"
[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)]이 나온다.

{{{#!wiki style="text-align: center"
[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)]이 되는지 알아보자.

[[파일:이웃하지 않는 경우의 수 4.png|width=500&align=center]]
위 그림과 같이 총 상자의 개수가 [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)]개가 됨을 확인할 수 있다. 이를 표로 나타내면 다음과 같다.

||<tablealign=center><table bgcolor=#ffffff,#000000><rowbgcolor=#efefef,#555555> '''총 상자 개수''' || '''넣을 수 있는 공 개수''' ||
|| [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)] ||
||<-2> [math(\therefore r\leq\dfrac{n+1}2)] ||

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

{{{#!wiki style="text-align: center"
[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!)]을 모두 곱하면 된다. 이 말을 그림으로 쉽게 이해해 보자.

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

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

[[파일:이웃하지 않게 배열하기 2.jpg|width=550&align=center]]
즉, 앞서 도출된 [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)]까지의 이름을 붙이면 다음과 같은 일이 발생한다.

[[파일:이웃하지 않게 배열하기 3.jpg|width=550&align=center]]
즉, 앞서 도출된 [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!)]이 된다.

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

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

==== 예제 및 오개념: '같다'와 '다르다'의 의미 ====
||<tablealign=center><#ffffff> [[파일:2019 7평 나 16.png|width=350]] ||
|| '''2019년 7월 가형 27번/나형 16번'''[* 2019년 7월 [[전국연합학력평가]]의 가형과 나형의 공통 문항이다. 가형에서는 단답형으로, 나형에서는 객관식으로 출제되었다. 사진은 나형 버전이다.] ||
이 경우 [math(n=8,\,r=3)]이고 레인은 구별되지 않고 사람은 모두 구별되므로 정답은 다음과 같다.

{{{#!wiki style="text-align: center"
[math({}_{8-3+1}{\rm P}_3={}_6{\rm P}_3=120\\\textsf{or}\\{}_{3+1}{\rm H}_{8-2\times3+1}\times3!={}_4{\rm H}_3\times3!={}_6{\rm C}_3\times6=120)]}}}
이때, 각 레인에 떡하니 [math(1)]부터 [math(8)]까지의 서로 다른 번호가 붙어 있는데 레인이 구별되지 않는다는 말이 얼른 이해되지 않을지 모른다. 문제에서 주어진 상황에서는 단지 레인이 일렬로 [math(8)]개가 늘어서 있음을 나타낼 뿐이다. 다시 말해서 상식적으로 레인이란 하나의 수영장을 여러 구획으로 나눈 것에 불과하므로 레인을 뒤섞어 다시 '배열'한다는 것은 말이 되지 않는다. 또한 각 레인의 수심이라든지 총 거리 등 레인을 차별화할 수 있는 어떤 요소도 문제에서 언급된 적이 없다. 따라서 레인의 배열의 가짓수가 [math(8!)]이 된다는 접근은 근거가 없다고 할 수 있겠다. 요컨대 레인의 배열은 경우의 수를 구할 때 고려하지 않는 요소가 되므로, 레인을 '같은 것', 즉 '구별되지 않는 것'으로 취급하는 것이다.

그러나 여전히 풀리지 않는 의문이 있을 것이다. 어쨌든 각 레인의 번호 자체는 분명히 모두 '다르므로', 서로 '구별'되고 있지 않은가? 그럼에도 불구하고 레인은 구별되지 않는다고 한다면, 여기에서 이야기하는 '같다', '다르다', '구별된다', '구별되지 않는다'의 근본적인 의미란 무엇인가?

결론부터 말하면 레인의 번호는 각 레인의 '''상대적 위치''', 즉 각 레인이 왼쪽에서 몇 번째에 있는 레인인지를 알려주는 번호일 뿐, 레인들 자체의 '''고유한 특성'''을 차별화하여 레인이 서로 구별되게 하는 번호가 아니다. 이 말의 의미를 이해해 보자.

일단 상식을 무시하여 레인을 뒤섞어 본다고 하자. 그러면 [math(1)]번 레인과 [math(2)]번 레인의 자리를 서로 바꾼다 한들 문제의 레인의 번호는 바뀌지 않는 것이다. 왜냐하면 이 번호는 [math(8)]개의 레인을 어떻게 배열해 놓든, 무조건 왼쪽에서 첫 번째에 있는 레인에 [math(1)]번을 부여하는 식이기 때문이다. 따라서 이 경우 위 설명과 같이 레인의 서로 다른 [math(8!)]가지의 경우 중 어느 하나를 고를 수 없으며, 레인의 번호의 순서는 무조건 [math(1)][math(2)][math(3)][math(4)][math(5)][math(6)][math(7)][math(8)]이 된다.

만약 레인의 번호가 각 레인들의 '''고유한 특성'''에 직접 대응하여 그 특성을 대표하는 번호였다면 [math(1)]번 레인과 [math(2)]번 레인의 자리를 서로 바꾸었을 때 번호의 순서는 [math(2)][math(1)][math(3)][math(4)][math(5)][math(6)][math(7)][math(8)]이 될 것이다. 이런 식으로 레인을 뒤섞으면 [math(8!)]가지의 배열이 나오게 될 것이다. 쉽게 말해 레인 자체에 이름을 짓는다고 생각하면 된다. 번호가 적힌 이름표를 레인에 달아 레인을 배열한다면, 그 번호는 레인을 그대로 '따라다닐' 것이다. 따라서 레인의 배열이 달라지면 그에 맞게 번호의 순서 역시 [math(4)][math(2)][math(8)][math(7)][math(1)][math(3)][math(6)][math(5)], [math(7)][math(6)][math(5)][math(4)][math(3)][math(2)][math(1)][math(8)]과 같이 이리저리 달라지게 되며 그 모든 가짓수가 [math(8!)]이라는 것이다. 이와 같이 번호가 레인에 근본적으로 대응하여 레인을 '따라다니는' 경우, 이 번호가 한 레인을 다른 레인과 구별되게 해주는 '''고유한 특성'''처럼 기능한다.

그러나 번호가 '''상대적 위치'''를 나타내는 경우에는 제아무리 레인의 자리를 바꾼다 한들 왼쪽에서 첫 번째에 있는 레인에 [math(1)]번이 붙는 식이므로, 사실상은 배열을 끝마친 다음 왼쪽부터 무조건 [math(1)][math(2)][math(3)][math(4)][math(5)][math(6)][math(7)][math(8)]의 이름표를 달아주는 것이나 마찬가지이다. 결국 레인을 뒤섞는다는 것 자체가 의미를 잃어버리며, 레인의 배열은 [math(1)][math(2)][math(3)][math(4)][math(5)][math(6)][math(7)][math(8)] 하나뿐이므로 레인의 배열은 경우의 수에 영향을 주지 않는다.

한편, '''상대적 위치'''와 '''고유한 특성'''의 또 다른 차이가 있다. '''상대적 위치'''란 일단 대상들을 배열하고 난 다음에야 비로소 유효한 개념인 반면 '''고유한 특성'''은 그렇지 않다. 예를 들어 빨간 공, 파란 공, 노란 공을 생각하자. 이 공 세 개는 분명히 '다른' 공인데, 이는 어디까지나 상대적 위치가 아닌 고유한 특성이 다르다는 의미이다. 각 공은 색상이라는 측면에서 고유한 특성이 모두 다르다. 고유한 특성은 그 대상 자체가 근본적으로 갖는 요소이기 때문에 대상들을 배열하든 배열하지 않든 고유한 특성은 유지된다. 이 공 세 개를 배열하지 않고 가만히 손에 쥐고 있더라도 빨간 공은 빨간 공이고 파란 공은 파란 공이며 노란 공은 노란 공인 식이다. 그러나 공들을 배열하지 않으면 어떤 색상의 공이 왼쪽에서 몇 번째에 있는지 말할 수조차 없다. 즉, 상대적 위치는 대상들의 배열을 전제로 하는 개념이다.

이번엔 검은 공 세 개를 생각하자. 이 공 세 개를 일렬로 나열하면 각 공은 왼쪽에서 첫 번째, 두 번째, 세 번째에 있을 것이다. 즉, 상대적 위치가 모두 다르다. 그렇다고 해서 이 공들이 모두 다른 공인가? 당연히 아니다. 이것만 보더라도 대상의 같고 다름을 상대적 위치로 판별하는 것은 어불성설임을 실감할 수 있을 것이다. 사실 '''상대적 위치'''는 대상을 배열하고 나면 모든 대상이 자신만의 위치에 자리하므로 의미가 없는 것이다. '같다', '다르다', '구별된다', '구별되지 않는다'가 상대적 위치에 관한 진술이라면 이 세상 모든 문제 상황의 모든 대상은 제각각 다 다르고 구별된다는 말이 되어, 이는 '서로 같은 연필을 나누어주는 상황' 따위를 전면 부정하는 결론이므로 당연히 말이 되지 않는다.

또한 '''상대적 위치'''는 대상을 배열하는 방식에 따라 임의적으로 달라지므로, 상대적 위치에 따라 대상의 같고 다름을 판별하면 대상들을 배열하기에 따라 같은 대상이 될 수도 있고 다른 대상이 될 수도 있다는 결론이 나오는데 이 역시 말이 되지 않는다. 예를 들어 왼쪽 상자와 오른쪽 상자가 있을 때 검은 공 세 개를 왼쪽 상자에 모두 넣으면 이 공들은 같은 공들이 되고, 하나를 오른쪽 상자에 넣으면 이 공은 나머지 두 공과 순식간에 다른 공이 되어 버린다. 요컨대 대상의 배열은 지극히 임의적이므로 이를 가지고 대상의 같고 다름을 판별할 수 없음은 자명하다. 반면 '''고유한 특성'''은 대상의 배열 여부 또는 배열 형태에 관계없이 대상의 같고 다름을 일관되게 판별할 수 있는 기준이라고 할 수 있다.

결론적으로, 대상들이 서로 '같다', '다르다', '구별된다', '구별되지 않는다'라는 것은 대상의 '''고유한 특성'''에 관한 진술이며, '''상대적 위치'''에 관한 진술이 아니다. 위 문제의 번호는 분명히 서로 다르지만, 각 레인의 상대적 위치를 나타낼 뿐 고유한 특성을 대표하지 않으므로 제아무리 번호가 다르더라도 레인이 구별된다고 할 수 없다.[* 이때, 이렇게 되는 근본적인 이유는 어디까지나 문제 상황과 상식에 기대어야 알 수 있음에 유의하자. 상대적 위치와 고유한 특성의 개념적 차이를 분석한다고 해서 알 수 있는 것이 아니라는 말이다. 레인이 구별되지 않는 이유는 처음에 밝혔듯이 문제의 어디에서도 레인이 구별된다고 볼 만한 근거가 없기 때문이다. 근본적인 이유는 그것이며, 이제 이를 두고 '사후적으로' 상대적 위치와 고유한 특성의 개념적 차이에 입각하여 레인의 번호는 고유한 특성이 아닌 상대적 위치를 나타낼 뿐이라는 해석을 내놓는 것이 논리의 올바른 순서이다. 문제의 레인이 왜 구별되지 않느냐는 질문에 레인이 상대적 위치를 나타내기 때문이라고 답하는 것은 [[동어 반복]](tautology)에 불과하다. 결국 왜 레인이 상대적 위치를 나타내느냐고 재질문할 수밖에 없는데, 이를 설명하려면 문제 상황과 상식에 의존해야 한다. 결국 대상의 같고 다름은 문제에 제시된 상황을 보아야 판단할 수 있음을 명심하자.]

그런데, 더욱 헷갈리는 말이겠지만 사실 문제의 레인들이 구별이 된다고 해석할 수도 있다. 단 이 경우에는 반드시 '''레인의 재배열이 허용되지 않는다'''는 새로운 전제를 도입해야만 한다. 예를 들어 레인의 수심이 레인마다 모두 다르다고 하여, 예컨대 레인의 번호는 그 레인의 수심을 미터([math(\rm m)]) 단위로 나타낸 것이라고 하자. 그러면 수심은 레인 자체가 갖는 고유한 특성이라는 점에서 다른 레인이라고 볼 수 있는 것이다. 이때 수영장은 원래 바닥을 레인마다 따로따로 위아래로 움직여 각 레인의 수심을 조절할 수 있는 구조라고 하자. 그러면 레인의 수심을 조절하는 것이 결국 레인의 재배열과 같다. 그런데 경우의 수를 구하는 조건에서 수심의 조절을 금한다면, 레인의 재배열이 금지되어 [math(1)][math(2)][math(3)][math(4)][math(5)][math(6)][math(7)][math(8)] 이외의 배열이 불가능해진다. 이는 처음부터 레인이 모두 같은 레인이라고 생각하고 각 번호가 레인의 상대적 위치를 나타내는 것에 불과하다고 보는 시각과 그 결론이 완전히 동일하다. 결국 이는 문제 상황을 바라보는 시각의 차이일 뿐, 수학적인 결론은 동일한 것이다.

한편, 사람은 굳이 같고 다름을 명시하지 않아도 무조건 다른 대상이라는 사실도 주목할 만하다. 여러 경우의 수 문제를 보더라도 같은/다른 공, 같은/다른 연필이라는 표현은 등장할지 몰라도 같은/다른 사람이라는 표현은 등장하지 않는다. 사람은 그야말로 모두가 유일한 존재이므로 단지 '사람'이라고만 써도 모두 구별되는 대상임이 자명하기 때문이다. 이런 대상은 달리 찾아보기 힘들다. 꽃의 경우에도 자세히 보면 모두 다르게 생겼을지 몰라도 그것을 구별하는 것은 현실적으로 거의 불가능하므로 문제에서도 같은 종의 꽃이면 같은 것으로 본다. 그러나 사람은 같은 종인데도 모두 다른 대상으로 취급한다는 점이 꽤 흥미로운 대목이다. 다음 두 문제는 꽃에 대한 경우의 수 문제이다.

||<tablealign=center><#ffffff> [[파일:2020학년도 3월 고2 29번.jpg|width=350&align=center]] ||
|| '''2020학년도 3월 고2 29번''' ||
이 문제에서는 꽃 네 송이를 서로 다른 것으로 만들기 위하여 '서로 다른 종류의 꽃'이라는 말을 명시함과 동시에 서로 다른 모양의 꽃 그림까지 첨부해 놓았다. 꽃이 아니라 사람이었다면 이렇게까지 할 필요가 없다.


||<tablealign=center><#ffffff> [[파일:2016학년도 10월 가형 26번.jpg|width=350&align=center]] ||
|| '''2016학년도 10월 가형 26번''' ||
이 문제에서는 꽃을 장미, 카네이션, 백합으로 구별했다. 그러면 이름이 다른 꽃끼리는 다른 꽃으로, 이름이 같은 꽃끼리는 같은 꽃으로 취급하라는 뜻이 된다. 아예 같은 종류의 꽃끼리는 구별하지 않는다는 단서까지 달려 있다. 꽃이 아니라 사람이었다면 불가능한 일이다.
=== [[이항정리]] ===
[math((a+b)^n)]의 전개식에서, [math(a^rb^{n-r})]의 계수는 [math(r)]개의 [math(a)]와 [math((n-r))]개의 [math(b)]를 일렬로 나열하는 경우의 수이므로 다음과 같이 '''같은 것이 있는 순열'''로 구할 수 있으며, 이는 '''[[조합]]'''과도 일치한다. 조합의 이명이 '이항계수(binomial coefficient)'인 이유이기도 하다.

{{{#!wiki style="text-align: center;"
[math(\dfrac{n!}{r!(n-r)!}={}_n{\rm C}_r)]}}}
단, 표수가 [[소수(수론)|소수]]인 [[유한체]]에서는 표수와 같은 값으로 제곱할 시 [[1학년의 꿈|[math({}_n{\rm C}_r =1)]인 항을 제외한 모든 항이 [math(0)]이 된다.]]

=== [[최단거리]]로 가는 방법 ===
[[파일:최단거리 수정.png|width=340&align=center]]
[[마름모]]가 변끼리 겹치도록 가로로 [math(m)]개, 세로로 [math(n)]개를 그리면 좌하단 점 [math(\rm A)]에서 우상단 점 [math(\rm B)]까지 최단거리로 이동하는 경우의 수는 다음과 같이 '''같은 것이 있는 순열'''로 구할 수 있으며, 이는 '''[[조합]]'''과도 일치한다.

{{{#!wiki style="text-align: center;"
[math(\dfrac{(m+n)!}{m!n!}={}_{m+n}{\rm C}_m={}_{m+n}{\rm C}_n)]}}}

[[파일:최단거리 증명 수정.png|width=340&align=center]]
이를 증명하여 보자. 모든 [[사각형]]의 변의 길이가 같기 때문에, 최단거리로 좌하단 점에서 우상단 점까지 가려면 무조건 오른쪽 또는 위쪽으로만 이동해야 한다. 그러자면 위 그림과 같이 모든 최단거리의 길은 가로로 [math(m)]번, 세로로 [math(n)]번 이동하는 길이 될 수밖에 없으며, 가로의 길과 세로의 길을 어떤 순서로 선택하느냐에 따라 길이 달라진다. 따라서 최단거리의 경우의 수는 같은 것이 있는 순열로 구할 수 있다.

크기 관련해서는 [[택시 기하학]] 문서도 참조.[* 택시 기하학에서의 공리를 활용한 최단거리 문제가 나올 수 있다.]
== 공식 일람 ==
 * [[순열]]([[계승(수학)#s-2|하강 계승]])
  * [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})]
 * [[계승(수학)#s-2|상승 계승]]
  * [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)][* 그 다음부터는 [math(D_6=265,\,D_7=1854)]와 같이 값이 너무 커지고, 위 점화식을 이용한 계산을 너무 많이 반복해야 하기 때문에 문제에 잘 나오지 않는다. [math(D_5)]마저도 잘 나오지 않으며 [math(D_4)] 정도까지 빈번하게 다뤄진다.]
  * [math(D_n = {\rm round}\left(\dfrac{n!}{e}\right))][* [math(e)]는 [[자연로그의 밑]]이다.]
 * [[원순열]]
  * 서로 다른 [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})][* [math(B_k)]는 [[베르누이 수열]]이다.]
 * [[중복조합]](중복집합계수)
  * [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)][* [math(n/2)]보다 작은 정수의 최댓값을 구한다는 뜻이다.]
  * [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)][* [math(n^2/12)]을 [[소수(실수)|소수]] 첫째 자리에서 [[반올림]]하여 [[정수]]로 만든다는 뜻이다.]
 * [[집합의 분할]]
  * [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)]
 * [[https://en.wikipedia.org/wiki/Eulerian_number|오일러 수]]
  * [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)]
 * 최단거리의 길이([[노름(수학)#s-4.2.2|택시 노름]])
  * [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)]
=== 상보적 관계 ===
 * [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))]
경우의 수/공식 (덤프버전으로 되돌리기)

캡챠
