The asymptotic number of 12..d12..d-Avoiding Words with rr occurrences of each letter 1,2,...,n1,2, ..., n

preprint2014arXivOpen access

Abstract

Following Ekhad and Zeilberger (The Personal Journal of Shalosh B. Ekhad and Doron Zeilberger, Dec 5 2014; see also arXiv:1412.2035), we study the asymptotics for large nn of the number Ad,r(n)A_{d,r}(n) of words of length rnrn having rr letters ii for i=1..ni=1..n, and having no increasing subsequence of length dd. We prove an asymptotic formula conjectured by these authors, and we give explicitly the multiplicative constant appearing in the result, answering a question they asked. These two results should make the OEIS richer by 100+25=125 dollars. In the case r=1r=1 we recover Regev's result for permutations. Our proof goes as follows: expressing Ad,r(n)A_{d,r}(n) as a sum over tableaux via the RSK correspondence, we show that the only tableaux contributing to the sum are "almost" rectangular (in the scale n\sqrt{n}). This relies on asymptotic estimates for the Kotska numbers Kλ,rnK_{λ,r^n} when λλ has a fixed number of parts. Contrarily to the case r=1r=1 where these numbers are given by the hook-length formula, we don't have closed form expressions here, so to get our asymptotic estimates we rely on more delicate computations, via the Jacobi-Trudi identity and saddle-point estimates.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.