Làm cách nào để bạn tính tổng số của tất cả các tập con duy nhất có thể từ một tập hợp có lặp lại?

Question

Đưa ra một tập hợp ** S chứa các phần tử trùng lặp, làm cách nào để xác định tổng số tất cả các tập con có thể có của S, trong đó mỗi tập hợp con là duy nhất.

Ví dụ: giả sử S = {A, B, B} và cho K là tập hợp của tất cả các tập con, sau đó K = {{}, {A}, {B}, {A, B}, {B , B}, {A, B, B}} và do đó | K | = 6.

Ví dụ khác sẽ là nếu S = {A, A, B, B}, thì K = {{}, {A}, {B}, {A, B}, {A, A} , {B, B}, {A, B, B}, {A, A, B}, {A, A, B, B}} và cho phép | K | = 9

Thật dễ dàng để thấy rằng nếu S là tập hợp thực, chỉ có các phần tử duy nhất, thì | K | = 2^| S |.

Công thức tính giá trị này | K | đưa ra một "thiết lập" S (với các bản sao), mà không tạo ra tất cả các tập con?

** Không phải là một bộ kỹ thuật.

Answer 1

Lấy sản phẩm của tất cả (tần số + 1).

Ví dụ, trong {A, B, B}, câu trả lời là (1 + 1) [số lượng Như] * (2 + 1) [số lượng Bs] = 6.

Trong ví dụ thứ hai, đếm (A) = 2 và đếm (B) = 2. Vì vậy, câu trả lời là (2 + 1) * (2 + 1) = 9.

Lý do công trình này là bạn có thể xác định bất kỳ tập hợp con dưới dạng vectơ đếm - cho {A, B, B}, các tập con có thể được mô tả là {A = 0, B = 0}, {A = 0, B = 1}, {0,2}, {1 , 0}, {1,1}, {1,2}.

Đối với mỗi số đếm [] có (tần số của đối tượng đó + 1) giá trị có thể có. (0..frequencies)

Do đó, tổng số khả năng là sản phẩm của tất cả (tần số + 1).

Trường hợp "tất cả duy nhất" cũng có thể được giải thích theo cách này - có một lần xuất hiện của từng đối tượng, vì vậy câu trả lời là (1 + 1)^| S | = 2^| S |.

Answer 2

Tôi sẽ cho rằng vấn đề này rất đơn giản để giải quyết, khi được xem theo cách thích hợp. Bạn không quan tâm đến thứ tự của các yếu tố, chỉ cho dù chúng xuất hiện trong một tập hợp con của không.

Đếm số lần mỗi phần tử xuất hiện trong tập hợp. Đối với một phần tử được đặt {A}, có bao nhiêu tập hợp con? Rõ ràng chỉ có hai bộ. Bây giờ giả sử chúng ta đã thêm một phần tử khác, B, khác biệt với A, để tạo thành tập hợp {A, B}. Chúng tôi có thể tạo danh sách tất cả các bộ rất dễ dàng. Lấy tất cả các bộ mà chúng ta đã tạo ra bằng cách sử dụng chỉ A, và thêm vào số không hoặc một bản sao B. Trong thực tế, chúng ta tăng gấp đôi số lượng các bộ. Rõ ràng chúng ta có thể sử dụng cảm ứng để cho thấy rằng đối với N yếu tố riêng biệt, tổng số bộ chỉ là 2^N.

Giả sử một số thành phần xuất hiện nhiều lần? Hãy xem xét các thiết lập với ba bản sao của A. Vì vậy, {A, A, A}. Bạn có thể tạo bao nhiêu tập con? Một lần nữa, điều này rất đơn giản. Chúng tôi có thể có 0, 1, 2 hoặc 3 bản sao của A, vì vậy tổng số tập con là 4 vì thứ tự không quan trọng.

Nói chung, đối với N bản sao của phần tử A, chúng tôi sẽ kết thúc với N + 1 tập con có thể. Bây giờ, mở rộng điều này bằng cách thêm vào một số, M, các bản sao của B. Vì vậy, chúng tôi có N bản sao của A và M bản sao của B. Có bao nhiêu tổng tập con? Vâng, điều này có vẻ rõ ràng. Đối với mọi tập con có thể chỉ có A trong đó (có N + 1 trong số chúng) chúng ta có thể thêm từ 0 đến M bản sao B.

Vì vậy, tổng số tập con khi chúng tôi có N bản sao của bản sao A và M của B rất đơn giản. Nó phải là (N + 1) * (M + 1). Một lần nữa, chúng ta có thể sử dụng một đối số quy nạp để chỉ ra rằng tổng số tập con là sản phẩm của các thuật ngữ đó. Chỉ đếm tổng số bản sao cho mỗi phần tử riêng biệt, thêm 1 và lấy sản phẩm.

Xem điều gì xảy ra với tập hợp {A, B, B}. Chúng tôi nhận được 2 * 3 = 6.

Đối với bộ {A, A, B, B}, chúng tôi nhận được 3 * 3 = 9.