I'm quite confused on how to calculate the number of all the possible strings that can occur for a given string. For example take the word 'cat', such that we can generate the possibilities:
'cat', 'cta', 'atc', 'act', 'tac', 'tca', 'at', 'ac', 'ct', 'ca', 'ta', 'tc', 'a', 'c', 't'.
Is there any mathematical formula to calculate the above? Any help is much appreciated, thanks in advance!
No simple formula is known. But if all the letters are different, it's not hard to calculate. Let's write $a(n)$ for the number of possible strings you can make from a string with $n$ letters, all different. For example, you observed that $a(3)=15$ because "cat" has 3 letters and 15 strings can be made from it.
Then: $$a(n) = n\cdot a(n-1) +n.$$
This means you can calculate $a(4)$ as $4\cdot15+4=64$ and $a(5)$ as $5\cdot 64+5=325$.
If not all the letters are different, the problem is more complicated. For example, only 8 strings, not 15, can be made from
poo.More advanced information is available at OEIS.
I hope this is helpful.
Addendum: A simple formula is known, and it is amazing. According to OEIS, $$a(n) = \left\lfloor e\cdot n! - 1\right\rfloor,$$
where $e=2.71828…$ and $\lfloor\ldots\rfloor$ means to throw away the fraction part.