Book Sorting
Let f(b) be the number of ways to arrange up to b books. Assume that the order matters and that it is possible to place no books.
Example: f(2)=5 because if the books are titled a and b, the following arrangements are valid: No books, a, b, ab and ba, which is five arrangements.
How much is ?
The answer is 2018.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
The number of ways to arrange n books from a set of b is ( b − n ) ! b ! . In this case, all values of n from 0 to b are possible, f(b) is the sum of all possibilities, which is b ! b ! + ( b − 1 ) ! b ! +...+ ( 1 ) ! b ! + ( 0 ) ! b ! .
f(b+1)= ( b + 1 ) ! ( b + 1 ) ! + ( b ) ! ( b + 1 ) ! +...+ ( 1 ) ! ( b + 1 ) ! + ( 0 ) ! ( b + 1 ) ! =1+ ( b ) ! b ! ( b + 1 ) + ( b − 1 ) ! b ! ( b + 1 ) +...+ ( 1 ) ! b ! ( b + 1 ) + ( 0 ) ! b ! ( b + 1 ) =1+( ( b ) ! b ! + ( b − 1 ) ! b ! +...+ ( 1 ) ! b ! + ( 0 ) ! b ! )(b+1). By commutativity and substitution, f(b+1)=(b+1)f(b)+1.
Using the above formula, f ( 2 0 1 7 ) f ( 2 0 1 8 ) − 1 = f ( 2 0 1 7 ) f ( 2 0 1 7 + 1 ) − 1 = f ( 2 0 1 7 ) ( 2 0 1 7 + 1 ) f ( 2 0 1 7 ) + 1 − 1 = f ( 2 0 1 7 ) 2 0 1 8 f ( 2 0 1 7 ) =2018.