항아리에 n개의 공이 담겨있음. 각 공에 번호가 써있음 (1부터 n까지).
항아리에서 k번 공을 꺼내서 공에 적힌 번호를 순서대로 기록함 (x1, ..., xk). 공을 다시 항아리에 넣지 않는다고 가정하면, 총 갯수는 n * (n-1) * ... * (n-(k-1)) = n! / (n-k)! 이 되는건 누구나 아는 문제.
만일, 그 번호의 공이 처음 뽑힌 공이면 다시 항아리에 넣고, 두번째로 다시 뽑힌 공이라면 다시 항아리에 넣지 않는다고 가정하면, 이 때 총 갯수는 어떻게 셀 수 있음?
예를 들어, n=4이고, k=2라면, 첫번째 꺼낸 공이 1이면 (1,,,)가 되고, 1은 다시 넣음. 다시 꺼낸 공이 또 1이라면 (1,1,,)이 되고, 1은 다시 넣지 않음. 따라서 그 이후는 (1,1,2,3)이 될 수도 있고 하지만, 1은 그 뒤에 다시 못나옴.
n, k에 대해 총 경우의 수를 closed form으로 나타낼 수 있을까?
케이스 쪼개야 됨. m=[k/2] 면 번복이 최대 m번 발생할거고 번복이 i번 발생할때의 경우의 수들을 더하면됨. i=0,...,m 이게 깔끔한 형태가 되는지는 글쎄
(1+x+x^2)^n에서 x^k 계수 찾는건데 closed form이 알려진건 없을거고 n이 고정되면 저 식 전개해서 k를 한번에 찾거나, k가 고정되어있을땐 n에 대한 k차 다항식으로 점화식 풀어서 적는거 자첸 가능한데, 그냥 n,k 주어질때 하나 계산하는건 combination 계산한거보다 빠르진 않음.
순서를 기록하니까 아니지 않나요?
아 그네 잘못이해함. 그럼 그냥 nCr k! /2^r r <= k/2 합한거네. 여전히 그 이상의 뭐는 안되고. 알려진 뭐랑 같지도 않는거로 보임
문제 괜찮은거 같아 보이나요? 오늘 공부하다 갑자기 생각나서 만들어봤는데..
네. 그런데 예시에서 k = 4이지 않나요?