How many ways to fill in a square grid with certain restrictions
Suppose I have a 5x5 grid of squares. I would like to fill in 15 checkmarks in the squares such that (1) each of the 25 square cells contains at most one checkmark, (2) each row has exactly 3 checkmarks, and (3) each column has exactly 3 checkmarks. How many ways are there to fill in these 15 checkmarks?
More generally, suppose I have an $n times n $ square grid, and I would like to fill in $mn$ checkmarks such that (1) each of the $n^2$ square cells contains at most one checkmark, (2) each row has exactly m checkmarks, and (3) each column has exactly m checkmarks. How many ways are there to do so? If $m=1,$ I think the answer is $n!$. But I am not sure about the general case.
Also, if I have an additional restriction that no checkmarks on the diagonal, i.e., no checkmark in the (1,1), (2,2),... (n,n) cells. How many ways are there?
Thanks very much! Wish all very happy new year!
co.combinatorics
add a comment |
Suppose I have a 5x5 grid of squares. I would like to fill in 15 checkmarks in the squares such that (1) each of the 25 square cells contains at most one checkmark, (2) each row has exactly 3 checkmarks, and (3) each column has exactly 3 checkmarks. How many ways are there to fill in these 15 checkmarks?
More generally, suppose I have an $n times n $ square grid, and I would like to fill in $mn$ checkmarks such that (1) each of the $n^2$ square cells contains at most one checkmark, (2) each row has exactly m checkmarks, and (3) each column has exactly m checkmarks. How many ways are there to do so? If $m=1,$ I think the answer is $n!$. But I am not sure about the general case.
Also, if I have an additional restriction that no checkmarks on the diagonal, i.e., no checkmark in the (1,1), (2,2),... (n,n) cells. How many ways are there?
Thanks very much! Wish all very happy new year!
co.combinatorics
If you remove the only one checkmark per box requirement then you are looking at the Ehrhart polynomial of the Birkhoff polytope, and get into the Anand-Dumir-Gupta conjecture and related areas.
– Sam Hopkins
10 hours ago
add a comment |
Suppose I have a 5x5 grid of squares. I would like to fill in 15 checkmarks in the squares such that (1) each of the 25 square cells contains at most one checkmark, (2) each row has exactly 3 checkmarks, and (3) each column has exactly 3 checkmarks. How many ways are there to fill in these 15 checkmarks?
More generally, suppose I have an $n times n $ square grid, and I would like to fill in $mn$ checkmarks such that (1) each of the $n^2$ square cells contains at most one checkmark, (2) each row has exactly m checkmarks, and (3) each column has exactly m checkmarks. How many ways are there to do so? If $m=1,$ I think the answer is $n!$. But I am not sure about the general case.
Also, if I have an additional restriction that no checkmarks on the diagonal, i.e., no checkmark in the (1,1), (2,2),... (n,n) cells. How many ways are there?
Thanks very much! Wish all very happy new year!
co.combinatorics
Suppose I have a 5x5 grid of squares. I would like to fill in 15 checkmarks in the squares such that (1) each of the 25 square cells contains at most one checkmark, (2) each row has exactly 3 checkmarks, and (3) each column has exactly 3 checkmarks. How many ways are there to fill in these 15 checkmarks?
More generally, suppose I have an $n times n $ square grid, and I would like to fill in $mn$ checkmarks such that (1) each of the $n^2$ square cells contains at most one checkmark, (2) each row has exactly m checkmarks, and (3) each column has exactly m checkmarks. How many ways are there to do so? If $m=1,$ I think the answer is $n!$. But I am not sure about the general case.
Also, if I have an additional restriction that no checkmarks on the diagonal, i.e., no checkmark in the (1,1), (2,2),... (n,n) cells. How many ways are there?
Thanks very much! Wish all very happy new year!
co.combinatorics
co.combinatorics
asked 12 hours ago
KPU
563
563
If you remove the only one checkmark per box requirement then you are looking at the Ehrhart polynomial of the Birkhoff polytope, and get into the Anand-Dumir-Gupta conjecture and related areas.
– Sam Hopkins
10 hours ago
add a comment |
If you remove the only one checkmark per box requirement then you are looking at the Ehrhart polynomial of the Birkhoff polytope, and get into the Anand-Dumir-Gupta conjecture and related areas.
– Sam Hopkins
10 hours ago
If you remove the only one checkmark per box requirement then you are looking at the Ehrhart polynomial of the Birkhoff polytope, and get into the Anand-Dumir-Gupta conjecture and related areas.
– Sam Hopkins
10 hours ago
If you remove the only one checkmark per box requirement then you are looking at the Ehrhart polynomial of the Birkhoff polytope, and get into the Anand-Dumir-Gupta conjecture and related areas.
– Sam Hopkins
10 hours ago
add a comment |
2 Answers
2
active
oldest
votes
What you are looking for is the number of matrices in the class $mathcal A(n,m)$ of $(0,1)$-matrices that are $ntimes n$ and have each row and column containing exactly $m$ entries equal to $1$. This is a pretty well-studied question, but an exact answer isn't known except in some small cases.
You are right that for $m=1$, the number is $n!$, as then you are counting the $ntimes n$ permutation matrices. A sort of generalization of this was obtained in
Wei, Wan-Di. "The class $mathfrak A(R,S)$ of $(0,1)$-matrices." Discrete Mathematics 39, no. 3 (1982): 301–305. Journal link
where it is given that the number of such matrices is at least
$$frac{(n!)^m}{(m!)^n}.$$
I say it is “sort of” a generalization because it is only a lower bound. Again, there is no closed form known for the exact number. I think the most frequently-cited asymptotic results are those of McKay and others, for example see
McKay, Brendan D., Wang, Xiaoji. "Asymptotic enumeration of 0-1 matrices with equal row sums and equal column sums." Linear Algebra and its Applications. 373 (2003): 273–287. Journal link
and anything that cites it.
There are other results – and other asymptotic results – out there. A good starting point for more details is the book Combinatorial Matrix Classes by Brualdi.
Finally, note that this is the same as counting balanced regular bipartite graphs. For example, your question is the same as this one where the $d_v$ and $d_c$ of that question are taken to be equal. So you may wish to see the answer – provided by McKay! – appearing there.
Thanks so much for the very helpful information!! Happy New Year!
– KPU
3 hours ago
add a comment |
The problem amounts to counting binary or $0/1$-matrices with restrictions on row/column sums.
In general, let the row sums be $r(n)=(r_1,dots,r_n)$ and column sums $c(n)=(c_1,dots,c_n)$. Obviously, $0leq r_i, c_jleq n$ for all $i, j$. Further, let $mathbf{x}=(x_1,dots,x_n)$ and $mathbf{y}=(y_1,dots,y_n)$ with the multi-exponent notation $mathbf{x}^{u}=x_1^{u_1}cdots x_n^{u_n}$. Then, there is this generating function
$$prod_{i,j=1}^n(1+x_iy_j)=sum_{r(n),c(n)} N(r(n),c(n))mathbf{x}^{r(n)}mathbf{y}^{c(n)} tag1$$
for the enumeration $N(r(n),c(n))$ of the number of binary matrices with row sums $r(n)$ and $c(n)$.
To get back to your question, extract the coefficient $N((k,dots,k),(k,dots,k))$ of
$$mathbf{x}^{(k,dots,k)}mathbf{y}^{(k,dots,k)}$$
from the above product in (1).
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: "504"
};
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%2fmathoverflow.net%2fquestions%2f319842%2fhow-many-ways-to-fill-in-a-square-grid-with-certain-restrictions%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
What you are looking for is the number of matrices in the class $mathcal A(n,m)$ of $(0,1)$-matrices that are $ntimes n$ and have each row and column containing exactly $m$ entries equal to $1$. This is a pretty well-studied question, but an exact answer isn't known except in some small cases.
You are right that for $m=1$, the number is $n!$, as then you are counting the $ntimes n$ permutation matrices. A sort of generalization of this was obtained in
Wei, Wan-Di. "The class $mathfrak A(R,S)$ of $(0,1)$-matrices." Discrete Mathematics 39, no. 3 (1982): 301–305. Journal link
where it is given that the number of such matrices is at least
$$frac{(n!)^m}{(m!)^n}.$$
I say it is “sort of” a generalization because it is only a lower bound. Again, there is no closed form known for the exact number. I think the most frequently-cited asymptotic results are those of McKay and others, for example see
McKay, Brendan D., Wang, Xiaoji. "Asymptotic enumeration of 0-1 matrices with equal row sums and equal column sums." Linear Algebra and its Applications. 373 (2003): 273–287. Journal link
and anything that cites it.
There are other results – and other asymptotic results – out there. A good starting point for more details is the book Combinatorial Matrix Classes by Brualdi.
Finally, note that this is the same as counting balanced regular bipartite graphs. For example, your question is the same as this one where the $d_v$ and $d_c$ of that question are taken to be equal. So you may wish to see the answer – provided by McKay! – appearing there.
Thanks so much for the very helpful information!! Happy New Year!
– KPU
3 hours ago
add a comment |
What you are looking for is the number of matrices in the class $mathcal A(n,m)$ of $(0,1)$-matrices that are $ntimes n$ and have each row and column containing exactly $m$ entries equal to $1$. This is a pretty well-studied question, but an exact answer isn't known except in some small cases.
You are right that for $m=1$, the number is $n!$, as then you are counting the $ntimes n$ permutation matrices. A sort of generalization of this was obtained in
Wei, Wan-Di. "The class $mathfrak A(R,S)$ of $(0,1)$-matrices." Discrete Mathematics 39, no. 3 (1982): 301–305. Journal link
where it is given that the number of such matrices is at least
$$frac{(n!)^m}{(m!)^n}.$$
I say it is “sort of” a generalization because it is only a lower bound. Again, there is no closed form known for the exact number. I think the most frequently-cited asymptotic results are those of McKay and others, for example see
McKay, Brendan D., Wang, Xiaoji. "Asymptotic enumeration of 0-1 matrices with equal row sums and equal column sums." Linear Algebra and its Applications. 373 (2003): 273–287. Journal link
and anything that cites it.
There are other results – and other asymptotic results – out there. A good starting point for more details is the book Combinatorial Matrix Classes by Brualdi.
Finally, note that this is the same as counting balanced regular bipartite graphs. For example, your question is the same as this one where the $d_v$ and $d_c$ of that question are taken to be equal. So you may wish to see the answer – provided by McKay! – appearing there.
Thanks so much for the very helpful information!! Happy New Year!
– KPU
3 hours ago
add a comment |
What you are looking for is the number of matrices in the class $mathcal A(n,m)$ of $(0,1)$-matrices that are $ntimes n$ and have each row and column containing exactly $m$ entries equal to $1$. This is a pretty well-studied question, but an exact answer isn't known except in some small cases.
You are right that for $m=1$, the number is $n!$, as then you are counting the $ntimes n$ permutation matrices. A sort of generalization of this was obtained in
Wei, Wan-Di. "The class $mathfrak A(R,S)$ of $(0,1)$-matrices." Discrete Mathematics 39, no. 3 (1982): 301–305. Journal link
where it is given that the number of such matrices is at least
$$frac{(n!)^m}{(m!)^n}.$$
I say it is “sort of” a generalization because it is only a lower bound. Again, there is no closed form known for the exact number. I think the most frequently-cited asymptotic results are those of McKay and others, for example see
McKay, Brendan D., Wang, Xiaoji. "Asymptotic enumeration of 0-1 matrices with equal row sums and equal column sums." Linear Algebra and its Applications. 373 (2003): 273–287. Journal link
and anything that cites it.
There are other results – and other asymptotic results – out there. A good starting point for more details is the book Combinatorial Matrix Classes by Brualdi.
Finally, note that this is the same as counting balanced regular bipartite graphs. For example, your question is the same as this one where the $d_v$ and $d_c$ of that question are taken to be equal. So you may wish to see the answer – provided by McKay! – appearing there.
What you are looking for is the number of matrices in the class $mathcal A(n,m)$ of $(0,1)$-matrices that are $ntimes n$ and have each row and column containing exactly $m$ entries equal to $1$. This is a pretty well-studied question, but an exact answer isn't known except in some small cases.
You are right that for $m=1$, the number is $n!$, as then you are counting the $ntimes n$ permutation matrices. A sort of generalization of this was obtained in
Wei, Wan-Di. "The class $mathfrak A(R,S)$ of $(0,1)$-matrices." Discrete Mathematics 39, no. 3 (1982): 301–305. Journal link
where it is given that the number of such matrices is at least
$$frac{(n!)^m}{(m!)^n}.$$
I say it is “sort of” a generalization because it is only a lower bound. Again, there is no closed form known for the exact number. I think the most frequently-cited asymptotic results are those of McKay and others, for example see
McKay, Brendan D., Wang, Xiaoji. "Asymptotic enumeration of 0-1 matrices with equal row sums and equal column sums." Linear Algebra and its Applications. 373 (2003): 273–287. Journal link
and anything that cites it.
There are other results – and other asymptotic results – out there. A good starting point for more details is the book Combinatorial Matrix Classes by Brualdi.
Finally, note that this is the same as counting balanced regular bipartite graphs. For example, your question is the same as this one where the $d_v$ and $d_c$ of that question are taken to be equal. So you may wish to see the answer – provided by McKay! – appearing there.
answered 10 hours ago
Louis Deaett
7551618
7551618
Thanks so much for the very helpful information!! Happy New Year!
– KPU
3 hours ago
add a comment |
Thanks so much for the very helpful information!! Happy New Year!
– KPU
3 hours ago
Thanks so much for the very helpful information!! Happy New Year!
– KPU
3 hours ago
Thanks so much for the very helpful information!! Happy New Year!
– KPU
3 hours ago
add a comment |
The problem amounts to counting binary or $0/1$-matrices with restrictions on row/column sums.
In general, let the row sums be $r(n)=(r_1,dots,r_n)$ and column sums $c(n)=(c_1,dots,c_n)$. Obviously, $0leq r_i, c_jleq n$ for all $i, j$. Further, let $mathbf{x}=(x_1,dots,x_n)$ and $mathbf{y}=(y_1,dots,y_n)$ with the multi-exponent notation $mathbf{x}^{u}=x_1^{u_1}cdots x_n^{u_n}$. Then, there is this generating function
$$prod_{i,j=1}^n(1+x_iy_j)=sum_{r(n),c(n)} N(r(n),c(n))mathbf{x}^{r(n)}mathbf{y}^{c(n)} tag1$$
for the enumeration $N(r(n),c(n))$ of the number of binary matrices with row sums $r(n)$ and $c(n)$.
To get back to your question, extract the coefficient $N((k,dots,k),(k,dots,k))$ of
$$mathbf{x}^{(k,dots,k)}mathbf{y}^{(k,dots,k)}$$
from the above product in (1).
add a comment |
The problem amounts to counting binary or $0/1$-matrices with restrictions on row/column sums.
In general, let the row sums be $r(n)=(r_1,dots,r_n)$ and column sums $c(n)=(c_1,dots,c_n)$. Obviously, $0leq r_i, c_jleq n$ for all $i, j$. Further, let $mathbf{x}=(x_1,dots,x_n)$ and $mathbf{y}=(y_1,dots,y_n)$ with the multi-exponent notation $mathbf{x}^{u}=x_1^{u_1}cdots x_n^{u_n}$. Then, there is this generating function
$$prod_{i,j=1}^n(1+x_iy_j)=sum_{r(n),c(n)} N(r(n),c(n))mathbf{x}^{r(n)}mathbf{y}^{c(n)} tag1$$
for the enumeration $N(r(n),c(n))$ of the number of binary matrices with row sums $r(n)$ and $c(n)$.
To get back to your question, extract the coefficient $N((k,dots,k),(k,dots,k))$ of
$$mathbf{x}^{(k,dots,k)}mathbf{y}^{(k,dots,k)}$$
from the above product in (1).
add a comment |
The problem amounts to counting binary or $0/1$-matrices with restrictions on row/column sums.
In general, let the row sums be $r(n)=(r_1,dots,r_n)$ and column sums $c(n)=(c_1,dots,c_n)$. Obviously, $0leq r_i, c_jleq n$ for all $i, j$. Further, let $mathbf{x}=(x_1,dots,x_n)$ and $mathbf{y}=(y_1,dots,y_n)$ with the multi-exponent notation $mathbf{x}^{u}=x_1^{u_1}cdots x_n^{u_n}$. Then, there is this generating function
$$prod_{i,j=1}^n(1+x_iy_j)=sum_{r(n),c(n)} N(r(n),c(n))mathbf{x}^{r(n)}mathbf{y}^{c(n)} tag1$$
for the enumeration $N(r(n),c(n))$ of the number of binary matrices with row sums $r(n)$ and $c(n)$.
To get back to your question, extract the coefficient $N((k,dots,k),(k,dots,k))$ of
$$mathbf{x}^{(k,dots,k)}mathbf{y}^{(k,dots,k)}$$
from the above product in (1).
The problem amounts to counting binary or $0/1$-matrices with restrictions on row/column sums.
In general, let the row sums be $r(n)=(r_1,dots,r_n)$ and column sums $c(n)=(c_1,dots,c_n)$. Obviously, $0leq r_i, c_jleq n$ for all $i, j$. Further, let $mathbf{x}=(x_1,dots,x_n)$ and $mathbf{y}=(y_1,dots,y_n)$ with the multi-exponent notation $mathbf{x}^{u}=x_1^{u_1}cdots x_n^{u_n}$. Then, there is this generating function
$$prod_{i,j=1}^n(1+x_iy_j)=sum_{r(n),c(n)} N(r(n),c(n))mathbf{x}^{r(n)}mathbf{y}^{c(n)} tag1$$
for the enumeration $N(r(n),c(n))$ of the number of binary matrices with row sums $r(n)$ and $c(n)$.
To get back to your question, extract the coefficient $N((k,dots,k),(k,dots,k))$ of
$$mathbf{x}^{(k,dots,k)}mathbf{y}^{(k,dots,k)}$$
from the above product in (1).
edited 11 hours ago
answered 11 hours ago
T. Amdeberhan
17.1k228126
17.1k228126
add a comment |
add a comment |
Thanks for contributing an answer to MathOverflow!
- 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%2fmathoverflow.net%2fquestions%2f319842%2fhow-many-ways-to-fill-in-a-square-grid-with-certain-restrictions%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
If you remove the only one checkmark per box requirement then you are looking at the Ehrhart polynomial of the Birkhoff polytope, and get into the Anand-Dumir-Gupta conjecture and related areas.
– Sam Hopkins
10 hours ago