Combinations of red and black balls
Given $N$ Identical Red balls and $M$ Identical Black balls, in how many ways we can arrange them such that not more than $K$ adjacent balls are of same color.
Example : For $1$ Red ball and $1$ black ball, with $K=1$, there are $2$ ways $[RB,BR]$
Can there be a general formula for given $N$,$M$ and $K$ ?
I have read about Dutch flag problem to find number of ways to find such that no adjacent balls are of same color. I am bit stuck on how to find for at max K balls.
combinatorics number-theory algorithms dynamic-programming
asked Jan 4 at 17:01
Gaurav GuptaGaurav Gupta
212
New contributor
Gaurav Gupta is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
|
show 1 more comment
Given $N$ Identical Red balls and $M$ Identical Black balls, in how many ways we can arrange them such that not more than $K$ adjacent balls are of same color.
Example : For $1$ Red ball and $1$ black ball, with $K=1$, there are $2$ ways $[RB,BR]$
Can there be a general formula for given $N$,$M$ and $K$ ?
I have read about Dutch flag problem to find number of ways to find such that no adjacent balls are of same color. I am bit stuck on how to find for at max K balls.
combinatorics number-theory algorithms dynamic-programming
asked Jan 4 at 17:01
Gaurav GuptaGaurav Gupta
212
New contributor
Gaurav Gupta is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
I'm pretty sure there is no closed form.
– Don Thousand
Jan 4 at 17:09
@DonThousand No closed form as in ?
– Gaurav Gupta
Jan 4 at 17:19
No general formula
– Don Thousand
Jan 4 at 17:20
@DonThousand Ah I see. I was thinking of something like, if 1 adjacent ball can be of same color then how many ways + if 2 adjacent balls can be of same color then how manys and so on upto K. Wasn't able to have a general solution :(
– Gaurav Gupta
Jan 4 at 17:23
@DonThousand Looks like there exist a dynamic programming solution to this to find it.
– Gaurav Gupta
Jan 4 at 17:43
|
show 1 more comment
Given $N$ Identical Red balls and $M$ Identical Black balls, in how many ways we can arrange them such that not more than $K$ adjacent balls are of same color.
Example : For $1$ Red ball and $1$ black ball, with $K=1$, there are $2$ ways $[RB,BR]$
Can there be a general formula for given $N$,$M$ and $K$ ?
I have read about Dutch flag problem to find number of ways to find such that no adjacent balls are of same color. I am bit stuck on how to find for at max K balls.
combinatorics number-theory algorithms dynamic-programming
asked Jan 4 at 17:01
Gaurav GuptaGaurav Gupta
212
New contributor
Gaurav Gupta is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Given $N$ Identical Red balls and $M$ Identical Black balls, in how many ways we can arrange them such that not more than $K$ adjacent balls are of same color.
Example : For $1$ Red ball and $1$ black ball, with $K=1$, there are $2$ ways $[RB,BR]$
Can there be a general formula for given $N$,$M$ and $K$ ?
I have read about Dutch flag problem to find number of ways to find such that no adjacent balls are of same color. I am bit stuck on how to find for at max K balls.
combinatorics number-theory algorithms dynamic-programming
combinatorics number-theory algorithms dynamic-programming
asked Jan 4 at 17:01
Gaurav GuptaGaurav Gupta
212
New contributor
Gaurav Gupta is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Jan 4 at 17:01
Gaurav GuptaGaurav Gupta
212
New contributor
Gaurav Gupta is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited Jan 4 at 17:44
Gaurav Gupta
asked Jan 4 at 17:01
Gaurav GuptaGaurav Gupta
212
New contributor
Gaurav Gupta is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Jan 4 at 17:01
Gaurav GuptaGaurav Gupta
212
asked Jan 4 at 17:01
Gaurav GuptaGaurav Gupta
212
212
New contributor
Gaurav Gupta is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Gaurav Gupta is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Gaurav Gupta is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
I'm pretty sure there is no closed form.
– Don Thousand
Jan 4 at 17:09
@DonThousand No closed form as in ?
– Gaurav Gupta
Jan 4 at 17:19
No general formula
– Don Thousand
Jan 4 at 17:20
@DonThousand Ah I see. I was thinking of something like, if 1 adjacent ball can be of same color then how many ways + if 2 adjacent balls can be of same color then how manys and so on upto K. Wasn't able to have a general solution :(
– Gaurav Gupta
Jan 4 at 17:23
@DonThousand Looks like there exist a dynamic programming solution to this to find it.
– Gaurav Gupta
Jan 4 at 17:43
|
show 1 more comment
I'm pretty sure there is no closed form.
– Don Thousand
Jan 4 at 17:09
@DonThousand No closed form as in ?
– Gaurav Gupta
Jan 4 at 17:19
No general formula
– Don Thousand
Jan 4 at 17:20
@DonThousand Ah I see. I was thinking of something like, if 1 adjacent ball can be of same color then how many ways + if 2 adjacent balls can be of same color then how manys and so on upto K. Wasn't able to have a general solution :(
– Gaurav Gupta
Jan 4 at 17:23
@DonThousand Looks like there exist a dynamic programming solution to this to find it.
– Gaurav Gupta
Jan 4 at 17:43
I'm pretty sure there is no closed form.
– Don Thousand
Jan 4 at 17:09
I'm pretty sure there is no closed form.
– Don Thousand
Jan 4 at 17:09
@DonThousand No closed form as in ?
– Gaurav Gupta
Jan 4 at 17:19
@DonThousand No closed form as in ?
– Gaurav Gupta
Jan 4 at 17:19
No general formula
– Don Thousand
Jan 4 at 17:20
No general formula
– Don Thousand
Jan 4 at 17:20
@DonThousand Ah I see. I was thinking of something like, if 1 adjacent ball can be of same color then how many ways + if 2 adjacent balls can be of same color then how manys and so on upto K. Wasn't able to have a general solution :(
– Gaurav Gupta
Jan 4 at 17:23
@DonThousand Ah I see. I was thinking of something like, if 1 adjacent ball can be of same color then how many ways + if 2 adjacent balls can be of same color then how manys and so on upto K. Wasn't able to have a general solution :(
– Gaurav Gupta
Jan 4 at 17:23
@DonThousand Looks like there exist a dynamic programming solution to this to find it.
– Gaurav Gupta
Jan 4 at 17:43
@DonThousand Looks like there exist a dynamic programming solution to this to find it.
– Gaurav Gupta
Jan 4 at 17:43
|
show 1 more comment
1 Answer
1
active
oldest
votes
$f(n,k) = $ number of sequences with $n$ balls and exactly $k$ repeats, which is exactly this:
$f(n,k) = 2 binom{n-1}{k}$
Essentially, there are two sequences with 0 repeats and $n-k$ length. Given a string with no repeats, we choose how many extra balls are added into each spot, which is equivalent to multiplying by the multichoose $left( binom{n-k}{k} right) = binom{n-1}{k}$.
I guess you’d want to sum this function for all k less than K, but that’s the nicest idea I could come up with. Apologies for my sloppy phrasing, I can clarify where needed.
answered Jan 5 at 11:40
Zachary HunterZachary Hunter
51310
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Gaurav Gupta is a new contributor. Be nice, and check out our Code of Conduct.
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%2f3061834%2fcombinations-of-red-and-black-balls%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$f(n,k) = $ number of sequences with $n$ balls and exactly $k$ repeats, which is exactly this:
$f(n,k) = 2 binom{n-1}{k}$
Essentially, there are two sequences with 0 repeats and $n-k$ length. Given a string with no repeats, we choose how many extra balls are added into each spot, which is equivalent to multiplying by the multichoose $left( binom{n-k}{k} right) = binom{n-1}{k}$.
I guess you’d want to sum this function for all k less than K, but that’s the nicest idea I could come up with. Apologies for my sloppy phrasing, I can clarify where needed.
answered Jan 5 at 11:40
Zachary HunterZachary Hunter
51310
add a comment |
$f(n,k) = $ number of sequences with $n$ balls and exactly $k$ repeats, which is exactly this:
$f(n,k) = 2 binom{n-1}{k}$
Essentially, there are two sequences with 0 repeats and $n-k$ length. Given a string with no repeats, we choose how many extra balls are added into each spot, which is equivalent to multiplying by the multichoose $left( binom{n-k}{k} right) = binom{n-1}{k}$.
I guess you’d want to sum this function for all k less than K, but that’s the nicest idea I could come up with. Apologies for my sloppy phrasing, I can clarify where needed.
answered Jan 5 at 11:40
Zachary HunterZachary Hunter
51310
add a comment |
$f(n,k) = $ number of sequences with $n$ balls and exactly $k$ repeats, which is exactly this:
$f(n,k) = 2 binom{n-1}{k}$
Essentially, there are two sequences with 0 repeats and $n-k$ length. Given a string with no repeats, we choose how many extra balls are added into each spot, which is equivalent to multiplying by the multichoose $left( binom{n-k}{k} right) = binom{n-1}{k}$.
I guess you’d want to sum this function for all k less than K, but that’s the nicest idea I could come up with. Apologies for my sloppy phrasing, I can clarify where needed.
answered Jan 5 at 11:40
Zachary HunterZachary Hunter
51310
$f(n,k) = $ number of sequences with $n$ balls and exactly $k$ repeats, which is exactly this:
$f(n,k) = 2 binom{n-1}{k}$
Essentially, there are two sequences with 0 repeats and $n-k$ length. Given a string with no repeats, we choose how many extra balls are added into each spot, which is equivalent to multiplying by the multichoose $left( binom{n-k}{k} right) = binom{n-1}{k}$.
I guess you’d want to sum this function for all k less than K, but that’s the nicest idea I could come up with. Apologies for my sloppy phrasing, I can clarify where needed.
answered Jan 5 at 11:40
Zachary HunterZachary Hunter
51310
answered Jan 5 at 11:40
Zachary HunterZachary Hunter
51310
answered Jan 5 at 11:40
Zachary HunterZachary Hunter
51310
answered Jan 5 at 11:40
Zachary HunterZachary Hunter
51310
51310
add a comment |
add a comment |
Gaurav Gupta is a new contributor. Be nice, and check out our Code of Conduct.
Gaurav Gupta is a new contributor. Be nice, and check out our Code of Conduct.
Gaurav Gupta is a new contributor. Be nice, and check out our Code of Conduct.
Gaurav Gupta is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
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%2f3061834%2fcombinations-of-red-and-black-balls%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'm pretty sure there is no closed form.
– Don Thousand
Jan 4 at 17:09
@DonThousand No closed form as in ?
– Gaurav Gupta
Jan 4 at 17:19
No general formula
– Don Thousand
Jan 4 at 17:20
@DonThousand Ah I see. I was thinking of something like, if 1 adjacent ball can be of same color then how many ways + if 2 adjacent balls can be of same color then how manys and so on upto K. Wasn't able to have a general solution :(
– Gaurav Gupta
Jan 4 at 17:23
@DonThousand Looks like there exist a dynamic programming solution to this to find it.
– Gaurav Gupta
Jan 4 at 17:43