On the number of words with restrictions on the number of symbols

Abstract

Demostramos que, en un alfabeto de n símbolos, el número de palabras de longitud n cuyo número de símbolos diferentes se aleja de (1?1/e)n, que es el valor esperado por la distribución de Poisson, presenta decaimiento exponencial en n. Utilizamos el método de Laplace para sumas y cotas conocidas de números de Stirling de segunda especie. Expresamos nuestro resultado en términos de desigualdades.

We show that, in an alphabet of n symbols, the number of words of length n whose number of different symbols is away from (1?1/e)n, which is the value expected by the Poisson distribution, has exponential decay in n. We use Laplace's method for sums and known bounds of Stirling numbers of the second kind. We express our result in terms of inequalities

Mostramos que, em um alfabeto de n símbolos, o número de palavras de comprimento n cujo número de símbolos diferentes está distante de (1?1/e)n, que é o valor esperado pela distribuição de Poisson, apresenta decaimento exponencial em n. Usamos o método de Laplace para somas e limites conhecidos de números de Stirling do segundo tipo. Expressamos nosso resultado em termos de desigualdades.