Mixing
In how many ways can $4$ books be removed from a bookshelf with $15$ books such that no two adjacent books are chosen? [duplicate]
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
This question already has an answer here:
In how many ways can you choose $k$ numbers out of $1,2,3,dots,n$ so none of them is consecutive?
3 answers
A bookshelf has $15$ books. in how many ways can $4$ books be removed such that no two adjacent books are chosen?
I started to solve the question by saying that the first book can be selected in $15$ ways, the second one can be selected in $13$ ways,the third one in 11 ways and the fourth one in $9$ ways. Total number of ways:$15times13times11times9=19305$. However the correct answer must be $495$. Can you explain why my counting technique is false and provide me with hints about the correct one? Thanks you for your help
combinatorics
edited Jul 14 at 14:55
N. F. Taussig
38.4k93053
asked Jul 14 at 14:00
Roy Rizk
887
marked as duplicate by N. F. Taussig, Benjamin Dickman, amWhy, Parcly Taxel, Isaac Browne Jul 15 at 4:45
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |Â
up vote
1
down vote
favorite
This question already has an answer here:
In how many ways can you choose $k$ numbers out of $1,2,3,dots,n$ so none of them is consecutive?
3 answers
A bookshelf has $15$ books. in how many ways can $4$ books be removed such that no two adjacent books are chosen?
I started to solve the question by saying that the first book can be selected in $15$ ways, the second one can be selected in $13$ ways,the third one in 11 ways and the fourth one in $9$ ways. Total number of ways:$15times13times11times9=19305$. However the correct answer must be $495$. Can you explain why my counting technique is false and provide me with hints about the correct one? Thanks you for your help
combinatorics
edited Jul 14 at 14:55
N. F. Taussig
38.4k93053
asked Jul 14 at 14:00
Roy Rizk
887
marked as duplicate by N. F. Taussig, Benjamin Dickman, amWhy, Parcly Taxel, Isaac Browne Jul 15 at 4:45
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
1
There are two problems. One is double counting; you are counting every selection $4!$ times. The other is that if a book is selected from the middle of the shelf, there are only $12$ ways to select the next book. It's only when you select one of the two books on the ends that there are $13$ choices for the second book.
– saulspatz
Jul 14 at 14:25
I tried to count starting from the middle I got 15x12x10x8=14400 and dividing by 4! Because the order among the selection doesn’t matter I got then 600 instead of 495
– Roy Rizk
Jul 14 at 14:34
Please help me with this question
– Roy Rizk
Jul 14 at 14:47
Your over-counting error is that in counting the number of ways that the second one can be selected. If the first one was one the outside, then yes there are 13 ways to select the second. However if, (for example) the first book selected was the second-most from the right, then there are only 12 ways to select the next book.
– Martin Roberts
Jul 14 at 16:02
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
This question already has an answer here:
In how many ways can you choose $k$ numbers out of $1,2,3,dots,n$ so none of them is consecutive?
3 answers
A bookshelf has $15$ books. in how many ways can $4$ books be removed such that no two adjacent books are chosen?
I started to solve the question by saying that the first book can be selected in $15$ ways, the second one can be selected in $13$ ways,the third one in 11 ways and the fourth one in $9$ ways. Total number of ways:$15times13times11times9=19305$. However the correct answer must be $495$. Can you explain why my counting technique is false and provide me with hints about the correct one? Thanks you for your help
combinatorics
edited Jul 14 at 14:55
N. F. Taussig
38.4k93053
asked Jul 14 at 14:00
Roy Rizk
887
This question already has an answer here:
In how many ways can you choose $k$ numbers out of $1,2,3,dots,n$ so none of them is consecutive?
3 answers
A bookshelf has $15$ books. in how many ways can $4$ books be removed such that no two adjacent books are chosen?
I started to solve the question by saying that the first book can be selected in $15$ ways, the second one can be selected in $13$ ways,the third one in 11 ways and the fourth one in $9$ ways. Total number of ways:$15times13times11times9=19305$. However the correct answer must be $495$. Can you explain why my counting technique is false and provide me with hints about the correct one? Thanks you for your help
This question already has an answer here:
In how many ways can you choose $k$ numbers out of $1,2,3,dots,n$ so none of them is consecutive?
3 answers
combinatorics
edited Jul 14 at 14:55
N. F. Taussig
38.4k93053
asked Jul 14 at 14:00
Roy Rizk
887
edited Jul 14 at 14:55
N. F. Taussig
38.4k93053
edited Jul 14 at 14:55
N. F. Taussig
38.4k93053
edited Jul 14 at 14:55
N. F. Taussig
38.4k93053
38.4k93053
asked Jul 14 at 14:00
Roy Rizk
887
asked Jul 14 at 14:00
Roy Rizk
887
asked Jul 14 at 14:00
Roy Rizk
887
887
marked as duplicate by N. F. Taussig, Benjamin Dickman, amWhy, Parcly Taxel, Isaac Browne Jul 15 at 4:45
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by N. F. Taussig, Benjamin Dickman, amWhy, Parcly Taxel, Isaac Browne Jul 15 at 4:45
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
1
There are two problems. One is double counting; you are counting every selection $4!$ times. The other is that if a book is selected from the middle of the shelf, there are only $12$ ways to select the next book. It's only when you select one of the two books on the ends that there are $13$ choices for the second book.
– saulspatz
Jul 14 at 14:25
I tried to count starting from the middle I got 15x12x10x8=14400 and dividing by 4! Because the order among the selection doesn’t matter I got then 600 instead of 495
– Roy Rizk
Jul 14 at 14:34
Please help me with this question
– Roy Rizk
Jul 14 at 14:47
Your over-counting error is that in counting the number of ways that the second one can be selected. If the first one was one the outside, then yes there are 13 ways to select the second. However if, (for example) the first book selected was the second-most from the right, then there are only 12 ways to select the next book.
– Martin Roberts
Jul 14 at 16:02
add a comment |Â
1
There are two problems. One is double counting; you are counting every selection $4!$ times. The other is that if a book is selected from the middle of the shelf, there are only $12$ ways to select the next book. It's only when you select one of the two books on the ends that there are $13$ choices for the second book.
– saulspatz
Jul 14 at 14:25
I tried to count starting from the middle I got 15x12x10x8=14400 and dividing by 4! Because the order among the selection doesn’t matter I got then 600 instead of 495
– Roy Rizk
Jul 14 at 14:34
Please help me with this question
– Roy Rizk
Jul 14 at 14:47
Your over-counting error is that in counting the number of ways that the second one can be selected. If the first one was one the outside, then yes there are 13 ways to select the second. However if, (for example) the first book selected was the second-most from the right, then there are only 12 ways to select the next book.
– Martin Roberts
Jul 14 at 16:02
1
1
There are two problems. One is double counting; you are counting every selection $4!$ times. The other is that if a book is selected from the middle of the shelf, there are only $12$ ways to select the next book. It's only when you select one of the two books on the ends that there are $13$ choices for the second book.
– saulspatz
Jul 14 at 14:25
There are two problems. One is double counting; you are counting every selection $4!$ times. The other is that if a book is selected from the middle of the shelf, there are only $12$ ways to select the next book. It's only when you select one of the two books on the ends that there are $13$ choices for the second book.
– saulspatz
Jul 14 at 14:25
I tried to count starting from the middle I got 15x12x10x8=14400 and dividing by 4! Because the order among the selection doesn’t matter I got then 600 instead of 495
– Roy Rizk
Jul 14 at 14:34
I tried to count starting from the middle I got 15x12x10x8=14400 and dividing by 4! Because the order among the selection doesn’t matter I got then 600 instead of 495
– Roy Rizk
Jul 14 at 14:34
Please help me with this question
– Roy Rizk
Jul 14 at 14:47
Please help me with this question
– Roy Rizk
Jul 14 at 14:47
Your over-counting error is that in counting the number of ways that the second one can be selected. If the first one was one the outside, then yes there are 13 ways to select the second. However if, (for example) the first book selected was the second-most from the right, then there are only 12 ways to select the next book.
– Martin Roberts
Jul 14 at 16:02
Your over-counting error is that in counting the number of ways that the second one can be selected. If the first one was one the outside, then yes there are 13 ways to select the second. However if, (for example) the first book selected was the second-most from the right, then there are only 12 ways to select the next book.
– Martin Roberts
Jul 14 at 16:02
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
2
down vote
This solution uses the stars and bars method of counting.
Consider the 4 books you select as bars and the 11 remaining books as stars. That is, we have need to arrange 4 bars and 11 stars, under the constraint that between any two bars there is at least one star.
There are $3$ spaces between the bars, so there must be 3 stars between them.
That now simply requires us to fix the remaining 12 objects (8 stars and 4 bars).
We can do this in $binom124=495$ ways.
The obviously generalises to the following:
For $nge2m-1$, there are $dbinomn-m+1m$ ways to select $m$ non-consecutive items from a set of $n$ items.
answered Jul 14 at 15:02
Martin Roberts
1,189318
add a comment |Â
up vote
0
down vote
The remaining $11$ books create $12$ slots where the four chosen books could have been. There are $12choose4=495$ ways to choose $4$ slots.
answered Jul 14 at 15:18
Christian Blatter
164k7108306
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
This solution uses the stars and bars method of counting.
Consider the 4 books you select as bars and the 11 remaining books as stars. That is, we have need to arrange 4 bars and 11 stars, under the constraint that between any two bars there is at least one star.
There are $3$ spaces between the bars, so there must be 3 stars between them.
That now simply requires us to fix the remaining 12 objects (8 stars and 4 bars).
We can do this in $binom124=495$ ways.
The obviously generalises to the following:
For $nge2m-1$, there are $dbinomn-m+1m$ ways to select $m$ non-consecutive items from a set of $n$ items.
answered Jul 14 at 15:02
Martin Roberts
1,189318
add a comment |Â
up vote
2
down vote
This solution uses the stars and bars method of counting.
Consider the 4 books you select as bars and the 11 remaining books as stars. That is, we have need to arrange 4 bars and 11 stars, under the constraint that between any two bars there is at least one star.
There are $3$ spaces between the bars, so there must be 3 stars between them.
That now simply requires us to fix the remaining 12 objects (8 stars and 4 bars).
We can do this in $binom124=495$ ways.
The obviously generalises to the following:
For $nge2m-1$, there are $dbinomn-m+1m$ ways to select $m$ non-consecutive items from a set of $n$ items.
answered Jul 14 at 15:02
Martin Roberts
1,189318
add a comment |Â
up vote
2
down vote
up vote
2
down vote
This solution uses the stars and bars method of counting.
Consider the 4 books you select as bars and the 11 remaining books as stars. That is, we have need to arrange 4 bars and 11 stars, under the constraint that between any two bars there is at least one star.
There are $3$ spaces between the bars, so there must be 3 stars between them.
That now simply requires us to fix the remaining 12 objects (8 stars and 4 bars).
We can do this in $binom124=495$ ways.
The obviously generalises to the following:
For $nge2m-1$, there are $dbinomn-m+1m$ ways to select $m$ non-consecutive items from a set of $n$ items.
answered Jul 14 at 15:02
Martin Roberts
1,189318
This solution uses the stars and bars method of counting.
Consider the 4 books you select as bars and the 11 remaining books as stars. That is, we have need to arrange 4 bars and 11 stars, under the constraint that between any two bars there is at least one star.
There are $3$ spaces between the bars, so there must be 3 stars between them.
That now simply requires us to fix the remaining 12 objects (8 stars and 4 bars).
We can do this in $binom124=495$ ways.
The obviously generalises to the following:
For $nge2m-1$, there are $dbinomn-m+1m$ ways to select $m$ non-consecutive items from a set of $n$ items.
answered Jul 14 at 15:02
Martin Roberts
1,189318
answered Jul 14 at 15:02
Martin Roberts
1,189318
answered Jul 14 at 15:02
Martin Roberts
1,189318
answered Jul 14 at 15:02
Martin Roberts
1,189318
1,189318
add a comment |Â
add a comment |Â
up vote
0
down vote
The remaining $11$ books create $12$ slots where the four chosen books could have been. There are $12choose4=495$ ways to choose $4$ slots.
answered Jul 14 at 15:18
Christian Blatter
164k7108306
add a comment |Â
up vote
0
down vote
The remaining $11$ books create $12$ slots where the four chosen books could have been. There are $12choose4=495$ ways to choose $4$ slots.
answered Jul 14 at 15:18
Christian Blatter
164k7108306
add a comment |Â
up vote
0
down vote
up vote
0
down vote
The remaining $11$ books create $12$ slots where the four chosen books could have been. There are $12choose4=495$ ways to choose $4$ slots.
answered Jul 14 at 15:18
Christian Blatter
164k7108306
The remaining $11$ books create $12$ slots where the four chosen books could have been. There are $12choose4=495$ ways to choose $4$ slots.
answered Jul 14 at 15:18
Christian Blatter
164k7108306
answered Jul 14 at 15:18
Christian Blatter
164k7108306
answered Jul 14 at 15:18
Christian Blatter
164k7108306
answered Jul 14 at 15:18
Christian Blatter
164k7108306
164k7108306
add a comment |Â
add a comment |Â
1
There are two problems. One is double counting; you are counting every selection $4!$ times. The other is that if a book is selected from the middle of the shelf, there are only $12$ ways to select the next book. It's only when you select one of the two books on the ends that there are $13$ choices for the second book.
– saulspatz
Jul 14 at 14:25
I tried to count starting from the middle I got 15x12x10x8=14400 and dividing by 4! Because the order among the selection doesn’t matter I got then 600 instead of 495
– Roy Rizk
Jul 14 at 14:34
Please help me with this question
– Roy Rizk
Jul 14 at 14:47
Your over-counting error is that in counting the number of ways that the second one can be selected. If the first one was one the outside, then yes there are 13 ways to select the second. However if, (for example) the first book selected was the second-most from the right, then there are only 12 ways to select the next book.
– Martin Roberts
Jul 14 at 16:02