Combinations of red and black balls
$begingroup$
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
$endgroup$
|
show 1 more comment
$begingroup$
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
$endgroup$
$begingroup$
I'm pretty sure there is no closed form.
$endgroup$
– Don Thousand
Jan 4 at 17:09
$begingroup$
@DonThousand No closed form as in ?
$endgroup$
– Gaurav Gupta
Jan 4 at 17:19
$begingroup$
No general formula
$endgroup$
– Don Thousand
Jan 4 at 17:20
$begingroup$
@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 :(
$endgroup$
– Gaurav Gupta
Jan 4 at 17:23
$begingroup$
@DonThousand Looks like there exist a dynamic programming solution to this to find it.
$endgroup$
– Gaurav Gupta
Jan 4 at 17:43
|
show 1 more comment
$begingroup$
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
$endgroup$
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
asked Jan 4 at 17:01
Gaurav GuptaGaurav Gupta
212
edited Jan 4 at 17:44
Gaurav Gupta
asked Jan 4 at 17:01
Gaurav GuptaGaurav Gupta
212
asked Jan 4 at 17:01
Gaurav GuptaGaurav Gupta
212
asked Jan 4 at 17:01
Gaurav GuptaGaurav Gupta
212
212
$begingroup$
I'm pretty sure there is no closed form.
$endgroup$
– Don Thousand
Jan 4 at 17:09
$begingroup$
@DonThousand No closed form as in ?
$endgroup$
– Gaurav Gupta
Jan 4 at 17:19
$begingroup$
No general formula
$endgroup$
– Don Thousand
Jan 4 at 17:20
$begingroup$
@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 :(
$endgroup$
– Gaurav Gupta
Jan 4 at 17:23
$begingroup$
@DonThousand Looks like there exist a dynamic programming solution to this to find it.
$endgroup$
– Gaurav Gupta
Jan 4 at 17:43
|
show 1 more comment
$begingroup$
I'm pretty sure there is no closed form.
$endgroup$
– Don Thousand
Jan 4 at 17:09
$begingroup$
@DonThousand No closed form as in ?
$endgroup$
– Gaurav Gupta
Jan 4 at 17:19
$begingroup$
No general formula
$endgroup$
– Don Thousand
Jan 4 at 17:20
$begingroup$
@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 :(
$endgroup$
– Gaurav Gupta
Jan 4 at 17:23
$begingroup$
@DonThousand Looks like there exist a dynamic programming solution to this to find it.
$endgroup$
– Gaurav Gupta
Jan 4 at 17:43
$begingroup$
I'm pretty sure there is no closed form.
$endgroup$
– Don Thousand
Jan 4 at 17:09
$begingroup$
I'm pretty sure there is no closed form.
$endgroup$
– Don Thousand
Jan 4 at 17:09
$begingroup$
@DonThousand No closed form as in ?
$endgroup$
– Gaurav Gupta
Jan 4 at 17:19
$begingroup$
@DonThousand No closed form as in ?
$endgroup$
– Gaurav Gupta
Jan 4 at 17:19
$begingroup$
No general formula
$endgroup$
– Don Thousand
Jan 4 at 17:20
$begingroup$
No general formula
$endgroup$
– Don Thousand
Jan 4 at 17:20
$begingroup$
@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 :(
$endgroup$
– Gaurav Gupta
Jan 4 at 17:23
$begingroup$
@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 :(
$endgroup$
– Gaurav Gupta
Jan 4 at 17:23
$begingroup$
@DonThousand Looks like there exist a dynamic programming solution to this to find it.
$endgroup$
– Gaurav Gupta
Jan 4 at 17:43
$begingroup$
@DonThousand Looks like there exist a dynamic programming solution to this to find it.
$endgroup$
– Gaurav Gupta
Jan 4 at 17:43
|
show 1 more comment
1 Answer
1
active
oldest
votes
$begingroup$
$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
57611
$endgroup$
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
});
}
});
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
$begingroup$
$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
57611
$endgroup$
add a comment |
$begingroup$
$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
57611
$endgroup$
add a comment |
$begingroup$
$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
57611
$endgroup$
$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
57611
answered Jan 5 at 11:40
Zachary HunterZachary Hunter
57611
answered Jan 5 at 11:40
Zachary HunterZachary Hunter
57611
answered Jan 5 at 11:40
Zachary HunterZachary Hunter
57611
57611
add a comment |
add a comment |
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.
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
$begingroup$
I'm pretty sure there is no closed form.
$endgroup$
– Don Thousand
Jan 4 at 17:09
$begingroup$
@DonThousand No closed form as in ?
$endgroup$
– Gaurav Gupta
Jan 4 at 17:19
$begingroup$
No general formula
$endgroup$
– Don Thousand
Jan 4 at 17:20
$begingroup$
@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 :(
$endgroup$
– Gaurav Gupta
Jan 4 at 17:23
$begingroup$
@DonThousand Looks like there exist a dynamic programming solution to this to find it.
$endgroup$
– Gaurav Gupta
Jan 4 at 17:43