How to prove this strange combinatorical identity?
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
Let $ninmathbbN$. I observed today that
$$1+n+sum_i_1=1^ni_1+sum_i_2=1^nsum_i_1=1^i_2i_1+sum_i_3=1^nsum_i_2=1^i_3sum_i_1=1^i_2i_1+dots + sum_i_n-1^nsum_i_n-2=1^i_n-1dotssum_i_1=1^i_2i_1=frac(2n)!(n!)^2$$
I'm wondering how this identity can be proven. Note that there are $n+1$ terms on the LHS.
combinatorics number-theory
asked Sep 10 at 20:35
Adam
398113
add a comment |Â
up vote
2
down vote
favorite
Let $ninmathbbN$. I observed today that
$$1+n+sum_i_1=1^ni_1+sum_i_2=1^nsum_i_1=1^i_2i_1+sum_i_3=1^nsum_i_2=1^i_3sum_i_1=1^i_2i_1+dots + sum_i_n-1^nsum_i_n-2=1^i_n-1dotssum_i_1=1^i_2i_1=frac(2n)!(n!)^2$$
I'm wondering how this identity can be proven. Note that there are $n+1$ terms on the LHS.
combinatorics number-theory
asked Sep 10 at 20:35
Adam
398113
2
The right side is $(n+1)C_n$, where $C_n$ is the Catalan number. So it looks like the left side counts the number of catalan paths, with multiplicity. I'd guess that multiplicity is from where the path makes its first turn.
– Alex R.
Sep 10 at 21:00
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Let $ninmathbbN$. I observed today that
$$1+n+sum_i_1=1^ni_1+sum_i_2=1^nsum_i_1=1^i_2i_1+sum_i_3=1^nsum_i_2=1^i_3sum_i_1=1^i_2i_1+dots + sum_i_n-1^nsum_i_n-2=1^i_n-1dotssum_i_1=1^i_2i_1=frac(2n)!(n!)^2$$
I'm wondering how this identity can be proven. Note that there are $n+1$ terms on the LHS.
combinatorics number-theory
asked Sep 10 at 20:35
Adam
398113
Let $ninmathbbN$. I observed today that
$$1+n+sum_i_1=1^ni_1+sum_i_2=1^nsum_i_1=1^i_2i_1+sum_i_3=1^nsum_i_2=1^i_3sum_i_1=1^i_2i_1+dots + sum_i_n-1^nsum_i_n-2=1^i_n-1dotssum_i_1=1^i_2i_1=frac(2n)!(n!)^2$$
I'm wondering how this identity can be proven. Note that there are $n+1$ terms on the LHS.
combinatorics number-theory
combinatorics number-theory
asked Sep 10 at 20:35
Adam
398113
asked Sep 10 at 20:35
Adam
398113
edited Sep 10 at 20:53
asked Sep 10 at 20:35
Adam
398113
asked Sep 10 at 20:35
Adam
398113
asked Sep 10 at 20:35
Adam
398113
398113
2
The right side is $(n+1)C_n$, where $C_n$ is the Catalan number. So it looks like the left side counts the number of catalan paths, with multiplicity. I'd guess that multiplicity is from where the path makes its first turn.
– Alex R.
Sep 10 at 21:00
add a comment |Â
2
The right side is $(n+1)C_n$, where $C_n$ is the Catalan number. So it looks like the left side counts the number of catalan paths, with multiplicity. I'd guess that multiplicity is from where the path makes its first turn.
– Alex R.
Sep 10 at 21:00
2
2
The right side is $(n+1)C_n$, where $C_n$ is the Catalan number. So it looks like the left side counts the number of catalan paths, with multiplicity. I'd guess that multiplicity is from where the path makes its first turn.
– Alex R.
Sep 10 at 21:00
The right side is $(n+1)C_n$, where $C_n$ is the Catalan number. So it looks like the left side counts the number of catalan paths, with multiplicity. I'd guess that multiplicity is from where the path makes its first turn.
– Alex R.
Sep 10 at 21:00
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
3
down vote
accepted
Ignoring the initial $1$ on the LHS, you can write the $k^th$ term on the LHS as
$$
sum_i_1=1^nsum_i_2=1^i_1cdots sum_i_k=1^i_k-1i_k=sum_i_1=1^nsum_i_2=1^i_1cdots sum_i_k=1^i_k-1sum_i_k+1=1^i_k1
$$
Since we are summing the number $1$, the value of the summation is just equal to the number of ways to choose the indices.
A choice of indices is a weakly decreasing list $nge i_1ge i_2ge dots ge i_kge i_k+1ge 1$. Choosing these is equivalent to choosing a multi-set of $[n]$ of size $k+1$, the number of which is $binomn+kn-1$. Therefore, the LHS is
$$
1+binomnn-1+binomn+1n-1+dots+binom2n-1n-1,
$$
and the result follows by the hockey stick identity.
answered Sep 10 at 21:19
Mike Earnest
18.6k11950
add a comment |Â
up vote
2
down vote
Fix $1leqslant pleqslant 2n$ and let $A_p$ denote the number of ways to choose an $n$ element subset $T$ of $1, ldots, 2n$ with $max T=p$. Note that $A_p=0$ for $p<n$, $A_n=1$, and for $1leqslant jleqslant n$, $$A_n+j=sum_i_j=1^nldots sum_i_2=1^i_3 sum_i_1=1^i_21 = sum_i_j=1^nldots sum_i_2=1^i_3i_2.$$ Summing over $p$ gives the number of $n$ element subsets of $2n$, which is $binom2nn$, your right side, and it is also equal to $sum_p=n^2nA_p$, which is your left side.
answered Sep 10 at 21:30
bangs
4628
+1, But I think it is not quite so obvious why $A_n+j$ is equal to the number of subsets with maximum $n+j$. What do the numbers $i_1,i_2,dots,i_j$ represent?
– Mike Earnest
Sep 10 at 21:38
It was obvious enough to me that that's what the left side was counting without interpreting the indices. But I came up with: Computing $A_n+j$ involves counting a certain number of sets $T$ with $|T|=n$ and $max T=n+j$, which is the same as counting the distinct sets $1, ldots, n+jsetminus T$. Thus we can count the number of $j$ element subsets of $1, ldots, n+j-1$. If $U=t_1, ldots, t_j$ with $t_1<ldots <t_j$ is such a set, $i_k=t_k-k+1$ gives a $1$-$1$ correspondence to the indices that the sum $sum_i_j=1^n ldots sum_i_2=1^i_3sum_i_1=1^i_21$ is counting.
– bangs
Sep 10 at 21:59
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
accepted
Ignoring the initial $1$ on the LHS, you can write the $k^th$ term on the LHS as
$$
sum_i_1=1^nsum_i_2=1^i_1cdots sum_i_k=1^i_k-1i_k=sum_i_1=1^nsum_i_2=1^i_1cdots sum_i_k=1^i_k-1sum_i_k+1=1^i_k1
$$
Since we are summing the number $1$, the value of the summation is just equal to the number of ways to choose the indices.
A choice of indices is a weakly decreasing list $nge i_1ge i_2ge dots ge i_kge i_k+1ge 1$. Choosing these is equivalent to choosing a multi-set of $[n]$ of size $k+1$, the number of which is $binomn+kn-1$. Therefore, the LHS is
$$
1+binomnn-1+binomn+1n-1+dots+binom2n-1n-1,
$$
and the result follows by the hockey stick identity.
answered Sep 10 at 21:19
Mike Earnest
18.6k11950
add a comment |Â
up vote
3
down vote
accepted
Ignoring the initial $1$ on the LHS, you can write the $k^th$ term on the LHS as
$$
sum_i_1=1^nsum_i_2=1^i_1cdots sum_i_k=1^i_k-1i_k=sum_i_1=1^nsum_i_2=1^i_1cdots sum_i_k=1^i_k-1sum_i_k+1=1^i_k1
$$
Since we are summing the number $1$, the value of the summation is just equal to the number of ways to choose the indices.
A choice of indices is a weakly decreasing list $nge i_1ge i_2ge dots ge i_kge i_k+1ge 1$. Choosing these is equivalent to choosing a multi-set of $[n]$ of size $k+1$, the number of which is $binomn+kn-1$. Therefore, the LHS is
$$
1+binomnn-1+binomn+1n-1+dots+binom2n-1n-1,
$$
and the result follows by the hockey stick identity.
answered Sep 10 at 21:19
Mike Earnest
18.6k11950
add a comment |Â
up vote
3
down vote
accepted
up vote
3
down vote
accepted
Ignoring the initial $1$ on the LHS, you can write the $k^th$ term on the LHS as
$$
sum_i_1=1^nsum_i_2=1^i_1cdots sum_i_k=1^i_k-1i_k=sum_i_1=1^nsum_i_2=1^i_1cdots sum_i_k=1^i_k-1sum_i_k+1=1^i_k1
$$
Since we are summing the number $1$, the value of the summation is just equal to the number of ways to choose the indices.
A choice of indices is a weakly decreasing list $nge i_1ge i_2ge dots ge i_kge i_k+1ge 1$. Choosing these is equivalent to choosing a multi-set of $[n]$ of size $k+1$, the number of which is $binomn+kn-1$. Therefore, the LHS is
$$
1+binomnn-1+binomn+1n-1+dots+binom2n-1n-1,
$$
and the result follows by the hockey stick identity.
answered Sep 10 at 21:19
Mike Earnest
18.6k11950
Ignoring the initial $1$ on the LHS, you can write the $k^th$ term on the LHS as
$$
sum_i_1=1^nsum_i_2=1^i_1cdots sum_i_k=1^i_k-1i_k=sum_i_1=1^nsum_i_2=1^i_1cdots sum_i_k=1^i_k-1sum_i_k+1=1^i_k1
$$
Since we are summing the number $1$, the value of the summation is just equal to the number of ways to choose the indices.
A choice of indices is a weakly decreasing list $nge i_1ge i_2ge dots ge i_kge i_k+1ge 1$. Choosing these is equivalent to choosing a multi-set of $[n]$ of size $k+1$, the number of which is $binomn+kn-1$. Therefore, the LHS is
$$
1+binomnn-1+binomn+1n-1+dots+binom2n-1n-1,
$$
and the result follows by the hockey stick identity.
answered Sep 10 at 21:19
Mike Earnest
18.6k11950
answered Sep 10 at 21:19
Mike Earnest
18.6k11950
answered Sep 10 at 21:19
Mike Earnest
18.6k11950
answered Sep 10 at 21:19
Mike Earnest
18.6k11950
18.6k11950
add a comment |Â
add a comment |Â
up vote
2
down vote
Fix $1leqslant pleqslant 2n$ and let $A_p$ denote the number of ways to choose an $n$ element subset $T$ of $1, ldots, 2n$ with $max T=p$. Note that $A_p=0$ for $p<n$, $A_n=1$, and for $1leqslant jleqslant n$, $$A_n+j=sum_i_j=1^nldots sum_i_2=1^i_3 sum_i_1=1^i_21 = sum_i_j=1^nldots sum_i_2=1^i_3i_2.$$ Summing over $p$ gives the number of $n$ element subsets of $2n$, which is $binom2nn$, your right side, and it is also equal to $sum_p=n^2nA_p$, which is your left side.
answered Sep 10 at 21:30
bangs
4628
+1, But I think it is not quite so obvious why $A_n+j$ is equal to the number of subsets with maximum $n+j$. What do the numbers $i_1,i_2,dots,i_j$ represent?
– Mike Earnest
Sep 10 at 21:38
It was obvious enough to me that that's what the left side was counting without interpreting the indices. But I came up with: Computing $A_n+j$ involves counting a certain number of sets $T$ with $|T|=n$ and $max T=n+j$, which is the same as counting the distinct sets $1, ldots, n+jsetminus T$. Thus we can count the number of $j$ element subsets of $1, ldots, n+j-1$. If $U=t_1, ldots, t_j$ with $t_1<ldots <t_j$ is such a set, $i_k=t_k-k+1$ gives a $1$-$1$ correspondence to the indices that the sum $sum_i_j=1^n ldots sum_i_2=1^i_3sum_i_1=1^i_21$ is counting.
– bangs
Sep 10 at 21:59
add a comment |Â
up vote
2
down vote
Fix $1leqslant pleqslant 2n$ and let $A_p$ denote the number of ways to choose an $n$ element subset $T$ of $1, ldots, 2n$ with $max T=p$. Note that $A_p=0$ for $p<n$, $A_n=1$, and for $1leqslant jleqslant n$, $$A_n+j=sum_i_j=1^nldots sum_i_2=1^i_3 sum_i_1=1^i_21 = sum_i_j=1^nldots sum_i_2=1^i_3i_2.$$ Summing over $p$ gives the number of $n$ element subsets of $2n$, which is $binom2nn$, your right side, and it is also equal to $sum_p=n^2nA_p$, which is your left side.
answered Sep 10 at 21:30
bangs
4628
+1, But I think it is not quite so obvious why $A_n+j$ is equal to the number of subsets with maximum $n+j$. What do the numbers $i_1,i_2,dots,i_j$ represent?
– Mike Earnest
Sep 10 at 21:38
It was obvious enough to me that that's what the left side was counting without interpreting the indices. But I came up with: Computing $A_n+j$ involves counting a certain number of sets $T$ with $|T|=n$ and $max T=n+j$, which is the same as counting the distinct sets $1, ldots, n+jsetminus T$. Thus we can count the number of $j$ element subsets of $1, ldots, n+j-1$. If $U=t_1, ldots, t_j$ with $t_1<ldots <t_j$ is such a set, $i_k=t_k-k+1$ gives a $1$-$1$ correspondence to the indices that the sum $sum_i_j=1^n ldots sum_i_2=1^i_3sum_i_1=1^i_21$ is counting.
– bangs
Sep 10 at 21:59
add a comment |Â
up vote
2
down vote
up vote
2
down vote
Fix $1leqslant pleqslant 2n$ and let $A_p$ denote the number of ways to choose an $n$ element subset $T$ of $1, ldots, 2n$ with $max T=p$. Note that $A_p=0$ for $p<n$, $A_n=1$, and for $1leqslant jleqslant n$, $$A_n+j=sum_i_j=1^nldots sum_i_2=1^i_3 sum_i_1=1^i_21 = sum_i_j=1^nldots sum_i_2=1^i_3i_2.$$ Summing over $p$ gives the number of $n$ element subsets of $2n$, which is $binom2nn$, your right side, and it is also equal to $sum_p=n^2nA_p$, which is your left side.
answered Sep 10 at 21:30
bangs
4628
Fix $1leqslant pleqslant 2n$ and let $A_p$ denote the number of ways to choose an $n$ element subset $T$ of $1, ldots, 2n$ with $max T=p$. Note that $A_p=0$ for $p<n$, $A_n=1$, and for $1leqslant jleqslant n$, $$A_n+j=sum_i_j=1^nldots sum_i_2=1^i_3 sum_i_1=1^i_21 = sum_i_j=1^nldots sum_i_2=1^i_3i_2.$$ Summing over $p$ gives the number of $n$ element subsets of $2n$, which is $binom2nn$, your right side, and it is also equal to $sum_p=n^2nA_p$, which is your left side.
answered Sep 10 at 21:30
bangs
4628
answered Sep 10 at 21:30
bangs
4628
answered Sep 10 at 21:30
bangs
4628
answered Sep 10 at 21:30
bangs
4628
4628
+1, But I think it is not quite so obvious why $A_n+j$ is equal to the number of subsets with maximum $n+j$. What do the numbers $i_1,i_2,dots,i_j$ represent?
– Mike Earnest
Sep 10 at 21:38
It was obvious enough to me that that's what the left side was counting without interpreting the indices. But I came up with: Computing $A_n+j$ involves counting a certain number of sets $T$ with $|T|=n$ and $max T=n+j$, which is the same as counting the distinct sets $1, ldots, n+jsetminus T$. Thus we can count the number of $j$ element subsets of $1, ldots, n+j-1$. If $U=t_1, ldots, t_j$ with $t_1<ldots <t_j$ is such a set, $i_k=t_k-k+1$ gives a $1$-$1$ correspondence to the indices that the sum $sum_i_j=1^n ldots sum_i_2=1^i_3sum_i_1=1^i_21$ is counting.
– bangs
Sep 10 at 21:59
add a comment |Â
+1, But I think it is not quite so obvious why $A_n+j$ is equal to the number of subsets with maximum $n+j$. What do the numbers $i_1,i_2,dots,i_j$ represent?
– Mike Earnest
Sep 10 at 21:38
It was obvious enough to me that that's what the left side was counting without interpreting the indices. But I came up with: Computing $A_n+j$ involves counting a certain number of sets $T$ with $|T|=n$ and $max T=n+j$, which is the same as counting the distinct sets $1, ldots, n+jsetminus T$. Thus we can count the number of $j$ element subsets of $1, ldots, n+j-1$. If $U=t_1, ldots, t_j$ with $t_1<ldots <t_j$ is such a set, $i_k=t_k-k+1$ gives a $1$-$1$ correspondence to the indices that the sum $sum_i_j=1^n ldots sum_i_2=1^i_3sum_i_1=1^i_21$ is counting.
– bangs
Sep 10 at 21:59
+1, But I think it is not quite so obvious why $A_n+j$ is equal to the number of subsets with maximum $n+j$. What do the numbers $i_1,i_2,dots,i_j$ represent?
– Mike Earnest
Sep 10 at 21:38
+1, But I think it is not quite so obvious why $A_n+j$ is equal to the number of subsets with maximum $n+j$. What do the numbers $i_1,i_2,dots,i_j$ represent?
– Mike Earnest
Sep 10 at 21:38
It was obvious enough to me that that's what the left side was counting without interpreting the indices. But I came up with: Computing $A_n+j$ involves counting a certain number of sets $T$ with $|T|=n$ and $max T=n+j$, which is the same as counting the distinct sets $1, ldots, n+jsetminus T$. Thus we can count the number of $j$ element subsets of $1, ldots, n+j-1$. If $U=t_1, ldots, t_j$ with $t_1<ldots <t_j$ is such a set, $i_k=t_k-k+1$ gives a $1$-$1$ correspondence to the indices that the sum $sum_i_j=1^n ldots sum_i_2=1^i_3sum_i_1=1^i_21$ is counting.
– bangs
Sep 10 at 21:59
It was obvious enough to me that that's what the left side was counting without interpreting the indices. But I came up with: Computing $A_n+j$ involves counting a certain number of sets $T$ with $|T|=n$ and $max T=n+j$, which is the same as counting the distinct sets $1, ldots, n+jsetminus T$. Thus we can count the number of $j$ element subsets of $1, ldots, n+j-1$. If $U=t_1, ldots, t_j$ with $t_1<ldots <t_j$ is such a set, $i_k=t_k-k+1$ gives a $1$-$1$ correspondence to the indices that the sum $sum_i_j=1^n ldots sum_i_2=1^i_3sum_i_1=1^i_21$ is counting.
– bangs
Sep 10 at 21:59
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%2f2912325%2fhow-to-prove-this-strange-combinatorical-identity%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
2
The right side is $(n+1)C_n$, where $C_n$ is the Catalan number. So it looks like the left side counts the number of catalan paths, with multiplicity. I'd guess that multiplicity is from where the path makes its first turn.
– Alex R.
Sep 10 at 21:00