확률과 통계 > 여러 가지 순열과 조합

응용 : 공과 상자

공의 구별과 남김 여부, 빈 상자의 존재 여부에 따른 다양한 상황을 다루어봅시다.

공과 상자를 이용하여 다양한 상황 해석하기

공 $4$개를 상자 $3$개에 담을 때, 다음의 네 여부에 따라 상황을 해석하는 방법이 달라집니다.
  1. 공이 서로 구별되는가?
  2. 상자가 서로 구별되는가?
  3. 공을 남김없이 다 넣는가?
  4. 빈 상자가 있을 수도 있는가?
그럼 총 $2^4 = 16$가지의 케이스가 있을 것입니다. 이제 각각의 케이스를 모두 해석할 것입니다. 아래의 본문에서 곧바로 해설이 제시됩니다. 따라서 본문을 읽어나가기 전에 빈 종이나 공책을 펴고, 지금까지 우리가 배운 모든 개념을 총동원하여 빈 종이에 각각의 케이스를 스스로 해석한 뒤 읽어보세요.

1) 공이 구별되고, 상자가 구별되지 않는 경우

1-1) 공을 남김없이 다 넣고, 빈 상자가 있을 수도 있는 경우

몇 개의 상자에 공을 담을지를 기준으로 분류해봅시다. 이때 각 상자가 구별되지 않으므로, 몇 개의 상자를 고르더라도 상자를 고르는 경우의 수는 $1$입니다.
  1. 상자를 한 개 사용하는 경우
    공 $4$개를 $1$개의 모둠으로 만들어야 합니다. 따라서 경우의 수는 $1$입니다.
  2. 상자를 두 개 사용하는 경우
    공 $4$개를 $2$개의 모둠으로 만들어야 합니다. 이는 $3+1$과 $2+2$가 있습니다. 전자의 경우 $\NCR{4}{1} = 4$, 후자의 경우 $\NCR{4}{2}\times \NCR{2}{2}\times \dfrac{1}{2!} = 3$입니다. 따라서 경우의 수는 $4+3=7$입니다.
  3. 상자를 세 개 사용하는 경우
    공 $4$개를 $3$개의 모둠으로 만들어야 합니다. 이는 $1+1+2$뿐입니다. 따라서 경우의 수는 $\NCR{4}{1}\times \NCR{3}{1}\times \NCR{2}{2}\times\dfrac{1}{2!} = 6$입니다.
정리하면 $1\times \left( 1+7+6 \right) = 14 $입니다.

1-2) 공을 남김없이 다 넣고, 빈 상자가 없는 경우

빈 상자가 없는 경우는 $1-1)$의 \hcn3과 동치입니다. 따라서 경우의 수는 $6$입니다.

1-3) 공을 남길 수 있고, 빈 상자가 있을 수도 있는 경우

몇 개의 공을 사용하는지를 기준으로 분류해봅시다.
  1. 공을 사용하지 않는 경우
    공을 사용하지 않으므로, 상자가 모두 비어 있는 경우입니다. 따라서 경우의 수는 $1$입니다.
  2. 공을 $1$개 사용하는 경우
    어떤 공을 사용할지 고르는 경우의 수는 $\NCR{4}{1}$이고, 공은 상자 $1$개에 모두 들어가야 합니다. 따라서 경우의 수는 $4\times 1 = 4$입니다.
  3. 공을 $2$개 사용하는 경우
    어떤 공을 사용할지 고르는 경우의 수는 $\NCR{4}{2}$이고, 공은 상자 $1$개에 모두 들어가거나, 상자 $2$개에 하나씩 들어가야 합니다. 따라서 경우의 수는 $6\times 2 = 12$입니다.
  4. 공을 $3$개 사용하는 경우
    어떤 공을 사용할지 고르는 경우의 수는 $\NCR{4}{3}$이고, 공은 상자 $1$개에 모두 들어가거나, 상자 $2$개에 $1$개, $2$개로 나누어 들어가거나, 상자 $3$개에 하나씩 들어가야 합니다. 이때 $3$개의 공을 나누어 넣는 경우의 수는 각각 $1$, $\NCR{3}{1}$, $1$이므로 경우의 수는 $4\times \left( 1+3+1 \right) = 20$입니다.
  5. 공을 $4$개 사용하는 경우
    공을 남김없이 다 넣고, 빈 상자가 있을 수도 있는 경우와 동치입니다. 따라서 경우의 수는 $14$입니다.
정리하면 $1+4+12+20+14=51$입니다.

1-4) 공을 남길 수 있고, 빈 상자가 없는 경우

몇 개의 공을 사용하는지를 기준으로 분류해봅시다.
  1. 공을 사용하지 않는 경우 : 반드시 빈 상자가 존재하므로 문제의 조건에 위배됩니다.
  2. 공을 $1$개 사용하는 경우 : 반드시 빈 상자가 존재하므로 문제의 조건에 위배됩니다.
  3. 공을 $2$개 사용하는 경우 : 반드시 빈 상자가 존재하므로 문제의 조건에 위배됩니다.
  4. 공을 $3$개 사용하는 경우
    어떤 공을 사용할지 고르는 경우의 수는 $\NCR{4}{3}$이고, 세 개의 공은 상자 $3$개에 하나씩 들어가야 합니다. 따라서 경우의 수는 $4\times 1 = 4$입니다.
  5. 공을 $4$개 사용하는 경우
    공 $4$개를 $1$개, $1$개, $2$개로 나눈 $3$개의 모둠으로 만들고, 들어갈 상자를 고르면 됩니다. 따라서 경우의 수는 $\NCR{4}{1}\times \NCR{3}{1}\times\NCR{2}{2}\times\dfrac{1}{2!}\times 1 = 6$입니다.
정리하면 경우의 수는 $4+6=10$입니다.

2) 공이 구별되고, 상자가 구별되는 경우

2-1) 공을 남김없이 다 넣고, 빈 상자가 있을 수도 있는 경우

몇 개의 상자에 공을 담을지를 기준으로 분류하고$\cdots (1)$, 상자의 개수에 따라 모둠을 만들어 공을 나누어 담으면$\cdots (2)$ 됩니다.
  1. 상자를 $1$개 사용하는 경우
    1. $\NCR 31 = 3$입니다.
    2. 공 $4$개가 한 모둠이고, 이를 선택한 한 상자에 넣는 방법의 수는 $1$입니다.
    따라서 경우의 수는 $3\times 1 =3$입니다.
  2. 상자를 $2$개 사용하는 경우
    1. $\NCR 32 = 3$입니다.
    2. 공 $4$개를 $2$개의 모둠으로 만든 후, 이를 두 개의 상자에 나누어 담는 방법의 수를 구해야 합니다. 이는 $3+1$과 $2+2$가 있습니다. 전자의 경우 $\NCR{4}{3} = 4$, 후자의 경우 $\NCR{4}{2}\times \NCR{2}{2}\times \dfrac{1}{2!} = 3$입니다. 이 두 모둠을 두 상자에 나누어 넣는 방법의 수는 $2!$입니다. 따라서 $\left( 4+3 \right) \times 2! = 14$입니다.
    따라서 경우의 수는 $3 \times14 = 42$입니다.

  3. 상자를 세 개 사용하는 경우
    1. $\NCR 33 = 1$입니다.
    2. 공 $4$개를 $3$개의 모둠으로 만든 후, 이를 세 개의 상자에 나누어 담는 방법의 수를 구해야 합니다. 이는 $1+1+2$만 가능합니다. 모둠을 만드는 방법의 수는 $\NCR{4}{1}\times \NCR{3}{1}\times \NCR{2}{2}\times\dfrac{1}{2!}$이고, 이 세 모둠을 세 상자에 나누어 담는 경우의 수는 $3!$입니다. 따라서 $\NCR{4}{1}\times \NCR{3}{1}\times \NCR{2}{2}\times\dfrac{1}{2!}\times 3! = 36$입니다.
    따라서 경우의 수는 $1 \times 36=36$입니다.
정리하면 경우의 수는 $3+42+36 = 81$입니다. $81$이라 하니 주어진 상황이 $3^4$으로 계산되는 상황이 아니었을까 추측해볼 수 있습니다. 이를 다시 생각해보면, 공 $4$개가 세 상자 중 어느 상자에 들어갈지를 각각 선택하면 되므로 $3^4=81$이라고 볼 수 있습니다.

2-2) 공을 남김없이 다 넣고, 빈 상자가 없는 경우

빈 상자가 없는 경우는 $2-1)$의 \hcn3과 동치입니다. 따라서 경우의 수는 $36$입니다.

2-3) 공을 남길 수 있고, 빈 상자가 있을 수도 있는 경우

몇 개의 공을 사용하는지를 기준으로 분류해봅시다.
  1. 공을 사용하지 않는 경우
    공을 사용하지 않으므로, 상자가 모두 비어 있는 경우입니다. 따라서 경우의 수는 $1$입니다.
  2. 공을 $1$개 사용하는 경우
    어떤 공을 사용할지 고르는 경우의 수는 $\NCR{4}{1}$이고, 선택한 공이 들어갈 상자를 선택하는 경우의 수는 $3$입니다. 따라서 경우의 수는 $4\times 3 = 12$입니다.
  3. 공을 $2$개 사용하는 경우
    어떤 공을 사용할지 고르는 경우의 수는 $\NCR{4}{2}$이고, 선택한 두 공이 들어갈 상자를 각각 선택하는 경우의 수는 $3^2$입니다. 따라서 경우의 수는 $6\times 9 = 54$입니다.
  4. 공을 $3$개 사용하는 경우
    어떤 공을 사용할지 고르는 경우의 수는 $\NCR{4}{3}$이고, 선택한 세 공이 들어갈 상자를 각각 선택하는 경우의 수는 $3^3$입니다. 따라서 경우의 수는 $4\times 27 = 108$입니다.
  5. 공을 $4$개 사용하는 경우
    공을 남김없이 다 넣고, 빈 상자가 있을 수도 있는 경우와 동치입니다. 따라서 경우의 수는 $3^4 = 81$입니다.
정리하면 경우의 수는 $1+12+54+108+81 = 256$입니다. 그런데, 이것도 뭔가 합리적 의심이 드는 숫자입니다. 이는 공 $4$개가 각각 세 상자 중 들어갈 상자를 선택하거나, 들어가지 않으면 되는 상황이므로 $4^4 = 256$으로 계산한 것입니다.

2-4) 공을 남길 수 있고, 빈 상자가 없는 경우

빈 상자가 없으려면 공은 $3$개 또는 $4$개를 사용해야 합니다. 경우를 나누어 계산해봅시다.
  1. 공을 $3$개 사용하는 경우
    어떤 공을 사용할지 고르는 경우의 수는 $\NCR{4}{3}$이고, 세 개의 공은 상자 $3$개에 하나씩 들어가야 합니다. 따라서 경우의 수는 $4\times 3! = 24$입니다.
  2. 공을 $4$개 사용하는 경우
    공 $4$개를 $1$개, $1$개, $2$개로 나눈 $3$개의 모둠으로 만들고, 세 개의 모둠을 상자 $3$개에 하나씩 대응시키면 됩니다. 따라서 경우의 수는 $\NCR{4}{1}\times \NCR{3}{1}\times \dfrac{1}{2!}\times 3! = 36$입니다.
정리하면 경우의 수는 $24+36 = 60$입니다.

3) 공이 구별되지 않고, 상자가 구별되는 경우

각 상자에 공이 몇 개씩 들어갔는지만 고려하면 됩니다. 따라서 각 상자에 들어간 공의 개수를 각각 $x, \; y, \; z$라 하고 상황에 맞는 순서쌍 $\xyz xyz$의 개수를 구하면 됩니다. 따라서 전형적인 중복조합과 그 변형꼴입니다.

3-1) 공을 남김없이 다 넣고, 빈 상자가 있을 수도 있는 경우

$x+y+z=4$을 만족시키는 음이 아닌 정수 $x, \; y, \; z$의 모든 순서쌍 $\xyz xyz$의 개수를 구하면 됩니다. 따라서 구하는 경우의 수는 $\NHR{3}{4} = \NCR{6}{2} = 15$입니다.

3-2) 공을 남김없이 다 넣고, 빈 상자가 없는 경우

$x+y+z=4$을 만족시키는 자연수 $x, \; y, \; z$의 모든 순서쌍 $\xyz xyz$의 개수를 구하면 됩니다. 따라서 구하는 경우의 수는1$x'$, $y'$, $z'$을 도입하는 과정은 생략하겠습니다. $\NHR{3}{1} = \NCR{3}{1} = 3$입니다.

3-3) 공을 남길 수 있고, 빈 상자가 있을 수도 있는 경우

식 $x+y+z\le 4$를 만족시키는 음이 아닌 정수 $x, \; y, \; z$의 모든 순서쌍 $\xyz xyz$의 개수를 구해야 합니다. $0 \le x+y+z \le 4$이므로, $x+y+z$의 값에 따라 분류해봅시다.
  1. $x+y+z=0$인 경우, 경우의 수는 $\NHR{3}{0} = \NCR{2}{2} = 1$입니다.
  2. $x+y+z=1$인 경우, 경우의 수는 $\NHR{3}{1} = \NCR{3}{2} = 3$입니다.
  3. $x+y+z=2$인 경우, 경우의 수는 $\NHR{3}{2} = \NCR{4}{2} = 6$입니다.
  4. $x+y+z=3$인 경우, 경우의 수는 $\NHR{3}{3} = \NCR{5}{2} = 10$입니다.
  5. $x+y+z=4$인 경우, 경우의 수는 $\NHR{3}{4} = \NCR{6}{2} = 15$입니다.
정리하면 구하는 경우의 수는 $1+3+6+10+15=35$입니다.2이때 앞서 배운 바와 같이 새로운 음이 아닌 정수 $w$를 도입하여 $x+y+z+w=4$라 두어 부등호를 없애 계산하면 $\NHR{4}{4} = \NCR{7}{3} = 35$입니다. 이때 $w$는 상자에 담지 않고 남겨질 공의 개수라 생각할 수 있습니다.

3-4) 공을 남길 수 있고, 빈 상자가 없는 경우

식 $x+y+z\le 4$를 만족시키는 자연수 $x, \; y, \; z$의 모든 순서쌍 $\xyz xyz$의 개수를 구해야 합니다. 이때 $x+y+z\ge 3$이므로, $x+y+z$의 값을 기준으로 분류해봅시다.
  1. $x+y+z=3$인 경우, 경우의 수는 $\NHR{3}{0} = \NCR{2}{0} = 1$입니다.
  2. $x+y+z=4$인 경우, 경우의 수는 $\NHR{3}{1} = \NCR{3}{1} = 3$입니다.
정리하면 구하는 경우의 수는 $1+3=4$입니다.

$3-4)$도 $3-3)$의 주석과 마찬가지로 음이 아닌 정수 $w$를 도입하여 해결할 수도 있습니다. 그러나 $x+y+z+w = 4$인 경우를 구한 후 $w=2$, $3$, $4$인 경우를 빼주어야 하므로, 오히려 분류하여 푸는 것보다 복잡합니다.3그러나 만약 문제가 $x+y+z\le 10$과 같은 상황이었다면 $w$를 도입하는 것이 더 유리할 것입니다.

4) 공이 구별되지 않고, 상자가 구별되지 않는 경우

4-1) 공을 남김없이 다 넣고, 빈 상자가 있을 수도 있는 경우

자연수를 $3$개 이하로 사용해서 $4$를 만들어야 합니다. 이는 다음과 같습니다. \[\begin{align*} 4 &= 0+0+4 = 0+1+3\\ &= 0+2+2= 1+1+2 \end{align*}\] 따라서 경우의 수는 $4$입니다.

4-2) 공을 남김없이 다 넣고, 빈 상자가 없는 경우

세 개의 자연수를 사용해서 $4$를 만들어야 합니다. 이는 $4=1+1+2$의 경우뿐이므로, 경우의 수는 $1$입니다.

4-3) 공을 남길 수 있고, 빈 상자가 있을 수도 있는 경우

자연수를 $3$개 이하로 사용해서 $4$ 이하의 수를 만들어야 합니다. 경우를 나누어 계산해봅시다.
  1. 자연수를 $3$개 이하로 사용해서 $0$을 만드는 경우
    $0=0+0+0$입니다. 따라서 경우의 수는 $1$입니다.
  2. 자연수를 $3$개 이하로 사용해서 $1$을 만드는 경우
    $1=0+0+1$입니다. 따라서 경우의 수는 $1$입니다.
  3. 자연수를 $3$개 이하로 사용해서 $2$를 만드는 경우
    $2=0+0+2=0+1+1$입니다. 따라서 경우의 수는 $2$입니다.
  4. 자연수를 $3$개 이하로 사용해서 $3$을 만드는 경우
    자연수를 $3$개 이하로 사용해서 $3$을 만들어야 합니다. 이는 다음과 같습니다. \[\begin{align*} 3 = 0+0+3 = 0+1+2 =1+1+1 \end{align*}\] 따라서 경우의 수는 $3$입니다.
  5. 자연수를 $3$개 이하로 사용해서 $4$를 만드는 경우
    $4-1)$에서 구한 것과 동치입니다. 따라서 경우의 수는 $4$입니다.
정리하면 경우의 수는 $1+1+2+3+4=11$입니다.

4-4) 공을 남길 수 있고, 빈 상자가 없는 경우

세 개의 자연수를 사용해서 $4$ 이하의 수를 만들어야 합니다. 이는 $4=1+1+2$, $3=1+1+1$의 두 경우뿐이므로, 경우의 수는 $2$입니다.
  1. 1. $x'$, $y'$, $z'$을 도입하는 과정은 생략하겠습니다.
  2. 2. 이때 앞서 배운 바와 같이 새로운 음이 아닌 정수 $w$를 도입하여 $x+y+z+w=4$라 두어 부등호를 없애 계산하면 $\NHR{4}{4} = \NCR{7}{3} = 35$입니다. 이때 $w$는 상자에 담지 않고 남겨질 공의 개수라 생각할 수 있습니다.
  3. 3. 그러나 만약 문제가 $x+y+z\le 10$과 같은 상황이었다면 $w$를 도입하는 것이 더 유리할 것입니다.