Mixing
Show that the cardinal of $ A := left{ k in mathbf{Z} | 0 leq k leq n text{ and } binom{n}{k} text{ is odd}...
$begingroup$
This question already has an answer here:
Number of odd binomial coefficients is a power of $2$
2 answers
Let $ A := left{ k in mathbf{Z} | 0 leq k leq n text{ and } binom{n}{k} text{ is odd} right} $.
I must show that the cardinal of $A$ is a power of 2.
I have tried to show that there exist a bijection between $A$ and the set of subparts of another set, but unsuccessfully.
I also thought about trying to show that the cardinal of $A$ must divide the cardinal of $ P(left{ k in mathbf{Z} | 0 leq k leq n right}) $ (it is $ 2^{n+1} $), which would ensure the result, but I do not think this a good path.
Are there simple arguments to show that ?
combinatorics binomial-coefficients cardinals
asked Jan 28 at 21:05
MrMathsMrMaths
1809
$endgroup$
marked as duplicate by Chris Culter, Cesareo, Theo Bendit, Lord Shark the Unknown, mrtaurho Jan 29 at 6:11
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 odd binomial coefficients is a power of $2$
2 answers
Let $ A := left{ k in mathbf{Z} | 0 leq k leq n text{ and } binom{n}{k} text{ is odd} right} $.
I must show that the cardinal of $A$ is a power of 2.
I have tried to show that there exist a bijection between $A$ and the set of subparts of another set, but unsuccessfully.
I also thought about trying to show that the cardinal of $A$ must divide the cardinal of $ P(left{ k in mathbf{Z} | 0 leq k leq n right}) $ (it is $ 2^{n+1} $), which would ensure the result, but I do not think this a good path.
Are there simple arguments to show that ?
combinatorics binomial-coefficients cardinals
asked Jan 28 at 21:05
MrMathsMrMaths
1809
$endgroup$
marked as duplicate by Chris Culter, Cesareo, Theo Bendit, Lord Shark the Unknown, mrtaurho Jan 29 at 6:11
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.
$begingroup$
But the solution given is not very simple. Simplier arguments ?
$endgroup$
– MrMaths
Jan 28 at 21:22
add a comment |
$begingroup$
This question already has an answer here:
Number of odd binomial coefficients is a power of $2$
2 answers
Let $ A := left{ k in mathbf{Z} | 0 leq k leq n text{ and } binom{n}{k} text{ is odd} right} $.
I must show that the cardinal of $A$ is a power of 2.
I have tried to show that there exist a bijection between $A$ and the set of subparts of another set, but unsuccessfully.
I also thought about trying to show that the cardinal of $A$ must divide the cardinal of $ P(left{ k in mathbf{Z} | 0 leq k leq n right}) $ (it is $ 2^{n+1} $), which would ensure the result, but I do not think this a good path.
Are there simple arguments to show that ?
combinatorics binomial-coefficients cardinals
asked Jan 28 at 21:05
MrMathsMrMaths
1809
$endgroup$
This question already has an answer here:
Number of odd binomial coefficients is a power of $2$
2 answers
Let $ A := left{ k in mathbf{Z} | 0 leq k leq n text{ and } binom{n}{k} text{ is odd} right} $.
I must show that the cardinal of $A$ is a power of 2.
I have tried to show that there exist a bijection between $A$ and the set of subparts of another set, but unsuccessfully.
I also thought about trying to show that the cardinal of $A$ must divide the cardinal of $ P(left{ k in mathbf{Z} | 0 leq k leq n right}) $ (it is $ 2^{n+1} $), which would ensure the result, but I do not think this a good path.
Are there simple arguments to show that ?
This question already has an answer here:
Number of odd binomial coefficients is a power of $2$
2 answers
combinatorics binomial-coefficients cardinals
combinatorics binomial-coefficients cardinals
asked Jan 28 at 21:05
MrMathsMrMaths
1809
asked Jan 28 at 21:05
MrMathsMrMaths
1809
edited Jan 28 at 21:25
MrMaths
asked Jan 28 at 21:05
MrMathsMrMaths
1809
asked Jan 28 at 21:05
MrMathsMrMaths
1809
asked Jan 28 at 21:05
MrMathsMrMaths
1809
1809
marked as duplicate by Chris Culter, Cesareo, Theo Bendit, Lord Shark the Unknown, mrtaurho Jan 29 at 6:11
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 Chris Culter, Cesareo, Theo Bendit, Lord Shark the Unknown, mrtaurho Jan 29 at 6:11
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.
$begingroup$
But the solution given is not very simple. Simplier arguments ?
$endgroup$
– MrMaths
Jan 28 at 21:22
add a comment |
$begingroup$
But the solution given is not very simple. Simplier arguments ?
$endgroup$
– MrMaths
Jan 28 at 21:22
$begingroup$
But the solution given is not very simple. Simplier arguments ?
$endgroup$
– MrMaths
Jan 28 at 21:22
$begingroup$
But the solution given is not very simple. Simplier arguments ?
$endgroup$
– MrMaths
Jan 28 at 21:22
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Let $n=a_rcdot2^r+cdots+a_1cdot2+a_0$ where all $a_iin{0,1}$. For $0le kle n$ let $k=b_rcdot2^r+cdots+b_1cdot2+b_0$ where all $b_iin{0,1}$.
For convenience, denote $Z={i:a_i=0}$ and $N={i:a_i=1}$. Then Lucas Correspondence tells us that
$binom{n}{k}$ is odd if and only if $prod_{iin Z}binom{0}{b_i}cdotprod_{jin N}binom{1}{b_j}=1$. Since $b_i,b_jin{0,1}$, we can conclude that $binom{n}{k}$ is odd if and only if $b_i=0$ for all $iin Z$. This implies that the number of integers $k$ such that $binom{n}{k}$ is odd is exactly $2^{|N|}$.
answered Jan 28 at 22:55
Eric YauEric Yau
609310
$endgroup$
1
$begingroup$
Is there any proof which does not use Lucas Correspondance ?
$endgroup$
– MrMaths
Jan 29 at 7:45
add a comment |
$begingroup$
Consider the following partial involution on the set of size $k$ subsets of ${1,2,dots,n}$. Given such a subset $S$, find the smallest number $i$ such that $S$ contains exactly one of the numbers in ${2i-1,2i}$. Then $f(S)$ is attained by removing that number and adding the other one. We can divide the set of subsets for which $f(S)$ is defined into pairs, ${S,f(S)}$.
The involution is undefined if $S$ contains neither or both of ${2i-1,2i}$ for all $1le i le lfloor n/2rfloor$. If $n$ is even and $k$ is odd, then $f(S)$ is defined for all subsets (why?). Otherwise, there are precisely $binom{lfloor n/2rfloor}{lfloor k/2rfloor}$ subsets for which the involution is undefined. Since removing the pairs defined by $f$ does not affect the parity of $binom{n}k$, this shows
$$
binom{n}{k}equiv_{pmod 2}
begin{cases}
0 & nequiv 0, kequiv 1pmod 2\
binom{lfloor n/2rfloor}{lfloor k/2rfloor} & text{otherwise}
end{cases}tag{1}
$$
Now, let $a_n$ be the number of odd entries in the $n^{th}$ row of Pascal's triangle.
If $n=2m$ is even, then $binom{2m}k$ is even whenever $k$ is odd. There are $m+1$ entries in the $(2m)^{th}$ row of Pascal's triangle for which $k$ is even. The parities of these entries are equal to the $m+1$ entries of the $m^{th}$ row of Pascal's triangle, because $binom{2m}{2i}equiv binom{m}i$, by $(1)$. Therefore,$$a_{2m}=a_m.$$
If $n=2m+1$ is odd, then $(1)$ implies $binom{2m+1}{2i}equivbinom{2m+1}{2i+1}equiv binom{m}i$. This means each odd entry in the $(m)^{th}$ row of Pascal's triangle corresponds to two odd entries on the $(2m+1)^{st}$ row, so $$a_{2m+1}=2a_m.$$
These last two equations imply that $a_n$ is always a power of $2$.
answered Jan 28 at 22:30
Mike EarnestMike Earnest
26.2k22151
$endgroup$
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Let $n=a_rcdot2^r+cdots+a_1cdot2+a_0$ where all $a_iin{0,1}$. For $0le kle n$ let $k=b_rcdot2^r+cdots+b_1cdot2+b_0$ where all $b_iin{0,1}$.
For convenience, denote $Z={i:a_i=0}$ and $N={i:a_i=1}$. Then Lucas Correspondence tells us that
$binom{n}{k}$ is odd if and only if $prod_{iin Z}binom{0}{b_i}cdotprod_{jin N}binom{1}{b_j}=1$. Since $b_i,b_jin{0,1}$, we can conclude that $binom{n}{k}$ is odd if and only if $b_i=0$ for all $iin Z$. This implies that the number of integers $k$ such that $binom{n}{k}$ is odd is exactly $2^{|N|}$.
answered Jan 28 at 22:55
Eric YauEric Yau
609310
$endgroup$
1
$begingroup$
Is there any proof which does not use Lucas Correspondance ?
$endgroup$
– MrMaths
Jan 29 at 7:45
add a comment |
$begingroup$
Let $n=a_rcdot2^r+cdots+a_1cdot2+a_0$ where all $a_iin{0,1}$. For $0le kle n$ let $k=b_rcdot2^r+cdots+b_1cdot2+b_0$ where all $b_iin{0,1}$.
For convenience, denote $Z={i:a_i=0}$ and $N={i:a_i=1}$. Then Lucas Correspondence tells us that
$binom{n}{k}$ is odd if and only if $prod_{iin Z}binom{0}{b_i}cdotprod_{jin N}binom{1}{b_j}=1$. Since $b_i,b_jin{0,1}$, we can conclude that $binom{n}{k}$ is odd if and only if $b_i=0$ for all $iin Z$. This implies that the number of integers $k$ such that $binom{n}{k}$ is odd is exactly $2^{|N|}$.
answered Jan 28 at 22:55
Eric YauEric Yau
609310
$endgroup$
1
$begingroup$
Is there any proof which does not use Lucas Correspondance ?
$endgroup$
– MrMaths
Jan 29 at 7:45
add a comment |
$begingroup$
Let $n=a_rcdot2^r+cdots+a_1cdot2+a_0$ where all $a_iin{0,1}$. For $0le kle n$ let $k=b_rcdot2^r+cdots+b_1cdot2+b_0$ where all $b_iin{0,1}$.
For convenience, denote $Z={i:a_i=0}$ and $N={i:a_i=1}$. Then Lucas Correspondence tells us that
$binom{n}{k}$ is odd if and only if $prod_{iin Z}binom{0}{b_i}cdotprod_{jin N}binom{1}{b_j}=1$. Since $b_i,b_jin{0,1}$, we can conclude that $binom{n}{k}$ is odd if and only if $b_i=0$ for all $iin Z$. This implies that the number of integers $k$ such that $binom{n}{k}$ is odd is exactly $2^{|N|}$.
answered Jan 28 at 22:55
Eric YauEric Yau
609310
$endgroup$
Let $n=a_rcdot2^r+cdots+a_1cdot2+a_0$ where all $a_iin{0,1}$. For $0le kle n$ let $k=b_rcdot2^r+cdots+b_1cdot2+b_0$ where all $b_iin{0,1}$.
For convenience, denote $Z={i:a_i=0}$ and $N={i:a_i=1}$. Then Lucas Correspondence tells us that
$binom{n}{k}$ is odd if and only if $prod_{iin Z}binom{0}{b_i}cdotprod_{jin N}binom{1}{b_j}=1$. Since $b_i,b_jin{0,1}$, we can conclude that $binom{n}{k}$ is odd if and only if $b_i=0$ for all $iin Z$. This implies that the number of integers $k$ such that $binom{n}{k}$ is odd is exactly $2^{|N|}$.
answered Jan 28 at 22:55
Eric YauEric Yau
609310
answered Jan 28 at 22:55
Eric YauEric Yau
609310
answered Jan 28 at 22:55
Eric YauEric Yau
609310
answered Jan 28 at 22:55
Eric YauEric Yau
609310
609310
1
$begingroup$
Is there any proof which does not use Lucas Correspondance ?
$endgroup$
– MrMaths
Jan 29 at 7:45
add a comment |
1
$begingroup$
Is there any proof which does not use Lucas Correspondance ?
$endgroup$
– MrMaths
Jan 29 at 7:45
1
1
$begingroup$
Is there any proof which does not use Lucas Correspondance ?
$endgroup$
– MrMaths
Jan 29 at 7:45
$begingroup$
Is there any proof which does not use Lucas Correspondance ?
$endgroup$
– MrMaths
Jan 29 at 7:45
add a comment |
$begingroup$
Consider the following partial involution on the set of size $k$ subsets of ${1,2,dots,n}$. Given such a subset $S$, find the smallest number $i$ such that $S$ contains exactly one of the numbers in ${2i-1,2i}$. Then $f(S)$ is attained by removing that number and adding the other one. We can divide the set of subsets for which $f(S)$ is defined into pairs, ${S,f(S)}$.
The involution is undefined if $S$ contains neither or both of ${2i-1,2i}$ for all $1le i le lfloor n/2rfloor$. If $n$ is even and $k$ is odd, then $f(S)$ is defined for all subsets (why?). Otherwise, there are precisely $binom{lfloor n/2rfloor}{lfloor k/2rfloor}$ subsets for which the involution is undefined. Since removing the pairs defined by $f$ does not affect the parity of $binom{n}k$, this shows
$$
binom{n}{k}equiv_{pmod 2}
begin{cases}
0 & nequiv 0, kequiv 1pmod 2\
binom{lfloor n/2rfloor}{lfloor k/2rfloor} & text{otherwise}
end{cases}tag{1}
$$
Now, let $a_n$ be the number of odd entries in the $n^{th}$ row of Pascal's triangle.
If $n=2m$ is even, then $binom{2m}k$ is even whenever $k$ is odd. There are $m+1$ entries in the $(2m)^{th}$ row of Pascal's triangle for which $k$ is even. The parities of these entries are equal to the $m+1$ entries of the $m^{th}$ row of Pascal's triangle, because $binom{2m}{2i}equiv binom{m}i$, by $(1)$. Therefore,$$a_{2m}=a_m.$$
If $n=2m+1$ is odd, then $(1)$ implies $binom{2m+1}{2i}equivbinom{2m+1}{2i+1}equiv binom{m}i$. This means each odd entry in the $(m)^{th}$ row of Pascal's triangle corresponds to two odd entries on the $(2m+1)^{st}$ row, so $$a_{2m+1}=2a_m.$$
These last two equations imply that $a_n$ is always a power of $2$.
answered Jan 28 at 22:30
Mike EarnestMike Earnest
26.2k22151
$endgroup$
add a comment |
$begingroup$
Consider the following partial involution on the set of size $k$ subsets of ${1,2,dots,n}$. Given such a subset $S$, find the smallest number $i$ such that $S$ contains exactly one of the numbers in ${2i-1,2i}$. Then $f(S)$ is attained by removing that number and adding the other one. We can divide the set of subsets for which $f(S)$ is defined into pairs, ${S,f(S)}$.
The involution is undefined if $S$ contains neither or both of ${2i-1,2i}$ for all $1le i le lfloor n/2rfloor$. If $n$ is even and $k$ is odd, then $f(S)$ is defined for all subsets (why?). Otherwise, there are precisely $binom{lfloor n/2rfloor}{lfloor k/2rfloor}$ subsets for which the involution is undefined. Since removing the pairs defined by $f$ does not affect the parity of $binom{n}k$, this shows
$$
binom{n}{k}equiv_{pmod 2}
begin{cases}
0 & nequiv 0, kequiv 1pmod 2\
binom{lfloor n/2rfloor}{lfloor k/2rfloor} & text{otherwise}
end{cases}tag{1}
$$
Now, let $a_n$ be the number of odd entries in the $n^{th}$ row of Pascal's triangle.
If $n=2m$ is even, then $binom{2m}k$ is even whenever $k$ is odd. There are $m+1$ entries in the $(2m)^{th}$ row of Pascal's triangle for which $k$ is even. The parities of these entries are equal to the $m+1$ entries of the $m^{th}$ row of Pascal's triangle, because $binom{2m}{2i}equiv binom{m}i$, by $(1)$. Therefore,$$a_{2m}=a_m.$$
If $n=2m+1$ is odd, then $(1)$ implies $binom{2m+1}{2i}equivbinom{2m+1}{2i+1}equiv binom{m}i$. This means each odd entry in the $(m)^{th}$ row of Pascal's triangle corresponds to two odd entries on the $(2m+1)^{st}$ row, so $$a_{2m+1}=2a_m.$$
These last two equations imply that $a_n$ is always a power of $2$.
answered Jan 28 at 22:30
Mike EarnestMike Earnest
26.2k22151
$endgroup$
add a comment |
$begingroup$
Consider the following partial involution on the set of size $k$ subsets of ${1,2,dots,n}$. Given such a subset $S$, find the smallest number $i$ such that $S$ contains exactly one of the numbers in ${2i-1,2i}$. Then $f(S)$ is attained by removing that number and adding the other one. We can divide the set of subsets for which $f(S)$ is defined into pairs, ${S,f(S)}$.
The involution is undefined if $S$ contains neither or both of ${2i-1,2i}$ for all $1le i le lfloor n/2rfloor$. If $n$ is even and $k$ is odd, then $f(S)$ is defined for all subsets (why?). Otherwise, there are precisely $binom{lfloor n/2rfloor}{lfloor k/2rfloor}$ subsets for which the involution is undefined. Since removing the pairs defined by $f$ does not affect the parity of $binom{n}k$, this shows
$$
binom{n}{k}equiv_{pmod 2}
begin{cases}
0 & nequiv 0, kequiv 1pmod 2\
binom{lfloor n/2rfloor}{lfloor k/2rfloor} & text{otherwise}
end{cases}tag{1}
$$
Now, let $a_n$ be the number of odd entries in the $n^{th}$ row of Pascal's triangle.
If $n=2m$ is even, then $binom{2m}k$ is even whenever $k$ is odd. There are $m+1$ entries in the $(2m)^{th}$ row of Pascal's triangle for which $k$ is even. The parities of these entries are equal to the $m+1$ entries of the $m^{th}$ row of Pascal's triangle, because $binom{2m}{2i}equiv binom{m}i$, by $(1)$. Therefore,$$a_{2m}=a_m.$$
If $n=2m+1$ is odd, then $(1)$ implies $binom{2m+1}{2i}equivbinom{2m+1}{2i+1}equiv binom{m}i$. This means each odd entry in the $(m)^{th}$ row of Pascal's triangle corresponds to two odd entries on the $(2m+1)^{st}$ row, so $$a_{2m+1}=2a_m.$$
These last two equations imply that $a_n$ is always a power of $2$.
answered Jan 28 at 22:30
Mike EarnestMike Earnest
26.2k22151
$endgroup$
Consider the following partial involution on the set of size $k$ subsets of ${1,2,dots,n}$. Given such a subset $S$, find the smallest number $i$ such that $S$ contains exactly one of the numbers in ${2i-1,2i}$. Then $f(S)$ is attained by removing that number and adding the other one. We can divide the set of subsets for which $f(S)$ is defined into pairs, ${S,f(S)}$.
The involution is undefined if $S$ contains neither or both of ${2i-1,2i}$ for all $1le i le lfloor n/2rfloor$. If $n$ is even and $k$ is odd, then $f(S)$ is defined for all subsets (why?). Otherwise, there are precisely $binom{lfloor n/2rfloor}{lfloor k/2rfloor}$ subsets for which the involution is undefined. Since removing the pairs defined by $f$ does not affect the parity of $binom{n}k$, this shows
$$
binom{n}{k}equiv_{pmod 2}
begin{cases}
0 & nequiv 0, kequiv 1pmod 2\
binom{lfloor n/2rfloor}{lfloor k/2rfloor} & text{otherwise}
end{cases}tag{1}
$$
Now, let $a_n$ be the number of odd entries in the $n^{th}$ row of Pascal's triangle.
If $n=2m$ is even, then $binom{2m}k$ is even whenever $k$ is odd. There are $m+1$ entries in the $(2m)^{th}$ row of Pascal's triangle for which $k$ is even. The parities of these entries are equal to the $m+1$ entries of the $m^{th}$ row of Pascal's triangle, because $binom{2m}{2i}equiv binom{m}i$, by $(1)$. Therefore,$$a_{2m}=a_m.$$
If $n=2m+1$ is odd, then $(1)$ implies $binom{2m+1}{2i}equivbinom{2m+1}{2i+1}equiv binom{m}i$. This means each odd entry in the $(m)^{th}$ row of Pascal's triangle corresponds to two odd entries on the $(2m+1)^{st}$ row, so $$a_{2m+1}=2a_m.$$
These last two equations imply that $a_n$ is always a power of $2$.
answered Jan 28 at 22:30
Mike EarnestMike Earnest
26.2k22151
answered Jan 28 at 22:30
Mike EarnestMike Earnest
26.2k22151
answered Jan 28 at 22:30
Mike EarnestMike Earnest
26.2k22151
answered Jan 28 at 22:30
Mike EarnestMike Earnest
26.2k22151
26.2k22151
add a comment |
add a comment |
$begingroup$
But the solution given is not very simple. Simplier arguments ?
$endgroup$
– MrMaths
Jan 28 at 21:22