Mixing
![Finding the probabilty $P(Y>S| Y>t)$ for an exponential probabilty distribution. [on hold]](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhZCTB4-bb-s-32SAm6ytjzFOU06cH9o8q-a_wq_UnH6lcd8hvws23CmBWHM6g256LzTX9yK1EiCCzTC1NSgtxlNk_J9hdr9bA3tD0Nqntbl521j4bLAm_uXPANuWLBhcCKTKzns2gaUodx/s72-c/1.jpg)
Counting tuples of subsets for which every subtuple of a given size has union equal to the entire set
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
I have a question which is a refined version of the question asked here. Let $A = 1,ldots,n$, $S_r = = r$ for $0 < r leq n$, $S_r^m = (a_1,ldots,a_m) : a_i in S_r $ for $m>0$, and consider, for $0 < d leq m$, the set $$ U^n_r,m,d = T in S_r^m : text the union of any $d$ components of $T$ equals $A$ subset S_r^m $$
Note that $U^n_r,m,1 subset U^n_r,m,2 subset cdots subset U^n_r,m,m subset S_r^m$.
I'm interested in computing $tau(n,r,m,d) triangleq |U^n_r,m,d|$.
My first guess is to use an inclusion-exclusion argument. I'll run through it to illustrate where it gets stuck (as far as I can tell). We try to calculate the cardinality of the complement of $U^n_r,m,d$, say $S_r^m = U^n_r,m,d sqcup V^n_r,m,d$. For $ell in A$ let $ K_ell = (a_1,ldots,a_m) in S_r^m : exists i_1,ldots,i_d text with
ell notin cup_j a_i_j $, wherefore $$ V^n_r,m,d = bigcup_ell in A K_ell $$ To proceed we are required to be able to express the cardinality of $bigcap_j in J K_j$, for $J subset A$. I don't know how to do this. It seems tricky to count: if $(a_1,ldots,a_m) in K_1 cap K_2$, we know that for some $i_1,ldots,i_d$, $1 notin cup_j a_i_j$, and for some $k_1,ldots,k_d$, $2 notin cup_j a_k_j$, but these tuples may not have any relation to one another in general.
When $m = d$, it simplifies because they must be the same $m$-tuple of indices. Namely we know that $$ bigcap_j in J K_j = (a_1,ldots,a_m) in S_r^m : exists ell in J , ell notin cup_i a_i $$ The cardinality of this is simply $binomn-jr^m$, the result of independently choosing a subset of size $r$ from $A - J$ a total of $m$ times. One concludes that
beginalign
tau(n,r,m,m) = | S_r^m| - |V^n_r,m,d| &= binomnr^m -sum_j = 1^n (-1)^j-1 binomnj binomn-jr^m \
&=sum_j = 0^n (-1)^j binomnj binomn-jr^m endalign Note that the upper bound for the sum in the answer to the other problem is (with respect to the variables here) $n - r$ and not $n$ as it is here. If mine is the one which is mistaken please leave a comment.
combinatorics inclusion-exclusion
asked Aug 2 at 15:35
Andrew
11113
add a comment |Â
up vote
2
down vote
favorite
I have a question which is a refined version of the question asked here. Let $A = 1,ldots,n$, $S_r = = r$ for $0 < r leq n$, $S_r^m = (a_1,ldots,a_m) : a_i in S_r $ for $m>0$, and consider, for $0 < d leq m$, the set $$ U^n_r,m,d = T in S_r^m : text the union of any $d$ components of $T$ equals $A$ subset S_r^m $$
Note that $U^n_r,m,1 subset U^n_r,m,2 subset cdots subset U^n_r,m,m subset S_r^m$.
I'm interested in computing $tau(n,r,m,d) triangleq |U^n_r,m,d|$.
My first guess is to use an inclusion-exclusion argument. I'll run through it to illustrate where it gets stuck (as far as I can tell). We try to calculate the cardinality of the complement of $U^n_r,m,d$, say $S_r^m = U^n_r,m,d sqcup V^n_r,m,d$. For $ell in A$ let $ K_ell = (a_1,ldots,a_m) in S_r^m : exists i_1,ldots,i_d text with
ell notin cup_j a_i_j $, wherefore $$ V^n_r,m,d = bigcup_ell in A K_ell $$ To proceed we are required to be able to express the cardinality of $bigcap_j in J K_j$, for $J subset A$. I don't know how to do this. It seems tricky to count: if $(a_1,ldots,a_m) in K_1 cap K_2$, we know that for some $i_1,ldots,i_d$, $1 notin cup_j a_i_j$, and for some $k_1,ldots,k_d$, $2 notin cup_j a_k_j$, but these tuples may not have any relation to one another in general.
When $m = d$, it simplifies because they must be the same $m$-tuple of indices. Namely we know that $$ bigcap_j in J K_j = (a_1,ldots,a_m) in S_r^m : exists ell in J , ell notin cup_i a_i $$ The cardinality of this is simply $binomn-jr^m$, the result of independently choosing a subset of size $r$ from $A - J$ a total of $m$ times. One concludes that
beginalign
tau(n,r,m,m) = | S_r^m| - |V^n_r,m,d| &= binomnr^m -sum_j = 1^n (-1)^j-1 binomnj binomn-jr^m \
&=sum_j = 0^n (-1)^j binomnj binomn-jr^m endalign Note that the upper bound for the sum in the answer to the other problem is (with respect to the variables here) $n - r$ and not $n$ as it is here. If mine is the one which is mistaken please leave a comment.
combinatorics inclusion-exclusion
asked Aug 2 at 15:35
Andrew
11113
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
I have a question which is a refined version of the question asked here. Let $A = 1,ldots,n$, $S_r = = r$ for $0 < r leq n$, $S_r^m = (a_1,ldots,a_m) : a_i in S_r $ for $m>0$, and consider, for $0 < d leq m$, the set $$ U^n_r,m,d = T in S_r^m : text the union of any $d$ components of $T$ equals $A$ subset S_r^m $$
Note that $U^n_r,m,1 subset U^n_r,m,2 subset cdots subset U^n_r,m,m subset S_r^m$.
I'm interested in computing $tau(n,r,m,d) triangleq |U^n_r,m,d|$.
My first guess is to use an inclusion-exclusion argument. I'll run through it to illustrate where it gets stuck (as far as I can tell). We try to calculate the cardinality of the complement of $U^n_r,m,d$, say $S_r^m = U^n_r,m,d sqcup V^n_r,m,d$. For $ell in A$ let $ K_ell = (a_1,ldots,a_m) in S_r^m : exists i_1,ldots,i_d text with
ell notin cup_j a_i_j $, wherefore $$ V^n_r,m,d = bigcup_ell in A K_ell $$ To proceed we are required to be able to express the cardinality of $bigcap_j in J K_j$, for $J subset A$. I don't know how to do this. It seems tricky to count: if $(a_1,ldots,a_m) in K_1 cap K_2$, we know that for some $i_1,ldots,i_d$, $1 notin cup_j a_i_j$, and for some $k_1,ldots,k_d$, $2 notin cup_j a_k_j$, but these tuples may not have any relation to one another in general.
When $m = d$, it simplifies because they must be the same $m$-tuple of indices. Namely we know that $$ bigcap_j in J K_j = (a_1,ldots,a_m) in S_r^m : exists ell in J , ell notin cup_i a_i $$ The cardinality of this is simply $binomn-jr^m$, the result of independently choosing a subset of size $r$ from $A - J$ a total of $m$ times. One concludes that
beginalign
tau(n,r,m,m) = | S_r^m| - |V^n_r,m,d| &= binomnr^m -sum_j = 1^n (-1)^j-1 binomnj binomn-jr^m \
&=sum_j = 0^n (-1)^j binomnj binomn-jr^m endalign Note that the upper bound for the sum in the answer to the other problem is (with respect to the variables here) $n - r$ and not $n$ as it is here. If mine is the one which is mistaken please leave a comment.
combinatorics inclusion-exclusion
asked Aug 2 at 15:35
Andrew
11113
I have a question which is a refined version of the question asked here. Let $A = 1,ldots,n$, $S_r = = r$ for $0 < r leq n$, $S_r^m = (a_1,ldots,a_m) : a_i in S_r $ for $m>0$, and consider, for $0 < d leq m$, the set $$ U^n_r,m,d = T in S_r^m : text the union of any $d$ components of $T$ equals $A$ subset S_r^m $$
Note that $U^n_r,m,1 subset U^n_r,m,2 subset cdots subset U^n_r,m,m subset S_r^m$.
I'm interested in computing $tau(n,r,m,d) triangleq |U^n_r,m,d|$.
My first guess is to use an inclusion-exclusion argument. I'll run through it to illustrate where it gets stuck (as far as I can tell). We try to calculate the cardinality of the complement of $U^n_r,m,d$, say $S_r^m = U^n_r,m,d sqcup V^n_r,m,d$. For $ell in A$ let $ K_ell = (a_1,ldots,a_m) in S_r^m : exists i_1,ldots,i_d text with
ell notin cup_j a_i_j $, wherefore $$ V^n_r,m,d = bigcup_ell in A K_ell $$ To proceed we are required to be able to express the cardinality of $bigcap_j in J K_j$, for $J subset A$. I don't know how to do this. It seems tricky to count: if $(a_1,ldots,a_m) in K_1 cap K_2$, we know that for some $i_1,ldots,i_d$, $1 notin cup_j a_i_j$, and for some $k_1,ldots,k_d$, $2 notin cup_j a_k_j$, but these tuples may not have any relation to one another in general.
When $m = d$, it simplifies because they must be the same $m$-tuple of indices. Namely we know that $$ bigcap_j in J K_j = (a_1,ldots,a_m) in S_r^m : exists ell in J , ell notin cup_i a_i $$ The cardinality of this is simply $binomn-jr^m$, the result of independently choosing a subset of size $r$ from $A - J$ a total of $m$ times. One concludes that
beginalign
tau(n,r,m,m) = | S_r^m| - |V^n_r,m,d| &= binomnr^m -sum_j = 1^n (-1)^j-1 binomnj binomn-jr^m \
&=sum_j = 0^n (-1)^j binomnj binomn-jr^m endalign Note that the upper bound for the sum in the answer to the other problem is (with respect to the variables here) $n - r$ and not $n$ as it is here. If mine is the one which is mistaken please leave a comment.
combinatorics inclusion-exclusion
asked Aug 2 at 15:35
Andrew
11113
edited Aug 2 at 15:41
asked Aug 2 at 15:35
Andrew
11113
asked Aug 2 at 15:35
Andrew
11113
asked Aug 2 at 15:35
Andrew
11113
11113
add a comment |Â
add a comment |Â
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f2870188%2fcounting-tuples-of-subsets-for-which-every-subtuple-of-a-given-size-has-union-eq%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