Correct solutions were also received from Jeffrey Downin, Jan Siwanowicz and William V. Webb.
Look at the left most digit, call it L. The digits less than L must follow in decreasing order while those greater than L must follow in increasing order. If L = d, there are no digits larger than L; if L = d - 1, there is one digit larger than L and it can appear in any of d - 1 places; if L = d - 2, there are two digits larger than L and they take up two of the following d - 1 places; and so on. This gives the total number to be
where C(d-1,k) is the number of ways to select a subset of size k from a set of size d - 1. The above sum is the desired number given above.
You are visitor number 5272
to
this page.
Page last updated 24 April 1998.