{
  "id": "1801.08262",
  "version": "v1",
  "published": "2018-01-25T03:02:31.000Z",
  "updated": "2018-01-25T03:02:31.000Z",
  "title": "Wilf equivalence relations for consecutive patterns",
  "authors": [
    "Tim Dwyer",
    "Sergi Elizalde"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Two permutations $\\pi$ and $\\tau$ are c-Wilf equivalent if, for each $n$, the number of permutations in $S_n$ avoiding $\\pi$ as a consecutive pattern (i.e., in adjacent positions) is the same as the number of those avoiding $\\tau$. In addition, $\\pi$ and $\\tau$ are strongly c-Wilf equivalent if, for each $n$ and $k$, the number of permutations in $S_n$ containing $k$ occurrences of $\\pi$ as a consecutive pattern is the same as for $\\tau$. In this paper we introduce a third, more restrictive equivalence relation, defining $\\pi$ and $\\tau$ to be super-strongly c-Wilf equivalent if the above condition holds for any set of prescribed positions for the $k$ occurrences. We show that, when restricted to non-overlapping permutations, these three equivalence relations coincide. We also give a necessary condition for two permutations to be strongly c-Wilf equivalent. Specifically, we show that if $\\pi,\\tau$ in $S_m$ are strongly c-Wilf equivalent, then $|\\pi_m-\\pi_1|=|\\tau_m-\\tau_1|$. In the special case of non-overlapping permutations $\\pi$ and $\\tau$, this proves a weaker version of a conjecture of the second author stating that $\\pi$ and $\\tau$ are c-Wilf equivalent if and only if $\\pi_1=\\tau_1$ and $\\pi_m=\\tau_m$, up to trivial symmetries. Finally, we strengthen a recent result of Nakamura and Khoroshkin-Shapiro giving sufficient conditions for strong c-Wilf equivalence.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-01-25T03:02:31.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A05",
      "05A15",
      "06A07"
    ],
    "keywords": [
      "wilf equivalence relations",
      "consecutive pattern",
      "strongly c-wilf equivalent",
      "non-overlapping permutations",
      "strong c-wilf equivalence"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}