Mixing
Number of ways to insert $kin[n]$ identical elements to two $n$ long lists
up vote
1
down vote
favorite
Suppose we have two lists $a=a_{1},a_{2},ldots,a_{n}$, $ b=b_{1},b_{2},ldots,b_{n}$ and we want to determine how many ways there are to insert $k$ identical elements $X$ independently into both lists (i.e. at the beginning, between two elements, or at the end, where we can have consecutive Xs) and $k$ can range from 1 to $n$.
Given $k$, we can model this as choosing $k$ slots with replacement out of the $n+1$ available slots. Since both lists are independent, this should be squared, giving $$binom{n+k}{n}^{2}$$
Considering any possible $kinleft[nright]$, this becomes $$sum_{k=1}^{n}binom{n+k}{n}^{2}$$
Is this analysis correct? If so, what is the best exponential lower bound I can get for the above expression?
combinatorics
asked 2 days ago
H.Rappeport
6161410
add a comment |
up vote
1
down vote
favorite
Suppose we have two lists $a=a_{1},a_{2},ldots,a_{n}$, $ b=b_{1},b_{2},ldots,b_{n}$ and we want to determine how many ways there are to insert $k$ identical elements $X$ independently into both lists (i.e. at the beginning, between two elements, or at the end, where we can have consecutive Xs) and $k$ can range from 1 to $n$.
Given $k$, we can model this as choosing $k$ slots with replacement out of the $n+1$ available slots. Since both lists are independent, this should be squared, giving $$binom{n+k}{n}^{2}$$
Considering any possible $kinleft[nright]$, this becomes $$sum_{k=1}^{n}binom{n+k}{n}^{2}$$
Is this analysis correct? If so, what is the best exponential lower bound I can get for the above expression?
combinatorics
asked 2 days ago
H.Rappeport
6161410
I think it should be $n+kchoose n$ not $n+k-1choose n$. I don't understand why you are choosing $k-1$ slots when you have $k$ identical elements.
– Levent
2 days ago
Oi, you are right of course, thanks.
– H.Rappeport
2 days ago
I want to point out that $2^{2n}$ is a lower bound for the expression if that is useful to you.
– Levent
2 days ago
@Levent Could you provide a reference or a sketch of the derivation for this bound?
– H.Rappeport
2 days ago
Note that the last summand is ${2nchoose n}^2$ and I used the fact that $2^nleq{2nchoose n}$.
– Levent
yesterday
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Suppose we have two lists $a=a_{1},a_{2},ldots,a_{n}$, $ b=b_{1},b_{2},ldots,b_{n}$ and we want to determine how many ways there are to insert $k$ identical elements $X$ independently into both lists (i.e. at the beginning, between two elements, or at the end, where we can have consecutive Xs) and $k$ can range from 1 to $n$.
Given $k$, we can model this as choosing $k$ slots with replacement out of the $n+1$ available slots. Since both lists are independent, this should be squared, giving $$binom{n+k}{n}^{2}$$
Considering any possible $kinleft[nright]$, this becomes $$sum_{k=1}^{n}binom{n+k}{n}^{2}$$
Is this analysis correct? If so, what is the best exponential lower bound I can get for the above expression?
combinatorics
asked 2 days ago
H.Rappeport
6161410
Suppose we have two lists $a=a_{1},a_{2},ldots,a_{n}$, $ b=b_{1},b_{2},ldots,b_{n}$ and we want to determine how many ways there are to insert $k$ identical elements $X$ independently into both lists (i.e. at the beginning, between two elements, or at the end, where we can have consecutive Xs) and $k$ can range from 1 to $n$.
Given $k$, we can model this as choosing $k$ slots with replacement out of the $n+1$ available slots. Since both lists are independent, this should be squared, giving $$binom{n+k}{n}^{2}$$
Considering any possible $kinleft[nright]$, this becomes $$sum_{k=1}^{n}binom{n+k}{n}^{2}$$
Is this analysis correct? If so, what is the best exponential lower bound I can get for the above expression?
combinatorics
combinatorics
asked 2 days ago
H.Rappeport
6161410
asked 2 days ago
H.Rappeport
6161410
edited 2 days ago
asked 2 days ago
H.Rappeport
6161410
asked 2 days ago
H.Rappeport
6161410
asked 2 days ago
H.Rappeport
6161410
6161410
I think it should be $n+kchoose n$ not $n+k-1choose n$. I don't understand why you are choosing $k-1$ slots when you have $k$ identical elements.
– Levent
2 days ago
Oi, you are right of course, thanks.
– H.Rappeport
2 days ago
I want to point out that $2^{2n}$ is a lower bound for the expression if that is useful to you.
– Levent
2 days ago
@Levent Could you provide a reference or a sketch of the derivation for this bound?
– H.Rappeport
2 days ago
Note that the last summand is ${2nchoose n}^2$ and I used the fact that $2^nleq{2nchoose n}$.
– Levent
yesterday
add a comment |
I think it should be $n+kchoose n$ not $n+k-1choose n$. I don't understand why you are choosing $k-1$ slots when you have $k$ identical elements.
– Levent
2 days ago
Oi, you are right of course, thanks.
– H.Rappeport
2 days ago
I want to point out that $2^{2n}$ is a lower bound for the expression if that is useful to you.
– Levent
2 days ago
@Levent Could you provide a reference or a sketch of the derivation for this bound?
– H.Rappeport
2 days ago
Note that the last summand is ${2nchoose n}^2$ and I used the fact that $2^nleq{2nchoose n}$.
– Levent
yesterday
I think it should be $n+kchoose n$ not $n+k-1choose n$. I don't understand why you are choosing $k-1$ slots when you have $k$ identical elements.
– Levent
2 days ago
I think it should be $n+kchoose n$ not $n+k-1choose n$. I don't understand why you are choosing $k-1$ slots when you have $k$ identical elements.
– Levent
2 days ago
Oi, you are right of course, thanks.
– H.Rappeport
2 days ago
Oi, you are right of course, thanks.
– H.Rappeport
2 days ago
I want to point out that $2^{2n}$ is a lower bound for the expression if that is useful to you.
– Levent
2 days ago
I want to point out that $2^{2n}$ is a lower bound for the expression if that is useful to you.
– Levent
2 days ago
@Levent Could you provide a reference or a sketch of the derivation for this bound?
– H.Rappeport
2 days ago
@Levent Could you provide a reference or a sketch of the derivation for this bound?
– H.Rappeport
2 days ago
Note that the last summand is ${2nchoose n}^2$ and I used the fact that $2^nleq{2nchoose n}$.
– Levent
yesterday
Note that the last summand is ${2nchoose n}^2$ and I used the fact that $2^nleq{2nchoose n}$.
– Levent
yesterday
add a comment |
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3005444%2fnumber-of-ways-to-insert-k-inn-identical-elements-to-two-n-long-lists%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
I think it should be $n+kchoose n$ not $n+k-1choose n$. I don't understand why you are choosing $k-1$ slots when you have $k$ identical elements.
– Levent
2 days ago
Oi, you are right of course, thanks.
– H.Rappeport
2 days ago
I want to point out that $2^{2n}$ is a lower bound for the expression if that is useful to you.
– Levent
2 days ago
@Levent Could you provide a reference or a sketch of the derivation for this bound?
– H.Rappeport
2 days ago
Note that the last summand is ${2nchoose n}^2$ and I used the fact that $2^nleq{2nchoose n}$.
– Levent
yesterday