3 votes 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? Combinatory kenneth-rosen discrete-mathematics combinatory + – aditi19 asked Apr 16, 2019 aditi19 1.8k views answer comment Share Follow See all 32 Comments See all 32 32 Comments reply srestha commented Apr 19, 2019 reply Follow Share $k^{n}$ 0 votes 0 votes aditi19 commented Apr 20, 2019 reply Follow Share this isn't the ans 0 votes 0 votes srestha commented Apr 20, 2019 reply Follow Share then I think ans not correct what is ans? –1 votes –1 votes aditi19 commented Apr 20, 2019 reply Follow Share answer is $\frac{(n+k-1)!}{(k-1)!)}$ 0 votes 0 votes srestha commented Apr 20, 2019 reply Follow Share That will be ans if selves are indistinguishable but here ans will be $k^{n}$ 0 votes 0 votes Verma Ashish commented Apr 20, 2019 reply Follow Share https://math.stackexchange.com/questions/1246694/how-many-ways-can-n-books-be-placed-on-k-distinguishable-shelves-if-no-2-books-a 0 votes 0 votes srestha commented Apr 20, 2019 reply Follow Share a bit Confusing, they considered selves as indistinguishable @Verma Ashish if it is exam hall, what will be ur ans? 0 votes 0 votes Verma Ashish commented Apr 20, 2019 reply Follow Share 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! 1 votes 1 votes srestha commented Apr 20, 2019 reply Follow Share 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 )!}$ 0 votes 0 votes Verma Ashish commented Apr 20, 2019 reply Follow Share 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.. 0 votes 0 votes Verma Ashish commented Apr 20, 2019 reply Follow Share 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.. 0 votes 0 votes srestha commented Apr 20, 2019 reply Follow Share 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 0 votes 0 votes Verma Ashish commented Apr 20, 2019 reply Follow Share 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. 0 votes 0 votes srestha commented Apr 20, 2019 reply Follow Share give me a question where $k^{n}$ is used 0 votes 0 votes Verma Ashish commented Apr 20, 2019 reply Follow Share Placing 5 letters in 4 boxes. 0 votes 0 votes srestha commented Apr 20, 2019 reply Follow Share Same type as I told and (repetition required) any other type? 0 votes 0 votes Verma Ashish commented Apr 20, 2019 reply Follow Share @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!$ 0 votes 0 votes Verma Ashish commented Apr 20, 2019 reply Follow Share Sorry, i think my responses are not synchronized with your arguments.. 0 votes 0 votes srestha commented Apr 20, 2019 reply Follow Share 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? 0 votes 0 votes Verma Ashish commented Apr 20, 2019 reply Follow Share 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.. 0 votes 0 votes Verma Ashish commented Apr 20, 2019 reply Follow Share 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.. 0 votes 0 votes srestha commented Apr 21, 2019 reply Follow Share 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? 0 votes 0 votes Verma Ashish commented Apr 21, 2019 reply Follow Share This explains difference between two cases. Is it clear?? 1 votes 1 votes srestha commented Apr 21, 2019 reply Follow Share I understood what u mean but a box containing letter abc or bca or cab ,.... this will not matter in box and letter problem 0 votes 0 votes Verma Ashish commented Apr 21, 2019 reply Follow Share @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. 1 votes 1 votes tusharp commented Apr 21, 2019 reply Follow Share @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! 1 votes 1 votes srestha commented Apr 21, 2019 reply Follow Share @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? 1 votes 1 votes tusharp commented Apr 21, 2019 reply Follow Share @srestha are you looking for why not k^n? 0 votes 0 votes tusharp commented Apr 21, 2019 reply Follow Share 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. 0 votes 0 votes tusharp commented Apr 21, 2019 reply Follow Share 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. 1 votes 1 votes Verma Ashish commented Apr 21, 2019 reply Follow Share Yes..correct👍👍 0 votes 0 votes mb14 commented Nov 2, 2019 i edited by mb14 Nov 2, 2019 reply Follow Share @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. 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes Source: Rosen Solution Manual smsubham answered Mar 1, 2020 smsubham comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 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 ma1999 answered Apr 20, 2019 ma1999 comment Share Follow See all 0 reply Please log in or register to add a comment.