Mixing
Number of ways of build a binary matrix with constraints
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
We have an $Ntimes N$ matrix U whose elements can only be $0$ or $1$. I would like to count the multiplicity of the following matrix:
$E$ non-zero entries
$sum_i U_i j = a_j$ i.e. fixed sum along each row
$sum_j U_i j = b_j$ i.e. fixed sum along each column
At first I thought to map the problem as a "distinguishable balls into distinguishable boxes" problem but with no results. Now I am thinking that maybe a solution can be reached using the Stirling numbers of the first kind since the problem can be traced to analysing the permutations of the sequence $(u^1_1 u^1_2 ... u^1_a_1)(u^2_1 u^2_2 ... u^2_a_2)...(u^N_1 u^N_2 ... u^N_a_N)$ by using the interpretation that $u^1_i=5$ it means that $U_1 5 = 1$.
Any idea?
combinatorics permutations combinations permutation-cycles
edited Jul 26 at 14:34
joriki
164k10180328
asked Jul 26 at 14:32
Ninja Warrior
385
add a comment |Â
up vote
2
down vote
favorite
We have an $Ntimes N$ matrix U whose elements can only be $0$ or $1$. I would like to count the multiplicity of the following matrix:
$E$ non-zero entries
$sum_i U_i j = a_j$ i.e. fixed sum along each row
$sum_j U_i j = b_j$ i.e. fixed sum along each column
At first I thought to map the problem as a "distinguishable balls into distinguishable boxes" problem but with no results. Now I am thinking that maybe a solution can be reached using the Stirling numbers of the first kind since the problem can be traced to analysing the permutations of the sequence $(u^1_1 u^1_2 ... u^1_a_1)(u^2_1 u^2_2 ... u^2_a_2)...(u^N_1 u^N_2 ... u^N_a_N)$ by using the interpretation that $u^1_i=5$ it means that $U_1 5 = 1$.
Any idea?
combinatorics permutations combinations permutation-cycles
edited Jul 26 at 14:34
joriki
164k10180328
asked Jul 26 at 14:32
Ninja Warrior
385
1
Do the $a_j$ and $b_j$ vary?
– saulspatz
Jul 26 at 15:36
no we can consider them fixed (but different for each row/column)
– Ninja Warrior
Jul 27 at 10:34
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
We have an $Ntimes N$ matrix U whose elements can only be $0$ or $1$. I would like to count the multiplicity of the following matrix:
$E$ non-zero entries
$sum_i U_i j = a_j$ i.e. fixed sum along each row
$sum_j U_i j = b_j$ i.e. fixed sum along each column
At first I thought to map the problem as a "distinguishable balls into distinguishable boxes" problem but with no results. Now I am thinking that maybe a solution can be reached using the Stirling numbers of the first kind since the problem can be traced to analysing the permutations of the sequence $(u^1_1 u^1_2 ... u^1_a_1)(u^2_1 u^2_2 ... u^2_a_2)...(u^N_1 u^N_2 ... u^N_a_N)$ by using the interpretation that $u^1_i=5$ it means that $U_1 5 = 1$.
Any idea?
combinatorics permutations combinations permutation-cycles
edited Jul 26 at 14:34
joriki
164k10180328
asked Jul 26 at 14:32
Ninja Warrior
385
We have an $Ntimes N$ matrix U whose elements can only be $0$ or $1$. I would like to count the multiplicity of the following matrix:
$E$ non-zero entries
$sum_i U_i j = a_j$ i.e. fixed sum along each row
$sum_j U_i j = b_j$ i.e. fixed sum along each column
At first I thought to map the problem as a "distinguishable balls into distinguishable boxes" problem but with no results. Now I am thinking that maybe a solution can be reached using the Stirling numbers of the first kind since the problem can be traced to analysing the permutations of the sequence $(u^1_1 u^1_2 ... u^1_a_1)(u^2_1 u^2_2 ... u^2_a_2)...(u^N_1 u^N_2 ... u^N_a_N)$ by using the interpretation that $u^1_i=5$ it means that $U_1 5 = 1$.
Any idea?
combinatorics permutations combinations permutation-cycles
edited Jul 26 at 14:34
joriki
164k10180328
asked Jul 26 at 14:32
Ninja Warrior
385
edited Jul 26 at 14:34
joriki
164k10180328
edited Jul 26 at 14:34
joriki
164k10180328
edited Jul 26 at 14:34
joriki
164k10180328
164k10180328
asked Jul 26 at 14:32
Ninja Warrior
385
asked Jul 26 at 14:32
Ninja Warrior
385
asked Jul 26 at 14:32
Ninja Warrior
385
385
1
Do the $a_j$ and $b_j$ vary?
– saulspatz
Jul 26 at 15:36
no we can consider them fixed (but different for each row/column)
– Ninja Warrior
Jul 27 at 10:34
add a comment |Â
1
Do the $a_j$ and $b_j$ vary?
– saulspatz
Jul 26 at 15:36
no we can consider them fixed (but different for each row/column)
– Ninja Warrior
Jul 27 at 10:34
1
1
Do the $a_j$ and $b_j$ vary?
– saulspatz
Jul 26 at 15:36
Do the $a_j$ and $b_j$ vary?
– saulspatz
Jul 26 at 15:36
no we can consider them fixed (but different for each row/column)
– Ninja Warrior
Jul 27 at 10:34
no we can consider them fixed (but different for each row/column)
– Ninja Warrior
Jul 27 at 10:34
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
0
down vote
From a008300 in oeis, it seems already difficult when $a_j$ and $b_i$ are all the same number.
If I assume the rowsums are correct independently of the column sums,
I get a ballpark figure
$$fracf(a_1,...,a_N)f(b_1,...,b_N)N^2choose E$$
This won't be correct, for example if $vec a=(3,0,0)$ and $vec b=(2,1,0)$ there are no common solutions. And when $vec a=(2,2,2,2)=vec b$, the estimate is 130.5 instead of the true answer of 90.
EDIT:
$$f(a_1,...a_N)=Nchoose a_1Nchoose a_2...Nchoose a_N$$
When all $a_j$ and $b_i$ are 2, the 1s in the matrix form loops, as you go from any 1 to the other 1 in the same row, then the other 1 in the same column, then the other 1 in the same row, and so on.
The number of ways to form a loop that includes the 1s in the first row, and involves $k$ rows and columns, is $frac12N(N!)^2/((N-k)!)^2$.
If $g(N,2)$ is the number of ways for an $Ntimes N$ matrix when all $a_j=2$ and all $b_i=2$, then
$$g(N,2)=frac12Nsum_k=2^Nleft(fracN!(N-k)!right)^2g(N-k,2)$$
with initial conditions $g(0,2)=1,g(1,2)=0$
Can you better define $f$ please? And how did you find the true answer of the second case ?
– Ninja Warrior
Jul 27 at 10:37
In the second case, what value of $N$ are you using?
– saulspatz
Jul 27 at 12:16
All $N$. If $N=2$, then $g(2,2)=(1/4)(2!)^2=1$; if $N=3$ then $g(3,2)=(1/6)(3!)^2=6$; if $N=4$ then $g(4,2)=(1/8)(4!/2!)^2+(1/8)(4!/0!)^2=18+72=90$
– Empy2
Jul 27 at 12:38
Sorry, my formula assumes the first row is included in the loop
– Empy2
Jul 27 at 12:49
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
From a008300 in oeis, it seems already difficult when $a_j$ and $b_i$ are all the same number.
If I assume the rowsums are correct independently of the column sums,
I get a ballpark figure
$$fracf(a_1,...,a_N)f(b_1,...,b_N)N^2choose E$$
This won't be correct, for example if $vec a=(3,0,0)$ and $vec b=(2,1,0)$ there are no common solutions. And when $vec a=(2,2,2,2)=vec b$, the estimate is 130.5 instead of the true answer of 90.
EDIT:
$$f(a_1,...a_N)=Nchoose a_1Nchoose a_2...Nchoose a_N$$
When all $a_j$ and $b_i$ are 2, the 1s in the matrix form loops, as you go from any 1 to the other 1 in the same row, then the other 1 in the same column, then the other 1 in the same row, and so on.
The number of ways to form a loop that includes the 1s in the first row, and involves $k$ rows and columns, is $frac12N(N!)^2/((N-k)!)^2$.
If $g(N,2)$ is the number of ways for an $Ntimes N$ matrix when all $a_j=2$ and all $b_i=2$, then
$$g(N,2)=frac12Nsum_k=2^Nleft(fracN!(N-k)!right)^2g(N-k,2)$$
with initial conditions $g(0,2)=1,g(1,2)=0$
Can you better define $f$ please? And how did you find the true answer of the second case ?
– Ninja Warrior
Jul 27 at 10:37
In the second case, what value of $N$ are you using?
– saulspatz
Jul 27 at 12:16
All $N$. If $N=2$, then $g(2,2)=(1/4)(2!)^2=1$; if $N=3$ then $g(3,2)=(1/6)(3!)^2=6$; if $N=4$ then $g(4,2)=(1/8)(4!/2!)^2+(1/8)(4!/0!)^2=18+72=90$
– Empy2
Jul 27 at 12:38
Sorry, my formula assumes the first row is included in the loop
– Empy2
Jul 27 at 12:49
add a comment |Â
up vote
0
down vote
From a008300 in oeis, it seems already difficult when $a_j$ and $b_i$ are all the same number.
If I assume the rowsums are correct independently of the column sums,
I get a ballpark figure
$$fracf(a_1,...,a_N)f(b_1,...,b_N)N^2choose E$$
This won't be correct, for example if $vec a=(3,0,0)$ and $vec b=(2,1,0)$ there are no common solutions. And when $vec a=(2,2,2,2)=vec b$, the estimate is 130.5 instead of the true answer of 90.
EDIT:
$$f(a_1,...a_N)=Nchoose a_1Nchoose a_2...Nchoose a_N$$
When all $a_j$ and $b_i$ are 2, the 1s in the matrix form loops, as you go from any 1 to the other 1 in the same row, then the other 1 in the same column, then the other 1 in the same row, and so on.
The number of ways to form a loop that includes the 1s in the first row, and involves $k$ rows and columns, is $frac12N(N!)^2/((N-k)!)^2$.
If $g(N,2)$ is the number of ways for an $Ntimes N$ matrix when all $a_j=2$ and all $b_i=2$, then
$$g(N,2)=frac12Nsum_k=2^Nleft(fracN!(N-k)!right)^2g(N-k,2)$$
with initial conditions $g(0,2)=1,g(1,2)=0$
Can you better define $f$ please? And how did you find the true answer of the second case ?
– Ninja Warrior
Jul 27 at 10:37
In the second case, what value of $N$ are you using?
– saulspatz
Jul 27 at 12:16
All $N$. If $N=2$, then $g(2,2)=(1/4)(2!)^2=1$; if $N=3$ then $g(3,2)=(1/6)(3!)^2=6$; if $N=4$ then $g(4,2)=(1/8)(4!/2!)^2+(1/8)(4!/0!)^2=18+72=90$
– Empy2
Jul 27 at 12:38
Sorry, my formula assumes the first row is included in the loop
– Empy2
Jul 27 at 12:49
add a comment |Â
up vote
0
down vote
up vote
0
down vote
From a008300 in oeis, it seems already difficult when $a_j$ and $b_i$ are all the same number.
If I assume the rowsums are correct independently of the column sums,
I get a ballpark figure
$$fracf(a_1,...,a_N)f(b_1,...,b_N)N^2choose E$$
This won't be correct, for example if $vec a=(3,0,0)$ and $vec b=(2,1,0)$ there are no common solutions. And when $vec a=(2,2,2,2)=vec b$, the estimate is 130.5 instead of the true answer of 90.
EDIT:
$$f(a_1,...a_N)=Nchoose a_1Nchoose a_2...Nchoose a_N$$
When all $a_j$ and $b_i$ are 2, the 1s in the matrix form loops, as you go from any 1 to the other 1 in the same row, then the other 1 in the same column, then the other 1 in the same row, and so on.
The number of ways to form a loop that includes the 1s in the first row, and involves $k$ rows and columns, is $frac12N(N!)^2/((N-k)!)^2$.
If $g(N,2)$ is the number of ways for an $Ntimes N$ matrix when all $a_j=2$ and all $b_i=2$, then
$$g(N,2)=frac12Nsum_k=2^Nleft(fracN!(N-k)!right)^2g(N-k,2)$$
with initial conditions $g(0,2)=1,g(1,2)=0$
From a008300 in oeis, it seems already difficult when $a_j$ and $b_i$ are all the same number.
If I assume the rowsums are correct independently of the column sums,
I get a ballpark figure
$$fracf(a_1,...,a_N)f(b_1,...,b_N)N^2choose E$$
This won't be correct, for example if $vec a=(3,0,0)$ and $vec b=(2,1,0)$ there are no common solutions. And when $vec a=(2,2,2,2)=vec b$, the estimate is 130.5 instead of the true answer of 90.
EDIT:
$$f(a_1,...a_N)=Nchoose a_1Nchoose a_2...Nchoose a_N$$
When all $a_j$ and $b_i$ are 2, the 1s in the matrix form loops, as you go from any 1 to the other 1 in the same row, then the other 1 in the same column, then the other 1 in the same row, and so on.
The number of ways to form a loop that includes the 1s in the first row, and involves $k$ rows and columns, is $frac12N(N!)^2/((N-k)!)^2$.
If $g(N,2)$ is the number of ways for an $Ntimes N$ matrix when all $a_j=2$ and all $b_i=2$, then
$$g(N,2)=frac12Nsum_k=2^Nleft(fracN!(N-k)!right)^2g(N-k,2)$$
with initial conditions $g(0,2)=1,g(1,2)=0$
edited Jul 27 at 12:50
community wiki
6 revs
Empy2
Can you better define $f$ please? And how did you find the true answer of the second case ?
– Ninja Warrior
Jul 27 at 10:37
In the second case, what value of $N$ are you using?
– saulspatz
Jul 27 at 12:16
All $N$. If $N=2$, then $g(2,2)=(1/4)(2!)^2=1$; if $N=3$ then $g(3,2)=(1/6)(3!)^2=6$; if $N=4$ then $g(4,2)=(1/8)(4!/2!)^2+(1/8)(4!/0!)^2=18+72=90$
– Empy2
Jul 27 at 12:38
Sorry, my formula assumes the first row is included in the loop
– Empy2
Jul 27 at 12:49
add a comment |Â
Can you better define $f$ please? And how did you find the true answer of the second case ?
– Ninja Warrior
Jul 27 at 10:37
In the second case, what value of $N$ are you using?
– saulspatz
Jul 27 at 12:16
All $N$. If $N=2$, then $g(2,2)=(1/4)(2!)^2=1$; if $N=3$ then $g(3,2)=(1/6)(3!)^2=6$; if $N=4$ then $g(4,2)=(1/8)(4!/2!)^2+(1/8)(4!/0!)^2=18+72=90$
– Empy2
Jul 27 at 12:38
Sorry, my formula assumes the first row is included in the loop
– Empy2
Jul 27 at 12:49
Can you better define $f$ please? And how did you find the true answer of the second case ?
– Ninja Warrior
Jul 27 at 10:37
Can you better define $f$ please? And how did you find the true answer of the second case ?
– Ninja Warrior
Jul 27 at 10:37
In the second case, what value of $N$ are you using?
– saulspatz
Jul 27 at 12:16
In the second case, what value of $N$ are you using?
– saulspatz
Jul 27 at 12:16
All $N$. If $N=2$, then $g(2,2)=(1/4)(2!)^2=1$; if $N=3$ then $g(3,2)=(1/6)(3!)^2=6$; if $N=4$ then $g(4,2)=(1/8)(4!/2!)^2+(1/8)(4!/0!)^2=18+72=90$
– Empy2
Jul 27 at 12:38
All $N$. If $N=2$, then $g(2,2)=(1/4)(2!)^2=1$; if $N=3$ then $g(3,2)=(1/6)(3!)^2=6$; if $N=4$ then $g(4,2)=(1/8)(4!/2!)^2+(1/8)(4!/0!)^2=18+72=90$
– Empy2
Jul 27 at 12:38
Sorry, my formula assumes the first row is included in the loop
– Empy2
Jul 27 at 12:49
Sorry, my formula assumes the first row is included in the loop
– Empy2
Jul 27 at 12:49
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2863460%2fnumber-of-ways-of-build-a-binary-matrix-with-constraints%23new-answer', 'question_page');
);
Post as a guest
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
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
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
1
Do the $a_j$ and $b_j$ vary?
– saulspatz
Jul 26 at 15:36
no we can consider them fixed (but different for each row/column)
– Ninja Warrior
Jul 27 at 10:34