11. 함수의 개수 & 조 나누기

---

---

11. 함수의 개수 & 조 나누기

 

---

🧸 01. Intro

       : 안녕하세요, 삐약 은지입니다😊

         오늘은 "함수의 개수와 조 나누기 문제"에 대해 살펴보겠습니다 

---

 

---

🧸 02. 함수의 개수 

       : 중복 순열의 대표적인 응용 문제 중 하나가 바로

         ‘함수의 개수’ 와 관련된 문제입니다

 

         함수란 집합 X의 각 원소가 집합 Y의 한 원소와 대응되는 관계로,

         다음 두 조건을 만족하면 함수라고 부릅니다

            ① 모든 정의역의 원소들이

            ② 각각 한 발씩 화살을 쏴야 합니

 

         이제 예시를 통해 함수의 개수와 관련된 문제를 살펴보겠습니다

 

         집합 X와 Y에 다음과 같이 원소들이 있다고 가정해보겠습니다

         이때 정의역 X의 원소들이 공역 Y의 원소로 화살을 쏘는 방법은 총 몇 가지일까요?

        정답은 5⁴입니다

        예를 들어, 정의역의 첫 번째 원소가 1이라면
        공역 Y={1,2,3,4,5} 중 어느 원소로도 화살을 쏠 수 있습니다

        그렇기에 5가지 선택이 가능합니다 (아래 사진)

        결국 이와 같은 방식으로 정의역의 모든 원소가 각각 5가지 경우를 가지므로,
        전체 경우의 수는 총 5⁴이 됩니다         

        따라서 위 개념은 중복 순열과 동일한 원리로 볼 수 있습니다

        (중복 순열: https://eunjiblog.tistory.com/55)

 

        이번에는 다른 예시에 대해 살펴보겠습니다 

        예를 들어 x1 < x2이면 f(x1) < f(x2)를 만족하는

        함수의 개수를 세야한다고 가정해보겠습니다 🤔

       위 문제는 정의역 X의 원소가 어떤 공역 Y의 원소에 화살을 쏘느냐에 따라,
       다음 정의역 원소가 선택할 수 있는 범위가 달라집니다

 

       예를 들어,

       정의역 X의 첫 번째 원소 1이 공역 Y의 원소 2에 화살을 쏘면,
       다음 원소 2는 3, 4, 5 중 하나만 선택할 수 있습니다

       반대로 첫 번째 원소가 공역의 3을 쏘게 된다면,
       두 번째 원소는 4, 5 중 하나만 선택할 수 있습니다

 

       결국 정의역 X의 원소가 어떤 값을 선택하느냐에 따라
       다음 원소가 선택할 수 있는 경우가 달라지므로,
       이는 서로 영향을 주고받는 종속 관계입니다

 

       이러한 종속 관계의 문제를 풀기 위해서는
       먼저 공역 Y 에서 정의역 X의 원소 개수만큼 원소를 뽑아주고,
       그 후에 문제에서 주어진 조건 "x1​ < x2 ​⇒ f(x1​) < f(x2​)" 을 만족하도록

       배치만 시켜주면 됩니다 

      

       따라서 정의역의 원소가 모두 화살을 쏴야 하므로,
       공역의 5개의 원소 중 정의역의 4개를 뽑는 경우의 수를 계산하면

       아래와 같은 결론이 나오게 됩니다 🙂

       결과적으로,

       "x1 < x2이면 f(x1) < f(x2)" 형태의 증가 함수나

       "x1 < x2이면 f(x1) > f(x2)" 형태 감소 함수는

       서로 종속 관계가 포함된 경우이기 때문에,
       공역에서 정의역의 원소 개수만큼 원소를 뽑아서 배치해주면 됩니다

 

       이제 한 문제만 더 풀어보겠습니다 😊

       x1 < x2이면 f(x1) ≤ f(x2)를 만족하는 함수는 총 몇 가지일까요?

      이때도 앞선 두 번째 문제와 마찬가지로,
      공역에서 정의역의 원소 개수만큼 뽑아 배치만 시켜주면 됩니다

      단, 이번에는 “같아도 된다”는 조건이 포함되어 있으므로
      중복이 허용되는 경우입니다

 

      따라서 단순한 조합(Combination)이 아닌
      중복 조합(Combination with Repetition)을 사용하여 계산하면 됩니다

      아래와 같이요!

---

 

---

🧸 03. 조 나누기

       : 이번에 배워볼 내용은 조합의 대표적인 유형 중 하나인 ‘조 나누기’ 문제입니다

 

         예를 들어, 6명이 있다고 가정해보겠습니다

         그런데 만약 이들을 3명, 2명, 1명으로 나누어 3개의 조를 만들고 싶다면,

         먼저 6명 중 3명을 뽑고, 남은 3명 중에서 2명을 뽑고,

         마지막 남은 1명을 뽑으면 됩니다 

         

 

         이번에는 6명을 2명씩 3개의 조로 나누고 싶다고 가정해보겠습니다

         만약 위 문제와 똑같이 푼다면 6명 중에 2명을 뽑고, 남은 4명 중에 2명을 뽑고,

         남은 2명 중에 2명을 뽑아서 조를 만들면 됩니다

         하지만 위 문제는 첫 번째 문제처럼 풀면 틀리게 됩니다 

         왜 그런걸까요? 🤔

 

         그 이유는, 위 방식대로 계산하면
         ‘순서를 고려하지 않는 조합’이 아니라
         ‘순서를 고려한 순열’이 되기 때문입니다

         즉, 자리 바꾸는 경우의 수가 포함되기 때문입니다

         아래와 같이요!

         때문에 같은 인원수로 조를 나눌 경우에는 

         본의 아니게 자리 바꾸는 경우의 수가 포함되어있기에, 

         이를 제거해주어야합니다

         

         이 예에서는 3개의 조(2명, 2명, 2명)가 모두 같은 크기이므로,
         서로 자리를 바꿀 수 있는 경우가 3!가지이기에,
         3!로 나누어 제거해 주면 됩니다 (아래 사진)

         이번에는 조금 더 복잡한 예를 살펴보겠습니다

         12명의 사람을 5명, 5명, 2명씩 나누어
         A, B, C 세 조로 구성할 때 가능한 경우의 수는 몇 가지일까요?

 

         먼저 12명을 3개의 조로 나누는 방법의 수는 

         12명 중 5명을 뽑고, 남은 7명 중 5명을 뽑은 후

         남은 2명에 대해서 2명을 뽑아주면 됩니다

         이때는 같은 인원수 5명으로 2번 뽑아주기에, 

         2!를 통해 5명의 조끼리 자리 바꾸는 경우의 수를 제거해줍니다
         이때 위 과정을 분할이라고 합니다

         이제 만들어진 세 개의 조를 A, B, C로 구분해주어야 합니다  🤔

         이 경우는 총 3! 입니다

         따라서 최종적으로 아래와 같이 식을 작성할 수 있습니다 

         이때 위 과정을 분배라고 합니다

---

 

---

🧸 04. 마무리

       : 오늘은 "함수의 개수와 조 나누기 문제"에 대해 살펴보았습니다

         사실 오늘까지가 경우의 수와 관련된 내용들이었습니다 

 

         다음 시간부터는 "확률"이라는 새로운 챕터에 대해 살펴보겠습니다 

         그럼 모두 안녕 ~👋

---