경우의 수 공나누기 비교분석 | 중복순열 | 중복조합 | 분할분배

 n개의 공을 m개의 상자에 담는 다양한 방법을 통해서 각각의 상황에 맞는 차이를 분석해 보도록 하자.

 

$ \blacksquare $ 상자 구분(O) |  공 구분(O) | 빈 상자가 있어도 되는 경우

$$ {}_{m}\Pi  _{n} =m^n $$

 

Example 1

서로 다른  5개의 공 1,2,3,4,5를 서로 다른 상자 A,B,C에 넣는 방법을 수를 구하여라.(단, 빈상자가 있어도 된다.)

[해설]  이 경우는 중복순열 문제가 된다.
    1번 공을 담는 방법은 3가지
    2번 공을 담는 방법은 3가지
    3번 공을 담는 방법은 3가지

    4번 공을 담는 방법은 3가지
    5번 공을 담는 방법은 3가지

 $$ 3 \times 3 \times 3 \times 3 \times 3 ={}_{3}\Pi  _{5} $$ 

 

$ \blacksquare $ 상자 구분(O) |  공 구분(O) | 빈 상자가 없는 경우
$$ m! \times {\rm S} (n, m) $$

 

Example 1

서로 다른 5개의 공 1,2,3,4,5를 서로 다른 상자 A,B,C에 넣는 방법을 수를 구하여라.(단, 적어도 한 개 이상 넣는다.)

[해설]   이 경우는 분배 문제가 된다.
    먼저 공을 (1, 1, 3), (1, 2, 2)로 나눈(분할) 다음 서로 다른 상자 A, B, C에 넣어야 한다.(분배)

   

    $ (i) (1,1,3) \Rightarrow {}_{5} \rm C  _{1}\times {}_{4} \rm C  _{1}\times {}_{3} \rm C  _{3}\times \displaystyle \frac{1}{2!} \times 3!=60 $ (가지)

   

    $  (ii) (1,2,2) \Rightarrow {}_{5} \rm C  _{1}\times {}_{4} \rm C  _{2}\times {}_{2} \rm C  _{2}\times \displaystyle \frac{1}{2!} \times 3!=90 $ (가지)

      $ \therefore 60+90=150 $ (가지)

 

    | 다른풀이 | $ 3! \times {\rm S} (5, 3)=150 $  (가지)

 

     참고로 집합의 분할수를 나타내는 $  {\rm S} (n, m)$는 다른 포스팅을 참고하기 바란다.

     또  $ m! \times {\rm S} (n, m) $는 전사함수의 개수와 같다. 

 

$ \blacksquare $ 상자 구분(O) |  공 구분(X) | 빈 상자가 있어도 되는 경우
$$ {}_{m} {\rm H}_{n} $$

 

Example 3

똑같은 5개의 공을 서로 다른 상자 A,B,C에 넣는 방법을 수를 구하여라.(단, 빈상자가 있어도 된다.)

[해설]   이 경우는 중복조합 문제가 된다.
    상자 A,B,C에 넣은 공의 개수를 각각 \( x,y,x \)라 하면

      \( x+y+z=5\)   (단, \( x\geq 0,  y\geq 0,  z\geq 0,   \;  x,y,z\)는 정수 )

        $ {}_{3} {\rm H}_{5}=21 $ (가지)

 

 

$ \blacksquare $ 상자 구분(O) |  공 구분(X) | 빈 상자가 없는 경우
$$ {}_{m} {\rm H}_{n-m} $$

 

Example 4

똑같은 5개의 공을 서로 다른 상자 A,B,C에 넣는 방법을 수를 구하여라.(단, 적어도 한 개 이상 넣는다.)

[해설]   이 경우는 조건이 있는 중복조합 문제가 된다.
    상자 A,B,C에 넣은 공의 개수를 각각 \( x,y,x \)라 하면
     \( x+y+z=5\)   (단, \( x\geq 1,  y\geq 1,  z\geq 1,   \;  x,y,z\)는 정수 )

        $ {}_{3} {\rm H}_{5-3}=6 $ (가지)

 

 

$ \blacksquare $ 상자 구분(X) |  공 구분(O) | 빈 상자가 없는 경우
$$ {\rm S} (n, m) $$

 

Example 5

서로 다른 5개의 공 1,2,3,4,5를 똑같은 세 상자에 넣는 방법을 수를 구하여라.(단, 각 상자에 적어도 한 개 이상 넣는다.)

[해설]  이 경우는 분할 문제가 된다.
    상자는 구분이 되지 않기 때문에  공을 (1, 1, 3), (1, 2, 2)로 분할하면 된다.

   

    $ (i) (1,1,3) \Rightarrow {}_{5} \rm C  _{1}\times {}_{4} \rm C  _{1}\times {}_{3} \rm C  _{3}\times \displaystyle \frac{1}{2!}=10 $ (가지)

   

    $  (ii) (1,2,2) \Rightarrow {}_{5} \rm C  _{1}\times {}_{4} \rm C  _{2}\times {}_{2} \rm C  _{2}\times \displaystyle \frac{1}{2!} =15 $ (가지)

      $ \therefore 10+15=25 $ (가지)

 

    | 다른풀이 | $  {\rm S} (5, 3)=25 $ (가지)

 

이후 경우는 참고만하기 바란다. 시험에는 출제되지 않는다. 또 출제 되더라도 그냥 세는 게 빠르다.

 

$ \blacksquare $ 상자 구분(X) |  공 구분(X) | 빈 상자가 없는 경우
$$ {\rm P} (n, m) $$

 

자연수의 분할을 나타내는 $  {\rm P} (n, m)$는 다른 포스팅을 참고하기 바란다.

 

Example 6

똑 같은 5개의 공을 똑같은 세 상자에 넣는 방법을 수를 구하여라.(단, 각 상자에 적어도 한 개 이상 넣는다.)

[해설] 5개의 공을 3뭉치로 나누어 주면 된다.

     $ 5=3+1+1=2+2+1 $

        \(2\) (가지)

   | 다른풀이 |   $ {\rm P} (5, 3) =2$

 

 

$ \blacksquare $ 상자 구분(X) |  공 구분(X) | 빈 상자가 있어도 되는 경우
$$ {\rm P} (n, 1)+{\rm P} (n, 2)+\cdots + {\rm P} (n, n) $$

 

Example 7

똑 같은 5개의 공을 똑같은 세 상자에 넣는 방법을 수를 구하여라.(단, 빈상자가 있어도 된다.)

[해설]  상자 1개에 담는 방법   5=5                       1 (가지)

          상자 2개에 담는 방법   5=4+1=3+2             2 (가지)

              상자 3개에 담는 방법   5=3+1+1=2+2+1      2 (가지)

              1+2+2=5(가지)

   | 다른풀이 |  $ {\rm P} (5, 1)+{\rm P} (5, 2)+ {\rm P} (5, 3) =5 $

 

$ \blacksquare $ 상자 구분(X) |  공 구분(O) | 빈 상자가 있어도 되는 경우
$$ {\rm S} (n, 1)+{\rm S} (n, 2)+\cdots + {\rm S} (n, n) $$

 

Example 8

서로 다른 5개의 공 1,2,3,4,5를 똑같은 세 상자에 넣는 방법을 수를 구하여라.(단, 빈상자가 있어도 된다.)

[해설]  상자 1개에 담는 방법                          1 (가지)

          상자 2개에 담는 방법

           $ (i) \;(1,4) \Rightarrow {}_{5} \rm C  _{1}\times {}_{4} \rm C  _{4} =5 $ (가지)

           $ (ii) \;(2,3) \Rightarrow {}_{5} \rm C  _{2}\times {}_{3} \rm C  _{3} =10 $ (가지)

                 $  5+10=15 $ (가지)

          상자 3개에 담는 방법

          $ (i) \; (1,1,3) \Rightarrow {}_{5} \rm C  _{1}\times {}_{4} \rm C  _{1}\times {}_{3} \rm C  _{3}\times \displaystyle \frac{1}{2!} =10 $ (가지)

 

          $ (ii) \; (1,2,2) \Rightarrow {}_{5} \rm C  _{1}\times {}_{4} \rm C  _{2}\times {}_{2} \rm C  _{2}\times \displaystyle \frac{1}{2!} =15 $ (가지)

          $  10+15=25 $ (가지)

          따라서  $ 1+ 15+25=41 $(가지)

| 다른풀이 |  $ {\rm S} (5, 1)+{\rm S} (5, 2)+ {\rm S} (5, 3) =41 $

나만의 수학 비법

 

n개의 공을 m개의 상자에 넣는 방법의 수를 표로 만들어 보면 다음과 같다.

	빈상자(O)	빈상자(X)
공 구분(O) 상자 구분(O)	$m^n$	$m! {\rm S} (n, m) $
공 구분(X) 상자 구분(O)	${}_{m} {\rm H}  _{n}$	${}_{m} {\rm H}  _{n-m}$
공 구분(O) 상자 구분(X)	$ {\rm S} (n, 1)+{\rm S} (n, 2)+\cdots + {\rm S} (n, n) $	$ {\rm S} (n, m) $
공 구분(X) 상장 구분 (X)	$ {\rm P} (n, 1)+{\rm P} (n, 2)+\cdots + {\rm P} (n, n) $	$ {\rm P} (n, m) $