# Count compound words with an ambiguous decomposition

I have a set of words $$D$$, and I make compound words by concatenating a fixed number $$n$$ of words from $$D$$ (repetitions are allowed). Let's call such words $$n$$-compounds. I want to know how many distinct compound words can be formed, and how many $$n$$-compounds can be formed in $$a$$ ways for each value of $$a$$. For example, if $$D$$ is {hell, hello, open, pen} and $$n=2$$, the compound word hellopen can be formed as hell + open or hello + pen, so there are 16 distinct pairs of words in $$D$$, but only 15 distinct 2-compound words over $$D$$.

Formally, let $$\mathscr A$$ be a finite alphabet of size $$\ge 2$$, $$D$$ a finite set of words of length $$\ge 2$$ over $$\mathscr A$$, and $$n \ge 2$$ an integer. The set of valid $$n$$-compound word is $$C = \{ u_1 \ldots u_n \mid (u_1, \ldots, u_n) \in D^n \}$$. Let's call ambiguity of a word $$w$$ the number of $$n$$-tuples $$(u_1, \ldots, u_n) \in D^n$$ such that $$u_1 \ldots u_n = w$$. (So an ambiguity of 0 means that the word is not in $$C$$, an ambiguity of 1 means that the word can be decomposed uniquely, and larger ambiguities mean words that can be formed in multiple ways.)

I would like to calculate the number of distinct compound words, i.e. the size of $$C$$. I'm also interested in the number of words with ambiguity $$a$$ for each value of $$a$$, and especially the number of unambiguous compounds ($$a=1$$). This can obviously be done by enumerating all $$|D|^n$$ combinations and storing their multiplicity in a multiset structure, but that has a huge memory and time cost. Is there a better way? I have a feeling it would help to build a set of prefixes and suffixes, but I can't figure out how to chain those together.

If the exact calculation is impractical, I would be satisfied with an estimate. How can I sample my dictionary to get a reliable estimate? Also, if there's a method that works well except in some pathological cases, and it's possible to avoid those pathological cases by removing a few words from $$D$$, that's still fine for my application.

I am specifically interested in the following practical use case: $$D$$ is a set of a few thousand common English words (all lowercase), and $$n$$ is about 3 to 8. The application is the generation of “correct horse battery staple” style passwords: how much bias is introduced if you don't put spaces between words?