Consider generating a regular expression for the permutations of a set S. We can do this by divide-and-conquer: sum over all subsets T of S of size floor(n/2), and for each subset, concatenate the (recursive) result for T to the result for S-T. For example, for S = {1,2,3,4} one gets (12+21)(34+43)+(13+31)(24+42)+(23+32)(14+41)+(14+41)(23+32)+(24+42)(13+31)+(34+43)(12+21). The length of such an expression (where one counts only elements of S) is a(n).
