NUMBER OF POSSIBLE PAIRWISE ALIGNMENTS: The number of pairwise alignments increases factorially with the lengths of the sequences. If you consider Non-Boring Alignments(NBA) (where gaps are always paired with nucleotides) the number of all possible alignments of two sequences of lengths m and n is (m+n)!/m!*n!, so the formular for two sequences of equal length is so (2n)!/(n!)^2 which is often approximated (for practical reasons) to 2^2n/(π*n)^-0.5 [Lange (2002), Eddy, Nature Biotechnology (2004)].

For some small sequences' lengths, the number of possible alignments is already too big; for example fot two sequences of 11 nucleotides, there are 705,432 possible alignments, and for two sequences of 100 nucleotides, the number is astronomical (> 10^60).

NUMBER OF POSSIBLE MULTIPLE SEQUENCE ALIGNMENTS:

As for the number of possible alignments for more than two sequences, you can find the formula in Slowinski, Mol. Phylogenet. Evol (1998). Accordingly, there are 16,081 different alignments for 3 sequences of 3 characters each and 1.05*10^18 different alignments for 5 sequences of length of 5 nucleotides.

As a result, the calculation of an exact alignment becomes infeasible for relatively small sets of comparatively short sequences. For example, the dynamic programming algorithm implemented in the MSA program (Lipman et al., 1989) allows optimal alignment of up to roughly 10 protein sequences of small lengths of 200-300 residues.

There are far more than 3^m alignments for 2 strings. They can generate cigar strings (of match/mismatch, insertion, deletion, clip) symbols of length m to 2m (or 2m-1 if you require overlap), with some restrictions (for example, clips must be consecutive and on the end). 3^(2m) sounds realistic. It's definitely less than 4^(2m), and probably greater than 2^(2m). Let's suppose a constant Cwhich is greater than 2 and less than 4; the formula is C^(nm), where n is the number of strings and m is the length... I think. That would simplify to C^(sum of lengths) as long as you have at least two sequences.

You can also think of it like this:

You have N strings, and thus N specific alignments to a reference. That reference can only contain bases present in the strings you are aligning; thus, it can be at most N*(M-1)+1 bases long and at minimum 1 base long (if we assume these sequences overlap; otherwise it would be N*M and 0). But they can be arbitrarily interleaved. Interleavings which result in no two strings ever sharing a base are the worst-case scenario, which I expect to dominate the state-space.