N 컨테이너에서 M 객체의 분포

Question

컨테이너의 용량을 나타내는 요소를 가진 N 크기 배열이 주어진다 ... M 컨테이너가 얼마나 많은 방법으로 분포되어 각 컨테이너가 끝에 채워지는지. 예 :

for arr={2,1,2,1} N=4 and M=10 there comes out be 35 ways. 

이 질문에 대해 도와주세요.

Answer 1

먼저 컨테이너 크기의 합계를 계산하십시오. 나는 당신의 경우 2 + 1 + 2 + 1 = 6을 P라고합시다. M에서 P 객체를 선택하는 방법의 수를 찾으십시오. 첫 번째 객체에는 M 개의 선택 사항이 있고, 두 번째 객체에는 M-1, 두 번째 객체에 대해서는 M- 이것은 M * (M-1) * ... (M-p + 1) 또는 M!/(M-P)! 그러면 예를 들어 원하는 것보다 많은 주를 얻을 수 있습니다.

1 2 | 3 | 4 5 | 6 
2 1 | 3 | 4 5 | 6 

q가 있습니다! 우리는 factorial (arr [0])과 factorial (arr [1]) 등으로 나눌 필요가 있으므로 q 개의 객체에 q 객체를 배열하는 방법 등이 있습니다.이 경우 2로 나누십시오! * 1! * 2! * 1! = 4.

저는 35보다 훨씬 큰 숫자를 받았습니다. 10!/4! = 151200은 4로 나누면 37800이되므로 질문을 올바르게 이해했는지 확실하지 않습니다.

---

아, 그래서 당신은 N의 정수 N1, N2를 찾을 필요가있는 문제를보고 ..., 윈 있도록 N2 + N1 + ... + 윈 = M과 N1> = 편곡 [1], N2 > = arr [2].

아주 간단하게 보이고 위와 같습니다. 첫 번째 P 약을 가져다가 학생들에게 최소한의 수, arr [1], arr [2] 등을줍니다. MP 약이 남았을 때 R로합시다.

본질적으로 N> 0이 R에 합쳐집니다. 이것은 고전적인 문제입니다. 자사의 문제로 내가 당신을 위해 대답을하지 않지만 우리는 N = 4를 어기면, R = 4 대답 아래로 당신이 패턴

를 볼 수 있습니다

4 0 0 0  - 1 case starting with 4 
3 1 0 0  - 3 cases starting with 3 
3 0 1 0 
3 0 0 1 
2 2 0 0  - 6 cases 
2 1 1 0 
2 1 0 1 
2 0 2 0 
2 0 1 1 
2 0 0 2 

1 3 0 0  - 10 cases 
1 2 1 0 
1 2 0 1 
1 1 2 0 
1 1 1 1 
1 1 0 2 
1 0 3 0   
1 0 2 1 
1 0 1 2 
1 0 0 3 

0 4 0 0  - 15 cases 
0 3 1 0 
0 3 0 1 
0 2 2 0 
0 2 1 1 
0 2 0 2 
0 1 3 0 
0 1 2 1 
0 1 1 2 
0 1 0 3 
0 0 4 0 
0 0 3 1 
0 0 2 2 
0 0 1 3 
0 0 0 4 

당신은 번호 인식해야 1, 3, 6, 10, 15.