Exact Enumeration and Distribution of Word Trees

Definitions and mathematical statement

The supplied record asks two questions about $w$-trees and random functions associated with words, but does not define these objects or their probability model. Consequently, the following is a schematic formulation requiring the missing definitions.

For a word $W$ and its associated function $w$, let $\mathcal T_{w,n}$ provisionally denote the intended class of $w$-trees of size $n$. This notation does not specify what a $w$-tree is, how size is measured, or whether objects are labelled or counted up to isomorphism. Whenever this class is finite, write \[ a_w(n)=\lvert\mathcal T_{w,n}\rvert. \] The enumeration question is to determine these numbers exactly, by an explicit formula, a recurrence with sufficient initial conditions, or a functional equation that determines them. The permitted words, the admissible sizes, and the dependence of the class on $W$ remain unspecified.

For the distribution question, suppose the intended random functions associated with two distinct words $W$ and $W'$, at size $n$, have laws $\mu_{W,n}$ and $\mu_{W',n}$ on a common measurable space $(\Omega_n,\mathcal F_n)$. Define their total-variation distance by \[ d_n(W,W')=\sup_{A\in\mathcal F_n} \left|\mu_{W,n}(A)-\mu_{W',n}(A)\right|. \] Determine conditions on $W$ and $W'$ under which, as the intended size parameter tends to infinity, \[ d_n(W,W')\longrightarrow 0, \qquad d_n(W,W')\longrightarrow 1, \] or neither limit holds. Here "neither" leaves open both convergence to another value and failure to converge; the source does not distinguish these possibilities. The record does not specify the alphabet, word-evaluation rule, distribution of the underlying random maps, their dependence, the function domains and codomains, or whether the words are fixed as $n$ varies. Thus the displayed laws and limits cannot yet be instantiated as a fully specified mathematical problem.

The original excerpt continues into a separately headed problem about words in random permutations, attributed there to Valentin Féray. It does not establish that the permutation setting defines the preceding $w$-tree problem, so those hypotheses and conjectures are not transferred to this formulation.

Short English statement

Count the intended $w$-trees of each size exactly, and characterize when random functions associated with two distinct words become close in total variation, become asymptotically separated, or exhibit neither behavior. The supplied excerpt omits the definitions and probability model needed for a complete mathematical statement.

Sources

• Local UnsolvedMath registry: supplied record with permanent ID $30006529$, title "Exact Enumeration and Distribution of Word Trees", exact source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. The record gives proposed year $2026$ and no named proposer for this target problem.
• Supplied report citation: Enumerative Combinatorics (2026), Oberwolfach Reports, pp. 81--156, DOI 10.4171/owr/2026/2. https://doi.org/10.4171/owr/2026/2. The supplied background describes these reports as documenting mathematical workshops and their open-problem discussions.
• Supplied literature source: Chapuy--Perarnau, ACM Transactions on Algorithms. https://doi.org/10.1145/3736722.
• Supplied literature source: Oberwolfach Report 2026/2. https://doi.org/10.4171/owr/2026/2.
• Literature assessment dated exactly 2026-08-22: the supplied curation labels the record "partially solved" and states that exact enumeration of general $w$-trees and the total-variation comparison remain unresolved, while the primary random-automata literature supplies structural results and only partial enumeration and statistics results. This is supplied dated curation derived from the OWR material, not an independently verified literature assessment; its time-sensitive status and cited claims require independent verification.
• The supplied statement status is corrected_verified. Its accompanying qualification says that only clear formula delimiters, notation, grammar, and typography were repaired, preserving mathematical content and scope. This supplied label does not establish mathematical correctness or completeness.