TheoremBase

Counting Subsets

A set with n elements has C(n,k) subsets with k elements and 2^n subsets in all, and a sum over its subsets of a function of their size can be grouped by size.

Statement

In the setting of Finite Combinatorics: Notation, let AA be a finite set with #A=n\#A=n, and let k∈N0k\in\mathbb{N}_{0}.

Subsets of a given size. Pk(A)\mathcal{P}_{k}(A) is finite, and

#Pk(A)=(nk).\#\mathcal{P}_{k}(A)=\binom{n}{k}.

All subsets. P(A)\mathcal{P}(A) is finite, and

#P(A)=2n.\#\mathcal{P}(A)=2^{n}.

Grouping by size. For every map g:N0→Rg:\mathbb{N}_{0}\to\mathbb{R},

∑S∈P(A)g(#S)=∑j=0n(nj)g(j).\sum_{S\in\mathcal{P}(A)}g(\#S)=\sum_{j=0}^{n}\binom{n}{j}g(j).

Proofs

Log in to submit a proof.

Loading...

Citations

Loading…

Dependencies

Loading…

Related

0 relations

Curated associations between results. These are editable and subjective — they do not replace the dependency graph, which is derived from the references in the text.

No relations recorded yet.

Comments

Log in to comment.

Loading…