{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R587",
  "content_hash": null,
  "slug": "pnc-claim-exact-counts-and-recurrence",
  "type": "claim",
  "title": "Inclusion-exclusion gives the classical Hertzsprung numbers",
  "summary": "Runs of selected path edges give an exact double sum, its generating function, and Riordan's four-term recurrence.",
  "relevance": "For Monotonicity of consecutive-adjacency avoidance in random permutations, record pnc-claim-exact-counts-and-recurrence (“Inclusion-exclusion gives the classical Hertzsprung numbers”) records a bound, answer, status fact, or structural consequence. The record states: Runs of selected path edges give an exact double sum, its generating function, and Riordan's four-term recurrence.",
  "relevance_source": "recorded",
  "body": "The forbidden unordered value pairs are the \\(n-1\\) edges of the path\n\\[\n1-2-\\cdots-n.\n\\]\nChoose \\(k\\) of these edges for an inclusion-exclusion term. If the chosen edges form \\(r\\) nonempty runs, they collapse to \\(r\\) blocks. Each block has two orientations, and collapsing all \\(k\\) edges leaves \\(n-k\\) objects to permute. The number of \\(k\\)-edge subsets with \\(r\\) runs is\n\\[\n\\binom{k-1}{r-1}\\binom{n-k}{r}.\n\\]\nConsequently\n\\[\na_n=n!+\\sum_{k=1}^{n-1}(-1)^k(n-k)!\n\\sum_{r=1}^{k}2^r\\binom{k-1}{r-1}\\binom{n-k}{r}. \\tag{3}\n\\]\n\nRearranging (3) as a formal power series gives\n\\[\nA(x)=\\sum_{n\\geq0}a_nx^n\n=\\sum_{m\\geq0}m!\\left(\\frac{x(1-x)}{1+x}\\right)^m. \\tag{4}\n\\]\nIf \\(F(z)=\\sum_{m\\geq0}m!z^m\\), then\n\\[\nz^2F'(z)+(z-1)F(z)+1=0.\n\\]\nSubstitute \\(z=x(1-x)/(1+x)\\) in this formal identity and extract coefficients. This yields\n\\[\na_n=(n+1)a_{n-1}-(n-2)a_{n-2}-(n-5)a_{n-3}+(n-3)a_{n-4}\n\\]\nfor \\(n\\geq4\\), starting with \\(1,1,0,0\\).\n\nThe first positive terms are\n\\[\n2,14,90,646,5242,47622,479306,5296790,63779034,831283558,\n\\]\nat sizes 4 through 13. This is OEIS A002464, known as Hertzsprung's problem and as permutations without rising or falling successions.",
  "status": "established",
  "evidence_grade": "sourced",
  "scope": {
    "kind": "universal",
    "statement": "the number of permutations of each finite size with no rising or falling succession"
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "source_only",
    "kind": "claim",
    "citation": {
      "url": "https://oeis.org/A002464",
      "locator": "OEIS A002464 definition, formulas, and references; Riordan (1965); Flajolet and Sedgewick, Analytic Combinatorics (2009), page 373"
    },
    "missing": [
      "source",
      "command",
      "runtime",
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://oeis.org/A002464",
    "locator": "OEIS A002464 definition, formulas, and references; Riordan (1965); Flajolet and Sedgewick, Analytic Combinatorics (2009), page 373"
  },
  "models": [],
  "relations": [
    {
      "slug": "R588",
      "title": "The avoidance probability is strictly increasing for every n at least 4",
      "object_type": "claim",
      "relation": "supports",
      "direction": "outgoing"
    },
    {
      "slug": "R585",
      "title": "Exact recurrence, inclusion-exclusion, and brute-force verifier",
      "object_type": "artifact",
      "relation": "tests",
      "direction": "incoming"
    },
    {
      "slug": "R586",
      "title": "The counts and recurrence are classical Hertzsprung material",
      "object_type": "attempt",
      "relation": "informs",
      "direction": "incoming"
    },
    {
      "slug": "permutation-no-consecutive-adjacency-monotone",
      "title": "permutation no consecutive adjacency monotone",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}