The Gateway to Computer Science Excellence
+3 votes
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?
in Combinatory by | 248 views

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?



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}$


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]


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.

@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. 

2 Answers

+1 vote

Source: Rosen Solution Manual


0 votes
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

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,314 questions
60,435 answers
95,251 users