My main question is: Question: Can one do exact enumeration of w-trees?
Statement
My main question is: Question: Can one do exact enumeration of w-trees? Can you conjecture, or prove, an exact formula, or even a recurrence formula or functional equation, to produce the number of w-trees of size n? A related question is to ask, for two different words W and W ′ , whether the associated random functions w and w′ have distributions which are very similar, or very different. Does their total variation distance go to 0, to 1, or neither, with certain conditions on W and W ′ ? 5. Words in random permutations (problem of Valentin Féray) Setting. Consider two independent uniform random permutations \sigma, \tau , and set \pi = \sigma\tau \sigma 2 \tau 2 . As \pi is conjugacy invariant, we are interested in its cycle structure. The first conjecture deals with the length L1 of the cycle containing 1 in \pi. Conjecture 1. The random variable L1 /n converges in distribution to a uniform random variable in [0, 1]. We can also ask about the length Mk of the k-th largest cycle in \pi. Conjecture 2. The random variable (M1 /n, M2 /n, . . . ) converges in distribution to a the Poisson Dirichlet process of parameter 1. Informally, the two conjectures above mean that we expect \pi to behave asymp- totically as a uniform random permutation. Indeed, Conjectures 1 and 2 are well-known to hold if \pi is replaced by a uniform random permutation (in fact, in this case, the distribution of L1 is uniform on {1, . . . , n}). A stronger conjecture would be that the total variation distance dTV (\pi, Unif(Sn )) converges to 0. The counterpart for short cycles follow from a result of Kammoun and Maida [7]. Theorem 3. If Ck is the number of k-cycles in \pi, then the Ck ’s converge jointly in distribution to independent
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.