Mixing
Choosing subsets of 3 objects out of n, with specific conditions
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
Suppose there are $nge 3$ distinct objects from which one or more subsets of three are chosen.
I'd like help to find the maximum number of such subsets that can be chosen so that no two of those subsets contain (at least) two objects in common. In other words two chosen subsets can have at most one object in their intersection.
For example once we choose $a,b,c$ from $a,b,c,d$, then the choice $a,b,d$ is no longer available because it matches a pair of the earlier chosen subset. Indeed it follows that for $n=4$ the maximum number of subsets we can choose is one.
Similarly for $n=6$ we can choose a maximum of four subsets.
Is it possible to attack this problem using recurrence relations? Or do we have to count the number of ways directly?
What about the general case of subsets of size $klt n$ instead of $3$?
combinatorics
edited Jul 23 at 22:35
hardmath
28.1k94592
asked Jul 22 at 13:54
Fermat
4,2841926
 |Â
show 1 more comment
up vote
0
down vote
favorite
Suppose there are $nge 3$ distinct objects from which one or more subsets of three are chosen.
I'd like help to find the maximum number of such subsets that can be chosen so that no two of those subsets contain (at least) two objects in common. In other words two chosen subsets can have at most one object in their intersection.
For example once we choose $a,b,c$ from $a,b,c,d$, then the choice $a,b,d$ is no longer available because it matches a pair of the earlier chosen subset. Indeed it follows that for $n=4$ the maximum number of subsets we can choose is one.
Similarly for $n=6$ we can choose a maximum of four subsets.
Is it possible to attack this problem using recurrence relations? Or do we have to count the number of ways directly?
What about the general case of subsets of size $klt n$ instead of $3$?
combinatorics
edited Jul 23 at 22:35
hardmath
28.1k94592
asked Jul 22 at 13:54
Fermat
4,2841926
I think it would clarify matters to solve the case of $n=4,5$ completely. For $n=4$, say, surely that isn't difficult...there are only $4$ ways to choose three objects. If your first choice is $a,b,c$ then any other choice would have to have two in common with this one, yes? So in this case the answer would be $1$, no?
– lulu
Jul 22 at 14:10
See the topic balanced incomplete block designs for the special case where each pair appears exactly once in the collection of (equal sized) subsets. In considering how many subsets can be achieved where pairs appear at most once, the block designs are usually called packings.
– hardmath
Jul 22 at 14:14
@hardmath Yes, you are right and I correct it.
– Fermat
Jul 22 at 14:14
@lulu Yes, for n=4, the answer is 1.
– Fermat
Jul 22 at 14:16
1
What is the desired answer for $n=6$? If my first two choices are $a,b,c$ and $d,e,f$, the answer would seem to be $2$. But if my first two choices are $a,b,c$ and $c,d,e$, I could then go on to choose $a,d,f$ and $b,e,f$ and get an answer of $4$. In other words, it's still not clear exactly what it is you want to count.
– Barry Cipra
Jul 22 at 14:39
 |Â
show 1 more comment
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Suppose there are $nge 3$ distinct objects from which one or more subsets of three are chosen.
I'd like help to find the maximum number of such subsets that can be chosen so that no two of those subsets contain (at least) two objects in common. In other words two chosen subsets can have at most one object in their intersection.
For example once we choose $a,b,c$ from $a,b,c,d$, then the choice $a,b,d$ is no longer available because it matches a pair of the earlier chosen subset. Indeed it follows that for $n=4$ the maximum number of subsets we can choose is one.
Similarly for $n=6$ we can choose a maximum of four subsets.
Is it possible to attack this problem using recurrence relations? Or do we have to count the number of ways directly?
What about the general case of subsets of size $klt n$ instead of $3$?
combinatorics
edited Jul 23 at 22:35
hardmath
28.1k94592
asked Jul 22 at 13:54
Fermat
4,2841926
Suppose there are $nge 3$ distinct objects from which one or more subsets of three are chosen.
I'd like help to find the maximum number of such subsets that can be chosen so that no two of those subsets contain (at least) two objects in common. In other words two chosen subsets can have at most one object in their intersection.
For example once we choose $a,b,c$ from $a,b,c,d$, then the choice $a,b,d$ is no longer available because it matches a pair of the earlier chosen subset. Indeed it follows that for $n=4$ the maximum number of subsets we can choose is one.
Similarly for $n=6$ we can choose a maximum of four subsets.
Is it possible to attack this problem using recurrence relations? Or do we have to count the number of ways directly?
What about the general case of subsets of size $klt n$ instead of $3$?
combinatorics
edited Jul 23 at 22:35
hardmath
28.1k94592
asked Jul 22 at 13:54
Fermat
4,2841926
edited Jul 23 at 22:35
hardmath
28.1k94592
edited Jul 23 at 22:35
hardmath
28.1k94592
edited Jul 23 at 22:35
hardmath
28.1k94592
28.1k94592
asked Jul 22 at 13:54
Fermat
4,2841926
asked Jul 22 at 13:54
Fermat
4,2841926
asked Jul 22 at 13:54
Fermat
4,2841926
4,2841926
I think it would clarify matters to solve the case of $n=4,5$ completely. For $n=4$, say, surely that isn't difficult...there are only $4$ ways to choose three objects. If your first choice is $a,b,c$ then any other choice would have to have two in common with this one, yes? So in this case the answer would be $1$, no?
– lulu
Jul 22 at 14:10
See the topic balanced incomplete block designs for the special case where each pair appears exactly once in the collection of (equal sized) subsets. In considering how many subsets can be achieved where pairs appear at most once, the block designs are usually called packings.
– hardmath
Jul 22 at 14:14
@hardmath Yes, you are right and I correct it.
– Fermat
Jul 22 at 14:14
@lulu Yes, for n=4, the answer is 1.
– Fermat
Jul 22 at 14:16
1
What is the desired answer for $n=6$? If my first two choices are $a,b,c$ and $d,e,f$, the answer would seem to be $2$. But if my first two choices are $a,b,c$ and $c,d,e$, I could then go on to choose $a,d,f$ and $b,e,f$ and get an answer of $4$. In other words, it's still not clear exactly what it is you want to count.
– Barry Cipra
Jul 22 at 14:39
 |Â
show 1 more comment
I think it would clarify matters to solve the case of $n=4,5$ completely. For $n=4$, say, surely that isn't difficult...there are only $4$ ways to choose three objects. If your first choice is $a,b,c$ then any other choice would have to have two in common with this one, yes? So in this case the answer would be $1$, no?
– lulu
Jul 22 at 14:10
See the topic balanced incomplete block designs for the special case where each pair appears exactly once in the collection of (equal sized) subsets. In considering how many subsets can be achieved where pairs appear at most once, the block designs are usually called packings.
– hardmath
Jul 22 at 14:14
@hardmath Yes, you are right and I correct it.
– Fermat
Jul 22 at 14:14
@lulu Yes, for n=4, the answer is 1.
– Fermat
Jul 22 at 14:16
1
What is the desired answer for $n=6$? If my first two choices are $a,b,c$ and $d,e,f$, the answer would seem to be $2$. But if my first two choices are $a,b,c$ and $c,d,e$, I could then go on to choose $a,d,f$ and $b,e,f$ and get an answer of $4$. In other words, it's still not clear exactly what it is you want to count.
– Barry Cipra
Jul 22 at 14:39
I think it would clarify matters to solve the case of $n=4,5$ completely. For $n=4$, say, surely that isn't difficult...there are only $4$ ways to choose three objects. If your first choice is $a,b,c$ then any other choice would have to have two in common with this one, yes? So in this case the answer would be $1$, no?
– lulu
Jul 22 at 14:10
I think it would clarify matters to solve the case of $n=4,5$ completely. For $n=4$, say, surely that isn't difficult...there are only $4$ ways to choose three objects. If your first choice is $a,b,c$ then any other choice would have to have two in common with this one, yes? So in this case the answer would be $1$, no?
– lulu
Jul 22 at 14:10
See the topic balanced incomplete block designs for the special case where each pair appears exactly once in the collection of (equal sized) subsets. In considering how many subsets can be achieved where pairs appear at most once, the block designs are usually called packings.
– hardmath
Jul 22 at 14:14
See the topic balanced incomplete block designs for the special case where each pair appears exactly once in the collection of (equal sized) subsets. In considering how many subsets can be achieved where pairs appear at most once, the block designs are usually called packings.
– hardmath
Jul 22 at 14:14
@hardmath Yes, you are right and I correct it.
– Fermat
Jul 22 at 14:14
@hardmath Yes, you are right and I correct it.
– Fermat
Jul 22 at 14:14
@lulu Yes, for n=4, the answer is 1.
– Fermat
Jul 22 at 14:16
@lulu Yes, for n=4, the answer is 1.
– Fermat
Jul 22 at 14:16
1
1
What is the desired answer for $n=6$? If my first two choices are $a,b,c$ and $d,e,f$, the answer would seem to be $2$. But if my first two choices are $a,b,c$ and $c,d,e$, I could then go on to choose $a,d,f$ and $b,e,f$ and get an answer of $4$. In other words, it's still not clear exactly what it is you want to count.
– Barry Cipra
Jul 22 at 14:39
What is the desired answer for $n=6$? If my first two choices are $a,b,c$ and $d,e,f$, the answer would seem to be $2$. But if my first two choices are $a,b,c$ and $c,d,e$, I could then go on to choose $a,d,f$ and $b,e,f$ and get an answer of $4$. In other words, it's still not clear exactly what it is you want to count.
– Barry Cipra
Jul 22 at 14:39
 |Â
show 1 more comment
1 Answer
1
active
oldest
votes
up vote
2
down vote
accepted
This is one combinatorial problem among many similar topics, and we begin by introducing some notation that is commonly used.
By historical connection to experimental designs, the number of distinct objects is conventionally $v$ (for varieties) and the size of the subsets making up the "blocks" is $k$. The problem here is to achieve the maximum number of blocks, subject to the restrict that no pair of objects appears in more than one block ($k$-subset). This is known as the "packing problem", and the maximum number of blocks $b$ is known as the packing number $mathscr P(v,k)$.
[The dual problem involves choosing a collection of $k$-subsets in which each pair appears at least once. This is the covering problem. The minimum number of such blocks $b$ is called the covering number, and when there is a design with each pair appearing exactly once, the packing number and covering number agree.]
No simple formula or recurrence relation is known for the packing numbers $mathscr P(v,k)$, although there is a well-known upper bound (the Schönheim bound) based on dividing the total number of pairs $binomv2$ by the number pairs in one $k$-subset $binomk2$. There is also a substantial literature on when the upper bound can be attained (Balanced Incomplete Block Designs).
A relatively recent reference (2013) for the larger cluster of problems is "Covering and packing for pairs" by Chee, Colbourn, Lee, and Wilson:
In this paper it is shown that for all sufficiently large values of $v$, a packing and a covering on $v$ elements exist whose numbers of blocks differ from the basic bounds by no more than an additive constant depending only on $k$.
Block size $mathbfk=3$
The specific case of choosing subsets of size $3$ has been thoroughly examined, starting with those instances in which the upper bound can be attained:
$$ b = fracbinomv2binom32 = fracv(v-1)6 $$
for which the name Steiner triple systems is usual.
Here the number of pairs $v(v-1)/2$ must be divisible by $3$, which gives the necessary condition that $vequiv 1,3 bmod 6$. It was shown by R.C. Bose (1939) and by Th. Skolem (1958) that this necessary condition is also sufficient.
The details for the residues $vequiv 0,2,4,5 bmod 6$ are worked out in Chapter 4 of Design Theory 2nd Ed. by C. Lindner and C. Rodger (2008):
$$ beginarray hline
v bmod 6 & mathscrP(v,3) \ hline
0text or 2 & fracv(v-2)6 \
1text or 3 & fracv(v-1)6 \
4 & fracv^2-2v-26 \
5 & fracv^2-v-86 \
hline endarray $$
answered Jul 22 at 14:53
hardmath
28.1k94592
1
Thank you @hardmath for your detailed explanation and also for giving the references. I think there is a typo in the numerator of $b=...$ since it should be $vchoose 2$
– Fermat
Jul 23 at 5:55
1
@Fermat: Thanks for noticing that typo!
– hardmath
Jul 23 at 11:38
You're welcome.
– Fermat
Jul 23 at 20:43
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
This is one combinatorial problem among many similar topics, and we begin by introducing some notation that is commonly used.
By historical connection to experimental designs, the number of distinct objects is conventionally $v$ (for varieties) and the size of the subsets making up the "blocks" is $k$. The problem here is to achieve the maximum number of blocks, subject to the restrict that no pair of objects appears in more than one block ($k$-subset). This is known as the "packing problem", and the maximum number of blocks $b$ is known as the packing number $mathscr P(v,k)$.
[The dual problem involves choosing a collection of $k$-subsets in which each pair appears at least once. This is the covering problem. The minimum number of such blocks $b$ is called the covering number, and when there is a design with each pair appearing exactly once, the packing number and covering number agree.]
No simple formula or recurrence relation is known for the packing numbers $mathscr P(v,k)$, although there is a well-known upper bound (the Schönheim bound) based on dividing the total number of pairs $binomv2$ by the number pairs in one $k$-subset $binomk2$. There is also a substantial literature on when the upper bound can be attained (Balanced Incomplete Block Designs).
A relatively recent reference (2013) for the larger cluster of problems is "Covering and packing for pairs" by Chee, Colbourn, Lee, and Wilson:
In this paper it is shown that for all sufficiently large values of $v$, a packing and a covering on $v$ elements exist whose numbers of blocks differ from the basic bounds by no more than an additive constant depending only on $k$.
Block size $mathbfk=3$
The specific case of choosing subsets of size $3$ has been thoroughly examined, starting with those instances in which the upper bound can be attained:
$$ b = fracbinomv2binom32 = fracv(v-1)6 $$
for which the name Steiner triple systems is usual.
Here the number of pairs $v(v-1)/2$ must be divisible by $3$, which gives the necessary condition that $vequiv 1,3 bmod 6$. It was shown by R.C. Bose (1939) and by Th. Skolem (1958) that this necessary condition is also sufficient.
The details for the residues $vequiv 0,2,4,5 bmod 6$ are worked out in Chapter 4 of Design Theory 2nd Ed. by C. Lindner and C. Rodger (2008):
$$ beginarray hline
v bmod 6 & mathscrP(v,3) \ hline
0text or 2 & fracv(v-2)6 \
1text or 3 & fracv(v-1)6 \
4 & fracv^2-2v-26 \
5 & fracv^2-v-86 \
hline endarray $$
answered Jul 22 at 14:53
hardmath
28.1k94592
1
Thank you @hardmath for your detailed explanation and also for giving the references. I think there is a typo in the numerator of $b=...$ since it should be $vchoose 2$
– Fermat
Jul 23 at 5:55
1
@Fermat: Thanks for noticing that typo!
– hardmath
Jul 23 at 11:38
You're welcome.
– Fermat
Jul 23 at 20:43
add a comment |Â
up vote
2
down vote
accepted
This is one combinatorial problem among many similar topics, and we begin by introducing some notation that is commonly used.
By historical connection to experimental designs, the number of distinct objects is conventionally $v$ (for varieties) and the size of the subsets making up the "blocks" is $k$. The problem here is to achieve the maximum number of blocks, subject to the restrict that no pair of objects appears in more than one block ($k$-subset). This is known as the "packing problem", and the maximum number of blocks $b$ is known as the packing number $mathscr P(v,k)$.
[The dual problem involves choosing a collection of $k$-subsets in which each pair appears at least once. This is the covering problem. The minimum number of such blocks $b$ is called the covering number, and when there is a design with each pair appearing exactly once, the packing number and covering number agree.]
No simple formula or recurrence relation is known for the packing numbers $mathscr P(v,k)$, although there is a well-known upper bound (the Schönheim bound) based on dividing the total number of pairs $binomv2$ by the number pairs in one $k$-subset $binomk2$. There is also a substantial literature on when the upper bound can be attained (Balanced Incomplete Block Designs).
A relatively recent reference (2013) for the larger cluster of problems is "Covering and packing for pairs" by Chee, Colbourn, Lee, and Wilson:
In this paper it is shown that for all sufficiently large values of $v$, a packing and a covering on $v$ elements exist whose numbers of blocks differ from the basic bounds by no more than an additive constant depending only on $k$.
Block size $mathbfk=3$
The specific case of choosing subsets of size $3$ has been thoroughly examined, starting with those instances in which the upper bound can be attained:
$$ b = fracbinomv2binom32 = fracv(v-1)6 $$
for which the name Steiner triple systems is usual.
Here the number of pairs $v(v-1)/2$ must be divisible by $3$, which gives the necessary condition that $vequiv 1,3 bmod 6$. It was shown by R.C. Bose (1939) and by Th. Skolem (1958) that this necessary condition is also sufficient.
The details for the residues $vequiv 0,2,4,5 bmod 6$ are worked out in Chapter 4 of Design Theory 2nd Ed. by C. Lindner and C. Rodger (2008):
$$ beginarray hline
v bmod 6 & mathscrP(v,3) \ hline
0text or 2 & fracv(v-2)6 \
1text or 3 & fracv(v-1)6 \
4 & fracv^2-2v-26 \
5 & fracv^2-v-86 \
hline endarray $$
answered Jul 22 at 14:53
hardmath
28.1k94592
1
Thank you @hardmath for your detailed explanation and also for giving the references. I think there is a typo in the numerator of $b=...$ since it should be $vchoose 2$
– Fermat
Jul 23 at 5:55
1
@Fermat: Thanks for noticing that typo!
– hardmath
Jul 23 at 11:38
You're welcome.
– Fermat
Jul 23 at 20:43
add a comment |Â
up vote
2
down vote
accepted
up vote
2
down vote
accepted
This is one combinatorial problem among many similar topics, and we begin by introducing some notation that is commonly used.
By historical connection to experimental designs, the number of distinct objects is conventionally $v$ (for varieties) and the size of the subsets making up the "blocks" is $k$. The problem here is to achieve the maximum number of blocks, subject to the restrict that no pair of objects appears in more than one block ($k$-subset). This is known as the "packing problem", and the maximum number of blocks $b$ is known as the packing number $mathscr P(v,k)$.
[The dual problem involves choosing a collection of $k$-subsets in which each pair appears at least once. This is the covering problem. The minimum number of such blocks $b$ is called the covering number, and when there is a design with each pair appearing exactly once, the packing number and covering number agree.]
No simple formula or recurrence relation is known for the packing numbers $mathscr P(v,k)$, although there is a well-known upper bound (the Schönheim bound) based on dividing the total number of pairs $binomv2$ by the number pairs in one $k$-subset $binomk2$. There is also a substantial literature on when the upper bound can be attained (Balanced Incomplete Block Designs).
A relatively recent reference (2013) for the larger cluster of problems is "Covering and packing for pairs" by Chee, Colbourn, Lee, and Wilson:
In this paper it is shown that for all sufficiently large values of $v$, a packing and a covering on $v$ elements exist whose numbers of blocks differ from the basic bounds by no more than an additive constant depending only on $k$.
Block size $mathbfk=3$
The specific case of choosing subsets of size $3$ has been thoroughly examined, starting with those instances in which the upper bound can be attained:
$$ b = fracbinomv2binom32 = fracv(v-1)6 $$
for which the name Steiner triple systems is usual.
Here the number of pairs $v(v-1)/2$ must be divisible by $3$, which gives the necessary condition that $vequiv 1,3 bmod 6$. It was shown by R.C. Bose (1939) and by Th. Skolem (1958) that this necessary condition is also sufficient.
The details for the residues $vequiv 0,2,4,5 bmod 6$ are worked out in Chapter 4 of Design Theory 2nd Ed. by C. Lindner and C. Rodger (2008):
$$ beginarray hline
v bmod 6 & mathscrP(v,3) \ hline
0text or 2 & fracv(v-2)6 \
1text or 3 & fracv(v-1)6 \
4 & fracv^2-2v-26 \
5 & fracv^2-v-86 \
hline endarray $$
answered Jul 22 at 14:53
hardmath
28.1k94592
This is one combinatorial problem among many similar topics, and we begin by introducing some notation that is commonly used.
By historical connection to experimental designs, the number of distinct objects is conventionally $v$ (for varieties) and the size of the subsets making up the "blocks" is $k$. The problem here is to achieve the maximum number of blocks, subject to the restrict that no pair of objects appears in more than one block ($k$-subset). This is known as the "packing problem", and the maximum number of blocks $b$ is known as the packing number $mathscr P(v,k)$.
[The dual problem involves choosing a collection of $k$-subsets in which each pair appears at least once. This is the covering problem. The minimum number of such blocks $b$ is called the covering number, and when there is a design with each pair appearing exactly once, the packing number and covering number agree.]
No simple formula or recurrence relation is known for the packing numbers $mathscr P(v,k)$, although there is a well-known upper bound (the Schönheim bound) based on dividing the total number of pairs $binomv2$ by the number pairs in one $k$-subset $binomk2$. There is also a substantial literature on when the upper bound can be attained (Balanced Incomplete Block Designs).
A relatively recent reference (2013) for the larger cluster of problems is "Covering and packing for pairs" by Chee, Colbourn, Lee, and Wilson:
In this paper it is shown that for all sufficiently large values of $v$, a packing and a covering on $v$ elements exist whose numbers of blocks differ from the basic bounds by no more than an additive constant depending only on $k$.
Block size $mathbfk=3$
The specific case of choosing subsets of size $3$ has been thoroughly examined, starting with those instances in which the upper bound can be attained:
$$ b = fracbinomv2binom32 = fracv(v-1)6 $$
for which the name Steiner triple systems is usual.
Here the number of pairs $v(v-1)/2$ must be divisible by $3$, which gives the necessary condition that $vequiv 1,3 bmod 6$. It was shown by R.C. Bose (1939) and by Th. Skolem (1958) that this necessary condition is also sufficient.
The details for the residues $vequiv 0,2,4,5 bmod 6$ are worked out in Chapter 4 of Design Theory 2nd Ed. by C. Lindner and C. Rodger (2008):
$$ beginarray hline
v bmod 6 & mathscrP(v,3) \ hline
0text or 2 & fracv(v-2)6 \
1text or 3 & fracv(v-1)6 \
4 & fracv^2-2v-26 \
5 & fracv^2-v-86 \
hline endarray $$
answered Jul 22 at 14:53
hardmath
28.1k94592
edited Jul 23 at 11:37
answered Jul 22 at 14:53
hardmath
28.1k94592
answered Jul 22 at 14:53
hardmath
28.1k94592
answered Jul 22 at 14:53
hardmath
28.1k94592
28.1k94592
1
Thank you @hardmath for your detailed explanation and also for giving the references. I think there is a typo in the numerator of $b=...$ since it should be $vchoose 2$
– Fermat
Jul 23 at 5:55
1
@Fermat: Thanks for noticing that typo!
– hardmath
Jul 23 at 11:38
You're welcome.
– Fermat
Jul 23 at 20:43
add a comment |Â
1
Thank you @hardmath for your detailed explanation and also for giving the references. I think there is a typo in the numerator of $b=...$ since it should be $vchoose 2$
– Fermat
Jul 23 at 5:55
1
@Fermat: Thanks for noticing that typo!
– hardmath
Jul 23 at 11:38
You're welcome.
– Fermat
Jul 23 at 20:43
1
1
Thank you @hardmath for your detailed explanation and also for giving the references. I think there is a typo in the numerator of $b=...$ since it should be $vchoose 2$
– Fermat
Jul 23 at 5:55
Thank you @hardmath for your detailed explanation and also for giving the references. I think there is a typo in the numerator of $b=...$ since it should be $vchoose 2$
– Fermat
Jul 23 at 5:55
1
1
@Fermat: Thanks for noticing that typo!
– hardmath
Jul 23 at 11:38
@Fermat: Thanks for noticing that typo!
– hardmath
Jul 23 at 11:38
You're welcome.
– Fermat
Jul 23 at 20:43
You're welcome.
– Fermat
Jul 23 at 20:43
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%2f2859427%2fchoosing-subsets-of-3-objects-out-of-n-with-specific-conditions%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
I think it would clarify matters to solve the case of $n=4,5$ completely. For $n=4$, say, surely that isn't difficult...there are only $4$ ways to choose three objects. If your first choice is $a,b,c$ then any other choice would have to have two in common with this one, yes? So in this case the answer would be $1$, no?
– lulu
Jul 22 at 14:10
See the topic balanced incomplete block designs for the special case where each pair appears exactly once in the collection of (equal sized) subsets. In considering how many subsets can be achieved where pairs appear at most once, the block designs are usually called packings.
– hardmath
Jul 22 at 14:14
@hardmath Yes, you are right and I correct it.
– Fermat
Jul 22 at 14:14
@lulu Yes, for n=4, the answer is 1.
– Fermat
Jul 22 at 14:16
1
What is the desired answer for $n=6$? If my first two choices are $a,b,c$ and $d,e,f$, the answer would seem to be $2$. But if my first two choices are $a,b,c$ and $c,d,e$, I could then go on to choose $a,d,f$ and $b,e,f$ and get an answer of $4$. In other words, it's still not clear exactly what it is you want to count.
– Barry Cipra
Jul 22 at 14:39