/중복조합문제

인터넷에서 프로그래밍 질문글을 봤다가, 프로그래밍 자체는 쉽게 해결이 되는데, 정작 수학적으로 쉽게 풀 수 있는 공식이 도통 떠오르지 않는다. 이미 트위터, 페이스북에 호들갑 떨긴 했지만, 기록 보존 차원에서 적어둠.

문제는 다음과 같다:

1) (구분할 수 없는) 공이 6개
2) 공을 담을 수 있는 자리가 6곳
3) 한 자리에 담을 수 있는 공의 갯수는 최대 3개
이 때 공을 나누어 담을 수 있는 경우의 수는?

즉, 각 자리에 A,B,...,F 로 이름을 붙이면, 다음과 같은 조합들이 있다는 얘기:

A B C D E F
-----------
3 3 0 0 0 0
3 2 1 0 0 0
2 1 0 1 2 0
...
1 1 1 1 1 1

만약 3)번 제한이 없다면, 이 문제는 A부터 F까지 6개의 원소를 가지고 중복을 허용해서 6번 뽑는 문제와 같고, 이 답은 다음과 같다:

(빨간색 6이 원소의 갯수, 파란색 6이 자릿수)

문제는 3)번 제한인데... 이것 때문에 위처럼 한번에 풀 수 있는 공식을 구하지 못해 며칠째 심란함. 공식이 있긴 있는 건지도 모르겠음.

내가 생각할 수 있는 최선의 풀이는, 한 자리에 들어가는 공의 갯수에 따라서 경우를 나누어서

1) 3-3 : 6자리 중 2자리를 택하면 되니까 6C2 = 15
2) 3-2-1 : 6자리 중에 1자리 선택해서 3개, 남은 5자리 중 1자리 선택해서 2개, 남은 4자리 중 1자리 선택해서 1개 = 6C1 * 5C1 * 4C1 = 120
3) 3-1-1-1 : (이하 계산 생략) 60
4) 2-2-2 : 20
5) 2-2-1-1 : 90
6) 2-1-1-1-1 : 30
7) 1-1-1-1-1-1 : 1
다 합치면 336가지

이렇게 풀 수는 있는데, 공과 자리의 갯수나 자리당 공의 최대 갯수가 수십개가 된다면..? 경우를 나누는 것도 엄청난 일이 된다.

또는 위에서 말한 중복조합 6H6에서 한자리에 4개 이상이 들어가는 경우를 빼려고 해도, 역시 공의 갯수에 따라 4-2, 4-1-1, 5-1, 6 이렇게 네가지 경우를 각각 계산하여 빼야 한다.

인터넷을 뒤져봐도 "중복 조합", "Combination with repetition" 이렇게 검색하면 3)번 제한이 없는 경우의 설명이나 예제는 많은데... 뒤에 검색어를 어떻게 넣어야 저 제한이 있는 경우가 나오는지 찾기가 힘들다.

아니면 저렇게 나누어 푸는 게 최선인 걸까? 다른 방법이 없다거나, 있긴 하지만 대학교 이상의 과정에서 다루는 복잡한 식이 필요하다거나...

수학 잘 하는 사람의 도움을 받아보려고 몇 군데 질문글을 올렸는데 아직 소득이 없음

• [클리앙] : 여긴 글이 워낙 많이 올라와서, 당일날 답이 안 나왔으니 글렀고,
• [KLDP] : 여기서 링크를 하나 받았는데 읽을 엄두가 안 나는구나;;;;
• [Pomp On Math & Puzzle 방명록] : 결국 좀 전에 수학과 교수님의 블로그에 질문을 올림.

[Pomp On Math & Puzzle 방명록]에 박부성 교수님 답글. 역시 저렇게 경우를 나누어 셀 수 밖에 없다고 하심. 아 속 시원하다ㅋ

Comments & Trackbacks