How many set of size $m$ integers such that the product is $n$
up vote
2
down vote
favorite
This question is related to optimizing the amount of computations of a program.
How many sets of $m$ naturals can be formed such that their product equals the number $n$ ?
Here is what I tried
Let $prod_{i=1}^ell p_i^{k_i}$ be the prime factorization of $n$. Then we want to distribute the $k_i$ $p_i$s to the $m$ numbers in the set for every $i$. What we can do is making a list of $k_i$ stars and $m-1$ bars and choosing the placement of the $m-1$ bars among this list, this gives me ${k_i+m-1choose m-1}$ ways of choosing how to dispatch the $k_i$ $p_i$s to those $m$ numbers.
Then I multiply all these for any $i$ and since I don't care about rearrangement of the $m$ numbers. So my answer is
$$frac{1}{m!} prod_{i=1}^ell {k_i+m-1choose m-1},$$
which unfortunately is not necessarily an integer and doesn't match what I found manually. Does any of you have an idea ?
combinatorics prime-factorization
edited Nov 22 at 13:00
amWhy
191k28224439
asked Sep 8 at 17:40
P. Quinton
1,411213
add a comment |
up vote
2
down vote
favorite
This question is related to optimizing the amount of computations of a program.
How many sets of $m$ naturals can be formed such that their product equals the number $n$ ?
Here is what I tried
Let $prod_{i=1}^ell p_i^{k_i}$ be the prime factorization of $n$. Then we want to distribute the $k_i$ $p_i$s to the $m$ numbers in the set for every $i$. What we can do is making a list of $k_i$ stars and $m-1$ bars and choosing the placement of the $m-1$ bars among this list, this gives me ${k_i+m-1choose m-1}$ ways of choosing how to dispatch the $k_i$ $p_i$s to those $m$ numbers.
Then I multiply all these for any $i$ and since I don't care about rearrangement of the $m$ numbers. So my answer is
$$frac{1}{m!} prod_{i=1}^ell {k_i+m-1choose m-1},$$
which unfortunately is not necessarily an integer and doesn't match what I found manually. Does any of you have an idea ?
combinatorics prime-factorization
edited Nov 22 at 13:00
amWhy
191k28224439
asked Sep 8 at 17:40
P. Quinton
1,411213
Example: $m=3, n =6$. Then the set ${1,1,6}$ only has 3 rearrangements, while ${1,2,3}$ has all 6 kinds.
– xbh
Sep 8 at 17:52
1
This MSE link I might be relevant, as might be this MSE link II. These statistics have basic recurrences.
– Marko Riedel
Sep 8 at 18:07
add a comment |
up vote
2
down vote
favorite
up vote
2
down vote
favorite
This question is related to optimizing the amount of computations of a program.
How many sets of $m$ naturals can be formed such that their product equals the number $n$ ?
Here is what I tried
Let $prod_{i=1}^ell p_i^{k_i}$ be the prime factorization of $n$. Then we want to distribute the $k_i$ $p_i$s to the $m$ numbers in the set for every $i$. What we can do is making a list of $k_i$ stars and $m-1$ bars and choosing the placement of the $m-1$ bars among this list, this gives me ${k_i+m-1choose m-1}$ ways of choosing how to dispatch the $k_i$ $p_i$s to those $m$ numbers.
Then I multiply all these for any $i$ and since I don't care about rearrangement of the $m$ numbers. So my answer is
$$frac{1}{m!} prod_{i=1}^ell {k_i+m-1choose m-1},$$
which unfortunately is not necessarily an integer and doesn't match what I found manually. Does any of you have an idea ?
combinatorics prime-factorization
edited Nov 22 at 13:00
amWhy
191k28224439
asked Sep 8 at 17:40
P. Quinton
1,411213
This question is related to optimizing the amount of computations of a program.
How many sets of $m$ naturals can be formed such that their product equals the number $n$ ?
Here is what I tried
Let $prod_{i=1}^ell p_i^{k_i}$ be the prime factorization of $n$. Then we want to distribute the $k_i$ $p_i$s to the $m$ numbers in the set for every $i$. What we can do is making a list of $k_i$ stars and $m-1$ bars and choosing the placement of the $m-1$ bars among this list, this gives me ${k_i+m-1choose m-1}$ ways of choosing how to dispatch the $k_i$ $p_i$s to those $m$ numbers.
Then I multiply all these for any $i$ and since I don't care about rearrangement of the $m$ numbers. So my answer is
$$frac{1}{m!} prod_{i=1}^ell {k_i+m-1choose m-1},$$
which unfortunately is not necessarily an integer and doesn't match what I found manually. Does any of you have an idea ?
combinatorics prime-factorization
combinatorics prime-factorization
edited Nov 22 at 13:00
amWhy
191k28224439
asked Sep 8 at 17:40
P. Quinton
1,411213
edited Nov 22 at 13:00
amWhy
191k28224439
asked Sep 8 at 17:40
P. Quinton
1,411213
edited Nov 22 at 13:00
amWhy
191k28224439
edited Nov 22 at 13:00
amWhy
191k28224439
edited Nov 22 at 13:00
amWhy
191k28224439
191k28224439
asked Sep 8 at 17:40
P. Quinton
1,411213
asked Sep 8 at 17:40
P. Quinton
1,411213
asked Sep 8 at 17:40
P. Quinton
1,411213
1,411213
Example: $m=3, n =6$. Then the set ${1,1,6}$ only has 3 rearrangements, while ${1,2,3}$ has all 6 kinds.
– xbh
Sep 8 at 17:52
1
This MSE link I might be relevant, as might be this MSE link II. These statistics have basic recurrences.
– Marko Riedel
Sep 8 at 18:07
add a comment |
Example: $m=3, n =6$. Then the set ${1,1,6}$ only has 3 rearrangements, while ${1,2,3}$ has all 6 kinds.
– xbh
Sep 8 at 17:52
1
This MSE link I might be relevant, as might be this MSE link II. These statistics have basic recurrences.
– Marko Riedel
Sep 8 at 18:07
Example: $m=3, n =6$. Then the set ${1,1,6}$ only has 3 rearrangements, while ${1,2,3}$ has all 6 kinds.
– xbh
Sep 8 at 17:52
Example: $m=3, n =6$. Then the set ${1,1,6}$ only has 3 rearrangements, while ${1,2,3}$ has all 6 kinds.
– xbh
Sep 8 at 17:52
1
1
This MSE link I might be relevant, as might be this MSE link II. These statistics have basic recurrences.
– Marko Riedel
Sep 8 at 18:07
This MSE link I might be relevant, as might be this MSE link II. These statistics have basic recurrences.
– Marko Riedel
Sep 8 at 18:07
add a comment |
active
oldest
votes
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',
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%2f2909893%2fhow-many-set-of-size-m-integers-such-that-the-product-is-n%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f2909893%2fhow-many-set-of-size-m-integers-such-that-the-product-is-n%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
Example: $m=3, n =6$. Then the set ${1,1,6}$ only has 3 rearrangements, while ${1,2,3}$ has all 6 kinds.
– xbh
Sep 8 at 17:52
1
This MSE link I might be relevant, as might be this MSE link II. These statistics have basic recurrences.
– Marko Riedel
Sep 8 at 18:07