Mixing
Amount of nondecreasing integer k-tuples with limited delta
$begingroup$
This is a followup to this question, where the difference between consecutive entries of the tuple is at most $Delta$.
Question: Given $k, n, Delta in mathbb{N}$, how many integer tuples $(x_1, dots, x_k)$ are there such that:
- $1 leq x_1 leq x_2 leq cdots leq x_{k-1} leq x_k leq n$
$x_{i+1} - x_{i} leq Delta$ for all $i$
If we had only the first bullet point, the answer is available on the linked question above.
If we had only the second bullet point, I believe we could say that the amount of tuples is equal to $(1 + Delta)^{k}$ because for each entry of the tuple we have $1 + Delta$ options to choose the increase relative to the last entry.
But we have both restrictions simultaneously, so of course the amount of tuples is bounded above by the minimum of both values, but I'm stuck trying to find out the exact value.
Any help is appreciated! Thanks!
combinatorics combinations
asked Jan 12 at 17:23
Pedro APedro A
2,0211827
$endgroup$
add a comment |
$begingroup$
This is a followup to this question, where the difference between consecutive entries of the tuple is at most $Delta$.
Question: Given $k, n, Delta in mathbb{N}$, how many integer tuples $(x_1, dots, x_k)$ are there such that:
- $1 leq x_1 leq x_2 leq cdots leq x_{k-1} leq x_k leq n$
$x_{i+1} - x_{i} leq Delta$ for all $i$
If we had only the first bullet point, the answer is available on the linked question above.
If we had only the second bullet point, I believe we could say that the amount of tuples is equal to $(1 + Delta)^{k}$ because for each entry of the tuple we have $1 + Delta$ options to choose the increase relative to the last entry.
But we have both restrictions simultaneously, so of course the amount of tuples is bounded above by the minimum of both values, but I'm stuck trying to find out the exact value.
Any help is appreciated! Thanks!
combinatorics combinations
asked Jan 12 at 17:23
Pedro APedro A
2,0211827
$endgroup$
add a comment |
$begingroup$
This is a followup to this question, where the difference between consecutive entries of the tuple is at most $Delta$.
Question: Given $k, n, Delta in mathbb{N}$, how many integer tuples $(x_1, dots, x_k)$ are there such that:
- $1 leq x_1 leq x_2 leq cdots leq x_{k-1} leq x_k leq n$
$x_{i+1} - x_{i} leq Delta$ for all $i$
If we had only the first bullet point, the answer is available on the linked question above.
If we had only the second bullet point, I believe we could say that the amount of tuples is equal to $(1 + Delta)^{k}$ because for each entry of the tuple we have $1 + Delta$ options to choose the increase relative to the last entry.
But we have both restrictions simultaneously, so of course the amount of tuples is bounded above by the minimum of both values, but I'm stuck trying to find out the exact value.
Any help is appreciated! Thanks!
combinatorics combinations
asked Jan 12 at 17:23
Pedro APedro A
2,0211827
$endgroup$
This is a followup to this question, where the difference between consecutive entries of the tuple is at most $Delta$.
Question: Given $k, n, Delta in mathbb{N}$, how many integer tuples $(x_1, dots, x_k)$ are there such that:
- $1 leq x_1 leq x_2 leq cdots leq x_{k-1} leq x_k leq n$
$x_{i+1} - x_{i} leq Delta$ for all $i$
If we had only the first bullet point, the answer is available on the linked question above.
If we had only the second bullet point, I believe we could say that the amount of tuples is equal to $(1 + Delta)^{k}$ because for each entry of the tuple we have $1 + Delta$ options to choose the increase relative to the last entry.
But we have both restrictions simultaneously, so of course the amount of tuples is bounded above by the minimum of both values, but I'm stuck trying to find out the exact value.
Any help is appreciated! Thanks!
combinatorics combinations
combinatorics combinations
asked Jan 12 at 17:23
Pedro APedro A
2,0211827
asked Jan 12 at 17:23
Pedro APedro A
2,0211827
asked Jan 12 at 17:23
Pedro APedro A
2,0211827
asked Jan 12 at 17:23
Pedro APedro A
2,0211827
asked Jan 12 at 17:23
Pedro APedro A
2,0211827
2,0211827
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Let $z_0,z_1,dots,z_k$ be variables defined by $z_i=x_{i+1}-x_i$, with the convention that $z_0=x_1-1$ and $z_k=n-x_k$ Note that
$$
z_0+z_1+dots+z_k=n-1,\
z_0,z_nge 0,\tag 1
0le z_ile Deltaquadtext{for }1le ile k-1
$$
The number of integer solutions to this system of equations and inequalities can be found using generating functions. It is the coefficient of $t^{n-1}$ in the generating function
$$
(1+t+dots+t^Delta)^{k-1}(1-t)^{-2}=(1-t^{Delta+1})^{k-1}(1-t)^{-(k+1)}
$$
This coefficient is
$$
boxed{sum_{i=0}^{frac{k+n-1}{Delta+1}}binom{k-1}i(-1)^ibinom{k+(n-i(Delta+1))-1}{k}.}
$$
Edit: You can also count the solutions to $(1)$ using the principle of inclusion exclusion. Start by counting solutions to $(1)$ while ignoring the conditions $z_ile Delta$ for $1 le i le k-1$. Now you just want to count the number of series ways to choose non-negative integers $z_i$ summing to $n-1$; by stars-and-bars, this is $binom{n-1+k}{k}$.
From these, we must subtract the bad solutions where some $z_ige Delta+1$. If say $z_1ge Delta+1$, then looking at the variables $z_0,z_1-(Delta+1),z_2,dots,z_k$, then we have $k+1$ nonnegative variables summing to $n-1-(Delta+1)$. The number of ways to choose the bad variable is $binom{k-1}1$, and there are $binom{n-1-(Delta+1)+k}{k}$ ways to choose the bad solutions, so we must subtract $binom{k-1}1binom{n-1-(Delta+1)+k}{k}$.
However, we have double subtracted the number of solutions with two bad variables. These must be added back in, then the triple bad solutions must be subtracted out, etc. Going all the way down, you arrive at the same summation as before.
answered Jan 12 at 18:52
Mike EarnestMike Earnest
22.6k12051
$endgroup$
$begingroup$
Hello. I am very happy to see a closed formula, thank you. But I have never heard of generating functions, I've just read a bit on Wikipedia right now but I don't really understand what you did here. Can you clarify a bit? Thank you very much :)
$endgroup$
– Pedro A
Jan 13 at 4:39
$begingroup$
@PedroA I added an alternate method. The generating function method is worth learning, but is a bit difficult to explain.
$endgroup$
– Mike Earnest
Jan 14 at 19:31
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%2f3071142%2famount-of-nondecreasing-integer-k-tuples-with-limited-delta%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$
Let $z_0,z_1,dots,z_k$ be variables defined by $z_i=x_{i+1}-x_i$, with the convention that $z_0=x_1-1$ and $z_k=n-x_k$ Note that
$$
z_0+z_1+dots+z_k=n-1,\
z_0,z_nge 0,\tag 1
0le z_ile Deltaquadtext{for }1le ile k-1
$$
The number of integer solutions to this system of equations and inequalities can be found using generating functions. It is the coefficient of $t^{n-1}$ in the generating function
$$
(1+t+dots+t^Delta)^{k-1}(1-t)^{-2}=(1-t^{Delta+1})^{k-1}(1-t)^{-(k+1)}
$$
This coefficient is
$$
boxed{sum_{i=0}^{frac{k+n-1}{Delta+1}}binom{k-1}i(-1)^ibinom{k+(n-i(Delta+1))-1}{k}.}
$$
Edit: You can also count the solutions to $(1)$ using the principle of inclusion exclusion. Start by counting solutions to $(1)$ while ignoring the conditions $z_ile Delta$ for $1 le i le k-1$. Now you just want to count the number of series ways to choose non-negative integers $z_i$ summing to $n-1$; by stars-and-bars, this is $binom{n-1+k}{k}$.
From these, we must subtract the bad solutions where some $z_ige Delta+1$. If say $z_1ge Delta+1$, then looking at the variables $z_0,z_1-(Delta+1),z_2,dots,z_k$, then we have $k+1$ nonnegative variables summing to $n-1-(Delta+1)$. The number of ways to choose the bad variable is $binom{k-1}1$, and there are $binom{n-1-(Delta+1)+k}{k}$ ways to choose the bad solutions, so we must subtract $binom{k-1}1binom{n-1-(Delta+1)+k}{k}$.
However, we have double subtracted the number of solutions with two bad variables. These must be added back in, then the triple bad solutions must be subtracted out, etc. Going all the way down, you arrive at the same summation as before.
answered Jan 12 at 18:52
Mike EarnestMike Earnest
22.6k12051
$endgroup$
$begingroup$
Hello. I am very happy to see a closed formula, thank you. But I have never heard of generating functions, I've just read a bit on Wikipedia right now but I don't really understand what you did here. Can you clarify a bit? Thank you very much :)
$endgroup$
– Pedro A
Jan 13 at 4:39
$begingroup$
@PedroA I added an alternate method. The generating function method is worth learning, but is a bit difficult to explain.
$endgroup$
– Mike Earnest
Jan 14 at 19:31
add a comment |
$begingroup$
Let $z_0,z_1,dots,z_k$ be variables defined by $z_i=x_{i+1}-x_i$, with the convention that $z_0=x_1-1$ and $z_k=n-x_k$ Note that
$$
z_0+z_1+dots+z_k=n-1,\
z_0,z_nge 0,\tag 1
0le z_ile Deltaquadtext{for }1le ile k-1
$$
The number of integer solutions to this system of equations and inequalities can be found using generating functions. It is the coefficient of $t^{n-1}$ in the generating function
$$
(1+t+dots+t^Delta)^{k-1}(1-t)^{-2}=(1-t^{Delta+1})^{k-1}(1-t)^{-(k+1)}
$$
This coefficient is
$$
boxed{sum_{i=0}^{frac{k+n-1}{Delta+1}}binom{k-1}i(-1)^ibinom{k+(n-i(Delta+1))-1}{k}.}
$$
Edit: You can also count the solutions to $(1)$ using the principle of inclusion exclusion. Start by counting solutions to $(1)$ while ignoring the conditions $z_ile Delta$ for $1 le i le k-1$. Now you just want to count the number of series ways to choose non-negative integers $z_i$ summing to $n-1$; by stars-and-bars, this is $binom{n-1+k}{k}$.
From these, we must subtract the bad solutions where some $z_ige Delta+1$. If say $z_1ge Delta+1$, then looking at the variables $z_0,z_1-(Delta+1),z_2,dots,z_k$, then we have $k+1$ nonnegative variables summing to $n-1-(Delta+1)$. The number of ways to choose the bad variable is $binom{k-1}1$, and there are $binom{n-1-(Delta+1)+k}{k}$ ways to choose the bad solutions, so we must subtract $binom{k-1}1binom{n-1-(Delta+1)+k}{k}$.
However, we have double subtracted the number of solutions with two bad variables. These must be added back in, then the triple bad solutions must be subtracted out, etc. Going all the way down, you arrive at the same summation as before.
answered Jan 12 at 18:52
Mike EarnestMike Earnest
22.6k12051
$endgroup$
$begingroup$
Hello. I am very happy to see a closed formula, thank you. But I have never heard of generating functions, I've just read a bit on Wikipedia right now but I don't really understand what you did here. Can you clarify a bit? Thank you very much :)
$endgroup$
– Pedro A
Jan 13 at 4:39
$begingroup$
@PedroA I added an alternate method. The generating function method is worth learning, but is a bit difficult to explain.
$endgroup$
– Mike Earnest
Jan 14 at 19:31
add a comment |
$begingroup$
Let $z_0,z_1,dots,z_k$ be variables defined by $z_i=x_{i+1}-x_i$, with the convention that $z_0=x_1-1$ and $z_k=n-x_k$ Note that
$$
z_0+z_1+dots+z_k=n-1,\
z_0,z_nge 0,\tag 1
0le z_ile Deltaquadtext{for }1le ile k-1
$$
The number of integer solutions to this system of equations and inequalities can be found using generating functions. It is the coefficient of $t^{n-1}$ in the generating function
$$
(1+t+dots+t^Delta)^{k-1}(1-t)^{-2}=(1-t^{Delta+1})^{k-1}(1-t)^{-(k+1)}
$$
This coefficient is
$$
boxed{sum_{i=0}^{frac{k+n-1}{Delta+1}}binom{k-1}i(-1)^ibinom{k+(n-i(Delta+1))-1}{k}.}
$$
Edit: You can also count the solutions to $(1)$ using the principle of inclusion exclusion. Start by counting solutions to $(1)$ while ignoring the conditions $z_ile Delta$ for $1 le i le k-1$. Now you just want to count the number of series ways to choose non-negative integers $z_i$ summing to $n-1$; by stars-and-bars, this is $binom{n-1+k}{k}$.
From these, we must subtract the bad solutions where some $z_ige Delta+1$. If say $z_1ge Delta+1$, then looking at the variables $z_0,z_1-(Delta+1),z_2,dots,z_k$, then we have $k+1$ nonnegative variables summing to $n-1-(Delta+1)$. The number of ways to choose the bad variable is $binom{k-1}1$, and there are $binom{n-1-(Delta+1)+k}{k}$ ways to choose the bad solutions, so we must subtract $binom{k-1}1binom{n-1-(Delta+1)+k}{k}$.
However, we have double subtracted the number of solutions with two bad variables. These must be added back in, then the triple bad solutions must be subtracted out, etc. Going all the way down, you arrive at the same summation as before.
answered Jan 12 at 18:52
Mike EarnestMike Earnest
22.6k12051
$endgroup$
Let $z_0,z_1,dots,z_k$ be variables defined by $z_i=x_{i+1}-x_i$, with the convention that $z_0=x_1-1$ and $z_k=n-x_k$ Note that
$$
z_0+z_1+dots+z_k=n-1,\
z_0,z_nge 0,\tag 1
0le z_ile Deltaquadtext{for }1le ile k-1
$$
The number of integer solutions to this system of equations and inequalities can be found using generating functions. It is the coefficient of $t^{n-1}$ in the generating function
$$
(1+t+dots+t^Delta)^{k-1}(1-t)^{-2}=(1-t^{Delta+1})^{k-1}(1-t)^{-(k+1)}
$$
This coefficient is
$$
boxed{sum_{i=0}^{frac{k+n-1}{Delta+1}}binom{k-1}i(-1)^ibinom{k+(n-i(Delta+1))-1}{k}.}
$$
Edit: You can also count the solutions to $(1)$ using the principle of inclusion exclusion. Start by counting solutions to $(1)$ while ignoring the conditions $z_ile Delta$ for $1 le i le k-1$. Now you just want to count the number of series ways to choose non-negative integers $z_i$ summing to $n-1$; by stars-and-bars, this is $binom{n-1+k}{k}$.
From these, we must subtract the bad solutions where some $z_ige Delta+1$. If say $z_1ge Delta+1$, then looking at the variables $z_0,z_1-(Delta+1),z_2,dots,z_k$, then we have $k+1$ nonnegative variables summing to $n-1-(Delta+1)$. The number of ways to choose the bad variable is $binom{k-1}1$, and there are $binom{n-1-(Delta+1)+k}{k}$ ways to choose the bad solutions, so we must subtract $binom{k-1}1binom{n-1-(Delta+1)+k}{k}$.
However, we have double subtracted the number of solutions with two bad variables. These must be added back in, then the triple bad solutions must be subtracted out, etc. Going all the way down, you arrive at the same summation as before.
answered Jan 12 at 18:52
Mike EarnestMike Earnest
22.6k12051
edited Jan 14 at 19:25
answered Jan 12 at 18:52
Mike EarnestMike Earnest
22.6k12051
answered Jan 12 at 18:52
Mike EarnestMike Earnest
22.6k12051
answered Jan 12 at 18:52
Mike EarnestMike Earnest
22.6k12051
22.6k12051
$begingroup$
Hello. I am very happy to see a closed formula, thank you. But I have never heard of generating functions, I've just read a bit on Wikipedia right now but I don't really understand what you did here. Can you clarify a bit? Thank you very much :)
$endgroup$
– Pedro A
Jan 13 at 4:39
$begingroup$
@PedroA I added an alternate method. The generating function method is worth learning, but is a bit difficult to explain.
$endgroup$
– Mike Earnest
Jan 14 at 19:31
add a comment |
$begingroup$
Hello. I am very happy to see a closed formula, thank you. But I have never heard of generating functions, I've just read a bit on Wikipedia right now but I don't really understand what you did here. Can you clarify a bit? Thank you very much :)
$endgroup$
– Pedro A
Jan 13 at 4:39
$begingroup$
@PedroA I added an alternate method. The generating function method is worth learning, but is a bit difficult to explain.
$endgroup$
– Mike Earnest
Jan 14 at 19:31
$begingroup$
Hello. I am very happy to see a closed formula, thank you. But I have never heard of generating functions, I've just read a bit on Wikipedia right now but I don't really understand what you did here. Can you clarify a bit? Thank you very much :)
$endgroup$
– Pedro A
Jan 13 at 4:39
$begingroup$
Hello. I am very happy to see a closed formula, thank you. But I have never heard of generating functions, I've just read a bit on Wikipedia right now but I don't really understand what you did here. Can you clarify a bit? Thank you very much :)
$endgroup$
– Pedro A
Jan 13 at 4:39
$begingroup$
@PedroA I added an alternate method. The generating function method is worth learning, but is a bit difficult to explain.
$endgroup$
– Mike Earnest
Jan 14 at 19:31
$begingroup$
@PedroA I added an alternate method. The generating function method is worth learning, but is a bit difficult to explain.
$endgroup$
– Mike Earnest
Jan 14 at 19:31
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%2f3071142%2famount-of-nondecreasing-integer-k-tuples-with-limited-delta%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
