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.