Timeline for find number of disjoint subsets
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 9 at 14:54 | comment | added | RobPratt | Another way to see $3^n-1$ is to note that each element $i\in M$ appears in $U$, $V$, or neither ($3^n$ choices), but we must exclude $U=V=\emptyset$. | |
| Mar 9 at 14:50 | history | edited | RobPratt |
edited tags
|
|
| Mar 9 at 12:26 | comment | added | Aig | I missed $U\ne V$, the answer is $3^n-1$ indeed. | |
| Mar 9 at 12:04 | comment | added | Jean-Claude Colette | Once you have chosen U a subset of C (2^k possibilities), there is only one way to choose the complementary V of U in C to form a partition of C. So in total $\sum_{k=1}^{n}\left(\matrix{n\\k}\right)2^k=\sum_{k=0}^{n}\left(\matrix{n\\k}\right)2^k-1=3^n-1$ | |
| Mar 9 at 11:14 | comment | added | Aig | If you factor in that $k$ can be $0$, then $\sum_{k=0}^n{n\choose k}2^{n-k}$ is the right answer, since it’s equal to $3^n$ due to the binomial theorem. | |
| Mar 9 at 11:10 | history | edited | macman | CC BY-SA 4.0 |
deleted 3 characters in body
|
| Mar 9 at 10:58 | history | asked | macman | CC BY-SA 4.0 |