TransWikia.com

Counting the number of words of a fixed length, where the number of times each character appears across all words is bounded

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?

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP