| [ QuizWit ] in KIDS 글 쓴 이(By): Sue (eXponent) 날 짜 (Date): 2005년 10월 24일 월요일 오전 10시 36분 19초 제 목(Title): Re: 오랜만에 문제 하나 -_-;; 그냥 surjective function의 개수 세라고 문제 낸거 아닌가요? Principle of inclusion and exclusion쓰면 되는거말이에요.. 5개집합에서 k개 집합으로 가는 surjective function의 개수는 위에 적힌 포함과 배제의 원리를 적용하면 5^k - ( k choose 1) 5^{k-1} + (k choose 2) 5^{k-2} -(k choose 3) 5^{k-3} + ... + (-1)^k (k choose k) 5^0 3개 색깔일 경우 5^3 - 3 * 5^2 + 3 * 5 - 1 4개일경우 5^4 - 4 * 5^3 + 6 * 5^2 - 4 * 5 + 1 일거 같네요.... ---------------------------------------- 뭔가 비슷해보이기는 한데, 중복허용할 때 4가지색으로 5칸을 모두 칠하는 경우의 수는 5^4가 아니라 4^5이지요 3^5 - 3C2 * 2^5 + 3C1*1 = 150 = 3*5!/3! + 3*5!/(2!*2!) 4^5 - 4C1 * 3^5 + 4C2 *2^5 - 4C3*1 = 240 = 4*5!/2! @sangil군 애키우느라 내공이 많이 줄은거 같네.. :P ; Capture & Consider |