Solve for the generating function with $x^1, x^5, x^{10}, x^{20}, x^{50}, x^{100}, x^{500}$
$begingroup$
How would you find the coefficient of $x^{2000}$ in
$ = (x^0 + x + x^2 +...)(x^0 + x^5 + x^{10} +...)(x^0 + x^{10} + x^{20}+...)(x^0 + x^{20} + x^{40} + ...)(x^0 + \
x^{50} + x^{100} +...)(x^0 + x^{100} + x^{200} +...)(x^0 + x^{500} + x^{1000} +...)$
I've been trying to use Mathematica, but it's not giving me a solution (very new at using it).
combinatorics generating-functions
asked Dec 18 '18 at 21:30
Math NewbieMath Newbie
428
$endgroup$
add a comment |
$begingroup$
How would you find the coefficient of $x^{2000}$ in
$ = (x^0 + x + x^2 +...)(x^0 + x^5 + x^{10} +...)(x^0 + x^{10} + x^{20}+...)(x^0 + x^{20} + x^{40} + ...)(x^0 + \
x^{50} + x^{100} +...)(x^0 + x^{100} + x^{200} +...)(x^0 + x^{500} + x^{1000} +...)$
I've been trying to use Mathematica, but it's not giving me a solution (very new at using it).
combinatorics generating-functions
asked Dec 18 '18 at 21:30
Math NewbieMath Newbie
428
$endgroup$
4
$begingroup$
You need to find non-negative integer solutions to $$a+5b+10c+20d+50e+100f+500g = 2000$$
$endgroup$
– Fly by Night
Dec 18 '18 at 21:35
$begingroup$
@FlybyNight could you explain how to do that?
$endgroup$
– Math Newbie
Dec 18 '18 at 21:39
$begingroup$
You can ask WA to compute the number using commandSeriesCoefficient[ 1/((1-x)*(1-x^5)*(1-x^10)*(1-x^20)*(1-x^50)*(1-x^100)*(1-x^500)),{x,0,2000}](same command should work on Mathematica), the number you want is86950230.
$endgroup$
– achille hui
Dec 18 '18 at 23:52
$begingroup$
@MathNewbie No, sorry. This is related to "partitions" and that is a very difficult combinatorial problem. en.wikipedia.org/wiki/Partition_(number_theory)
$endgroup$
– Fly by Night
Dec 19 '18 at 0:46
add a comment |
$begingroup$
How would you find the coefficient of $x^{2000}$ in
$ = (x^0 + x + x^2 +...)(x^0 + x^5 + x^{10} +...)(x^0 + x^{10} + x^{20}+...)(x^0 + x^{20} + x^{40} + ...)(x^0 + \
x^{50} + x^{100} +...)(x^0 + x^{100} + x^{200} +...)(x^0 + x^{500} + x^{1000} +...)$
I've been trying to use Mathematica, but it's not giving me a solution (very new at using it).
combinatorics generating-functions
asked Dec 18 '18 at 21:30
Math NewbieMath Newbie
428
$endgroup$
How would you find the coefficient of $x^{2000}$ in
$ = (x^0 + x + x^2 +...)(x^0 + x^5 + x^{10} +...)(x^0 + x^{10} + x^{20}+...)(x^0 + x^{20} + x^{40} + ...)(x^0 + \
x^{50} + x^{100} +...)(x^0 + x^{100} + x^{200} +...)(x^0 + x^{500} + x^{1000} +...)$
I've been trying to use Mathematica, but it's not giving me a solution (very new at using it).
combinatorics generating-functions
combinatorics generating-functions
asked Dec 18 '18 at 21:30
Math NewbieMath Newbie
428
asked Dec 18 '18 at 21:30
Math NewbieMath Newbie
428
asked Dec 18 '18 at 21:30
Math NewbieMath Newbie
428
asked Dec 18 '18 at 21:30
Math NewbieMath Newbie
428
asked Dec 18 '18 at 21:30
Math NewbieMath Newbie
428
428
4
$begingroup$
You need to find non-negative integer solutions to $$a+5b+10c+20d+50e+100f+500g = 2000$$
$endgroup$
– Fly by Night
Dec 18 '18 at 21:35
$begingroup$
@FlybyNight could you explain how to do that?
$endgroup$
– Math Newbie
Dec 18 '18 at 21:39
$begingroup$
You can ask WA to compute the number using commandSeriesCoefficient[ 1/((1-x)*(1-x^5)*(1-x^10)*(1-x^20)*(1-x^50)*(1-x^100)*(1-x^500)),{x,0,2000}](same command should work on Mathematica), the number you want is86950230.
$endgroup$
– achille hui
Dec 18 '18 at 23:52
$begingroup$
@MathNewbie No, sorry. This is related to "partitions" and that is a very difficult combinatorial problem. en.wikipedia.org/wiki/Partition_(number_theory)
$endgroup$
– Fly by Night
Dec 19 '18 at 0:46
add a comment |
4
$begingroup$
You need to find non-negative integer solutions to $$a+5b+10c+20d+50e+100f+500g = 2000$$
$endgroup$
– Fly by Night
Dec 18 '18 at 21:35
$begingroup$
@FlybyNight could you explain how to do that?
$endgroup$
– Math Newbie
Dec 18 '18 at 21:39
$begingroup$
You can ask WA to compute the number using commandSeriesCoefficient[ 1/((1-x)*(1-x^5)*(1-x^10)*(1-x^20)*(1-x^50)*(1-x^100)*(1-x^500)),{x,0,2000}](same command should work on Mathematica), the number you want is86950230.
$endgroup$
– achille hui
Dec 18 '18 at 23:52
$begingroup$
@MathNewbie No, sorry. This is related to "partitions" and that is a very difficult combinatorial problem. en.wikipedia.org/wiki/Partition_(number_theory)
$endgroup$
– Fly by Night
Dec 19 '18 at 0:46
4
4
$begingroup$
You need to find non-negative integer solutions to $$a+5b+10c+20d+50e+100f+500g = 2000$$
$endgroup$
– Fly by Night
Dec 18 '18 at 21:35
$begingroup$
You need to find non-negative integer solutions to $$a+5b+10c+20d+50e+100f+500g = 2000$$
$endgroup$
– Fly by Night
Dec 18 '18 at 21:35
$begingroup$
@FlybyNight could you explain how to do that?
$endgroup$
– Math Newbie
Dec 18 '18 at 21:39
$begingroup$
@FlybyNight could you explain how to do that?
$endgroup$
– Math Newbie
Dec 18 '18 at 21:39
$begingroup$
You can ask WA to compute the number using command
SeriesCoefficient[ 1/((1-x)*(1-x^5)*(1-x^10)*(1-x^20)*(1-x^50)*(1-x^100)*(1-x^500)),{x,0,2000}] (same command should work on Mathematica), the number you want is 86950230.$endgroup$
– achille hui
Dec 18 '18 at 23:52
$begingroup$
You can ask WA to compute the number using command
SeriesCoefficient[ 1/((1-x)*(1-x^5)*(1-x^10)*(1-x^20)*(1-x^50)*(1-x^100)*(1-x^500)),{x,0,2000}] (same command should work on Mathematica), the number you want is 86950230.$endgroup$
– achille hui
Dec 18 '18 at 23:52
$begingroup$
@MathNewbie No, sorry. This is related to "partitions" and that is a very difficult combinatorial problem. en.wikipedia.org/wiki/Partition_(number_theory)
$endgroup$
– Fly by Night
Dec 19 '18 at 0:46
$begingroup$
@MathNewbie No, sorry. This is related to "partitions" and that is a very difficult combinatorial problem. en.wikipedia.org/wiki/Partition_(number_theory)
$endgroup$
– Fly by Night
Dec 19 '18 at 0:46
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
So you have to find the number of non-negative integer solutions to:
$$a+5b+10c+20d+50e+100f+500g = 2000$$
A short C++ program with no more than 20 lines of code and a simple recurrence will serve for the purpose.
#include <iostream>
using namespace std;
int numSolutions(int *list, int size, int sum) {
int num = list[0];
if(size == 1) {
return (sum % num == 0)? 1: 0;
}
int count = 0, cases = sum / num;
for(int i = 0; i <= cases; i++) {
count += numSolutions(list + 1, size - 1, sum - i * num);
}
return count;
}
int main() {
int list = {500, 100, 50, 20, 10, 5, 1};
int size = 7, sum = 2000;
cout << numSolutions(list, size, sum);
}
...and the answer is: 86950230. Execution time is less than a second.
answered Dec 19 '18 at 11:56
OldboyOldboy
8,1651936
$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%2f3045730%2fsolve-for-the-generating-function-with-x1-x5-x10-x20-x50-x100%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$
So you have to find the number of non-negative integer solutions to:
$$a+5b+10c+20d+50e+100f+500g = 2000$$
A short C++ program with no more than 20 lines of code and a simple recurrence will serve for the purpose.
#include <iostream>
using namespace std;
int numSolutions(int *list, int size, int sum) {
int num = list[0];
if(size == 1) {
return (sum % num == 0)? 1: 0;
}
int count = 0, cases = sum / num;
for(int i = 0; i <= cases; i++) {
count += numSolutions(list + 1, size - 1, sum - i * num);
}
return count;
}
int main() {
int list = {500, 100, 50, 20, 10, 5, 1};
int size = 7, sum = 2000;
cout << numSolutions(list, size, sum);
}
...and the answer is: 86950230. Execution time is less than a second.
answered Dec 19 '18 at 11:56
OldboyOldboy
8,1651936
$endgroup$
add a comment |
$begingroup$
So you have to find the number of non-negative integer solutions to:
$$a+5b+10c+20d+50e+100f+500g = 2000$$
A short C++ program with no more than 20 lines of code and a simple recurrence will serve for the purpose.
#include <iostream>
using namespace std;
int numSolutions(int *list, int size, int sum) {
int num = list[0];
if(size == 1) {
return (sum % num == 0)? 1: 0;
}
int count = 0, cases = sum / num;
for(int i = 0; i <= cases; i++) {
count += numSolutions(list + 1, size - 1, sum - i * num);
}
return count;
}
int main() {
int list = {500, 100, 50, 20, 10, 5, 1};
int size = 7, sum = 2000;
cout << numSolutions(list, size, sum);
}
...and the answer is: 86950230. Execution time is less than a second.
answered Dec 19 '18 at 11:56
OldboyOldboy
8,1651936
$endgroup$
add a comment |
$begingroup$
So you have to find the number of non-negative integer solutions to:
$$a+5b+10c+20d+50e+100f+500g = 2000$$
A short C++ program with no more than 20 lines of code and a simple recurrence will serve for the purpose.
#include <iostream>
using namespace std;
int numSolutions(int *list, int size, int sum) {
int num = list[0];
if(size == 1) {
return (sum % num == 0)? 1: 0;
}
int count = 0, cases = sum / num;
for(int i = 0; i <= cases; i++) {
count += numSolutions(list + 1, size - 1, sum - i * num);
}
return count;
}
int main() {
int list = {500, 100, 50, 20, 10, 5, 1};
int size = 7, sum = 2000;
cout << numSolutions(list, size, sum);
}
...and the answer is: 86950230. Execution time is less than a second.
answered Dec 19 '18 at 11:56
OldboyOldboy
8,1651936
$endgroup$
So you have to find the number of non-negative integer solutions to:
$$a+5b+10c+20d+50e+100f+500g = 2000$$
A short C++ program with no more than 20 lines of code and a simple recurrence will serve for the purpose.
#include <iostream>
using namespace std;
int numSolutions(int *list, int size, int sum) {
int num = list[0];
if(size == 1) {
return (sum % num == 0)? 1: 0;
}
int count = 0, cases = sum / num;
for(int i = 0; i <= cases; i++) {
count += numSolutions(list + 1, size - 1, sum - i * num);
}
return count;
}
int main() {
int list = {500, 100, 50, 20, 10, 5, 1};
int size = 7, sum = 2000;
cout << numSolutions(list, size, sum);
}
...and the answer is: 86950230. Execution time is less than a second.
answered Dec 19 '18 at 11:56
OldboyOldboy
8,1651936
answered Dec 19 '18 at 11:56
OldboyOldboy
8,1651936
answered Dec 19 '18 at 11:56
OldboyOldboy
8,1651936
answered Dec 19 '18 at 11:56
OldboyOldboy
8,1651936
8,1651936
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%2f3045730%2fsolve-for-the-generating-function-with-x1-x5-x10-x20-x50-x100%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
4
$begingroup$
You need to find non-negative integer solutions to $$a+5b+10c+20d+50e+100f+500g = 2000$$
$endgroup$
– Fly by Night
Dec 18 '18 at 21:35
$begingroup$
@FlybyNight could you explain how to do that?
$endgroup$
– Math Newbie
Dec 18 '18 at 21:39
$begingroup$
You can ask WA to compute the number using command
SeriesCoefficient[ 1/((1-x)*(1-x^5)*(1-x^10)*(1-x^20)*(1-x^50)*(1-x^100)*(1-x^500)),{x,0,2000}](same command should work on Mathematica), the number you want is86950230.$endgroup$
– achille hui
Dec 18 '18 at 23:52
$begingroup$
@MathNewbie No, sorry. This is related to "partitions" and that is a very difficult combinatorial problem. en.wikipedia.org/wiki/Partition_(number_theory)
$endgroup$
– Fly by Night
Dec 19 '18 at 0:46