Mixing
Show that the number of possible compositions for n ∈ $mathbb{N}$ is $2^{n−1}$ [duplicate]
$begingroup$
This question already has an answer here:
number of ordered partitions of integer
3 answers
Let n ∈ $mathbb{N}$ be a natural number, an ordered set of positive integers $(λ_{1},...,λ_{k})$ such that $λ_{1},+ , ... , + , λ_{k} = n$ is called a composition for n ∈ $mathbb{N}$. These integers are not necessarily distinct. Show that the number of possible compositions for n ∈ $mathbb{N}$ is $2^{n−1}$.
Example: the number $n = 4$ has the following 8 compositions
$(4),(3, 1),(2, 2),(2, 1, 1),(1, 3),(1, 2, 1),(1, 1, 2),(1, 1, 1, 1)$.
combinatorics
asked Jan 18 at 0:33
Kishan PatelKishan Patel
174
$endgroup$
marked as duplicate by lulu, Mike Earnest, Lord Shark the Unknown, José Carlos Santos, Claude Leibovici Jan 18 at 7:07
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |
$begingroup$
This question already has an answer here:
number of ordered partitions of integer
3 answers
Let n ∈ $mathbb{N}$ be a natural number, an ordered set of positive integers $(λ_{1},...,λ_{k})$ such that $λ_{1},+ , ... , + , λ_{k} = n$ is called a composition for n ∈ $mathbb{N}$. These integers are not necessarily distinct. Show that the number of possible compositions for n ∈ $mathbb{N}$ is $2^{n−1}$.
Example: the number $n = 4$ has the following 8 compositions
$(4),(3, 1),(2, 2),(2, 1, 1),(1, 3),(1, 2, 1),(1, 1, 2),(1, 1, 1, 1)$.
combinatorics
asked Jan 18 at 0:33
Kishan PatelKishan Patel
174
$endgroup$
marked as duplicate by lulu, Mike Earnest, Lord Shark the Unknown, José Carlos Santos, Claude Leibovici Jan 18 at 7:07
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |
$begingroup$
This question already has an answer here:
number of ordered partitions of integer
3 answers
Let n ∈ $mathbb{N}$ be a natural number, an ordered set of positive integers $(λ_{1},...,λ_{k})$ such that $λ_{1},+ , ... , + , λ_{k} = n$ is called a composition for n ∈ $mathbb{N}$. These integers are not necessarily distinct. Show that the number of possible compositions for n ∈ $mathbb{N}$ is $2^{n−1}$.
Example: the number $n = 4$ has the following 8 compositions
$(4),(3, 1),(2, 2),(2, 1, 1),(1, 3),(1, 2, 1),(1, 1, 2),(1, 1, 1, 1)$.
combinatorics
asked Jan 18 at 0:33
Kishan PatelKishan Patel
174
$endgroup$
This question already has an answer here:
number of ordered partitions of integer
3 answers
Let n ∈ $mathbb{N}$ be a natural number, an ordered set of positive integers $(λ_{1},...,λ_{k})$ such that $λ_{1},+ , ... , + , λ_{k} = n$ is called a composition for n ∈ $mathbb{N}$. These integers are not necessarily distinct. Show that the number of possible compositions for n ∈ $mathbb{N}$ is $2^{n−1}$.
Example: the number $n = 4$ has the following 8 compositions
$(4),(3, 1),(2, 2),(2, 1, 1),(1, 3),(1, 2, 1),(1, 1, 2),(1, 1, 1, 1)$.
This question already has an answer here:
number of ordered partitions of integer
3 answers
combinatorics
combinatorics
asked Jan 18 at 0:33
Kishan PatelKishan Patel
174
asked Jan 18 at 0:33
Kishan PatelKishan Patel
174
asked Jan 18 at 0:33
Kishan PatelKishan Patel
174
asked Jan 18 at 0:33
Kishan PatelKishan Patel
174
asked Jan 18 at 0:33
Kishan PatelKishan Patel
174
174
marked as duplicate by lulu, Mike Earnest, Lord Shark the Unknown, José Carlos Santos, Claude Leibovici Jan 18 at 7:07
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by lulu, Mike Earnest, Lord Shark the Unknown, José Carlos Santos, Claude Leibovici Jan 18 at 7:07
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
By using stars and bars, the number of partitions into $k$ groups is $n-1choose k-1$.
Adding up, and using the binomial theorem, we get $sum_{k=1}^n{n-1choose k-1}=sum_{k=0}^{n-1}{n-1choose k}=2^{n-1}$.
answered Jan 18 at 0:44
Chris CusterChris Custer
13.9k3827
$endgroup$
$begingroup$
Or more directly, in the unrestricted problem you have $n-1$ places to choose to place a bar or not.
$endgroup$
– Daniel Schepler
Jan 18 at 0:48
$begingroup$
@DanielSchepler very nice.
$endgroup$
– Chris Custer
Jan 18 at 0:52
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
By using stars and bars, the number of partitions into $k$ groups is $n-1choose k-1$.
Adding up, and using the binomial theorem, we get $sum_{k=1}^n{n-1choose k-1}=sum_{k=0}^{n-1}{n-1choose k}=2^{n-1}$.
answered Jan 18 at 0:44
Chris CusterChris Custer
13.9k3827
$endgroup$
$begingroup$
Or more directly, in the unrestricted problem you have $n-1$ places to choose to place a bar or not.
$endgroup$
– Daniel Schepler
Jan 18 at 0:48
$begingroup$
@DanielSchepler very nice.
$endgroup$
– Chris Custer
Jan 18 at 0:52
add a comment |
$begingroup$
By using stars and bars, the number of partitions into $k$ groups is $n-1choose k-1$.
Adding up, and using the binomial theorem, we get $sum_{k=1}^n{n-1choose k-1}=sum_{k=0}^{n-1}{n-1choose k}=2^{n-1}$.
answered Jan 18 at 0:44
Chris CusterChris Custer
13.9k3827
$endgroup$
$begingroup$
Or more directly, in the unrestricted problem you have $n-1$ places to choose to place a bar or not.
$endgroup$
– Daniel Schepler
Jan 18 at 0:48
$begingroup$
@DanielSchepler very nice.
$endgroup$
– Chris Custer
Jan 18 at 0:52
add a comment |
$begingroup$
By using stars and bars, the number of partitions into $k$ groups is $n-1choose k-1$.
Adding up, and using the binomial theorem, we get $sum_{k=1}^n{n-1choose k-1}=sum_{k=0}^{n-1}{n-1choose k}=2^{n-1}$.
answered Jan 18 at 0:44
Chris CusterChris Custer
13.9k3827
$endgroup$
By using stars and bars, the number of partitions into $k$ groups is $n-1choose k-1$.
Adding up, and using the binomial theorem, we get $sum_{k=1}^n{n-1choose k-1}=sum_{k=0}^{n-1}{n-1choose k}=2^{n-1}$.
answered Jan 18 at 0:44
Chris CusterChris Custer
13.9k3827
edited Jan 18 at 0:49
answered Jan 18 at 0:44
Chris CusterChris Custer
13.9k3827
answered Jan 18 at 0:44
Chris CusterChris Custer
13.9k3827
answered Jan 18 at 0:44
Chris CusterChris Custer
13.9k3827
13.9k3827
$begingroup$
Or more directly, in the unrestricted problem you have $n-1$ places to choose to place a bar or not.
$endgroup$
– Daniel Schepler
Jan 18 at 0:48
$begingroup$
@DanielSchepler very nice.
$endgroup$
– Chris Custer
Jan 18 at 0:52
add a comment |
$begingroup$
Or more directly, in the unrestricted problem you have $n-1$ places to choose to place a bar or not.
$endgroup$
– Daniel Schepler
Jan 18 at 0:48
$begingroup$
@DanielSchepler very nice.
$endgroup$
– Chris Custer
Jan 18 at 0:52
$begingroup$
Or more directly, in the unrestricted problem you have $n-1$ places to choose to place a bar or not.
$endgroup$
– Daniel Schepler
Jan 18 at 0:48
$begingroup$
Or more directly, in the unrestricted problem you have $n-1$ places to choose to place a bar or not.
$endgroup$
– Daniel Schepler
Jan 18 at 0:48
$begingroup$
@DanielSchepler very nice.
$endgroup$
– Chris Custer
Jan 18 at 0:52
$begingroup$
@DanielSchepler very nice.
$endgroup$
– Chris Custer
Jan 18 at 0:52
add a comment |
