Rosen 7e Exercise-6.5 question 45.b page 433

Question

How many ways can n books be placed on k distinguishable shelves if no two books are the same, and the positions of the books on the shelves matter?

Comments

$k^{n}$

---

this isn't the ans

---

then I think ans not correct

what is ans?

---

answer is $\frac{(n+k-1)!}{(k-1)!)}$

---

That will be ans if selves are indistinguishable

but here ans will be $k^{n}$

---

https://math.stackexchange.com/questions/1246694/how-many-ways-can-n-books-be-placed-on-k-distinguishable-shelves-if-no-2-books-a

---

a bit Confusing, they considered selves as indistinguishable

@Verma Ashish

if it is exam hall, what will be ur ans?

---

Now my answer will be

$^{n+r-1}C_{r-1} *n!$   😊

 

https://en.m.wikipedia.org/wiki/Stars_and_bars_(combinatorics)

In theorem2 stars are books but difference is here all books are distinct and there stars are indistinguishable.. So we multiplied with n!

---

yes

that "now" is matter. and that is most difficult part when no option given in question

ans will be $\frac{(n+k-1)!}{\left ( k-1 \right )!}$

---

why  $k^n $ is not correct-

We are assuming each of the n books have k choices that's how we get $k^n$

But if some books (let m books) go to same shelve S1 then we also have to consider m! ways of arrangement.. Beacuse order of books matters (given in question).. This makes it complex..

---

We can also take small example of two books B1 and B2 and two shelves S1 and S2.

According two k^n we get 4 ways.

But if we consider order then-- 6ways

S1	S2
B1	B2
B2	B1
B1,B2
B2,B1
	B1,B2
	B2,B1

In k^n we considered (B1,B2=B2,B1)

Hoping i am not wrong..

---

See 

when we do $k^{n}?$

Say how to arrange 1,2,....,9 numbers in 3 places?

i.e. $9^{3}?$ [where repetation allowed]

But how can we keep one book in 2 selves at the same time? that is why partition method applied here

---

I cannot remember more example on $k^{n}?$ If u get can give here

---

We can't compare this problem with numbers because in case of numbers we have multiple choices for a place( but we can't place more than one no. in one place).

We compare this problem with--

No. of ways of distributing n identical things among k people=$^{n+k-1}C_{k-1}$   (a person(shelve) may get 0 things)

Here difference is n books are distinct.

---

give me a question where $k^{n}$ is used

---

Placing 5 letters in 4 boxes.

---

Same type as I told and (repetition required)

any other type?

---

@srestha 

see, 

if letters are distinct ==> $4^5$ ways

if letters are all identical ==> $^8C_3$ ways

if placement order of letters in a post box matters then ==> $^8C_3*5!$

---

Sorry, i think my responses are not synchronized with your arguments..

---

think this

when u drop a letter in a postbox, how can u drop in other box?

So, answer always $_{3}^{8}\textrm{C}$

right?

---

when u drop a letter in a postbox, how can u drop in other box?

I'm not doing this..

If letter are distinct then 4^5 ways..

---

I think u r not confused with 

Say how to arrange 1,2,....,9 numbers in 3 places?

i.e. $9^3?$ [where repetation allowed]

And 

5 distinct letters in 4 post boxes==> $4^5$

Both are different approaches although final answer looks same...  In numbers at one place we can't place more than one no. But in one box we can place more than one letter..

In letters there is no repetition type of thing..

---

tell me one thing

if letters are distinct ==> $4^{5}$ ways

 

if placement order of letters in a post box matters then ==> $_{3}^{8}\textrm{C}\times 5!$

what is difference between two?

Can u write two full question for these 2 cases?

---

This explains difference between two cases.

Is it clear??

---

I understood what u mean
but a box containing letter abc or bca or cab ,.... this will not matter in box and letter problem

---

@srestha  yes.

that's why we don't consider 2nd case in box letter problem.(usually)

But in original question it is given that--

the positions of the books on the shelves matters. 

---

@Verma Ashish another way to analyze this question.

1. Consider all n books to be indistinguishable and we have to keep it in k distinguishable shelves:

  This can be done in n+k-1Ck-1 ways . It just gives how many books in each shelf like shef 1 + shelf 2....+shelf k = n

2. The number of ways to permute those books n books : n!

Answer :  n+k-1Ck-1 * n!

---

@Verma Ashish

Can we not mix these two question?

Like can we not think, three selves as three letter box?

Then what will be problem?

---

@srestha are you looking for why not k^n?

---

But if some books (let m books) go to same shelve S1 then we also have to consider m! ways of arrangement

@Verma Ashish when we do multiplication, the order is automatically considered. 

---

k^n fails because:

Take 3 shelves and 4 books

1. take the first book, you have 3 options.

2. For the second book, you don't have just 3 options. You have 3 ways to put it as the first book in any of the shelves OR to the right of the first book. 4 ways.

So for every book options varies like k, k+1, k+2 and so on.

---

Yes..correct👍👍

---

@tusharp I understood the case but how they derived the formula (k+n-1)!/(k-1)! for the product k,k+1,k+2.....

why you are considering indistinguishable to distinguishable case when already said that no two books are same. Hence books are distinguishable.

Anyone tell. 

Answer 1

Source: Rosen Solution Manual

 

Answer 2

n books places at k places with no repeatation(no two books are the same) and the no two books are the same means permutations so answer is npk