Permutations problem

Mar 2009
419
64
Uptown Manhattan, NY, USA
Not really probability/statistics but this is an introductory discrete mathematics class and I'm rusty on all of this material, so here it goes:

Pamela has 15 different books. In how many ways can she place her books on two shelves so that there is at least one book on each shelf?

So I considered the one event where 14 books are on Shelf A and only 1 on Shelf B, and so the possible arrangement of books in that scenario is \(\displaystyle 14! \times 1!\). Now, if there are 13 books on Shelf A and 2 are on Shelf B, the number of possible arrangements are \(\displaystyle 13! \times 2!\). And so it goes on as such and so the total possible arrangements would be \(\displaystyle 2(14! \times 1! + 13!\times 2! + ... + 9! \times 6! + 8! \times 7!)\). Is this correct or am I just way off? Thanks.
 

awkward

MHF Hall of Honor
Mar 2008
934
409
Not really probability/statistics but this is an introductory discrete mathematics class and I'm rusty on all of this material, so here it goes:

Pamela has 15 different books. In how many ways can she place her books on two shelves so that there is at least one book on each shelf?

So I considered the one event where 14 books are on Shelf A and only 1 on Shelf B, and so the possible arrangement of books in that scenario is \(\displaystyle 14! \times 1!\). Now, if there are 13 books on Shelf A and 2 are on Shelf B, the number of possible arrangements are \(\displaystyle 13! \times 2!\). And so it goes on as such and so the total possible arrangements would be \(\displaystyle 2(14! \times 1! + 13!\times 2! + ... + 9! \times 6! + 8! \times 7!)\). Is this correct or am I just way off? Thanks.
Hi Pinkk,

In the case where there are 8 books on the first shelf and 7 books on the second, for example, have you accounted for the number of ways you can split the books into a set of 8 and a set of 7?
 
  • Like
Reactions: Pinkk
Mar 2009
419
64
Uptown Manhattan, NY, USA
Isn't that taken into account with the 2 in front of everything in the parentheses? Because you can have 8 on shelf A and 7 on shelf B, or 7 on shelf A and 8 on shelf B, and in either case, the way you can arrange 8 on one shelf is \(\displaystyle 8!\) and the way you can arrange 7 on another shelf is \(\displaystyle 7!\), so the way you can arrange 8 on one shelf and 7 on another is \(\displaystyle 8! \times 7!\).
 
Dec 2009
3,120
1,342
Isn't that taken into account with the 2 in front of everything in the parentheses? Because you can have 8 on shelf A and 7 on shelf B, or 7 on shelf A and 8 on shelf B, and in either case, the way you can arrange 8 on one shelf is \(\displaystyle 8!\) and the way you can arrange 7 on another shelf is \(\displaystyle 7!\), so the way you can arrange 8 on one shelf and 7 on another is \(\displaystyle 8! \times 7!\).
You can arrange the 8 books with 8! on one shelf and the 7 on the other shelf as 7!
but that only takes into account the specific 8 books chosen from the 15
and the remaining 7 books.
You can split the 15 into 8 and 7 in many different ways, specifically \(\displaystyle \binom{15}{8}\)

You appear to want to count all possible arrangements, rather than just groups.
 
  • Like
Reactions: Pinkk

Soroban

MHF Hall of Honor
May 2006
12,028
6,341
Lexington, MA (USA)
Hello, Pinkk!

Pamela has 15 different books.
In how many ways can she place her books on two shelves
so that there is at least one book on each shelf?

For each of the 15 books, Pamela makes a decision:
. . (1) Place it on shelf A, or (3) place it on shelf B.

There are: .\(\displaystyle 2^{15} \:=\:32,768\) possible choices she can make.


However, these include these two disallowed cases:
. . All 15 books are on shelf A, and all 15 books are on shelf B.


Therefore, there are: .\(\displaystyle 32,768 - 2 \:=\:32,766\) ways to place the books
. . so that there is at least one book on each shelf.

 
  • Like
Reactions: Pinkk

Plato

MHF Helper
Aug 2006
22,507
8,664
The last reply to this thread is beyond me.
Let us we understand the question as:
“How many ways can we arrange fifteen books on two shelves so that no self is empty”
Then there are \(\displaystyle 15!\) ways to arrange those books.
For any one of those ways, there are fourteen ways to place that string onto two slelves.
Thus \(\displaystyle 14\cdot 15! =18307441152000\)
 
  • Like
Reactions: Pinkk
May 2010
13
1
I read it like the question and answer like this --

If order does not matter then the question is like a coin flip and yes it would be \(\displaystyle 2^{15} -2\), however order is likely to matter.

Because order does matter I think it would be \(\displaystyle 15! \cdot 14 = 1.6999 E^{13}\)

As a workable example if you had three books and order mattered there would be 24 ways to split across the two shelves.

6 ways for 0 books on the top shelf (/abc, /acb, /bac, /bca, /cab, /cba)
6 ways for 1 book on the top shelf (a/bc, a/cb, b/ac, b/ca, c/ab, c/ba)
6 ways for 2 books on the top shelf (ab/c, ba/c, ac/b, ca/b, bc/a, cb/a)
6 ways for 3 books on the top shelf (abc/, acb/, bac/, bca/, cab/, cba/)

So it's going to be n! books * ways to split. Because we can't have 0 or 15 books on the top shelf there are 14 ways (1 - 14) to split the books.
 
  • Like
Reactions: Pinkk

Soroban

MHF Hall of Honor
May 2006
12,028
6,341
Lexington, MA (USA)
Hello, Plato!

You're right . . . I forgot about the ordering of the books.
(There are 15 different books . . . I knew that! . . . *blush*)

 
  • Like
Reactions: Pinkk