{
  "id": "1412.6070",
  "version": "v1",
  "published": "2014-12-18T20:45:03.000Z",
  "updated": "2014-12-18T20:45:03.000Z",
  "title": "The asymptotic number of $12..d$-Avoiding Words with $r$ occurrences of each letter $1,2, ..., n$",
  "authors": [
    "Guillaume Chapuy"
  ],
  "categories": [
    "math.CO"
  ],
  "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 $n$ of the number $A_{d,r}(n)$ of words of length $rn$ having $n$ letters $i$ for $i=1..r$, and having no increasing subsequence of length $d$. 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=1$ we recover Regev's result for permutations. Our proof goes as follows: expressing $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 $\\sqrt{n}$). This relies on asymptotic estimates for the Kotska numbers $K_{\\lambda,r^n}$ when $\\lambda$ has a fixed number of parts. Contrarily to the case $r=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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-12-18T20:45:03.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "asymptotic number",
      "avoiding words",
      "occurrences",
      "asymptotic estimates",
      "jacobi-trudi identity"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1412.6070C"
    }
  }
}