Mixing
Filling a 5x5 array with X-s and O-s
$begingroup$
Consider a $5x5$ array. In how many ways can we fill the array with $X$'s and $O$'s so that no two consecutive rows are identical?
My tutor gave us the following answer:
$2^{(25)} - [4*2^{(20)} - 6*2^{(15)} + 4*2^{(10)} - 2^{(5)}]$
A ---------- B --------- C ---------- D --------- E
Where:
$A$ - all possible fillings
$B$ - fillings where 2 cons. rows are the same
$C$ - fillings where 3 cons. rows are the same + 2 cons. rows are the same, and another 2 rows are the same, leaving us with 1 row that can be freely changed
$D$ - $4$ cons. rows are same + $3$ cons rows , and another $2$ rows are same
$E$ - All rows are the same
I hope that my description is rather clear.
The real question is.. Why do we subtract $C$ and $E$, and add $B$ and $D$?
I understand that it has something to do with the intersection(Possibility of some fillings being the same as others), but some fillings also intersect with others, and yet - we add them.
Please, explain it to me.
combinatorics permutations
edited Dec 22 '18 at 12:08
Shaun
10.6k113687
asked Jan 30 '15 at 10:33
MacMac
1
$endgroup$
add a comment |
$begingroup$
Consider a $5x5$ array. In how many ways can we fill the array with $X$'s and $O$'s so that no two consecutive rows are identical?
My tutor gave us the following answer:
$2^{(25)} - [4*2^{(20)} - 6*2^{(15)} + 4*2^{(10)} - 2^{(5)}]$
A ---------- B --------- C ---------- D --------- E
Where:
$A$ - all possible fillings
$B$ - fillings where 2 cons. rows are the same
$C$ - fillings where 3 cons. rows are the same + 2 cons. rows are the same, and another 2 rows are the same, leaving us with 1 row that can be freely changed
$D$ - $4$ cons. rows are same + $3$ cons rows , and another $2$ rows are same
$E$ - All rows are the same
I hope that my description is rather clear.
The real question is.. Why do we subtract $C$ and $E$, and add $B$ and $D$?
I understand that it has something to do with the intersection(Possibility of some fillings being the same as others), but some fillings also intersect with others, and yet - we add them.
Please, explain it to me.
combinatorics permutations
edited Dec 22 '18 at 12:08
Shaun
10.6k113687
asked Jan 30 '15 at 10:33
MacMac
1
$endgroup$
5
$begingroup$
Looks like your tutor wants you to use inclusion-exclusion principle. I would approach the question differently: 1) How many ways to fill in the first row? 2) Given a first row, how many ways to fill in the 2nd row? 3) Given a second row, how many ways to...
$endgroup$
– Jyrki Lahtonen
Jan 30 '15 at 10:37
$begingroup$
Still, did he do it correctly? If i approaached it as you suggest, then: First row possibilities - 2^(5) 2nd row possibilities - 2^(5) - ..?
$endgroup$
– Mac
Jan 30 '15 at 11:19
add a comment |
$begingroup$
Consider a $5x5$ array. In how many ways can we fill the array with $X$'s and $O$'s so that no two consecutive rows are identical?
My tutor gave us the following answer:
$2^{(25)} - [4*2^{(20)} - 6*2^{(15)} + 4*2^{(10)} - 2^{(5)}]$
A ---------- B --------- C ---------- D --------- E
Where:
$A$ - all possible fillings
$B$ - fillings where 2 cons. rows are the same
$C$ - fillings where 3 cons. rows are the same + 2 cons. rows are the same, and another 2 rows are the same, leaving us with 1 row that can be freely changed
$D$ - $4$ cons. rows are same + $3$ cons rows , and another $2$ rows are same
$E$ - All rows are the same
I hope that my description is rather clear.
The real question is.. Why do we subtract $C$ and $E$, and add $B$ and $D$?
I understand that it has something to do with the intersection(Possibility of some fillings being the same as others), but some fillings also intersect with others, and yet - we add them.
Please, explain it to me.
combinatorics permutations
edited Dec 22 '18 at 12:08
Shaun
10.6k113687
asked Jan 30 '15 at 10:33
MacMac
1
$endgroup$
Consider a $5x5$ array. In how many ways can we fill the array with $X$'s and $O$'s so that no two consecutive rows are identical?
My tutor gave us the following answer:
$2^{(25)} - [4*2^{(20)} - 6*2^{(15)} + 4*2^{(10)} - 2^{(5)}]$
A ---------- B --------- C ---------- D --------- E
Where:
$A$ - all possible fillings
$B$ - fillings where 2 cons. rows are the same
$C$ - fillings where 3 cons. rows are the same + 2 cons. rows are the same, and another 2 rows are the same, leaving us with 1 row that can be freely changed
$D$ - $4$ cons. rows are same + $3$ cons rows , and another $2$ rows are same
$E$ - All rows are the same
I hope that my description is rather clear.
The real question is.. Why do we subtract $C$ and $E$, and add $B$ and $D$?
I understand that it has something to do with the intersection(Possibility of some fillings being the same as others), but some fillings also intersect with others, and yet - we add them.
Please, explain it to me.
combinatorics permutations
combinatorics permutations
edited Dec 22 '18 at 12:08
Shaun
10.6k113687
asked Jan 30 '15 at 10:33
MacMac
1
edited Dec 22 '18 at 12:08
Shaun
10.6k113687
asked Jan 30 '15 at 10:33
MacMac
1
edited Dec 22 '18 at 12:08
Shaun
10.6k113687
edited Dec 22 '18 at 12:08
Shaun
10.6k113687
edited Dec 22 '18 at 12:08
Shaun
10.6k113687
10.6k113687
asked Jan 30 '15 at 10:33
MacMac
1
asked Jan 30 '15 at 10:33
MacMac
1
asked Jan 30 '15 at 10:33
MacMac
1
1
5
$begingroup$
Looks like your tutor wants you to use inclusion-exclusion principle. I would approach the question differently: 1) How many ways to fill in the first row? 2) Given a first row, how many ways to fill in the 2nd row? 3) Given a second row, how many ways to...
$endgroup$
– Jyrki Lahtonen
Jan 30 '15 at 10:37
$begingroup$
Still, did he do it correctly? If i approaached it as you suggest, then: First row possibilities - 2^(5) 2nd row possibilities - 2^(5) - ..?
$endgroup$
– Mac
Jan 30 '15 at 11:19
add a comment |
5
$begingroup$
Looks like your tutor wants you to use inclusion-exclusion principle. I would approach the question differently: 1) How many ways to fill in the first row? 2) Given a first row, how many ways to fill in the 2nd row? 3) Given a second row, how many ways to...
$endgroup$
– Jyrki Lahtonen
Jan 30 '15 at 10:37
$begingroup$
Still, did he do it correctly? If i approaached it as you suggest, then: First row possibilities - 2^(5) 2nd row possibilities - 2^(5) - ..?
$endgroup$
– Mac
Jan 30 '15 at 11:19
5
5
$begingroup$
Looks like your tutor wants you to use inclusion-exclusion principle. I would approach the question differently: 1) How many ways to fill in the first row? 2) Given a first row, how many ways to fill in the 2nd row? 3) Given a second row, how many ways to...
$endgroup$
– Jyrki Lahtonen
Jan 30 '15 at 10:37
$begingroup$
Looks like your tutor wants you to use inclusion-exclusion principle. I would approach the question differently: 1) How many ways to fill in the first row? 2) Given a first row, how many ways to fill in the 2nd row? 3) Given a second row, how many ways to...
$endgroup$
– Jyrki Lahtonen
Jan 30 '15 at 10:37
$begingroup$
Still, did he do it correctly? If i approaached it as you suggest, then: First row possibilities - 2^(5) 2nd row possibilities - 2^(5) - ..?
$endgroup$
– Mac
Jan 30 '15 at 11:19
$begingroup$
Still, did he do it correctly? If i approaached it as you suggest, then: First row possibilities - 2^(5) 2nd row possibilities - 2^(5) - ..?
$endgroup$
– Mac
Jan 30 '15 at 11:19
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Your tutor used inclusion–exclusion principle formula in order to count when 2, 3, 4 or 5 rows are the same. Then from all possible fillings he subtracted B-C+D-E. The whole statement for the formula I mentioned, you can find on Inclusion - exclusion principle
A - all possible fillings : since we have 5 rows and 5 columns, in total we have 25 places where we can put either X or O. So from 2 letters (X, O) we choose 1 for each place. We do it in ${2 choose 1}^{25}$ ways.
B - fillings where 2 consecutive rows are the same : we fill 1 random row using X's and O's and we do it in ${2 choose 1}^{5}$ ways. Then from the rest 4 rows we choose 1 that we want to look exactly the same as the chosen row. We do it in ${4 choose 1}$ ways. We don't really care about remaining 3 rows - we just have to fill them in ${2 choose 1}^{15}$ ways. In total we have ${4 choose 1}$ ${2 choose 1}^{20}$ ways to do so.
C - fillings where 3 consecutive rows are the same : we fill 1 random row using X's and O's and we do it in ${2 choose 1}^5$ ways. Then from the rest 4 rows we choose 2 that we want to look exactly the same as the chosen row. We do it in ${4 choose 2}$ ways. Remaining 2 rows can be filled in ${2 choose 1}^{10}$ ways. In total we have ${4 choose 2}$ ${2 choose 1}^{15}$ ways to do so.
D - fillings where 4 consecutive rows are the same : we repeat same algorithm as we used in previous points. In total we have ${4 choose 3} {2 choose 1}^{10}$ ways to do so (since from 4 rows we choose 3 to be exactly the same as the first row).
E - fillings where 5 consecutive rows are the same : we fill 1 random row using X's and O's and we do it in ${2 choose 1}^5$ ways. Thus in total we have ${2 choose 1}^5$ ways.
answered Feb 3 at 10:37
MichaelMichael
266
$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%2f1126356%2ffilling-a-5x5-array-with-x-s-and-o-s%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$
Your tutor used inclusion–exclusion principle formula in order to count when 2, 3, 4 or 5 rows are the same. Then from all possible fillings he subtracted B-C+D-E. The whole statement for the formula I mentioned, you can find on Inclusion - exclusion principle
A - all possible fillings : since we have 5 rows and 5 columns, in total we have 25 places where we can put either X or O. So from 2 letters (X, O) we choose 1 for each place. We do it in ${2 choose 1}^{25}$ ways.
B - fillings where 2 consecutive rows are the same : we fill 1 random row using X's and O's and we do it in ${2 choose 1}^{5}$ ways. Then from the rest 4 rows we choose 1 that we want to look exactly the same as the chosen row. We do it in ${4 choose 1}$ ways. We don't really care about remaining 3 rows - we just have to fill them in ${2 choose 1}^{15}$ ways. In total we have ${4 choose 1}$ ${2 choose 1}^{20}$ ways to do so.
C - fillings where 3 consecutive rows are the same : we fill 1 random row using X's and O's and we do it in ${2 choose 1}^5$ ways. Then from the rest 4 rows we choose 2 that we want to look exactly the same as the chosen row. We do it in ${4 choose 2}$ ways. Remaining 2 rows can be filled in ${2 choose 1}^{10}$ ways. In total we have ${4 choose 2}$ ${2 choose 1}^{15}$ ways to do so.
D - fillings where 4 consecutive rows are the same : we repeat same algorithm as we used in previous points. In total we have ${4 choose 3} {2 choose 1}^{10}$ ways to do so (since from 4 rows we choose 3 to be exactly the same as the first row).
E - fillings where 5 consecutive rows are the same : we fill 1 random row using X's and O's and we do it in ${2 choose 1}^5$ ways. Thus in total we have ${2 choose 1}^5$ ways.
answered Feb 3 at 10:37
MichaelMichael
266
$endgroup$
add a comment |
$begingroup$
Your tutor used inclusion–exclusion principle formula in order to count when 2, 3, 4 or 5 rows are the same. Then from all possible fillings he subtracted B-C+D-E. The whole statement for the formula I mentioned, you can find on Inclusion - exclusion principle
A - all possible fillings : since we have 5 rows and 5 columns, in total we have 25 places where we can put either X or O. So from 2 letters (X, O) we choose 1 for each place. We do it in ${2 choose 1}^{25}$ ways.
B - fillings where 2 consecutive rows are the same : we fill 1 random row using X's and O's and we do it in ${2 choose 1}^{5}$ ways. Then from the rest 4 rows we choose 1 that we want to look exactly the same as the chosen row. We do it in ${4 choose 1}$ ways. We don't really care about remaining 3 rows - we just have to fill them in ${2 choose 1}^{15}$ ways. In total we have ${4 choose 1}$ ${2 choose 1}^{20}$ ways to do so.
C - fillings where 3 consecutive rows are the same : we fill 1 random row using X's and O's and we do it in ${2 choose 1}^5$ ways. Then from the rest 4 rows we choose 2 that we want to look exactly the same as the chosen row. We do it in ${4 choose 2}$ ways. Remaining 2 rows can be filled in ${2 choose 1}^{10}$ ways. In total we have ${4 choose 2}$ ${2 choose 1}^{15}$ ways to do so.
D - fillings where 4 consecutive rows are the same : we repeat same algorithm as we used in previous points. In total we have ${4 choose 3} {2 choose 1}^{10}$ ways to do so (since from 4 rows we choose 3 to be exactly the same as the first row).
E - fillings where 5 consecutive rows are the same : we fill 1 random row using X's and O's and we do it in ${2 choose 1}^5$ ways. Thus in total we have ${2 choose 1}^5$ ways.
answered Feb 3 at 10:37
MichaelMichael
266
$endgroup$
add a comment |
$begingroup$
Your tutor used inclusion–exclusion principle formula in order to count when 2, 3, 4 or 5 rows are the same. Then from all possible fillings he subtracted B-C+D-E. The whole statement for the formula I mentioned, you can find on Inclusion - exclusion principle
A - all possible fillings : since we have 5 rows and 5 columns, in total we have 25 places where we can put either X or O. So from 2 letters (X, O) we choose 1 for each place. We do it in ${2 choose 1}^{25}$ ways.
B - fillings where 2 consecutive rows are the same : we fill 1 random row using X's and O's and we do it in ${2 choose 1}^{5}$ ways. Then from the rest 4 rows we choose 1 that we want to look exactly the same as the chosen row. We do it in ${4 choose 1}$ ways. We don't really care about remaining 3 rows - we just have to fill them in ${2 choose 1}^{15}$ ways. In total we have ${4 choose 1}$ ${2 choose 1}^{20}$ ways to do so.
C - fillings where 3 consecutive rows are the same : we fill 1 random row using X's and O's and we do it in ${2 choose 1}^5$ ways. Then from the rest 4 rows we choose 2 that we want to look exactly the same as the chosen row. We do it in ${4 choose 2}$ ways. Remaining 2 rows can be filled in ${2 choose 1}^{10}$ ways. In total we have ${4 choose 2}$ ${2 choose 1}^{15}$ ways to do so.
D - fillings where 4 consecutive rows are the same : we repeat same algorithm as we used in previous points. In total we have ${4 choose 3} {2 choose 1}^{10}$ ways to do so (since from 4 rows we choose 3 to be exactly the same as the first row).
E - fillings where 5 consecutive rows are the same : we fill 1 random row using X's and O's and we do it in ${2 choose 1}^5$ ways. Thus in total we have ${2 choose 1}^5$ ways.
answered Feb 3 at 10:37
MichaelMichael
266
$endgroup$
Your tutor used inclusion–exclusion principle formula in order to count when 2, 3, 4 or 5 rows are the same. Then from all possible fillings he subtracted B-C+D-E. The whole statement for the formula I mentioned, you can find on Inclusion - exclusion principle
A - all possible fillings : since we have 5 rows and 5 columns, in total we have 25 places where we can put either X or O. So from 2 letters (X, O) we choose 1 for each place. We do it in ${2 choose 1}^{25}$ ways.
B - fillings where 2 consecutive rows are the same : we fill 1 random row using X's and O's and we do it in ${2 choose 1}^{5}$ ways. Then from the rest 4 rows we choose 1 that we want to look exactly the same as the chosen row. We do it in ${4 choose 1}$ ways. We don't really care about remaining 3 rows - we just have to fill them in ${2 choose 1}^{15}$ ways. In total we have ${4 choose 1}$ ${2 choose 1}^{20}$ ways to do so.
C - fillings where 3 consecutive rows are the same : we fill 1 random row using X's and O's and we do it in ${2 choose 1}^5$ ways. Then from the rest 4 rows we choose 2 that we want to look exactly the same as the chosen row. We do it in ${4 choose 2}$ ways. Remaining 2 rows can be filled in ${2 choose 1}^{10}$ ways. In total we have ${4 choose 2}$ ${2 choose 1}^{15}$ ways to do so.
D - fillings where 4 consecutive rows are the same : we repeat same algorithm as we used in previous points. In total we have ${4 choose 3} {2 choose 1}^{10}$ ways to do so (since from 4 rows we choose 3 to be exactly the same as the first row).
E - fillings where 5 consecutive rows are the same : we fill 1 random row using X's and O's and we do it in ${2 choose 1}^5$ ways. Thus in total we have ${2 choose 1}^5$ ways.
answered Feb 3 at 10:37
MichaelMichael
266
edited Feb 3 at 10:48
answered Feb 3 at 10:37
MichaelMichael
266
answered Feb 3 at 10:37
MichaelMichael
266
answered Feb 3 at 10:37
MichaelMichael
266
266
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%2f1126356%2ffilling-a-5x5-array-with-x-s-and-o-s%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
5
$begingroup$
Looks like your tutor wants you to use inclusion-exclusion principle. I would approach the question differently: 1) How many ways to fill in the first row? 2) Given a first row, how many ways to fill in the 2nd row? 3) Given a second row, how many ways to...
$endgroup$
– Jyrki Lahtonen
Jan 30 '15 at 10:37
$begingroup$
Still, did he do it correctly? If i approaached it as you suggest, then: First row possibilities - 2^(5) 2nd row possibilities - 2^(5) - ..?
$endgroup$
– Mac
Jan 30 '15 at 11:19