반복과 함께 집합에서 가능한 모든 고유 한 하위 집합의 총 수를 어떻게 계산합니까?

Question

중복 요소가 포함 된 집합 ** S가 주어지면 각 하위 집합이 고유 한 S의 가능한 모든 하위 집합의 총 수를 어떻게 결정할 수 있습니까?

예를 들어 S = {A, B, B}라고하고 K를 모든 하위 집합의 집합이라고하면 K = {{}, {A}, {B}, {A, B}, {B , B}, {A, B, B}} 따라서 | K | A = {A, B}, {A}, {B}, B = {A}, {A}, {B}, {A}, A} {A, A, B}, {A, A, B, B}} 및 그에 따른 | K | = 9

S가 실제 세트이고 유일한 요소 만 갖는다면 쉽게 볼 수 있습니다. = 2^| S |.

이 값을 계산하는 공식은 무엇입니까? | K | 모든 하위 집합을 생성하지 않고 "집합"S (중복 포함)가 있습니까?

** 기술적으로 세트가 아닙니다.

Answer 1

모든 (주파수 + 1)의 곱을 취하십시오.

예를 들면, {A는, B는 B}, 대답은 (+ 1 2) * [로서는 수 (+ 1) 기지국의 수 = 6

입니다 (2 + 1) * (2 + 1) = 9입니다.

이 작동하는 이유는 다음과 같이 정의 할 수 있습니다. {A, B, B}에 대해, {A = 0, B = 0}, {A = 0, B = 1}, {0,2}, {1 , 0}, {1,1}, {1,2}

counts [] 내의 각 숫자에 대해 (해당 객체의 빈도 +1) 가능한 값이 있습니다. (0..frequencies)

따라서, 총 가능성 수는 모두 (주파수 + 1)의 곱입니다.

"모든 고유"의 경우도 이렇게 설명 할 수 있습니다. 각 개체가 한 번 나타나므로 대답은 (1 + 1)^| S | = 2^| S |.

Answer 2

이 문제는 적절한 방식으로 볼 때 간단하게 해결할 수 있다고 주장합니다. 요소의 순서에 관심이 없으며 요소의 하위 집합에만 표시되는지 여부는 신경 쓰지 않습니다.

각 요소가 세트에 나타나는 횟수를 계산합니다. 하나의 요소 집합 {A}에 대해 몇 개의 하위 집합이 있습니까? 분명히 두 세트 만 있습니다. 이제 A와 구별되는 또 다른 요소 B를 추가하여 집합 {A, B}을 형성한다고 가정 해보십시오. 모든 세트의 목록을 매우 쉽게 작성할 수 있습니다. 우리가 만든 모든 세트를 A 만 사용하고 B의 사본을 0 개 또는 1 개 추가하십시오. 실제로 세트 수는 두 배가됩니다. 분명히 N 유도 요소를 사용하여 N 개의 별개 요소에 대해 총 세트 수가 단지 2^N임을 보여줄 수 있습니다.

몇 가지 요소가 여러 번 나타납니다. 따라서 {A, A, A}의 세 복사본을 가진 집합을 고려하십시오. 얼마나 많은 하위 집합을 만들 수 있습니까? 다시 말하지만, 이것은 간단합니다. A의 0, 1, 2 또는 3 개의 사본을 가질 수 있으므로 순서가 중요하지 않으므로 하위 집합의 총 수는 4입니다.

일반적으로 요소 A의 N 사본의 경우 N + 1 개의 가능한 하위 집합으로 끝납니다. 이제는 B의 복사본 몇 개를 M으로 추가하여 이것을 확장하십시오. 따라서 B의 A와 M 복사본의 N 개의 복사본이 있습니다. 전체 하위 집합의 수는 몇 개입니까? 그렇습니다, 이것은 또한 명확하게 보인다. A 만있는 모든 가능한 하위 집합 (N + 1 개가 있음)에 B의 0과 M 사본을 추가 할 수 있습니다.

따라서 B의 A 사본과 M 사본의 N 사본이있을 때 하위 세트의 총 수는 간단합니다. 그것은 (N + 1) * (M + 1)이어야합니다. 다시 말하자면, 우리는 귀납적 인 주장을 사용하여 총 부분 집합의 수를 그러한 용어의 산물임을 보여줄 수 있습니다. 각 개별 요소에 대한 복제의 총 수를 계산하고 1을 더하고 제품을 가져옵니다.

{A, B, B} 세트가 어떻게되는지 확인하십시오. 우리는, 우리가이 정말 수학 질문이 아닌 프로그래밍 질문 3 * 3 = 9