Question

find the recurrence relation for the number of ways to arrange distinct objects in a row . Find the number of arrangements of 9 objects​

Answer 1

Answer:

Let an be the number of ways to arrange n distinct objects in 5 distinct boxes. Clearly a1=5. (You can even start at a0=1. There’s just one way to arrange 0 objects: you put none of them in each box.) Now suppose that you know an for some n; what must an+1 be? Say that the objects are labelled 1 through n+1. You put the first n objects into the boxes; you can do this in an ways. Then you put the (n+1)-st object into one of the 5 boxes; in how many different ways can you do this? And how do you combine that number with an to get an+1, the number of ways to put all n+1 objects into the boxes? That formula is the desired recurrence relation.

Note that in this problem it’s easy to write down a closed form for an. If the boxes are numbered 1 through 5, each distribution of n objects numbered 1 through n to the boxes can be thought of as a function from {1,2,…,n} to {1,2,3,4,5}. How many of those are there? You can use that knowledge to check that your recurrence actually makes sense.