# How many bins do random numbers fill?

Given is a sequence $\langle a_1,a_2,\ldots,a_n\rangle$ over the alphabet $\{1,2,\ldots,m\}$ chosen uniformly at random among the $m^n$ possibilities. What is the expected size of the set $\{a_1,a_2,\ldots,a_n\}$?

If $m=n$ it seems the answer tends to $(1-1/e)n$ as $n\to\infty$, but I don't know why.

I bumped into this while benchmarking some code for hashtables, so I wouldn't be surprised if it is a standard result in the hash world.

Define the indicator random variable $I_i$ for $1 \leq i \leq m$ as $1$ if alphabet $i$ is present in the set ${a_1,\dots,a_n}$. Then the size of the set is simply $\sum_{i=1}^m I_i$. The expectation of this can be easily computed by linearity of expectation. The probability that $I_i$ equals $1$ is given by $1-\left( \frac{m-1}{m} \right)^n$ and therefore the expected size of the set is $m \left[ 1- \left( 1 - \frac{1}{m} \right)^n \right]$. For $m=n$, the limiting value is indeed as you mentioned in the question.
{"ft_lang_label":"__label__en","ft_lang_prob":0.9040756,"math_prob":0.9999424,"size":438,"snap":"2019-51-2020-05","text_gpt3_token_len":135,"char_repetition_ratio":0.108294934,"word_repetition_ratio":0.0,"special_character_ratio":0.30365297,"punctuation_ratio":0.15,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99997103,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-01-21T02:51:20Z\",\"WARC-Record-ID\":\"<urn:uuid:3ab93cb1-2b5c-4bc0-a294-710cdbf103d0>\",\"Content-Length\":\"145854\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:05e6ed07-6350-4c3c-8a72-de0f8f58dbaf>\",\"WARC-Concurrent-To\":\"<urn:uuid:1e52edf8-3221-447d-ad67-86cdba16924c>\",\"WARC-IP-Address\":\"151.101.193.69\",\"WARC-Target-URI\":\"https://math.stackexchange.com/questions/5775/how-many-bins-do-random-numbers-fill\",\"WARC-Payload-Digest\":\"sha1:BAG5YHSVKRD77VZLJMSJT2SLHDOOTUOR\",\"WARC-Block-Digest\":\"sha1:GUVLZGR24BCUZEXBDE2NIELWJXMBYLB6\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-05/CC-MAIN-2020-05_segments_1579250601241.42_warc_CC-MAIN-20200121014531-20200121043531-00308.warc.gz\"}"}