# Search Space for Genetic Algorithms

I have not been able to find anywhere a general formula for the size of the search space for Genetic Algorithms (GA).

I would imagine that such a formula would involve the binomial coefficient — maybe Stars and Bars

https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)

The reason I ask is because I have developed my own GA and would like to know the search space size as a means to motivate the need for, and usefulness of, metaheuristics like GAs for a manuscript that I am currently writing.

As an example, consider a simple binary (0/1) GA with string length of $$L$$ = 10 and population size (number of chromosomes) of $$N$$ = 100. Possible solutions could be:

``0100001110  1011010010  etc. ``

Since 0/1 can be repeated in any given string (chromosome), there would be exactly $$2^N$$ possible configurations. This would generalize to $$k^N$$ for any $$k$$-ary problem.

I feel this isn’t the whole story.

If I had to guess a closed-form expression using Stars and Bars for the binary GA case, it might be something like $$\binom{N + 2^N – 1}{N} = \binom{N + 2^N – 1}{2^N – 1} = \binom{100 + 2^{100} – 1}{100} = \binom{100 + 2^{100} – 1}{2^{100} – 1} \sim 10^{2852}$$

Is this the right line of thinking?

Any thoughts are greatly welcomed.