/sci/ - Science & Math

>>15216384
You are counting how many ways you can choose a subset [math]A[/math] of [math]\{ 1, 2, \ldots, n\}[/math] and then a subset [math]B[/math] of [math]A[/math] with cardinality [math]m[/math].
Hence, [math]B[/math] is a subset of [math]\{1, 2, \ldots, n\}[/math] with cardinality [math]m[/math]. Each subset of [math]\{1, 2, \ldots, n\}[/math] has probability of [math](1/2)^m[/math] of containing [math]B[/math], hence for each [math]B[/math] there are [math]2^n / (1/2)^m = 2^{n - m}[/math] subsets of [math]\{1, 2, \ldots, n\}[/math] containing it. There are [math]\displaystyle \binom{n}{m}[/math] [math]B[/math] candidates, so the solution is [math]\displaystyle 2^{n - m} \binom{n}{m}[/math]