분할에서 가능한 조합의 수

Question

주어진 크기 n의 집합 S는 크기 n1, .., nk의 클래스 (s1, .., sk)로 분할됩니다. 당연히 n = n1 + ... + nk를 유지합니다.

각 조합에 정확히 각 클래스의 요소가 하나씩 포함되도록이 분할의 요소를 결합 할 수있는 방법의 수를 찾는 데 관심이 있습니다.

s1에서 n1 개 요소를 선택하고 s2에서 n2 개 요소를 선택할 수 있으므로 임의의 n1에 대해 max (n1 * .. * nk)에 대한 솔루션을 찾고 있는데 n1 + .. + nk = n.

선형 최적화 문제라는 느낌이 들지만,이 자료를 학부생으로 배운 이후로 너무 오랜 시간이 걸렸습니다. 누군가가 이것을 계산하는 방법을 기억하기를 바랍니다.

Answer 1

floor(n/k)^(k - n mod k)*ceil(n/k)^(n mod k) 

- MarkusQ

P.S. 예를 들어 S = {1,2,3,4}, n = 4, k = 2라고하면 다음과 같이 나타납니다.

floor(4/2)^(2 - 4 mod 2)*ceil(4/2)^(4 mod 2) 
floor(2)^(2 - 0)*ceil(2)^(0) 
2^2 * 2^0 
4 * 1 
4 

... 원하는대로.

명확히하기 위해이 수식은 최대 순열 수와 함께 파티셔닝에 의해 생성 된 순열 수를 제공합니다. 당연히 다른 덜 적합한 분할이있을 것입니다.

주어진 둘레에 대해 가장 큰 면적의 사각형은 정사각형에 가장 가까운 직사각형입니다 (더 높은 치수에서는 동일 함). 이는 가능한 한 길이가 같은 변을 원한다는 것을 의미합니다 예 : 평균 길이를 반올림 또는 올림). 수식은 다음과 같을 수 있습니다.

(length of short sides)^(number of short sides) 
times 
    (length of long sides)^(number of long sides) 

이는이 제약 조건을 충족시키는 하이퍼 - 사각형의 볼륨입니다.

이렇게하면 최대 분할을 구성하는 방법을 알 수 있습니다.

Answer 2

각 파티션에서 요소 하나의 조합 수를 찾고 계십니까?

간단히 말해서 n1 * n2 * ... * nk입니다.

편집 : 또한 별도의 질문을 것 같다 :

을 감안할 때 N, I는 N1, N2를 할당 어떻게 ..., nk는 그들의 제품이 극대화되도록. 변수가 곱 해져서 실제로 선형 최적화 문제는 아닙니다.

이것은 미적분에 의해 해결 될 수 있습니다. 즉, Lagrange 승수를 사용하여 제약 조건과 함께 각 변수에서 부분 방부제를 복용함으로써 해결할 수 있습니다.

결과는 n1 .. nk가 가능한 한 동일한 크기에 가까워 야합니다.

if n is a multiple of k, then n_1 = n_2 = ... = n_k = n/k 

otherwise, n_1 = n_2 = ... = n_j = Ceiling[n/k] 
     and n_j+1 = ... = n_k = floor[n/k] 

기본적으로 가능한 한 균일하게 요소를 파티션에 배포하려고합니다. 그들이 균등하게 나뉘면 위대합니다. 그렇지 않다면 우리는 최대한 균등하게 나눕니다. 남은 것은 무엇이든 첫 번째 파티션에 여분의 요소를 각각 씁니다. (첫 번째 파티션 일 필요는 없으며 그 선택은 상당히 임의적입니다.)이 방법으로 두 파티션이 소유 한 요소의 수의 차이는 많아야 1이됩니다.

피투성이 세부는 :

이것은 우리가 극대화하고자하는 제품 기능입니다 :

P = N1 * 우리는 라그랑주 승수를 사용하여 새로운 함수를 정의

북한

* ... N2 :

람다 = P + 1 (N - N1 - N2 ... -nk)

그리고 취할 편미분의 L

및 L로 -

dLambda/dn_i = P/n_i :

dLambda/DL = N - N1 -N2 ... -nk

K 개의 n_i 각 변수 모든 부분 미분을 = 0으로 설정하면 k + 1 방정식의 시스템을 얻고이를 풀면 n1 = n2 = ...이됩니다.= 북한

몇 가지 유용한 링크 :

Lagrange Multipliers

Optimization