Attempt Let $x$ be any variable $X+0=n ; X+Y=n ; X+Y+Z=n ; \dots; X+Y+Z+A+\dots=n$ (sum of n-1 terms); $1+1+1+.......+1=n$ (sum of n terms). So total number of ways= $$(n-1) C (1-1)+(n-1) C (2-1)+\dots+(n-1) C (n-1)$$ This equation is correct & gives correct answer if we have a value of $n$ but equation in $n$ needs to be proven equal to $2^{n-1}$. Answer is $$2^{n-1}$$ What can be further done to solve it ?
$\begingroup$
$\endgroup$
3
-
2$\begingroup$ Do you mean this? en.wikipedia.org/wiki/Partition_(number_theory) $\endgroup$– Matti P.Commented Jan 18, 2021 at 12:44
-
$\begingroup$ See Partition function $p(n)$ (but usually $2+1$ and $1+2$ are not distinguished there). $\endgroup$– Dietrich BurdeCommented Jan 18, 2021 at 12:45
-
4$\begingroup$ If $2+1$ and $1+2$ are two different cases, then the objects you're counting are called compositions rather than partitions. $\endgroup$– bofCommented Jan 18, 2021 at 12:56
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Write down $n$ marks (e.g. "$x$"). Between any two $x$ you may put a "$+$" or not. Now replace each block of $x$ by their count, and you obtain a valid solution. (E.g., for $n=6$ we start with $xxxxxx$, then obtain prhaops $xx+x+xxx$ and finally $2+1+3$). As there are $n-1$ gaps between two consequtive $x$'s, we have $$2^{n-1}$$ ways to proceed.
answered Jan 18, 2021 at 12:50
$\begingroup$
$\endgroup$
Also to close the gap between your answer and the desired form, the combinatorial identity: $$ \sum_{k=0}^n \binom nk = 2^n$$ is fairly well known; the options of choosing any number of objects from a set is clearly counting the powerset of $n$ objects.
