Let's start with the RIPEMD-160 hash in the center of this image:
https://en.bitcoin.it/wiki/File:PubKeyToAddr.pngSo we have 160 bits or 20 bytes.
Which is 2^160 possible combinations.
Now we add the "1" to the front and 4 bytes checksum (that's why not every combination is valid),
which gives us 25 bytes. According to
http://en.wikipedia.org/wiki/Base64(where we assume that Bitcoin's Base58 leads to roughly the same numbers of characters as Base64 does)
we get four thirds of 25 bytes, which equals to something between 33 and 34 bytes. This is our Bitcoin address.
Hence our two little equations are:
- We have 2^( n*8 ) valid combinations.
- We get (n+5)/3*4 characters for the Bitcoin address.
Replace n with 20 for the unrestricted Bitcoin address space.
Now you want to take e.g. 6 characters out of the equation, because you choose a vanity address like this one:
1aaaaaaX298sdf3kjh394jh499o38te36a
So we have not 33 but 27 variable characters:
(n+5)/3*4 = 27,
and n=15 approximately.
Result: You end up with 2^( 15*8 ) valid combinations instead of 2^(20*8) of the full Bitcoin address space.
So the rough approximation is:
2^(( (33-x)/4*3 - 5 ) * 8 )
where x is the number of vanity characters (6 in the example above).