[조합론]이항계수(Binomial_coefficient)는 무엇? 그리고 알고리즘 구현법에 대해 알아보자

🚑 들어가기 앞서

---

이전에, 순열과 조합에 대한 내용을 포스팅한 적이 있었다. 하지만 해당 내용이 기초에 입각하여 새로운 주제와 함께 조합에 대해서 이전보다 자세히 알아보고자 한다.

🤔 이항계수란??

---

이항계수는 조합론에서 중요한 개념으로, 주어진 집합에서 특정 개수의 원소를 선택하는 방법을 나타낸다.
우리가 흔히 5개의 카드에서 3개의 카드를 중복없이 순서에 상관없이 뽑는 경우의 수를 계산할 때 조합을 사용할 수 있다.

수학에서 이항계수는 이항(두 개의 항) 정리에서 계수로 나타나는 양의 정수를 뜻하는데,
보통, n ≥ k ≥ 0의 정수 쌍으로 나타냅니다. ex) {n,k}

계수: 일반적으로 어떤 변수에 곱해진 인자
ax^2 + b가 존재할 때, 여기서 계수는 a, 변수는 x, ^2은 차수, b는 상수를 의미

이항계수는 다음과 같이 나타낼 수 있는데,

${\displaystyle {\binom {n}{k}}={\frac {n\times (n-1)\times \cdots \times (n-k+1)}{k\times (k-1)\ 번 \cdots \times 1}},}$

이를 풀어보면 우리가 아는 조합의 공식을 볼 수 있다.

${\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!}}.}$

여기서, 해당 ${\displaystyle {\tbinom {n}{k}}.}$ 이는 이항 거듭 제곱 $(1 + x )^ n$의 다항식 전개 에서 $x ^k$ 항의 계수로 이 계수는 곱셈 공식으로 계산할 수 있다.

그러면, 해당 계수를 어떻게 곱셈 공식을 계산하는지 알아보자,
※현재 위키백과를 통해 글을 풀이 하고 있어, 여기에 나타나 있는 예시를 사용하겠다.

그럼 $(1+x) ^ 4$을 풀이해보면, 아래와 같이 풀 수 있다.

여기서 만약, n = 4(네제곱)이고 k = 2(x제곱)인 계수를 찾고 싶다면, 문제에 나와있듯, 6인 것을 구할 수 있다.

간략하게 이해한 바를 정리하자면, x가 총 n개 존재할 때, 거기서 x가 두 개인 값을 뽑는 다는 것이다.

이렇게 이해하고자 하니, 어렵다. 그래서 타 블로그에서 쉽게 이해할 수 있도록 설명한 부분을 발췌해서 얘기하면 -> [백준] 11050번: 이항 계수1 - Java [자바] Stranger's LAB

💢 이항 계수 정리

---

우리가, $(a + b) ^ 3$을 전개할 때, b를 이용하여 풀어보겠다.
$(a + b) ^ 3 = (a+b)(a+b)(a+b)$
= $(a + b1)(a + b2)(a + b3)$
= $(a ^ 2 + ab1 + ab2 + b1b2)(a + b3)$
= $a3 + (b1 + b2 + b3)a2 + (b1b2 + b2b3 + b3b1)a + b1b2b3$

이렇게 풀 수 있다고 한다. 그렇다면, 여기서 b의 관점에서 해당 식을 해석해보면

$a^3$항은 b의 관점에서{b1,b2,b3}중 한 개도 뽑지 않았기 때문에 0개
$a^2$항은 b의 관점에서{b1,b2,b3}중 한 개씩 뽑았기 때문에 3개
$a^1$항은 b의 관점에서{b1,b2,b3}중 두 개씩(b1b2, b2b3) 뽑았기 때문에 3개
$a^0$항은 b의 관점에서{b1,b2,b3}중 세 개를 모두 뽑았기 때문에 1개

이를 더 보자면,
b가 n개(b1,b2,b3) 존재할 때, r개(1개면 b1..b2.. 2개면 b1b2, b2b3..)를 뽑는다는 얘기이다. n개중에서 r개를 뽑는다라.. 아하!
우리는 여기서 조합론을 떠올릴 수 있다. 조합은 순서 상관없이 중복없이 선택하는 경우의 수이다.

즉, $a^3$항은 b를 한 개도 뽑지 않았기 때문에 $3C0$ 으로 구할 수 있고
$a^2$항은 b를 한 개씩 뽑았기 때문에 $3C1$ 으로,
$a^1$항은 b를 두 개씩 뽑았기 때문에 $3C2$ 으로,
$a^0$항은 b를 세 개씩 뽑았기 때문에 $3C3$ 이 되는 것이다.

그래서 이를 표현하자면 아래와 같이 구할 수 있다.

조합에서 중요한 것은! 순서와 상관없다는 것인데(※순열은 순서에 따라!)
이게 무슨말이냐, $b1b2$ 와 $b2b1$ 가 존재하는데, 만약 순서에 상관이 있다면 두 변수는 별개의 변수로 봐야 할 것이다.
하지만! 순서와 상관 없는 조합은, 해당 변수를 하나의 값으로 볼 수 있다.
$b1b2$ $b2b1$ 모두 같은 값으로 본다는 얘깅다.

필자는 수포자이다... 그래서 여기까지 알고자 하려니 머리가 아프다
그래서, 필자와 같이 수포자인 분은 아래의 공식을 꼭 기억하자 (전공이 수학과인 분은 필자 좀 알려주시면 감사하겠다.)

자! 그러면 이제 이항계수가 왜! 조합론에서 중요하며, 조합 공식을 사용하는지를 알아보았다.

참고로, 이항계수 $(1 + x) ^ n$를 풀어 계수의 값을 나열하면,
ex) $(1 + x) ^ 4$ = $1 + 4x + 6x^2 + 4x^3 + x^4$
파스칼의 삼각형 형태가 된다.

1, 4, 6, 4, 1 해당 값은 네제곱을 나타낸 값으로, 1, 3, 3, 1은 세제곱을 나타낸 값이다.

😂 조합의 다양한 공식

---

위에서 우리는 조합의 공식을 한 개 알아보았다. (아래 공식을 참고)

해당 공식을 달리 표현한 공식이 또 존재하는 데, 이를 보고자 한다.

파스칼의 공식

파스칼 삼각형을 만들 때, 구하는 공식으로
n번째 행과 파스칼 삼각형의 k번째 열을 표시할 때 다음과 같은 공식을 사용 ->${\displaystyle {\binom {n}{k}}}$
아까, 위에서 네제곱에 대해서 $x^2$를 구했을 때 ${\displaystyle {\tbinom {4}{2}}={\tfrac {4\times 3}{2\times 1}}={\tfrac {4!}{2!2!}}=6}$ 이렇게 구할 수 있는 것을 의미한다.

또한 여기서 ${\displaystyle {0 \choose 0}=1}, {\displaystyle {n \choose 0}=1} ,{\displaystyle {n \choose n}=1}$ 의 값을 가진다는 것을 기억해야 한다.

그 후 해당 위의 표기법을 사용하면 이전 단락의 구성을 아래와 같을 수 있다.

👀 알고리즘으로 구현한 조합 공식

---

1번 공식 ${\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!}}.}$

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        /*
         * 조합에 사용될 변수 N과 K
         * N개의 서로 다른 원소에서 순서 상관없이 중복없이 K개를 뽑는 경우의 수
         */
        int N = sc.nextInt();
        int K = sc.nextInt();

        System.out.println(combi(N) / (combi(K) * combi(N-K)));
    }
    /*
     * 조합 메서드(Combination의 약자인 combi 사용)
     * 조합은 팩토리얼로 이루어져있어, 재귀함수를 통해 n!를 구한다.
     */
    static int combi(int value) {
        if(value <= 1) {
            return 1;
        }

        return value * combi(value - 1);
    }

}

2번 공식 ${\displaystyle {n \choose k }={n-1 \choose k-1 }+{n-1 \choose k }}$

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        /*
         * 조합에 사용될 변수 N과 K
         * N개의 서로 다른 원소에서 순서 상관없이 중복없이 K개를 뽑는 경우의 수
         */
        int N = sc.nextInt();
        int K = sc.nextInt();

        System.out.println(combi(N, K));
    }
    /*
     * 조합 메서드(Combination의 약자인 combi 사용)
     * 조합은 팩토리얼로 이루어져있어, 재귀함수를 통해 n!를 구한다.
     */
    static int combi(int N, int K) {
        /*
         *해당 공식이 중요한 이유는 nCn 이거나, nC0일 때 우리는 해당 경우의 수는 1이라고 배웠다.
         * 이를 예외 처리 해준 것이다.
         */
        if(N == K || K == 0) {
            return 1;
        }

        return combi(N-1, K-1) + combi(N-1, K);
    }

}

👦 마치며

---

이전에 순열과 조합에 대해서 간략히 포스팅 한 바가 있는데, 조합을 판다면 이렇게 더 깊게 들어갈 수 있다는 것을 알게되면서 수준이 높아질 수록 포스팅 수준 역시 높아져야 하고 끝없이 공부해 나가야 한다는 점을 배울 수 있었던 시간이었다.

아무튼, 조합에 대해서 깊이는 아니더라도 조금 배울 수 있었고, 이항계수가 왜 조합공식을 사용하는지와 파스칼 삼각형에 대해서도 간략히 배워볼 수 있었던 점을 배우며

이항정리를 마치겠다. 그리고 추후 조합에 대해서 또다시 문제가 나온다면 아래의 공식이 가장 많이 사용된다고 하니 필히 기억하도록 하자

💜 참고자료

---

위키 백과 이항계수

위키 백과 파스칼 삼각형

[백준] 11050번: 이항 계수1 - Java [자바] Stranger's LAB