So we have the Josephus problem, then another interesting example is the one that we had discussed in the lecture on Standard ML, that is the function that counts the different ways in which you can change a given amount of money. And then the well-parenthesised expression with n right parenthesis, or streams or equal or less than or equal. Now look at, for instance, as Fibonacci, Josephus and Catalan(n) look at how these are described. It is rather natural. What we are doing here we are just giving a specification. If you compare these definitions to the ones of the previous page just think that Catalan gives you the number of different expressions of well-parenthesised expressions with n open parenthesis. Of course this is rather easy because if you have just one open parenthesis then you have just one expression. If you have n plus 1 expressions, well how do you create such expressions? Well, either you have an outermost pair of brackets or otherwise you can split your well-formed expression in two sub-expressions each consisting of a smaller number of right expressions. This is essentially the definition. And this definitions seems magical. It gives a very easy way of describing such a function. Similar examples are listed here. I would really like for all the students to work out these examples because this is a very interesting list which really gives a feel for the kind of difference that there is and how much more easy it is to write an implicit definition rather than an explicit definition.

---