이항 계수: 정의, 구현 및 사용

소개

통계에서 이항 계수 는 분포와 함께 주로 사용됩니다. 그러나 계산 알고리즘에 적용하면 더 많은 것이 있습니다. 통계적 기계 학습 및 동적 프로그래밍 분야에서 광범위하게 사용됩니다. 이항 계수 에 대한 가장 기본적인 아이디어는 이항 분포에서 파생됩니다. 계수는 이항 정리, 따라서 이름에 사용됩니다.

기본적으로 이항 계수 에는 두 가지 정의가 있습니다. 그것들은 다음과 같습니다:

1. 조합을 찾기 위한 이항 계수

이항 계수 는 제공된 객체 풀에서 특정 수의 객체를 선택하는 방법의 수를 찾는 데 사용됩니다. 통계적으로 이항 계수 는 총 x개 개체에서 y개 개체를 선택할 수 있는 방법의 수를 찾는 데 도움이 될 수 있습니다. x에서 y 요소 하위 집합의 수입니다.

공식은 다음과 같이 파생됩니다.

x 개체에서 y 요소 하위 집합을 선택하기 위해 이항 계수 또는 가능한 조합은 xCy = x! / 야! * (xy)!

이 방법은 큰 개체 풀에서 가능한 조합의 수를 알아내야 하는 동안 매우 유용할 수 있습니다. 그러나 이것은 어디에 적용됩니까?

예시

15명의 학생이 있는 수업이 있다고 상상해보십시오. 경쟁을 위해 7명의 학생으로 구성된 팀을 선택해야 하는 경우 가능한 조합을 파악해야 합니다. 이항 계수 의 공식을 사용하는 동안 답을 쉽게 계산할 수 있습니다.

총 조합 = 15! / 7! * (15-7)! = 15! / 7! * 8!

이항 계수 가 사용되는 다른 많은 경우는 훨씬 더 복잡 합니다. 예를 들어, 선거를 위해 정당을 선택하거나 보다 구체적으로 신디케이트를 선택합니다. 통과시켜야 할 법안이 있고 당신이 여당의 다수를 차지한다고 상상해 보십시오. 귀하는 해당 법안에 대해 투표하는 데 필요한 표와 의원 수를 결정해야 합니다. 구성원은 여당과 야당 출신이어야 합니다. 조합을 적용하여 투표를 요청할 구성원을 찾을 수 있습니다.

읽어보기: 초보자를 위한 13가지 흥미로운 데이터 구조 프로젝트 아이디어 및 주제

2. 분포를 위한 이항 계수

이 정의는 보다 공식적이고 통계적입니다. 다항식 확장의 계수를 찾는 것을 의미합니다. 간단히 말해서, 이항 계수 C(a, b)는 (x+1)^a의 분포 형태에서 x^b의 계수로 정의될 수 있습니다.

예를 들어 이것을 이해합시다.

예시

예를 들어, (x+1)^2의 다항식 확장을 원합니다. 정의와 비교하면 =2 및 b=0,1,2가 됩니다.

수동 계산을 통해 (x+1)^2 = x^2 + 2x + 1의 확장을 알 수 있습니다. 그러나 이러한 계수는 어떻게 계산됩니까?

다음 공식을 적용해 보겠습니다.

x^0의 계수 = C(2,0)

x^1의 계수 = C(2,1)

x^2의 계수 = C(2,2)

따라서 확장은 다음과 같이 작성할 수 있습니다. C(2,0)x^0 + C(2,1)x^1 + C(2,2)x^2

공식은 그대로 유지됩니다. C(a,b) = 에이! / ㄴ! * (아)!

여기에 같은 공식을 적용하면 C(2,0) = 2! / 0! * (2-0)! = 1

C(2,1) = 2! / 1! * (2-1)! = 2

C(2,2) = 2! / 2! * (2-2)! = 1

이제 확장에서 이 값을 대입하면 x^2 + 2x + 1이 됩니다.

우리가 요구한 정확한 답변입니다. 작은 전개라서 간단한 곱셈 방식이 더 낫다고 느끼실 수 있습니다. 그러나 (x+1)^17의 확장된 형태를 계산해야 한다면 어떻게 될까요?

그렇게 여러 번 곱할 수 있는 방법은 없으며 지루한 작업이 될 것입니다. 그러나 이항 계수 의 개념을 사용 하면 작업이 간단해집니다.

읽기: Python 재귀 함수 개념: 초보자를 위한 Python 자습서

파이썬 구현

이항 계수 를 찾는 공식을 구현하기 전에 몇 가지 사항에 유의할 필요가 있습니다. 기능을 구현하는 데 필요한 두 부분이 있습니다. 하나는 하부구조이고, 두번째는 하부구조를 반복하는 기능이다.

C(a, b)의 값을 재귀적으로 찾기 위해 다음 하위 구조를 사용할 수 있습니다.

C(a, 0) 및 C(a, a) = 1

C(a, b) = C(a-1, b) + C(a-1, b-1)

이 두 공식을 사용하여 재귀 함수를 구현할 수 있습니다. 더 높은 수준의 확장에서는 많은 하위 구조가 반복된다는 점에 유의하십시오. 계산이 불필요하게 반복되면 계산 시간이 늘어날 수 있습니다. 따라서 효과적인 구현을 위해서는 이전의 모든 계산이 포함된 사전을 유지하는 것이 중요합니다.

이러한 유형의 구현은 O(a*b)의 시간 복잡도를 갖습니다. 공간 복잡도는 구현에 따라 다르지만 O(b)로 제한될 수 있습니다.

Python을 사용 중이고 함수를 직접 구현하지 않으려면 Python의 라이브러리 SciPy를 사용할 수 있습니다. SciPy의 특수 모듈에는 함수 binom()이 있습니다. 사용 방법은 다음과 같습니다.

scipy.special.binom(a, b)을 입력하기만 하면 동일한 값이 제공됩니다. 예를 들어, scipy.special.binom(4,3); 출력을 줄 것입니다 - 4.0

용법

이항 계수 의 주요 용도 는 이미 위에서 논의되었습니다. 이항 계수 는 이항 분포의 기초뿐만 아니라 분석에도 사용됩니다. 덜 알려진 사용법은 이항 계수 가 파스칼 삼각형의 항목을 나타내는 것입니다. 이러한 유형의 통계적 이유는 이항 계수 를 이해하는 데 필요합니다.

또한 체크아웃: 실제 예제를 사용한 Python의 이항 분포

결론

따라서 이것은 통계 및 구현 관점에서 이항 계수 에 관한 것이었습니다. 조합 및 확장 계수 계산에 대한 이항 계수 의 두 가지 정의에 대해 논의했습니다 . 구현 전략과 라이브러리 구현이 논의되었습니다.

특히 분포와 함께 볼 때 이항 계수 에 대한 더 많은 통계적 적용이 있습니다. 따라서 핵심 기계 학습 및 분석 알고리즘과 같은 고급 통계 기반 개념으로 향하기 전에 이항 계수 에 대해 배우는 것이 중요합니다 .

기계 학습에 대해 자세히 알아보려면 IIIT-B 및 upGrad의 기계 학습 및 AI PG 디플로마를 확인하세요. 이 PG 디플로마는 일하는 전문가를 위해 설계되었으며 450시간 이상의 엄격한 교육, 30개 이상의 사례 연구 및 과제, IIIT- B 동문 자격, 5개 이상의 실용적인 실습 캡스톤 프로젝트 및 최고의 기업과의 취업 지원.