Mixing
2D grid of size 3*n
$begingroup$
There is a 2D array of size 3*n.
Suppose there are 3 numbers 1, 2 and 3.
What can be the number of ways in which we can put numbers in 2D array using
these numbers only according to below rule
1)All the n cells of a single row do not have the same number
2)All the 3 cells of a single column do not have the same number.
I am trying to calculate answer for this but am not able to find how to calculate or what formula to use.
permutations combinations
asked Feb 2 at 18:07
sroxsrox
35
$endgroup$
add a comment |
$begingroup$
There is a 2D array of size 3*n.
Suppose there are 3 numbers 1, 2 and 3.
What can be the number of ways in which we can put numbers in 2D array using
these numbers only according to below rule
1)All the n cells of a single row do not have the same number
2)All the 3 cells of a single column do not have the same number.
I am trying to calculate answer for this but am not able to find how to calculate or what formula to use.
permutations combinations
asked Feb 2 at 18:07
sroxsrox
35
$endgroup$
$begingroup$
How can a row hold $n$ unique numbers if there are only three?
$endgroup$
– jvdhooft
Feb 2 at 18:14
$begingroup$
All the n cells of a single row do not have the same number means it should not be like 1 1 1 ........or 2 2 2 .............or 3 3 3 ..............
$endgroup$
– srox
Feb 2 at 18:38
$begingroup$
In that case, it would be better to phrase the rule as "not all cells of a single row have the same number" or "a row cannot contain the same number in all cells".
$endgroup$
– jvdhooft
Feb 2 at 18:42
$begingroup$
Sharing jvdhooft's confusion, I'd like to clarify: Is 112 allowed as a column?
$endgroup$
– Hagen von Eitzen
Feb 2 at 18:47
$begingroup$
@HagenvonEitzen I believe it is. Seems like we both got to the same result!
$endgroup$
– jvdhooft
Feb 2 at 20:02
add a comment |
$begingroup$
There is a 2D array of size 3*n.
Suppose there are 3 numbers 1, 2 and 3.
What can be the number of ways in which we can put numbers in 2D array using
these numbers only according to below rule
1)All the n cells of a single row do not have the same number
2)All the 3 cells of a single column do not have the same number.
I am trying to calculate answer for this but am not able to find how to calculate or what formula to use.
permutations combinations
asked Feb 2 at 18:07
sroxsrox
35
$endgroup$
There is a 2D array of size 3*n.
Suppose there are 3 numbers 1, 2 and 3.
What can be the number of ways in which we can put numbers in 2D array using
these numbers only according to below rule
1)All the n cells of a single row do not have the same number
2)All the 3 cells of a single column do not have the same number.
I am trying to calculate answer for this but am not able to find how to calculate or what formula to use.
permutations combinations
permutations combinations
asked Feb 2 at 18:07
sroxsrox
35
asked Feb 2 at 18:07
sroxsrox
35
asked Feb 2 at 18:07
sroxsrox
35
asked Feb 2 at 18:07
sroxsrox
35
asked Feb 2 at 18:07
sroxsrox
35
35
$begingroup$
How can a row hold $n$ unique numbers if there are only three?
$endgroup$
– jvdhooft
Feb 2 at 18:14
$begingroup$
All the n cells of a single row do not have the same number means it should not be like 1 1 1 ........or 2 2 2 .............or 3 3 3 ..............
$endgroup$
– srox
Feb 2 at 18:38
$begingroup$
In that case, it would be better to phrase the rule as "not all cells of a single row have the same number" or "a row cannot contain the same number in all cells".
$endgroup$
– jvdhooft
Feb 2 at 18:42
$begingroup$
Sharing jvdhooft's confusion, I'd like to clarify: Is 112 allowed as a column?
$endgroup$
– Hagen von Eitzen
Feb 2 at 18:47
$begingroup$
@HagenvonEitzen I believe it is. Seems like we both got to the same result!
$endgroup$
– jvdhooft
Feb 2 at 20:02
add a comment |
$begingroup$
How can a row hold $n$ unique numbers if there are only three?
$endgroup$
– jvdhooft
Feb 2 at 18:14
$begingroup$
All the n cells of a single row do not have the same number means it should not be like 1 1 1 ........or 2 2 2 .............or 3 3 3 ..............
$endgroup$
– srox
Feb 2 at 18:38
$begingroup$
In that case, it would be better to phrase the rule as "not all cells of a single row have the same number" or "a row cannot contain the same number in all cells".
$endgroup$
– jvdhooft
Feb 2 at 18:42
$begingroup$
Sharing jvdhooft's confusion, I'd like to clarify: Is 112 allowed as a column?
$endgroup$
– Hagen von Eitzen
Feb 2 at 18:47
$begingroup$
@HagenvonEitzen I believe it is. Seems like we both got to the same result!
$endgroup$
– jvdhooft
Feb 2 at 20:02
$begingroup$
How can a row hold $n$ unique numbers if there are only three?
$endgroup$
– jvdhooft
Feb 2 at 18:14
$begingroup$
How can a row hold $n$ unique numbers if there are only three?
$endgroup$
– jvdhooft
Feb 2 at 18:14
$begingroup$
All the n cells of a single row do not have the same number means it should not be like 1 1 1 ........or 2 2 2 .............or 3 3 3 ..............
$endgroup$
– srox
Feb 2 at 18:38
$begingroup$
All the n cells of a single row do not have the same number means it should not be like 1 1 1 ........or 2 2 2 .............or 3 3 3 ..............
$endgroup$
– srox
Feb 2 at 18:38
$begingroup$
In that case, it would be better to phrase the rule as "not all cells of a single row have the same number" or "a row cannot contain the same number in all cells".
$endgroup$
– jvdhooft
Feb 2 at 18:42
$begingroup$
In that case, it would be better to phrase the rule as "not all cells of a single row have the same number" or "a row cannot contain the same number in all cells".
$endgroup$
– jvdhooft
Feb 2 at 18:42
$begingroup$
Sharing jvdhooft's confusion, I'd like to clarify: Is 112 allowed as a column?
$endgroup$
– Hagen von Eitzen
Feb 2 at 18:47
$begingroup$
Sharing jvdhooft's confusion, I'd like to clarify: Is 112 allowed as a column?
$endgroup$
– Hagen von Eitzen
Feb 2 at 18:47
$begingroup$
@HagenvonEitzen I believe it is. Seems like we both got to the same result!
$endgroup$
– jvdhooft
Feb 2 at 20:02
$begingroup$
@HagenvonEitzen I believe it is. Seems like we both got to the same result!
$endgroup$
– jvdhooft
Feb 2 at 20:02
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
We can use the principle of inclusion-exclusion to solve this problem. We first determine the amount of ways to fill in the grid if no column holds the same three values. Since there are $3^3=27$ possible ways to fill in each column, $3$ of which are invalid, we have $24^n$ possible combinations.
Next, we determine all combinations where either one of the rows equals only ones, twos or threes. Note that if one value is determined, only eight more possible combinations for each column remain. Subtracting for three rows and three possible values to fill the row with, we arrive at $9 cdot 8^n$ combinations.
However, we counted options with two rows with the same values twice, and options with three rows with the same values thrice. Counting the number of combinations where there are exactly two rows with the same values, but two different values: ${3 choose 2}{3 choose 2}{2 choose 1}(3^n-3)$. Counting the number of combinations where there are exactly two rows with the same values, but both rows contain the same number: ${3 choose 1}{3 choose 2}(2^n - 2)$. Counting the number of combinations where the three rows contain the same values, with three possible numbers for the first row and eight for the remaining two rows: $3 cdot 8$.
The total number of valid combinations thus equals:
$$24^n - 9 cdot 8^n + 18 cdot (3^n - 3) + 9 cdot (2^n - 2) + 2 cdot 24$$
$$ = 24^n - 9 cdot 8^n + 18 cdot 3^n + 9 cdot 2^n - 24$$
answered Feb 2 at 19:55
jvdhooftjvdhooft
5,65961641
$endgroup$
add a comment |
$begingroup$
There are $3^3-3=24$ ways to fill a column so that the numbers are not all the same, so ignoring the row restriction there are $24^n$ ways to fill the grid.
We now subtract the cases with a constant row. There are $3$ ways to choose the row, $3$ ways to choose the common number, and $8$ ways to fill each column to not be constant for $9cdot 8^n$. We have subtracted grids with two constant rows twice, so have to add them back once. If the two constant rows have the same value there are $3$ ways to choose the rows, $3$ ways to choose the value, and $2^n$ ways to fill the other row. If the values are different, there are $3$ ways to choose the rows, $6$ ways to choose the values, and $3^n$ ways to fill the other row. We add$9cdot 2^n+18cdot 3^n$. Now we have counted the $24$ grids with all rows constant once, once, subtracted them three times, and added them three times, so we need to subtract them once. The final number is $$24^n-9cdot 8^n+9cdot 2^n+18cdot 3^n-24$$
answered Feb 2 at 20:23
Ross MillikanRoss Millikan
301k24200375
$endgroup$
add a comment |
Your Answer
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%2f3097588%2f2d-grid-of-size-3n%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
We can use the principle of inclusion-exclusion to solve this problem. We first determine the amount of ways to fill in the grid if no column holds the same three values. Since there are $3^3=27$ possible ways to fill in each column, $3$ of which are invalid, we have $24^n$ possible combinations.
Next, we determine all combinations where either one of the rows equals only ones, twos or threes. Note that if one value is determined, only eight more possible combinations for each column remain. Subtracting for three rows and three possible values to fill the row with, we arrive at $9 cdot 8^n$ combinations.
However, we counted options with two rows with the same values twice, and options with three rows with the same values thrice. Counting the number of combinations where there are exactly two rows with the same values, but two different values: ${3 choose 2}{3 choose 2}{2 choose 1}(3^n-3)$. Counting the number of combinations where there are exactly two rows with the same values, but both rows contain the same number: ${3 choose 1}{3 choose 2}(2^n - 2)$. Counting the number of combinations where the three rows contain the same values, with three possible numbers for the first row and eight for the remaining two rows: $3 cdot 8$.
The total number of valid combinations thus equals:
$$24^n - 9 cdot 8^n + 18 cdot (3^n - 3) + 9 cdot (2^n - 2) + 2 cdot 24$$
$$ = 24^n - 9 cdot 8^n + 18 cdot 3^n + 9 cdot 2^n - 24$$
answered Feb 2 at 19:55
jvdhooftjvdhooft
5,65961641
$endgroup$
add a comment |
$begingroup$
We can use the principle of inclusion-exclusion to solve this problem. We first determine the amount of ways to fill in the grid if no column holds the same three values. Since there are $3^3=27$ possible ways to fill in each column, $3$ of which are invalid, we have $24^n$ possible combinations.
Next, we determine all combinations where either one of the rows equals only ones, twos or threes. Note that if one value is determined, only eight more possible combinations for each column remain. Subtracting for three rows and three possible values to fill the row with, we arrive at $9 cdot 8^n$ combinations.
However, we counted options with two rows with the same values twice, and options with three rows with the same values thrice. Counting the number of combinations where there are exactly two rows with the same values, but two different values: ${3 choose 2}{3 choose 2}{2 choose 1}(3^n-3)$. Counting the number of combinations where there are exactly two rows with the same values, but both rows contain the same number: ${3 choose 1}{3 choose 2}(2^n - 2)$. Counting the number of combinations where the three rows contain the same values, with three possible numbers for the first row and eight for the remaining two rows: $3 cdot 8$.
The total number of valid combinations thus equals:
$$24^n - 9 cdot 8^n + 18 cdot (3^n - 3) + 9 cdot (2^n - 2) + 2 cdot 24$$
$$ = 24^n - 9 cdot 8^n + 18 cdot 3^n + 9 cdot 2^n - 24$$
answered Feb 2 at 19:55
jvdhooftjvdhooft
5,65961641
$endgroup$
add a comment |
$begingroup$
We can use the principle of inclusion-exclusion to solve this problem. We first determine the amount of ways to fill in the grid if no column holds the same three values. Since there are $3^3=27$ possible ways to fill in each column, $3$ of which are invalid, we have $24^n$ possible combinations.
Next, we determine all combinations where either one of the rows equals only ones, twos or threes. Note that if one value is determined, only eight more possible combinations for each column remain. Subtracting for three rows and three possible values to fill the row with, we arrive at $9 cdot 8^n$ combinations.
However, we counted options with two rows with the same values twice, and options with three rows with the same values thrice. Counting the number of combinations where there are exactly two rows with the same values, but two different values: ${3 choose 2}{3 choose 2}{2 choose 1}(3^n-3)$. Counting the number of combinations where there are exactly two rows with the same values, but both rows contain the same number: ${3 choose 1}{3 choose 2}(2^n - 2)$. Counting the number of combinations where the three rows contain the same values, with three possible numbers for the first row and eight for the remaining two rows: $3 cdot 8$.
The total number of valid combinations thus equals:
$$24^n - 9 cdot 8^n + 18 cdot (3^n - 3) + 9 cdot (2^n - 2) + 2 cdot 24$$
$$ = 24^n - 9 cdot 8^n + 18 cdot 3^n + 9 cdot 2^n - 24$$
answered Feb 2 at 19:55
jvdhooftjvdhooft
5,65961641
$endgroup$
We can use the principle of inclusion-exclusion to solve this problem. We first determine the amount of ways to fill in the grid if no column holds the same three values. Since there are $3^3=27$ possible ways to fill in each column, $3$ of which are invalid, we have $24^n$ possible combinations.
Next, we determine all combinations where either one of the rows equals only ones, twos or threes. Note that if one value is determined, only eight more possible combinations for each column remain. Subtracting for three rows and three possible values to fill the row with, we arrive at $9 cdot 8^n$ combinations.
However, we counted options with two rows with the same values twice, and options with three rows with the same values thrice. Counting the number of combinations where there are exactly two rows with the same values, but two different values: ${3 choose 2}{3 choose 2}{2 choose 1}(3^n-3)$. Counting the number of combinations where there are exactly two rows with the same values, but both rows contain the same number: ${3 choose 1}{3 choose 2}(2^n - 2)$. Counting the number of combinations where the three rows contain the same values, with three possible numbers for the first row and eight for the remaining two rows: $3 cdot 8$.
The total number of valid combinations thus equals:
$$24^n - 9 cdot 8^n + 18 cdot (3^n - 3) + 9 cdot (2^n - 2) + 2 cdot 24$$
$$ = 24^n - 9 cdot 8^n + 18 cdot 3^n + 9 cdot 2^n - 24$$
answered Feb 2 at 19:55
jvdhooftjvdhooft
5,65961641
answered Feb 2 at 19:55
jvdhooftjvdhooft
5,65961641
answered Feb 2 at 19:55
jvdhooftjvdhooft
5,65961641
answered Feb 2 at 19:55
jvdhooftjvdhooft
5,65961641
5,65961641
add a comment |
add a comment |
$begingroup$
There are $3^3-3=24$ ways to fill a column so that the numbers are not all the same, so ignoring the row restriction there are $24^n$ ways to fill the grid.
We now subtract the cases with a constant row. There are $3$ ways to choose the row, $3$ ways to choose the common number, and $8$ ways to fill each column to not be constant for $9cdot 8^n$. We have subtracted grids with two constant rows twice, so have to add them back once. If the two constant rows have the same value there are $3$ ways to choose the rows, $3$ ways to choose the value, and $2^n$ ways to fill the other row. If the values are different, there are $3$ ways to choose the rows, $6$ ways to choose the values, and $3^n$ ways to fill the other row. We add$9cdot 2^n+18cdot 3^n$. Now we have counted the $24$ grids with all rows constant once, once, subtracted them three times, and added them three times, so we need to subtract them once. The final number is $$24^n-9cdot 8^n+9cdot 2^n+18cdot 3^n-24$$
answered Feb 2 at 20:23
Ross MillikanRoss Millikan
301k24200375
$endgroup$
add a comment |
$begingroup$
There are $3^3-3=24$ ways to fill a column so that the numbers are not all the same, so ignoring the row restriction there are $24^n$ ways to fill the grid.
We now subtract the cases with a constant row. There are $3$ ways to choose the row, $3$ ways to choose the common number, and $8$ ways to fill each column to not be constant for $9cdot 8^n$. We have subtracted grids with two constant rows twice, so have to add them back once. If the two constant rows have the same value there are $3$ ways to choose the rows, $3$ ways to choose the value, and $2^n$ ways to fill the other row. If the values are different, there are $3$ ways to choose the rows, $6$ ways to choose the values, and $3^n$ ways to fill the other row. We add$9cdot 2^n+18cdot 3^n$. Now we have counted the $24$ grids with all rows constant once, once, subtracted them three times, and added them three times, so we need to subtract them once. The final number is $$24^n-9cdot 8^n+9cdot 2^n+18cdot 3^n-24$$
answered Feb 2 at 20:23
Ross MillikanRoss Millikan
301k24200375
$endgroup$
add a comment |
$begingroup$
There are $3^3-3=24$ ways to fill a column so that the numbers are not all the same, so ignoring the row restriction there are $24^n$ ways to fill the grid.
We now subtract the cases with a constant row. There are $3$ ways to choose the row, $3$ ways to choose the common number, and $8$ ways to fill each column to not be constant for $9cdot 8^n$. We have subtracted grids with two constant rows twice, so have to add them back once. If the two constant rows have the same value there are $3$ ways to choose the rows, $3$ ways to choose the value, and $2^n$ ways to fill the other row. If the values are different, there are $3$ ways to choose the rows, $6$ ways to choose the values, and $3^n$ ways to fill the other row. We add$9cdot 2^n+18cdot 3^n$. Now we have counted the $24$ grids with all rows constant once, once, subtracted them three times, and added them three times, so we need to subtract them once. The final number is $$24^n-9cdot 8^n+9cdot 2^n+18cdot 3^n-24$$
answered Feb 2 at 20:23
Ross MillikanRoss Millikan
301k24200375
$endgroup$
There are $3^3-3=24$ ways to fill a column so that the numbers are not all the same, so ignoring the row restriction there are $24^n$ ways to fill the grid.
We now subtract the cases with a constant row. There are $3$ ways to choose the row, $3$ ways to choose the common number, and $8$ ways to fill each column to not be constant for $9cdot 8^n$. We have subtracted grids with two constant rows twice, so have to add them back once. If the two constant rows have the same value there are $3$ ways to choose the rows, $3$ ways to choose the value, and $2^n$ ways to fill the other row. If the values are different, there are $3$ ways to choose the rows, $6$ ways to choose the values, and $3^n$ ways to fill the other row. We add$9cdot 2^n+18cdot 3^n$. Now we have counted the $24$ grids with all rows constant once, once, subtracted them three times, and added them three times, so we need to subtract them once. The final number is $$24^n-9cdot 8^n+9cdot 2^n+18cdot 3^n-24$$
answered Feb 2 at 20:23
Ross MillikanRoss Millikan
301k24200375
answered Feb 2 at 20:23
Ross MillikanRoss Millikan
301k24200375
answered Feb 2 at 20:23
Ross MillikanRoss Millikan
301k24200375
answered Feb 2 at 20:23
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%2f3097588%2f2d-grid-of-size-3n%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$
How can a row hold $n$ unique numbers if there are only three?
$endgroup$
– jvdhooft
Feb 2 at 18:14
$begingroup$
All the n cells of a single row do not have the same number means it should not be like 1 1 1 ........or 2 2 2 .............or 3 3 3 ..............
$endgroup$
– srox
Feb 2 at 18:38
$begingroup$
In that case, it would be better to phrase the rule as "not all cells of a single row have the same number" or "a row cannot contain the same number in all cells".
$endgroup$
– jvdhooft
Feb 2 at 18:42
$begingroup$
Sharing jvdhooft's confusion, I'd like to clarify: Is 112 allowed as a column?
$endgroup$
– Hagen von Eitzen
Feb 2 at 18:47
$begingroup$
@HagenvonEitzen I believe it is. Seems like we both got to the same result!
$endgroup$
– jvdhooft
Feb 2 at 20:02