Mixing
Partition of set with N integers such that each subset has length less K.
$begingroup$
You are given numbers $N$ and $K$. Consider the set $S = {1, 2, 3, . . . , N}$. An ordered
tuple is a sequence of integers from this set. For example, $(2, 4, 1)$ is a tuple, and
it is different from $(1, 2, 4)$. You need to partition the integers ${1, 2, 3, . . . , N}$ into
ordered tuples such that each tuple has at most $K$ integers. That is, you need to
get a set of tuples, such that each element of $S$ is in exactly one tuple, and each
tuple has at most $K$ elements. Find the number of ways to do so.
Note that elements inside a single tuple cannot be reordered. But tuples can be
reordered as a whole. For instance, if $N = 3$ i.e., $S = {1, 2, 3}$ — then ${ (2, 3),(1) }$ and ${ (1),(2, 3) }$ are considered the same partitions. But ${ (3, 2),(1) }$ is a different
partition.
For example, if $N = 2$ and $K = 2$, there are exactly $3$ valid ways to partition $S$, as
given below:
${ (1),(2) }$
${ (1, 2) }$
${ (2, 1) }$
Compute the number of ways to partition ${1, 2, 3, . . . , N}$ into ordered tuples of size
at most $K$ for the following instances.
$(a) N = 4,, K = 3$
$(b) N = 5,, K = 3$
$(c) N = 6,, K = 3$
Answers are : $(a), 49 ,, (b), 261,, (c), 1531$
This is the first question that I am asking on Math.StackExchange. I am sorry if I am being too direct in asking the question.
This is the Q4 of ZIO - 2018. See the QP here : https://www.iarcs.org.in/inoi/2018/zio2018/zio2018-question-paper.pdf
I am bad at explaining but here we go.
What I attempted to do was partition N into parts such that each is less than K.
i.e I got 3 such partitions for $N = 4, K = 3$ $(2,2 >&> 1,1,2 >&> 3,1)$.
Then there were $N!$ such ways to place the numbers into these partitions. This gives me the answer $(4! cdot 3 = 72)$, however that logic seems to be wrong.
Can anyone suggest a better path?
Thanks in advanced!
combinatorics permutations computer-science
asked Jan 30 at 18:49
Aditya DuttAditya Dutt
125
$endgroup$
add a comment |
$begingroup$
You are given numbers $N$ and $K$. Consider the set $S = {1, 2, 3, . . . , N}$. An ordered
tuple is a sequence of integers from this set. For example, $(2, 4, 1)$ is a tuple, and
it is different from $(1, 2, 4)$. You need to partition the integers ${1, 2, 3, . . . , N}$ into
ordered tuples such that each tuple has at most $K$ integers. That is, you need to
get a set of tuples, such that each element of $S$ is in exactly one tuple, and each
tuple has at most $K$ elements. Find the number of ways to do so.
Note that elements inside a single tuple cannot be reordered. But tuples can be
reordered as a whole. For instance, if $N = 3$ i.e., $S = {1, 2, 3}$ — then ${ (2, 3),(1) }$ and ${ (1),(2, 3) }$ are considered the same partitions. But ${ (3, 2),(1) }$ is a different
partition.
For example, if $N = 2$ and $K = 2$, there are exactly $3$ valid ways to partition $S$, as
given below:
${ (1),(2) }$
${ (1, 2) }$
${ (2, 1) }$
Compute the number of ways to partition ${1, 2, 3, . . . , N}$ into ordered tuples of size
at most $K$ for the following instances.
$(a) N = 4,, K = 3$
$(b) N = 5,, K = 3$
$(c) N = 6,, K = 3$
Answers are : $(a), 49 ,, (b), 261,, (c), 1531$
This is the first question that I am asking on Math.StackExchange. I am sorry if I am being too direct in asking the question.
This is the Q4 of ZIO - 2018. See the QP here : https://www.iarcs.org.in/inoi/2018/zio2018/zio2018-question-paper.pdf
I am bad at explaining but here we go.
What I attempted to do was partition N into parts such that each is less than K.
i.e I got 3 such partitions for $N = 4, K = 3$ $(2,2 >&> 1,1,2 >&> 3,1)$.
Then there were $N!$ such ways to place the numbers into these partitions. This gives me the answer $(4! cdot 3 = 72)$, however that logic seems to be wrong.
Can anyone suggest a better path?
Thanks in advanced!
combinatorics permutations computer-science
asked Jan 30 at 18:49
Aditya DuttAditya Dutt
125
$endgroup$
add a comment |
$begingroup$
You are given numbers $N$ and $K$. Consider the set $S = {1, 2, 3, . . . , N}$. An ordered
tuple is a sequence of integers from this set. For example, $(2, 4, 1)$ is a tuple, and
it is different from $(1, 2, 4)$. You need to partition the integers ${1, 2, 3, . . . , N}$ into
ordered tuples such that each tuple has at most $K$ integers. That is, you need to
get a set of tuples, such that each element of $S$ is in exactly one tuple, and each
tuple has at most $K$ elements. Find the number of ways to do so.
Note that elements inside a single tuple cannot be reordered. But tuples can be
reordered as a whole. For instance, if $N = 3$ i.e., $S = {1, 2, 3}$ — then ${ (2, 3),(1) }$ and ${ (1),(2, 3) }$ are considered the same partitions. But ${ (3, 2),(1) }$ is a different
partition.
For example, if $N = 2$ and $K = 2$, there are exactly $3$ valid ways to partition $S$, as
given below:
${ (1),(2) }$
${ (1, 2) }$
${ (2, 1) }$
Compute the number of ways to partition ${1, 2, 3, . . . , N}$ into ordered tuples of size
at most $K$ for the following instances.
$(a) N = 4,, K = 3$
$(b) N = 5,, K = 3$
$(c) N = 6,, K = 3$
Answers are : $(a), 49 ,, (b), 261,, (c), 1531$
This is the first question that I am asking on Math.StackExchange. I am sorry if I am being too direct in asking the question.
This is the Q4 of ZIO - 2018. See the QP here : https://www.iarcs.org.in/inoi/2018/zio2018/zio2018-question-paper.pdf
I am bad at explaining but here we go.
What I attempted to do was partition N into parts such that each is less than K.
i.e I got 3 such partitions for $N = 4, K = 3$ $(2,2 >&> 1,1,2 >&> 3,1)$.
Then there were $N!$ such ways to place the numbers into these partitions. This gives me the answer $(4! cdot 3 = 72)$, however that logic seems to be wrong.
Can anyone suggest a better path?
Thanks in advanced!
combinatorics permutations computer-science
asked Jan 30 at 18:49
Aditya DuttAditya Dutt
125
$endgroup$
You are given numbers $N$ and $K$. Consider the set $S = {1, 2, 3, . . . , N}$. An ordered
tuple is a sequence of integers from this set. For example, $(2, 4, 1)$ is a tuple, and
it is different from $(1, 2, 4)$. You need to partition the integers ${1, 2, 3, . . . , N}$ into
ordered tuples such that each tuple has at most $K$ integers. That is, you need to
get a set of tuples, such that each element of $S$ is in exactly one tuple, and each
tuple has at most $K$ elements. Find the number of ways to do so.
Note that elements inside a single tuple cannot be reordered. But tuples can be
reordered as a whole. For instance, if $N = 3$ i.e., $S = {1, 2, 3}$ — then ${ (2, 3),(1) }$ and ${ (1),(2, 3) }$ are considered the same partitions. But ${ (3, 2),(1) }$ is a different
partition.
For example, if $N = 2$ and $K = 2$, there are exactly $3$ valid ways to partition $S$, as
given below:
${ (1),(2) }$
${ (1, 2) }$
${ (2, 1) }$
Compute the number of ways to partition ${1, 2, 3, . . . , N}$ into ordered tuples of size
at most $K$ for the following instances.
$(a) N = 4,, K = 3$
$(b) N = 5,, K = 3$
$(c) N = 6,, K = 3$
Answers are : $(a), 49 ,, (b), 261,, (c), 1531$
This is the first question that I am asking on Math.StackExchange. I am sorry if I am being too direct in asking the question.
This is the Q4 of ZIO - 2018. See the QP here : https://www.iarcs.org.in/inoi/2018/zio2018/zio2018-question-paper.pdf
I am bad at explaining but here we go.
What I attempted to do was partition N into parts such that each is less than K.
i.e I got 3 such partitions for $N = 4, K = 3$ $(2,2 >&> 1,1,2 >&> 3,1)$.
Then there were $N!$ such ways to place the numbers into these partitions. This gives me the answer $(4! cdot 3 = 72)$, however that logic seems to be wrong.
Can anyone suggest a better path?
Thanks in advanced!
combinatorics permutations computer-science
combinatorics permutations computer-science
asked Jan 30 at 18:49
Aditya DuttAditya Dutt
125
asked Jan 30 at 18:49
Aditya DuttAditya Dutt
125
edited Jan 31 at 5:06
Aditya Dutt
asked Jan 30 at 18:49
Aditya DuttAditya Dutt
125
asked Jan 30 at 18:49
Aditya DuttAditya Dutt
125
asked Jan 30 at 18:49
Aditya DuttAditya Dutt
125
125
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
Letting $f(n,k)$ be the number of ways, a better path to compute $f(n,k)$ is recursively. Specifically,
$$
f(n,k) = binom{n-1}0cdot 1!cdot f(n-1,k) +binom{n-1}1cdot 2!cdot f(n-2,k) + dots+binom{n-1}{k-1}cdot k!cdot f(n-k,k)
$$
This follows by conditioning on the number of elements in the tuple containing $n$.
To see this in action:
$f(0,3) = 1$. (There is nothing to partition, so there is only the empty partition).
$f(1,3) = binom{0}{0}1!f(0,3)=1.$
$f(2,3) = binom{1}01!f(1,3)+binom{1}1cdot 2!f(0,3)=1cdot 1+2cdot 1=3$
$f(3,3) = binom{2}01!f(2,3) +binom212!f(1,3)+binom223!f(0,3)=1cdot 3+4cdot 1+6cdot 1=13$.
$f(4,3) = binom301!f(3,3)+binom312!f(2,3)+binom323!f(1,3)=1cdot 13+6cdot 3+18cdot 1=49.$
$f(5,3) = binom401!f(4,3)+binom412!f(3,3)+binom423!f(2,3)=1cdot 49+8cdot 13+36cdot 3=261.$
answered Jan 30 at 19:33
Mike EarnestMike Earnest
26.9k22152
$endgroup$
add a comment |
$begingroup$
Your main problem is the distinct tuples of the same size are not ordered. So the partition ${(1,2),(3,4)}$ is the same as the partition ${(3,4),(1,2)}$.
Your second problem is that you wrote down the partitions wrong. $1,1,1,2$ adds to $5$, not $4$, and you missed the trivial partition $1,1,1,1$. So the complete list:
$1,1,1,1 to 4!/4! = 1$ way
$1,1,2 to 4!/2! = 12$ ways
$2,2 to 4!/2! = 12$ ways
$3,1 to 4! = 24$ ways
Total : $49$
edited Feb 16 at 12:03
Aditya Dutt
125
answered Jan 30 at 19:00
Nathaniel MayerNathaniel Mayer
1,863516
$endgroup$
add a comment |
$begingroup$
The number of ways to assign the numbers to the partitions is much more complicated than that.
For $3,1$ there are $4!$ ways to assign them because each location is distinct.
For $1,1,1,1$ (which you missed) there is only one way to assign them because you are allowed to reorder the partitions.
For $2,2$ there are $12$ ways to assign them because you can assign the first in $12$ ways, the second in two ways, but you can swap the two pairs.
Finally for $1,1,2$ (you had an extra $1$) there are $12$ ways to choose the $2$, but the $1$s are then set.
This gives the desired $49$ ways.
Your approach of $N!$ times the number of partitions of $N$ into parts of at most $K$ is close. Each one just needs to be divided by the factorial of the number of matching parts. For $N=6,K=3$ the partition $(3,3)$ contributes $frac {6!}{2!}$, the partition $(2,2,2)$ contributes $frac {6!}{3!}$ and $(2,2,1,1)$ contributes $frac {6!}{2!2!}$
answered Jan 30 at 18:59
Ross MillikanRoss Millikan
301k24200375
$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%2f3093947%2fpartition-of-set-with-n-integers-such-that-each-subset-has-length-less-k%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Letting $f(n,k)$ be the number of ways, a better path to compute $f(n,k)$ is recursively. Specifically,
$$
f(n,k) = binom{n-1}0cdot 1!cdot f(n-1,k) +binom{n-1}1cdot 2!cdot f(n-2,k) + dots+binom{n-1}{k-1}cdot k!cdot f(n-k,k)
$$
This follows by conditioning on the number of elements in the tuple containing $n$.
To see this in action:
$f(0,3) = 1$. (There is nothing to partition, so there is only the empty partition).
$f(1,3) = binom{0}{0}1!f(0,3)=1.$
$f(2,3) = binom{1}01!f(1,3)+binom{1}1cdot 2!f(0,3)=1cdot 1+2cdot 1=3$
$f(3,3) = binom{2}01!f(2,3) +binom212!f(1,3)+binom223!f(0,3)=1cdot 3+4cdot 1+6cdot 1=13$.
$f(4,3) = binom301!f(3,3)+binom312!f(2,3)+binom323!f(1,3)=1cdot 13+6cdot 3+18cdot 1=49.$
$f(5,3) = binom401!f(4,3)+binom412!f(3,3)+binom423!f(2,3)=1cdot 49+8cdot 13+36cdot 3=261.$
answered Jan 30 at 19:33
Mike EarnestMike Earnest
26.9k22152
$endgroup$
add a comment |
$begingroup$
Letting $f(n,k)$ be the number of ways, a better path to compute $f(n,k)$ is recursively. Specifically,
$$
f(n,k) = binom{n-1}0cdot 1!cdot f(n-1,k) +binom{n-1}1cdot 2!cdot f(n-2,k) + dots+binom{n-1}{k-1}cdot k!cdot f(n-k,k)
$$
This follows by conditioning on the number of elements in the tuple containing $n$.
To see this in action:
$f(0,3) = 1$. (There is nothing to partition, so there is only the empty partition).
$f(1,3) = binom{0}{0}1!f(0,3)=1.$
$f(2,3) = binom{1}01!f(1,3)+binom{1}1cdot 2!f(0,3)=1cdot 1+2cdot 1=3$
$f(3,3) = binom{2}01!f(2,3) +binom212!f(1,3)+binom223!f(0,3)=1cdot 3+4cdot 1+6cdot 1=13$.
$f(4,3) = binom301!f(3,3)+binom312!f(2,3)+binom323!f(1,3)=1cdot 13+6cdot 3+18cdot 1=49.$
$f(5,3) = binom401!f(4,3)+binom412!f(3,3)+binom423!f(2,3)=1cdot 49+8cdot 13+36cdot 3=261.$
answered Jan 30 at 19:33
Mike EarnestMike Earnest
26.9k22152
$endgroup$
add a comment |
$begingroup$
Letting $f(n,k)$ be the number of ways, a better path to compute $f(n,k)$ is recursively. Specifically,
$$
f(n,k) = binom{n-1}0cdot 1!cdot f(n-1,k) +binom{n-1}1cdot 2!cdot f(n-2,k) + dots+binom{n-1}{k-1}cdot k!cdot f(n-k,k)
$$
This follows by conditioning on the number of elements in the tuple containing $n$.
To see this in action:
$f(0,3) = 1$. (There is nothing to partition, so there is only the empty partition).
$f(1,3) = binom{0}{0}1!f(0,3)=1.$
$f(2,3) = binom{1}01!f(1,3)+binom{1}1cdot 2!f(0,3)=1cdot 1+2cdot 1=3$
$f(3,3) = binom{2}01!f(2,3) +binom212!f(1,3)+binom223!f(0,3)=1cdot 3+4cdot 1+6cdot 1=13$.
$f(4,3) = binom301!f(3,3)+binom312!f(2,3)+binom323!f(1,3)=1cdot 13+6cdot 3+18cdot 1=49.$
$f(5,3) = binom401!f(4,3)+binom412!f(3,3)+binom423!f(2,3)=1cdot 49+8cdot 13+36cdot 3=261.$
answered Jan 30 at 19:33
Mike EarnestMike Earnest
26.9k22152
$endgroup$
Letting $f(n,k)$ be the number of ways, a better path to compute $f(n,k)$ is recursively. Specifically,
$$
f(n,k) = binom{n-1}0cdot 1!cdot f(n-1,k) +binom{n-1}1cdot 2!cdot f(n-2,k) + dots+binom{n-1}{k-1}cdot k!cdot f(n-k,k)
$$
This follows by conditioning on the number of elements in the tuple containing $n$.
To see this in action:
$f(0,3) = 1$. (There is nothing to partition, so there is only the empty partition).
$f(1,3) = binom{0}{0}1!f(0,3)=1.$
$f(2,3) = binom{1}01!f(1,3)+binom{1}1cdot 2!f(0,3)=1cdot 1+2cdot 1=3$
$f(3,3) = binom{2}01!f(2,3) +binom212!f(1,3)+binom223!f(0,3)=1cdot 3+4cdot 1+6cdot 1=13$.
$f(4,3) = binom301!f(3,3)+binom312!f(2,3)+binom323!f(1,3)=1cdot 13+6cdot 3+18cdot 1=49.$
$f(5,3) = binom401!f(4,3)+binom412!f(3,3)+binom423!f(2,3)=1cdot 49+8cdot 13+36cdot 3=261.$
answered Jan 30 at 19:33
Mike EarnestMike Earnest
26.9k22152
answered Jan 30 at 19:33
Mike EarnestMike Earnest
26.9k22152
answered Jan 30 at 19:33
Mike EarnestMike Earnest
26.9k22152
answered Jan 30 at 19:33
Mike EarnestMike Earnest
26.9k22152
26.9k22152
add a comment |
add a comment |
$begingroup$
Your main problem is the distinct tuples of the same size are not ordered. So the partition ${(1,2),(3,4)}$ is the same as the partition ${(3,4),(1,2)}$.
Your second problem is that you wrote down the partitions wrong. $1,1,1,2$ adds to $5$, not $4$, and you missed the trivial partition $1,1,1,1$. So the complete list:
$1,1,1,1 to 4!/4! = 1$ way
$1,1,2 to 4!/2! = 12$ ways
$2,2 to 4!/2! = 12$ ways
$3,1 to 4! = 24$ ways
Total : $49$
edited Feb 16 at 12:03
Aditya Dutt
125
answered Jan 30 at 19:00
Nathaniel MayerNathaniel Mayer
1,863516
$endgroup$
add a comment |
$begingroup$
Your main problem is the distinct tuples of the same size are not ordered. So the partition ${(1,2),(3,4)}$ is the same as the partition ${(3,4),(1,2)}$.
Your second problem is that you wrote down the partitions wrong. $1,1,1,2$ adds to $5$, not $4$, and you missed the trivial partition $1,1,1,1$. So the complete list:
$1,1,1,1 to 4!/4! = 1$ way
$1,1,2 to 4!/2! = 12$ ways
$2,2 to 4!/2! = 12$ ways
$3,1 to 4! = 24$ ways
Total : $49$
edited Feb 16 at 12:03
Aditya Dutt
125
answered Jan 30 at 19:00
Nathaniel MayerNathaniel Mayer
1,863516
$endgroup$
add a comment |
$begingroup$
Your main problem is the distinct tuples of the same size are not ordered. So the partition ${(1,2),(3,4)}$ is the same as the partition ${(3,4),(1,2)}$.
Your second problem is that you wrote down the partitions wrong. $1,1,1,2$ adds to $5$, not $4$, and you missed the trivial partition $1,1,1,1$. So the complete list:
$1,1,1,1 to 4!/4! = 1$ way
$1,1,2 to 4!/2! = 12$ ways
$2,2 to 4!/2! = 12$ ways
$3,1 to 4! = 24$ ways
Total : $49$
edited Feb 16 at 12:03
Aditya Dutt
125
answered Jan 30 at 19:00
Nathaniel MayerNathaniel Mayer
1,863516
$endgroup$
Your main problem is the distinct tuples of the same size are not ordered. So the partition ${(1,2),(3,4)}$ is the same as the partition ${(3,4),(1,2)}$.
Your second problem is that you wrote down the partitions wrong. $1,1,1,2$ adds to $5$, not $4$, and you missed the trivial partition $1,1,1,1$. So the complete list:
$1,1,1,1 to 4!/4! = 1$ way
$1,1,2 to 4!/2! = 12$ ways
$2,2 to 4!/2! = 12$ ways
$3,1 to 4! = 24$ ways
Total : $49$
edited Feb 16 at 12:03
Aditya Dutt
125
answered Jan 30 at 19:00
Nathaniel MayerNathaniel Mayer
1,863516
edited Feb 16 at 12:03
Aditya Dutt
125
edited Feb 16 at 12:03
Aditya Dutt
125
edited Feb 16 at 12:03
Aditya Dutt
125
125
answered Jan 30 at 19:00
Nathaniel MayerNathaniel Mayer
1,863516
answered Jan 30 at 19:00
Nathaniel MayerNathaniel Mayer
1,863516
answered Jan 30 at 19:00
Nathaniel MayerNathaniel Mayer
1,863516
1,863516
add a comment |
add a comment |
$begingroup$
The number of ways to assign the numbers to the partitions is much more complicated than that.
For $3,1$ there are $4!$ ways to assign them because each location is distinct.
For $1,1,1,1$ (which you missed) there is only one way to assign them because you are allowed to reorder the partitions.
For $2,2$ there are $12$ ways to assign them because you can assign the first in $12$ ways, the second in two ways, but you can swap the two pairs.
Finally for $1,1,2$ (you had an extra $1$) there are $12$ ways to choose the $2$, but the $1$s are then set.
This gives the desired $49$ ways.
Your approach of $N!$ times the number of partitions of $N$ into parts of at most $K$ is close. Each one just needs to be divided by the factorial of the number of matching parts. For $N=6,K=3$ the partition $(3,3)$ contributes $frac {6!}{2!}$, the partition $(2,2,2)$ contributes $frac {6!}{3!}$ and $(2,2,1,1)$ contributes $frac {6!}{2!2!}$
answered Jan 30 at 18:59
Ross MillikanRoss Millikan
301k24200375
$endgroup$
add a comment |
$begingroup$
The number of ways to assign the numbers to the partitions is much more complicated than that.
For $3,1$ there are $4!$ ways to assign them because each location is distinct.
For $1,1,1,1$ (which you missed) there is only one way to assign them because you are allowed to reorder the partitions.
For $2,2$ there are $12$ ways to assign them because you can assign the first in $12$ ways, the second in two ways, but you can swap the two pairs.
Finally for $1,1,2$ (you had an extra $1$) there are $12$ ways to choose the $2$, but the $1$s are then set.
This gives the desired $49$ ways.
Your approach of $N!$ times the number of partitions of $N$ into parts of at most $K$ is close. Each one just needs to be divided by the factorial of the number of matching parts. For $N=6,K=3$ the partition $(3,3)$ contributes $frac {6!}{2!}$, the partition $(2,2,2)$ contributes $frac {6!}{3!}$ and $(2,2,1,1)$ contributes $frac {6!}{2!2!}$
answered Jan 30 at 18:59
Ross MillikanRoss Millikan
301k24200375
$endgroup$
add a comment |
$begingroup$
The number of ways to assign the numbers to the partitions is much more complicated than that.
For $3,1$ there are $4!$ ways to assign them because each location is distinct.
For $1,1,1,1$ (which you missed) there is only one way to assign them because you are allowed to reorder the partitions.
For $2,2$ there are $12$ ways to assign them because you can assign the first in $12$ ways, the second in two ways, but you can swap the two pairs.
Finally for $1,1,2$ (you had an extra $1$) there are $12$ ways to choose the $2$, but the $1$s are then set.
This gives the desired $49$ ways.
Your approach of $N!$ times the number of partitions of $N$ into parts of at most $K$ is close. Each one just needs to be divided by the factorial of the number of matching parts. For $N=6,K=3$ the partition $(3,3)$ contributes $frac {6!}{2!}$, the partition $(2,2,2)$ contributes $frac {6!}{3!}$ and $(2,2,1,1)$ contributes $frac {6!}{2!2!}$
answered Jan 30 at 18:59
Ross MillikanRoss Millikan
301k24200375
$endgroup$
The number of ways to assign the numbers to the partitions is much more complicated than that.
For $3,1$ there are $4!$ ways to assign them because each location is distinct.
For $1,1,1,1$ (which you missed) there is only one way to assign them because you are allowed to reorder the partitions.
For $2,2$ there are $12$ ways to assign them because you can assign the first in $12$ ways, the second in two ways, but you can swap the two pairs.
Finally for $1,1,2$ (you had an extra $1$) there are $12$ ways to choose the $2$, but the $1$s are then set.
This gives the desired $49$ ways.
Your approach of $N!$ times the number of partitions of $N$ into parts of at most $K$ is close. Each one just needs to be divided by the factorial of the number of matching parts. For $N=6,K=3$ the partition $(3,3)$ contributes $frac {6!}{2!}$, the partition $(2,2,2)$ contributes $frac {6!}{3!}$ and $(2,2,1,1)$ contributes $frac {6!}{2!2!}$
answered Jan 30 at 18:59
Ross MillikanRoss Millikan
301k24200375
edited Jan 31 at 5:49
answered Jan 30 at 18:59
Ross MillikanRoss Millikan
301k24200375
answered Jan 30 at 18:59
Ross MillikanRoss Millikan
301k24200375
answered Jan 30 at 18:59
Ross MillikanRoss Millikan
301k24200375
301k24200375
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%2f3093947%2fpartition-of-set-with-n-integers-such-that-each-subset-has-length-less-k%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
