Mixing
Proving formula sum of product of binomial coefficients
Clash Royale CLAN TAG#URR8PPP
up vote
5
down vote
favorite
I have to proof the following formula
beginalign
sum_k=0^n/2 nchoose2k 2kchoose k 2^n-2k = 2nchoose n
endalign
I tried to use the fact that $2nchoose n = sum_k=0^n nchoose k^2$, but I don't get any conclusion. Any suggestions? Thanks in advance!
probability combinatorics binomial-coefficients combinatorial-proofs
asked 4 hours ago
userr777
16610
add a comment |Â
up vote
5
down vote
favorite
I have to proof the following formula
beginalign
sum_k=0^n/2 nchoose2k 2kchoose k 2^n-2k = 2nchoose n
endalign
I tried to use the fact that $2nchoose n = sum_k=0^n nchoose k^2$, but I don't get any conclusion. Any suggestions? Thanks in advance!
probability combinatorics binomial-coefficients combinatorial-proofs
asked 4 hours ago
userr777
16610
add a comment |Â
up vote
5
down vote
favorite
up vote
5
down vote
favorite
I have to proof the following formula
beginalign
sum_k=0^n/2 nchoose2k 2kchoose k 2^n-2k = 2nchoose n
endalign
I tried to use the fact that $2nchoose n = sum_k=0^n nchoose k^2$, but I don't get any conclusion. Any suggestions? Thanks in advance!
probability combinatorics binomial-coefficients combinatorial-proofs
asked 4 hours ago
userr777
16610
I have to proof the following formula
beginalign
sum_k=0^n/2 nchoose2k 2kchoose k 2^n-2k = 2nchoose n
endalign
I tried to use the fact that $2nchoose n = sum_k=0^n nchoose k^2$, but I don't get any conclusion. Any suggestions? Thanks in advance!
probability combinatorics binomial-coefficients combinatorial-proofs
probability combinatorics binomial-coefficients combinatorial-proofs
asked 4 hours ago
userr777
16610
asked 4 hours ago
userr777
16610
asked 4 hours ago
userr777
16610
asked 4 hours ago
userr777
16610
asked 4 hours ago
userr777
16610
16610
add a comment |Â
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
3
down vote
Define the following two sets:
$$mathcalA = x in 0, 1, 2, 3^n : mboxa number of $1$'s in $x$ and a number of $0$'s in $x$ are the same .$$
$$mathcalB = yin0, 1^2n : mboxthere are $n$ ones in $y$ .$$
Note that $|mathcalA|$ equals the left hand side and $|mathcalB|$ equals the right hand side. All that remains to do is to come up with a bijection between $mathcalA$ and $mathcalB$.
Define the following mapping
$$phi : mathcalA to mathcalB,$$
$$phi(x_1ldots x_n) = psi(x_1)ldots psi(x_n),$$
where $psi$ is a mapping from $0, 1, 2, 3$ to $0, 1^2$, defined as follows
$$psi(0) = 00, psi(1) = 11, psi(2) = 01, psi(3) = 10.$$
It's obvious that $phi$ is bijective. To show it formally you just have to notice the following thing. Take any $yin0, 1^2n$. Split $y$ into $n$ blocks of 2 consecutive bits. Then $yinmathcalB$ iff a number of $00$-blocks and a number of $11$-blocs are the same.
answered 3 hours ago
Sasha Kozachinskiy
66418
add a comment |Â
up vote
2
down vote
Starting from
$$sum_k=0^lfloor n/2 rfloor
nchoose 2k 2kchoose k 2^n-2k$$
we write
$$nchoose 2k 2kchoose k =
fracn!(n-2k)! times k! times k!
= nchoose k n-kchoose k$$
to obtain
$$sum_k=0^lfloor n/2 rfloor
nchoose k 2^n-2k n-kchoose n-2k
\ = sum_k=0^lfloor n/2 rfloor
nchoose k 2^n-2k [z^n-2k] (1+z)^n-k
\ = [z^n] sum_k=0^lfloor n/2 rfloor
nchoose k z^2k (1+z)^n-k 2^n-2k.$$
Now when $2kgt n$ there is no contribution to the coefficient
extractor and we may write
$$ [z^n] 2^n (1+z)^n sum_kge 0
nchoose k z^2k (1+z)^-k 2^-2k
\ = [z^n] 2^n (1+z)^n (1+z^2/(1+z)/2^2)^n
\ = frac12^n [z^n] (2^2+2^2z+z^2)^n
= frac12^n [z^n] (z+2)^2n
= frac12^n 2nchoose n 2^n = 2nchoose n.$$
This is the claim.
answered 1 hour ago
Marko Riedel
36.6k335106
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
Define the following two sets:
$$mathcalA = x in 0, 1, 2, 3^n : mboxa number of $1$'s in $x$ and a number of $0$'s in $x$ are the same .$$
$$mathcalB = yin0, 1^2n : mboxthere are $n$ ones in $y$ .$$
Note that $|mathcalA|$ equals the left hand side and $|mathcalB|$ equals the right hand side. All that remains to do is to come up with a bijection between $mathcalA$ and $mathcalB$.
Define the following mapping
$$phi : mathcalA to mathcalB,$$
$$phi(x_1ldots x_n) = psi(x_1)ldots psi(x_n),$$
where $psi$ is a mapping from $0, 1, 2, 3$ to $0, 1^2$, defined as follows
$$psi(0) = 00, psi(1) = 11, psi(2) = 01, psi(3) = 10.$$
It's obvious that $phi$ is bijective. To show it formally you just have to notice the following thing. Take any $yin0, 1^2n$. Split $y$ into $n$ blocks of 2 consecutive bits. Then $yinmathcalB$ iff a number of $00$-blocks and a number of $11$-blocs are the same.
answered 3 hours ago
Sasha Kozachinskiy
66418
add a comment |Â
up vote
3
down vote
Define the following two sets:
$$mathcalA = x in 0, 1, 2, 3^n : mboxa number of $1$'s in $x$ and a number of $0$'s in $x$ are the same .$$
$$mathcalB = yin0, 1^2n : mboxthere are $n$ ones in $y$ .$$
Note that $|mathcalA|$ equals the left hand side and $|mathcalB|$ equals the right hand side. All that remains to do is to come up with a bijection between $mathcalA$ and $mathcalB$.
Define the following mapping
$$phi : mathcalA to mathcalB,$$
$$phi(x_1ldots x_n) = psi(x_1)ldots psi(x_n),$$
where $psi$ is a mapping from $0, 1, 2, 3$ to $0, 1^2$, defined as follows
$$psi(0) = 00, psi(1) = 11, psi(2) = 01, psi(3) = 10.$$
It's obvious that $phi$ is bijective. To show it formally you just have to notice the following thing. Take any $yin0, 1^2n$. Split $y$ into $n$ blocks of 2 consecutive bits. Then $yinmathcalB$ iff a number of $00$-blocks and a number of $11$-blocs are the same.
answered 3 hours ago
Sasha Kozachinskiy
66418
add a comment |Â
up vote
3
down vote
up vote
3
down vote
Define the following two sets:
$$mathcalA = x in 0, 1, 2, 3^n : mboxa number of $1$'s in $x$ and a number of $0$'s in $x$ are the same .$$
$$mathcalB = yin0, 1^2n : mboxthere are $n$ ones in $y$ .$$
Note that $|mathcalA|$ equals the left hand side and $|mathcalB|$ equals the right hand side. All that remains to do is to come up with a bijection between $mathcalA$ and $mathcalB$.
Define the following mapping
$$phi : mathcalA to mathcalB,$$
$$phi(x_1ldots x_n) = psi(x_1)ldots psi(x_n),$$
where $psi$ is a mapping from $0, 1, 2, 3$ to $0, 1^2$, defined as follows
$$psi(0) = 00, psi(1) = 11, psi(2) = 01, psi(3) = 10.$$
It's obvious that $phi$ is bijective. To show it formally you just have to notice the following thing. Take any $yin0, 1^2n$. Split $y$ into $n$ blocks of 2 consecutive bits. Then $yinmathcalB$ iff a number of $00$-blocks and a number of $11$-blocs are the same.
answered 3 hours ago
Sasha Kozachinskiy
66418
Define the following two sets:
$$mathcalA = x in 0, 1, 2, 3^n : mboxa number of $1$'s in $x$ and a number of $0$'s in $x$ are the same .$$
$$mathcalB = yin0, 1^2n : mboxthere are $n$ ones in $y$ .$$
Note that $|mathcalA|$ equals the left hand side and $|mathcalB|$ equals the right hand side. All that remains to do is to come up with a bijection between $mathcalA$ and $mathcalB$.
Define the following mapping
$$phi : mathcalA to mathcalB,$$
$$phi(x_1ldots x_n) = psi(x_1)ldots psi(x_n),$$
where $psi$ is a mapping from $0, 1, 2, 3$ to $0, 1^2$, defined as follows
$$psi(0) = 00, psi(1) = 11, psi(2) = 01, psi(3) = 10.$$
It's obvious that $phi$ is bijective. To show it formally you just have to notice the following thing. Take any $yin0, 1^2n$. Split $y$ into $n$ blocks of 2 consecutive bits. Then $yinmathcalB$ iff a number of $00$-blocks and a number of $11$-blocs are the same.
answered 3 hours ago
Sasha Kozachinskiy
66418
answered 3 hours ago
Sasha Kozachinskiy
66418
answered 3 hours ago
Sasha Kozachinskiy
66418
answered 3 hours ago
Sasha Kozachinskiy
66418
66418
add a comment |Â
add a comment |Â
up vote
2
down vote
Starting from
$$sum_k=0^lfloor n/2 rfloor
nchoose 2k 2kchoose k 2^n-2k$$
we write
$$nchoose 2k 2kchoose k =
fracn!(n-2k)! times k! times k!
= nchoose k n-kchoose k$$
to obtain
$$sum_k=0^lfloor n/2 rfloor
nchoose k 2^n-2k n-kchoose n-2k
\ = sum_k=0^lfloor n/2 rfloor
nchoose k 2^n-2k [z^n-2k] (1+z)^n-k
\ = [z^n] sum_k=0^lfloor n/2 rfloor
nchoose k z^2k (1+z)^n-k 2^n-2k.$$
Now when $2kgt n$ there is no contribution to the coefficient
extractor and we may write
$$ [z^n] 2^n (1+z)^n sum_kge 0
nchoose k z^2k (1+z)^-k 2^-2k
\ = [z^n] 2^n (1+z)^n (1+z^2/(1+z)/2^2)^n
\ = frac12^n [z^n] (2^2+2^2z+z^2)^n
= frac12^n [z^n] (z+2)^2n
= frac12^n 2nchoose n 2^n = 2nchoose n.$$
This is the claim.
answered 1 hour ago
Marko Riedel
36.6k335106
add a comment |Â
up vote
2
down vote
Starting from
$$sum_k=0^lfloor n/2 rfloor
nchoose 2k 2kchoose k 2^n-2k$$
we write
$$nchoose 2k 2kchoose k =
fracn!(n-2k)! times k! times k!
= nchoose k n-kchoose k$$
to obtain
$$sum_k=0^lfloor n/2 rfloor
nchoose k 2^n-2k n-kchoose n-2k
\ = sum_k=0^lfloor n/2 rfloor
nchoose k 2^n-2k [z^n-2k] (1+z)^n-k
\ = [z^n] sum_k=0^lfloor n/2 rfloor
nchoose k z^2k (1+z)^n-k 2^n-2k.$$
Now when $2kgt n$ there is no contribution to the coefficient
extractor and we may write
$$ [z^n] 2^n (1+z)^n sum_kge 0
nchoose k z^2k (1+z)^-k 2^-2k
\ = [z^n] 2^n (1+z)^n (1+z^2/(1+z)/2^2)^n
\ = frac12^n [z^n] (2^2+2^2z+z^2)^n
= frac12^n [z^n] (z+2)^2n
= frac12^n 2nchoose n 2^n = 2nchoose n.$$
This is the claim.
answered 1 hour ago
Marko Riedel
36.6k335106
add a comment |Â
up vote
2
down vote
up vote
2
down vote
Starting from
$$sum_k=0^lfloor n/2 rfloor
nchoose 2k 2kchoose k 2^n-2k$$
we write
$$nchoose 2k 2kchoose k =
fracn!(n-2k)! times k! times k!
= nchoose k n-kchoose k$$
to obtain
$$sum_k=0^lfloor n/2 rfloor
nchoose k 2^n-2k n-kchoose n-2k
\ = sum_k=0^lfloor n/2 rfloor
nchoose k 2^n-2k [z^n-2k] (1+z)^n-k
\ = [z^n] sum_k=0^lfloor n/2 rfloor
nchoose k z^2k (1+z)^n-k 2^n-2k.$$
Now when $2kgt n$ there is no contribution to the coefficient
extractor and we may write
$$ [z^n] 2^n (1+z)^n sum_kge 0
nchoose k z^2k (1+z)^-k 2^-2k
\ = [z^n] 2^n (1+z)^n (1+z^2/(1+z)/2^2)^n
\ = frac12^n [z^n] (2^2+2^2z+z^2)^n
= frac12^n [z^n] (z+2)^2n
= frac12^n 2nchoose n 2^n = 2nchoose n.$$
This is the claim.
answered 1 hour ago
Marko Riedel
36.6k335106
Starting from
$$sum_k=0^lfloor n/2 rfloor
nchoose 2k 2kchoose k 2^n-2k$$
we write
$$nchoose 2k 2kchoose k =
fracn!(n-2k)! times k! times k!
= nchoose k n-kchoose k$$
to obtain
$$sum_k=0^lfloor n/2 rfloor
nchoose k 2^n-2k n-kchoose n-2k
\ = sum_k=0^lfloor n/2 rfloor
nchoose k 2^n-2k [z^n-2k] (1+z)^n-k
\ = [z^n] sum_k=0^lfloor n/2 rfloor
nchoose k z^2k (1+z)^n-k 2^n-2k.$$
Now when $2kgt n$ there is no contribution to the coefficient
extractor and we may write
$$ [z^n] 2^n (1+z)^n sum_kge 0
nchoose k z^2k (1+z)^-k 2^-2k
\ = [z^n] 2^n (1+z)^n (1+z^2/(1+z)/2^2)^n
\ = frac12^n [z^n] (2^2+2^2z+z^2)^n
= frac12^n [z^n] (z+2)^2n
= frac12^n 2nchoose n 2^n = 2nchoose n.$$
This is the claim.
answered 1 hour ago
Marko Riedel
36.6k335106
edited 1 hour ago
answered 1 hour ago
Marko Riedel
36.6k335106
answered 1 hour ago
Marko Riedel
36.6k335106
answered 1 hour ago
Marko Riedel
36.6k335106
36.6k335106
add a comment |Â
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%2f2932845%2fproving-formula-sum-of-product-of-binomial-coefficients%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
