경우의 수에서 배치문제(placing problem)로 골머리를 앓고있습니다.

choco6의 이미지

요즘 어떤 일 때문에 확률공부를 하고 있습니다.
확률이론 책 사서 열심히 읽고 있는데 확률의 기초인 챕터1에서부터 진도가 더뎌지는군요..-_-;;
본격적인 확률이론에 들어가기 전에 경우의 수를 거쳐가게 됩니다.
경우의 수에서 단순 조합과 순열에 대해서는 잘 이해했는데 배치문제에서 골머리를 앓고 있네요..

배치문제에서 단골로 나오는게 테이블에 사람 배치하기와 항아리에 공 넣는 문제죠..
제가 이해를 못하고 있는 부분은,
공의 색에 구분이 없고 항아리에 넣을 수 있는 공의 수에는 제한이 없지만 적어도 한 개 이상의 공을 넣어야 하는 경우입니다.

공의 수를 k개라고 하고 항아리의 수를 n개라고 했을 때 k는 n보다는 크거나 같겠죠.
정작 이와 같은 경우에 대하여 경우의 수를 구하려고 하니 간단한 문제가 아니네요..

가령, 5개의 항아리에 8개의 같은 색의 공을 넣는 경우의 수를 구하는 문제..
책에서는 8개의 공 사이에 7개의 틈이 있고 5개이 항아리에도 4개의 틈이 있으므로 틈 사이의 관계를 이끌어 내야 한다고 설명합니다.

그런데 종이에 아무리 끄적여 봐도 위 문제와 공 사이의 틈과 항아리 사이의 틈이 무슨 관계인지 잘 이해가 안되더라는겁니다..-_-;;
그렇다고 제 주위에 이걸 물어볼 만한 사람도 없고....

혹시 확률이론 잘 아시는 분... 이해하기 쉽게 설명해 주실 수 있는 분 계신가요??

익명 사용자의 이미지

http://sungod0.egloos.com/3158395

식사하는 철학자 문제.. 세마포어 관련
함 읽어보시는것도

익명 사용자의 이미지

항아리 5개(A, B, C, D, E) 중 중복을 허용하여 8개를 뽑는다.
H(5, 8) = C(13, 8) = 13! / (8! * 5! ) = 1287

choco6의 이미지

왜 그 공식을 쓰셨는지 모르겠지만....
하여튼 공식도 틀리고 답도 틀리셨는데요..-_-;;

익명 사용자의 이미지

아... 좀 실수가 있었네요...
H(5, 8) = C(12, 8) = 12! / (8! * 4!) = 495
이것은 맞는지 확인 좀 부탁합니다.

choco6의 이미지

그 역시 수식도 답도... 다 안맞는데요... -_-;;

klyx의 이미지

익명님께서는 중복조합을 적어주셨는데, 중복조합은 빈항아리도 허용하는 경우를 포함합니다.
지금 빈항아리는 제외해야하므로 우선 각 항아리에 하나씩 다 넣어둔 다음에 나머지를 분배하면됩니다.
다섯개에 하나씩 넣었으므로 3개의 공이 남아있고, 이 3개를 다섯개의 항아리에 중복을 포함하여 넣으면되므로 5H3을 계산하면됩니다.
틈새의 갯수를 생각하여 중복조합을 증명하는 내용은 널렸구요.

niuzeta의 이미지

가령, 5개의 항아리에 8개의 같은 색의 공을 넣는 경우의 수를 구하는 문제..

?????

...And all in war with Time for love of you,
As he takes from you, I engraft you new.

-Sonnet XV
전산계획설계사 지망 영문학과생

익명 사용자의 이미지

빈 항아리는 제외해야 한다는 조건이 있더군요.
위의 xylosper님이 설명을 잘 해주셨습니다.

yyongpil의 이미지

확률 공부한 지가 오래전이라 기억이 가물가물한데요... 그 틈새를 이용하라는 이야기는...
공이 8개 00000000 로 표현한다면
공을 항아리에 넣었을 때를 표현할 때 separator 로 | 를 사용한다고 합시다.
그러면 0000|0|0|0|0 이런식으로 표현이 가능하죠.
이건 경우의 수 중의 하나일 뿐이고...
000|00|0|0|0 이것도 하나... 이런식으로 공을 항아리 틈새의 갯수로 나누면 됩니다.
공식은 당장 잘 생각나지 않지만 책 읽어본다면 어렵지 않은 문제일텐데요...

choco6의 이미지

맞습니다!!!
yyongpil님의 말씀처럼 칸막이 개념으로 생각하니까 명쾌하게 이해가 가는군요~

k개의 공이 있을때 공을 일렬로 쭉 세우면 틈새에 k-1개의 칸막이가 생기겠죠.
그리고 n개의 항아리는 n-1개의 틈새가 생길겁니다.
그럼 항아리에 공을 배치하는 것은 결국 k-1개의 칸막이에서 n-1개의 separator를 선택하는 문제로 생각할 수 있겠군요!!!!

이렇게 간단한 문제를 2~3일 동안 고민했다니...ㅠㅠ
yyongpil님의 글 덕분에 비로소 이해할 수 있게되었습니다..
감사합니다..
학교때 수학 잘하셨을것 같은데요~^^

yyongpil의 이미지

아핫, 별 말씀을... :)