Mixing
Binomial coefficients and words of $n$ bits, why this works?
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
I read this on a webpage about the binomial coefficients:
If $0,1$ are bits and $k$ is the amount of "ones" $nchoosek$ gives the quantity of strings of length $n$ which have exactly $k$ ones in it.
Why is this true? I thought until now that the binomial coefficient $achooseb$ gave only informations about the numbers of ways you can choose a subsets of cardinality $b$ from one whose cardinality is $a$.
combinatorics
edited Aug 6 at 21:26
Davide Morgante
1,930220
asked Aug 6 at 21:23
Baffo rasta
15110
add a comment |Â
up vote
1
down vote
favorite
I read this on a webpage about the binomial coefficients:
If $0,1$ are bits and $k$ is the amount of "ones" $nchoosek$ gives the quantity of strings of length $n$ which have exactly $k$ ones in it.
Why is this true? I thought until now that the binomial coefficient $achooseb$ gave only informations about the numbers of ways you can choose a subsets of cardinality $b$ from one whose cardinality is $a$.
combinatorics
edited Aug 6 at 21:26
Davide Morgante
1,930220
asked Aug 6 at 21:23
Baffo rasta
15110
Or more briefly than the answers (and like you asked in a comment): It works because there are $nchoose k$ ways to choose a set of $k$ positions to put the $1$s in from among the $n$ available positions in a length-$n$ string.
– Steve Kass
Aug 6 at 21:36
That was what I wanted to know! Thanks.
– Baffo rasta
Aug 6 at 21:37
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I read this on a webpage about the binomial coefficients:
If $0,1$ are bits and $k$ is the amount of "ones" $nchoosek$ gives the quantity of strings of length $n$ which have exactly $k$ ones in it.
Why is this true? I thought until now that the binomial coefficient $achooseb$ gave only informations about the numbers of ways you can choose a subsets of cardinality $b$ from one whose cardinality is $a$.
combinatorics
edited Aug 6 at 21:26
Davide Morgante
1,930220
asked Aug 6 at 21:23
Baffo rasta
15110
I read this on a webpage about the binomial coefficients:
If $0,1$ are bits and $k$ is the amount of "ones" $nchoosek$ gives the quantity of strings of length $n$ which have exactly $k$ ones in it.
Why is this true? I thought until now that the binomial coefficient $achooseb$ gave only informations about the numbers of ways you can choose a subsets of cardinality $b$ from one whose cardinality is $a$.
combinatorics
edited Aug 6 at 21:26
Davide Morgante
1,930220
asked Aug 6 at 21:23
Baffo rasta
15110
edited Aug 6 at 21:26
Davide Morgante
1,930220
edited Aug 6 at 21:26
Davide Morgante
1,930220
edited Aug 6 at 21:26
Davide Morgante
1,930220
1,930220
asked Aug 6 at 21:23
Baffo rasta
15110
asked Aug 6 at 21:23
Baffo rasta
15110
asked Aug 6 at 21:23
Baffo rasta
15110
15110
Or more briefly than the answers (and like you asked in a comment): It works because there are $nchoose k$ ways to choose a set of $k$ positions to put the $1$s in from among the $n$ available positions in a length-$n$ string.
– Steve Kass
Aug 6 at 21:36
That was what I wanted to know! Thanks.
– Baffo rasta
Aug 6 at 21:37
add a comment |Â
Or more briefly than the answers (and like you asked in a comment): It works because there are $nchoose k$ ways to choose a set of $k$ positions to put the $1$s in from among the $n$ available positions in a length-$n$ string.
– Steve Kass
Aug 6 at 21:36
That was what I wanted to know! Thanks.
– Baffo rasta
Aug 6 at 21:37
Or more briefly than the answers (and like you asked in a comment): It works because there are $nchoose k$ ways to choose a set of $k$ positions to put the $1$s in from among the $n$ available positions in a length-$n$ string.
– Steve Kass
Aug 6 at 21:36
Or more briefly than the answers (and like you asked in a comment): It works because there are $nchoose k$ ways to choose a set of $k$ positions to put the $1$s in from among the $n$ available positions in a length-$n$ string.
– Steve Kass
Aug 6 at 21:36
That was what I wanted to know! Thanks.
– Baffo rasta
Aug 6 at 21:37
That was what I wanted to know! Thanks.
– Baffo rasta
Aug 6 at 21:37
add a comment |Â
3 Answers
3
active
oldest
votes
up vote
1
down vote
accepted
Consider the following transformation: let $B$ be a set of cardinality $b$ and let us represent a subset $A$ of $B$ as a binary string of length $b$ with a one if the corresponding element is taken and a zero otherwise.
E.g.
$$B= u, v, w, x, y, z$$
$$A= u, v, zleftrightarrow 110001.$$
Now how many strings of length $b$ having $a$ ones are there ?
answered Aug 6 at 21:30
Yves Daoust
111k665205
add a comment |Â
up vote
1
down vote
Let's rephrase the problem as the number of ways that a sequence of length $n$ can have $k$ ones.
In some sense, this becomes a combinatorics problem since we are selecting $k$ positions out of the $n$ to be "ones", and the rest to be zeros.
So, that explains why the result is $nchoosek$, since we are $textitchoosing$ $k$ ones from $n$ positions.
answered Aug 6 at 21:27
Rushabh Mehta
1,060114
1
My initial thought was that in this case $nchoosek$ could be giving me the number of different groups of indexes that could be taken by the 1 digits in a single string of $n$ bits. Is this correct?
– Baffo rasta
Aug 6 at 21:30
Well, not exactly. $nchoose k$ gives you the number of ways to pick $k$ things from a group of $n$ things. In this case, you are picking $k$ places out of $n$ places to put 1s, and the rest will be assigned 0s.
– Rushabh Mehta
Aug 6 at 21:32
add a comment |Â
up vote
0
down vote
Here's a bijective argument, let $mathcalP_k([n])$ be the set of subsets of $1, dots, n$ of size $k$, and let
$$
S = (b_1, dots, b_n) in 0,1^n
$$
Now, the mapping
$$
Lambda: mathcalP_k([n]) longrightarrow S \
A mapsto Lambda(A)
$$
with
$$
Lambda(A)_i := cases1 text if i in A\0 text if i not in A
$$
is bijective.
In effect, if $A neq B$, wlog there exists $j in A$ such that $j not in B$. Thus, $Lambda(A)_j = 1 neq 0 = Lambda(B)_j$ and so $Lambda(A) neq Lambda(B)$ which proves that $Lambda$ is injective. Finally, if $b in S$, you can check that $A_b := j in [n] : b_j = 1$ has size $k$ and verifies $Lambda(A_b) = b$.
answered Aug 6 at 21:33
Guido A.
3,851624
Well, I kind of get if this is the case what I am missing! That one is the argument of the next chapter of my book!
– Baffo rasta
Aug 6 at 21:35
This is a very common type of 'combinatorial proof'. Say you want to prove that $n = m$ for some natural numbers $n,m$; then sometimes these can be interpreted as the sizes of certain sets. Thus, $n = m$ will happen iff there is a bijection between these. That motivates this type of arguments. I'll add a proof of my claim for completion's sake :)
– Guido A.
Aug 6 at 21:37
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
Consider the following transformation: let $B$ be a set of cardinality $b$ and let us represent a subset $A$ of $B$ as a binary string of length $b$ with a one if the corresponding element is taken and a zero otherwise.
E.g.
$$B= u, v, w, x, y, z$$
$$A= u, v, zleftrightarrow 110001.$$
Now how many strings of length $b$ having $a$ ones are there ?
answered Aug 6 at 21:30
Yves Daoust
111k665205
add a comment |Â
up vote
1
down vote
accepted
Consider the following transformation: let $B$ be a set of cardinality $b$ and let us represent a subset $A$ of $B$ as a binary string of length $b$ with a one if the corresponding element is taken and a zero otherwise.
E.g.
$$B= u, v, w, x, y, z$$
$$A= u, v, zleftrightarrow 110001.$$
Now how many strings of length $b$ having $a$ ones are there ?
answered Aug 6 at 21:30
Yves Daoust
111k665205
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
Consider the following transformation: let $B$ be a set of cardinality $b$ and let us represent a subset $A$ of $B$ as a binary string of length $b$ with a one if the corresponding element is taken and a zero otherwise.
E.g.
$$B= u, v, w, x, y, z$$
$$A= u, v, zleftrightarrow 110001.$$
Now how many strings of length $b$ having $a$ ones are there ?
answered Aug 6 at 21:30
Yves Daoust
111k665205
Consider the following transformation: let $B$ be a set of cardinality $b$ and let us represent a subset $A$ of $B$ as a binary string of length $b$ with a one if the corresponding element is taken and a zero otherwise.
E.g.
$$B= u, v, w, x, y, z$$
$$A= u, v, zleftrightarrow 110001.$$
Now how many strings of length $b$ having $a$ ones are there ?
answered Aug 6 at 21:30
Yves Daoust
111k665205
answered Aug 6 at 21:30
Yves Daoust
111k665205
answered Aug 6 at 21:30
Yves Daoust
111k665205
answered Aug 6 at 21:30
Yves Daoust
111k665205
111k665205
add a comment |Â
add a comment |Â
up vote
1
down vote
Let's rephrase the problem as the number of ways that a sequence of length $n$ can have $k$ ones.
In some sense, this becomes a combinatorics problem since we are selecting $k$ positions out of the $n$ to be "ones", and the rest to be zeros.
So, that explains why the result is $nchoosek$, since we are $textitchoosing$ $k$ ones from $n$ positions.
answered Aug 6 at 21:27
Rushabh Mehta
1,060114
1
My initial thought was that in this case $nchoosek$ could be giving me the number of different groups of indexes that could be taken by the 1 digits in a single string of $n$ bits. Is this correct?
– Baffo rasta
Aug 6 at 21:30
Well, not exactly. $nchoose k$ gives you the number of ways to pick $k$ things from a group of $n$ things. In this case, you are picking $k$ places out of $n$ places to put 1s, and the rest will be assigned 0s.
– Rushabh Mehta
Aug 6 at 21:32
add a comment |Â
up vote
1
down vote
Let's rephrase the problem as the number of ways that a sequence of length $n$ can have $k$ ones.
In some sense, this becomes a combinatorics problem since we are selecting $k$ positions out of the $n$ to be "ones", and the rest to be zeros.
So, that explains why the result is $nchoosek$, since we are $textitchoosing$ $k$ ones from $n$ positions.
answered Aug 6 at 21:27
Rushabh Mehta
1,060114
1
My initial thought was that in this case $nchoosek$ could be giving me the number of different groups of indexes that could be taken by the 1 digits in a single string of $n$ bits. Is this correct?
– Baffo rasta
Aug 6 at 21:30
Well, not exactly. $nchoose k$ gives you the number of ways to pick $k$ things from a group of $n$ things. In this case, you are picking $k$ places out of $n$ places to put 1s, and the rest will be assigned 0s.
– Rushabh Mehta
Aug 6 at 21:32
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Let's rephrase the problem as the number of ways that a sequence of length $n$ can have $k$ ones.
In some sense, this becomes a combinatorics problem since we are selecting $k$ positions out of the $n$ to be "ones", and the rest to be zeros.
So, that explains why the result is $nchoosek$, since we are $textitchoosing$ $k$ ones from $n$ positions.
answered Aug 6 at 21:27
Rushabh Mehta
1,060114
Let's rephrase the problem as the number of ways that a sequence of length $n$ can have $k$ ones.
In some sense, this becomes a combinatorics problem since we are selecting $k$ positions out of the $n$ to be "ones", and the rest to be zeros.
So, that explains why the result is $nchoosek$, since we are $textitchoosing$ $k$ ones from $n$ positions.
answered Aug 6 at 21:27
Rushabh Mehta
1,060114
answered Aug 6 at 21:27
Rushabh Mehta
1,060114
answered Aug 6 at 21:27
Rushabh Mehta
1,060114
answered Aug 6 at 21:27
Rushabh Mehta
1,060114
1,060114
1
My initial thought was that in this case $nchoosek$ could be giving me the number of different groups of indexes that could be taken by the 1 digits in a single string of $n$ bits. Is this correct?
– Baffo rasta
Aug 6 at 21:30
Well, not exactly. $nchoose k$ gives you the number of ways to pick $k$ things from a group of $n$ things. In this case, you are picking $k$ places out of $n$ places to put 1s, and the rest will be assigned 0s.
– Rushabh Mehta
Aug 6 at 21:32
add a comment |Â
1
My initial thought was that in this case $nchoosek$ could be giving me the number of different groups of indexes that could be taken by the 1 digits in a single string of $n$ bits. Is this correct?
– Baffo rasta
Aug 6 at 21:30
Well, not exactly. $nchoose k$ gives you the number of ways to pick $k$ things from a group of $n$ things. In this case, you are picking $k$ places out of $n$ places to put 1s, and the rest will be assigned 0s.
– Rushabh Mehta
Aug 6 at 21:32
1
1
My initial thought was that in this case $nchoosek$ could be giving me the number of different groups of indexes that could be taken by the 1 digits in a single string of $n$ bits. Is this correct?
– Baffo rasta
Aug 6 at 21:30
My initial thought was that in this case $nchoosek$ could be giving me the number of different groups of indexes that could be taken by the 1 digits in a single string of $n$ bits. Is this correct?
– Baffo rasta
Aug 6 at 21:30
Well, not exactly. $nchoose k$ gives you the number of ways to pick $k$ things from a group of $n$ things. In this case, you are picking $k$ places out of $n$ places to put 1s, and the rest will be assigned 0s.
– Rushabh Mehta
Aug 6 at 21:32
Well, not exactly. $nchoose k$ gives you the number of ways to pick $k$ things from a group of $n$ things. In this case, you are picking $k$ places out of $n$ places to put 1s, and the rest will be assigned 0s.
– Rushabh Mehta
Aug 6 at 21:32
add a comment |Â
up vote
0
down vote
Here's a bijective argument, let $mathcalP_k([n])$ be the set of subsets of $1, dots, n$ of size $k$, and let
$$
S = (b_1, dots, b_n) in 0,1^n
$$
Now, the mapping
$$
Lambda: mathcalP_k([n]) longrightarrow S \
A mapsto Lambda(A)
$$
with
$$
Lambda(A)_i := cases1 text if i in A\0 text if i not in A
$$
is bijective.
In effect, if $A neq B$, wlog there exists $j in A$ such that $j not in B$. Thus, $Lambda(A)_j = 1 neq 0 = Lambda(B)_j$ and so $Lambda(A) neq Lambda(B)$ which proves that $Lambda$ is injective. Finally, if $b in S$, you can check that $A_b := j in [n] : b_j = 1$ has size $k$ and verifies $Lambda(A_b) = b$.
answered Aug 6 at 21:33
Guido A.
3,851624
Well, I kind of get if this is the case what I am missing! That one is the argument of the next chapter of my book!
– Baffo rasta
Aug 6 at 21:35
This is a very common type of 'combinatorial proof'. Say you want to prove that $n = m$ for some natural numbers $n,m$; then sometimes these can be interpreted as the sizes of certain sets. Thus, $n = m$ will happen iff there is a bijection between these. That motivates this type of arguments. I'll add a proof of my claim for completion's sake :)
– Guido A.
Aug 6 at 21:37
add a comment |Â
up vote
0
down vote
Here's a bijective argument, let $mathcalP_k([n])$ be the set of subsets of $1, dots, n$ of size $k$, and let
$$
S = (b_1, dots, b_n) in 0,1^n
$$
Now, the mapping
$$
Lambda: mathcalP_k([n]) longrightarrow S \
A mapsto Lambda(A)
$$
with
$$
Lambda(A)_i := cases1 text if i in A\0 text if i not in A
$$
is bijective.
In effect, if $A neq B$, wlog there exists $j in A$ such that $j not in B$. Thus, $Lambda(A)_j = 1 neq 0 = Lambda(B)_j$ and so $Lambda(A) neq Lambda(B)$ which proves that $Lambda$ is injective. Finally, if $b in S$, you can check that $A_b := j in [n] : b_j = 1$ has size $k$ and verifies $Lambda(A_b) = b$.
answered Aug 6 at 21:33
Guido A.
3,851624
Well, I kind of get if this is the case what I am missing! That one is the argument of the next chapter of my book!
– Baffo rasta
Aug 6 at 21:35
This is a very common type of 'combinatorial proof'. Say you want to prove that $n = m$ for some natural numbers $n,m$; then sometimes these can be interpreted as the sizes of certain sets. Thus, $n = m$ will happen iff there is a bijection between these. That motivates this type of arguments. I'll add a proof of my claim for completion's sake :)
– Guido A.
Aug 6 at 21:37
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Here's a bijective argument, let $mathcalP_k([n])$ be the set of subsets of $1, dots, n$ of size $k$, and let
$$
S = (b_1, dots, b_n) in 0,1^n
$$
Now, the mapping
$$
Lambda: mathcalP_k([n]) longrightarrow S \
A mapsto Lambda(A)
$$
with
$$
Lambda(A)_i := cases1 text if i in A\0 text if i not in A
$$
is bijective.
In effect, if $A neq B$, wlog there exists $j in A$ such that $j not in B$. Thus, $Lambda(A)_j = 1 neq 0 = Lambda(B)_j$ and so $Lambda(A) neq Lambda(B)$ which proves that $Lambda$ is injective. Finally, if $b in S$, you can check that $A_b := j in [n] : b_j = 1$ has size $k$ and verifies $Lambda(A_b) = b$.
answered Aug 6 at 21:33
Guido A.
3,851624
Here's a bijective argument, let $mathcalP_k([n])$ be the set of subsets of $1, dots, n$ of size $k$, and let
$$
S = (b_1, dots, b_n) in 0,1^n
$$
Now, the mapping
$$
Lambda: mathcalP_k([n]) longrightarrow S \
A mapsto Lambda(A)
$$
with
$$
Lambda(A)_i := cases1 text if i in A\0 text if i not in A
$$
is bijective.
In effect, if $A neq B$, wlog there exists $j in A$ such that $j not in B$. Thus, $Lambda(A)_j = 1 neq 0 = Lambda(B)_j$ and so $Lambda(A) neq Lambda(B)$ which proves that $Lambda$ is injective. Finally, if $b in S$, you can check that $A_b := j in [n] : b_j = 1$ has size $k$ and verifies $Lambda(A_b) = b$.
answered Aug 6 at 21:33
Guido A.
3,851624
edited Aug 6 at 21:40
answered Aug 6 at 21:33
Guido A.
3,851624
answered Aug 6 at 21:33
Guido A.
3,851624
answered Aug 6 at 21:33
Guido A.
3,851624
3,851624
Well, I kind of get if this is the case what I am missing! That one is the argument of the next chapter of my book!
– Baffo rasta
Aug 6 at 21:35
This is a very common type of 'combinatorial proof'. Say you want to prove that $n = m$ for some natural numbers $n,m$; then sometimes these can be interpreted as the sizes of certain sets. Thus, $n = m$ will happen iff there is a bijection between these. That motivates this type of arguments. I'll add a proof of my claim for completion's sake :)
– Guido A.
Aug 6 at 21:37
add a comment |Â
Well, I kind of get if this is the case what I am missing! That one is the argument of the next chapter of my book!
– Baffo rasta
Aug 6 at 21:35
This is a very common type of 'combinatorial proof'. Say you want to prove that $n = m$ for some natural numbers $n,m$; then sometimes these can be interpreted as the sizes of certain sets. Thus, $n = m$ will happen iff there is a bijection between these. That motivates this type of arguments. I'll add a proof of my claim for completion's sake :)
– Guido A.
Aug 6 at 21:37
Well, I kind of get if this is the case what I am missing! That one is the argument of the next chapter of my book!
– Baffo rasta
Aug 6 at 21:35
Well, I kind of get if this is the case what I am missing! That one is the argument of the next chapter of my book!
– Baffo rasta
Aug 6 at 21:35
This is a very common type of 'combinatorial proof'. Say you want to prove that $n = m$ for some natural numbers $n,m$; then sometimes these can be interpreted as the sizes of certain sets. Thus, $n = m$ will happen iff there is a bijection between these. That motivates this type of arguments. I'll add a proof of my claim for completion's sake :)
– Guido A.
Aug 6 at 21:37
This is a very common type of 'combinatorial proof'. Say you want to prove that $n = m$ for some natural numbers $n,m$; then sometimes these can be interpreted as the sizes of certain sets. Thus, $n = m$ will happen iff there is a bijection between these. That motivates this type of arguments. I'll add a proof of my claim for completion's sake :)
– Guido A.
Aug 6 at 21:37
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2874325%2fbinomial-coefficients-and-words-of-n-bits-why-this-works%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Or more briefly than the answers (and like you asked in a comment): It works because there are $nchoose k$ ways to choose a set of $k$ positions to put the $1$s in from among the $n$ available positions in a length-$n$ string.
– Steve Kass
Aug 6 at 21:36
That was what I wanted to know! Thanks.
– Baffo rasta
Aug 6 at 21:37