I am having trouble with this question, please take a look at it:
Find a recurrence relation for the number of ways to arrange n distinct objects in 5 distinct boxes.
this is my discrete math assignment and there is no example for this problem in my book .. and i cant find it on internet too.. Please help me.. thank you :)
Let $a_n$ be the number of ways to arrange $n$ distinct objects in $5$ distinct boxes. Clearly $a_1=5$. (You can even start at $a_0=1$. There’s just one way to arrange $0$ objects: you put none of them in each box.) Now suppose that you know $a_n$ for some $n$; what must $a_{n+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 $a_n$ 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 $a_n$ to get $a_{n+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 $a_n$. 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,\ldots,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.