Mathematics Asked by szxk on February 25, 2021
Suppose I have an alphabet of $k$ characters, like $Sigma = lbrace a, b, c, d, e rbrace$. I want to build words of length $m$, but I have a fixed budget for each character. The letter $a$ appears at most $m*n_a$ times, the letter $b$ at most $m*n_b$ times, etc., across all words. For example, if $n_a = 1$, then I can only have one word that begins with "a", one word that has "a" in the second position, etc. (and these don’t have to be separate words)
How many unique words can I create of length $m$?
Clearly for large enough $n_i$ and small enough $m$, we have that this is simply $|Sigma|^m$.
Another simple version of this, is where I have a binary alphabet {0, 1}, and have, say, $n_0 = m/3$. Then at most a third of any of the characters in our word are zeros, so the total words can be counted by the partial binomial sum $sum_{i=0}^{m/3} binom{m}{i}$, summing up to the integer part of $m/3$.
Edit: Another way to phrase this is suppose we have $m$ identical but ordered urns. Each urn is filled with balls of $k$ different colors, with $n_i$ (indistinguishable) balls per color, $i = 0, 1, …, k$. Drawing from each urn simultaneously without replacement, how many unique sequences can we draw from these urns?
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP