Is there any formula for the following permutation?

Question

2 elements {a,b} result:

• a, b, ab

3 elements {a,b,c} result:

• a, b, c, ab, ac, bc, abc

4 elements {a,b,c,d} result:

• a, b, c, d, ab, ac, ad, bc, bd, cd, abc, abd, acd, bcd, abcd

5 elements {a,b,c,d,e} result:

• a, b, c, d, e, ab, ac, ad, ae, bc, bd, be, cd, ce, de, abc, abd, abe, acd, ace, ade, bcd, bce, bde, cde, abcd, abce, abde, acde, bcde, abcde

and so on...

Answer 1

Looks like you want the number of nonempty ordered substrings of $a_1a_2...a_n$. Since the order is predetermined, all you have to do is specify which symbols are in the substring.

How many ways are there to do that?

Answer 2

There is a nice example for Erlang list comprehensions:

perms([]) -> [[]];
perms(L)  -> [[H|T] || H <- L, T <- perms(L--[H])].

This will generate:

> perms([b,u,g]).
[[b,u,g],[b,g,u],[u,b,g],[u,g,b],[g,b,u],[g,u,b]]

Your case is not about permutations, but seems to be generating the subsets (and ignoring the valid empty subset, or in your result format, the empty word $\epsilon$).

The mathematical equivalent of the above code, switching from lists (words, tuples) to sets would be something like:

\begin{align} p(\emptyset ) &= \{ \emptyset \} \\ p(A) &= \{ {a} \cup B \mid a \in A, B \in p(A \setminus \{ a \} \} \end{align}

Alas the binding rules of the symbols might not be the same.

The code equivalent would first select an $a$ from $A$ and then pick a $B$ from $p(A \setminus \{ a \})$ for that particular first selected $a$.