파티션에서 가능한 조합 수

Question

주어진 크기 N은 N1, .., NK 크기의 클래스 (S1, .., SK)로 분할됩니다. 당연히 n = n1+...+nk를 유지합니다.

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

S1, S2에서 N2 요소에서 N1 요소를 선택할 수 있으므로, 나는 임의의 N1 용 Max (n1*..*nk)에 대한 솔루션을 찾고 있습니다. = n.

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

Answer 1

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

- Markusq

추신 : 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입니다.

편집 : 당신은 또한 별도의 질문을하는 것 같습니다.

N1, N2, ..., NK를 어떻게 할당하여 제품이 최대화되도록 할당하려면 어떻게해야합니까? 변수가 곱하기 때문에 실제로 선형 최적화 문제가 아닙니다.

Lagrange Multipliers를 사용하여 각 변수에서 제약 조건을 사용하여 각 변수에서 부분적 인면을 취함으로써 일부 미적분학에 의해 해결 될 수 있습니다.

결과는 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 개입니다.

gory 세부 사항:

이것이 최대화하려는 제품 기능입니다.

P = N1*N2*... NK

Lagrange 승수를 사용하여 새로운 기능을 정의합니다.

lambda = p + l (n -n1 -n2 ... -nk)

각각의 k n_i 변수에서 부분 파생 상품을 사용하십시오.

dlambda/dn_i = p/n_i -l

그리고 L에서 :

dlambda/dl = n -n1 -n2 ... -nk

모든 부분 파생물 = 0을 설정하면 K + 1 방정식 시스템을 얻고 해결하면 N1 = N2 = ... = NK를 얻을 수 있습니다.

유용한 링크 :

Lagrange 승수

최적화