{"id":"861fd36e-ef8e-4df6-9fea-fd57a008c6b1","arxiv_id":"1908.07658","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"k-Naples parking functions are counted recursively, characterized for k=1 by a map to classical parking functions, and bijected to signature Dyck paths.","lead":"This paper defines k-Naples parking functions, where a car whose preferred spot is taken may back up to k spaces before driving forward. It proves a recursive counting formula, gives a test for the k=1 case, and connects decreasing examples to a family of lattice paths.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1.1's proof assumes without proof that the left-block and right-block parking assignments factor independently; the counts |PF_{i,k}| and |B_{n-i,k}| are asserted, not derived, and this is load-bearing.","rationale":"The central claim is the recursion in Theorem 1.1. The reader's weakest assumption is exactly where the proof is incomplete: the factorization of the count into a left block, a right block, and car n+1's preference is asserted without proving that the two blocks do not interact through the reserved spot i+1. I traced the argument: if spot i+1 remains empty until the last car, then any car with preference > i that would back into spots ≤ i must first encounter i+1 and park there, and any car with preference ≤ i that cannot find a spot in 1..i will move forward into i+1. Consequently the left block's preferences are necessarily in [i] and form a k-Naples parking function of length i, and the right block's preferences must be drawn from the contained set B_{n-i,k}. These facts are true but are not stated or proved in the paper; the proof jumps from the definition of S to the factors. I also verified that the recursion reproduces the table values for n up to 4, which is consistent with the claim but does not replace the missing lemma. Because the gap is fillable and the result appears correct, the conditional verdict is appropriate. The paper should add a lemma proving the block independence and clarifying the definition of B_{n,k} (Def. 3.2), whose wording is vague. The separate weakness in the proof of Theorem 1.2 does not affect the main recursion, though it should also be addressed.","tokens_in":14401,"tokens_out":23062,"duration_ms":180491,"concrete_test":"For n=4 and n=5, k=1 and k=2, brute-force enumerate all preferences in [n+1]^{n+1} and simulate the k-Naples rule, recording for each preference the final parking spot of car n+1 and the set of spots occupied by the first n cars. For each i with 0≤i≤n and each subset S of {1,...,n} of size i, count the preferences where car n+1 parks at i+1 and the cars in S occupy exactly spots 1..i. Compare this count with C(n,i) * |PF_{i,k}| * |B_{n-i,k}| * min(i+1+k,n+1), where |B_{m,k}|=(m+1)^{m-1} and |PF_{i,k}| is computed from the same enumeration. If the counts match for all i, the missing factorization is true; any mismatch invalidates the recursion.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 1.1 (Section 3, Eq. (2)) fixes S, the cars that park to the left of spot i+1, and asserts that the number of preferences for S is |PF_{i,k}| and that the complement's preferences avoiding spot i+1 are exactly B_{n-i,k}, with |B_{n-i,k}|=(n-i+1)^{n-i-1} from Lemma 3.4. Both assertions are load-bearing and neither is proved. They require that no left-parking car can have a preference east of the cut, and no right-parking car can occupy the reserved spot i+1. Under the k-Naples rule a car with preference > i might back into spot i or below, but only if the intervening spot i+1 is already occupied; since i+1 is empty until car n+1 arrives, such a car would park in i+1 first. Similarly, a car with preference ≤ i that exhausts spots 1..i would proceed east into i+1. Hence the block decomposition is plausible, but the paper states it in one sentence ('the number of ways ... is ... exactly B_{n-i,k}'). Without this independence lemma, the recursion could be counting preferences that violate the reservation of spot i+1 or missing valid ones. Definition 3.2 of B_{n,k} is also too terse to establish the needed equivalence with the circular spot-0 construction in Lemma 3.4.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces k-Naples parking functions, in which a car whose preferred spot is occupied may first back up up to k spaces before continuing east. The authors prove three main results: a recursion (Theorem 1.1) for the number |PF_{n+1,k}| of k-Naples parking functions, a characterization of the k=1 case via a map T to classical parking functions (Theorem 1.2), and a bijection between decreasing k-Naples parking functions and k-lattice paths (Theorem 1.3). The recursion is checked against a table of values computed by code posted on GitHub. The paper also gives a Pollak-style counting argument for a set of 'contained' parking functions and a bijection for the top two diagonal cases. The overall narrative is clear and the conjectured family is natural, but the proof of the main recursion and the proof of the k=1 characterization contain gaps that need to be repaired before the claims are fully established.","tokens_in":14720,"tokens_out":27827,"duration_ms":274228,"significance":"If the gaps are repaired, the paper would be a worthwhile contribution: the recursion genuinely interpolates between the classical parking-function count (n+1)^{n-1} at k=0 and the full set n^n at k>=n-1, the circular-counting idea is elegant, and the lattice-path bijection gives a new enumerative handle on decreasing k-Naples parking functions. The computational table and the GitHub code are a useful check and a reproducible complement to the proofs. The paper also identifies several natural open problems and gives explicit OEIS connections. The main deficits are in proof completeness rather than in the plausibility of the results.","major_comments":[{"comment":"The proof asserts, after fixing the subset S of cars that park to the left of spot i+1, that the number of preference assignments to S is |PF_{i,k}| and that the number of assignments to the complement is |B_{n-i,k}|, without proving either factorization. For S, one must show that no car in S can have a preference east of spot i+1, and that the induced parking process on spots 1 through i is exactly the k-Naples process on i cars; because spot i+1 is empty until the last car, this is plausible but not automatic. For the complement, one must show that after relabeling spots i+2 through n+1 as 1 through n-i, the condition 'these cars avoid parking in spot i+1' is exactly the contained-parking condition in Definition 3.2. These two factors are the core of the recursion, so Eq. (2) is not established by the present argument.","section":"Section 3, Eq. (2), proof of Theorem 1.1"},{"comment":"Definition 3.2 is not well-formed as written: the condition 'if cars c1,...,c_{i-1} have already filled spaces 1,...,a_i, then there is no car c_i with a parking preference 1 <= a_i <= k' uses i both as a running index and as the length parameter, and does not clearly define the set B_{n,k}. Lemma 3.4 then states |B_{n,k}|=(n+1)^{n-1}; because the defining set is ambiguous, this count is not verifiable as stated. The proof of Lemma 3.4 also switches inconsistently between 'spot 0' and 'spot n+1' in the circular construction, and it asserts the equivalence between B_{n,k} and 'the cars park leaving the extra spot empty' without proof. This is load-bearing, since Eq. (2) uses the value |B_{n-i,k}|=(n-i+1)^{n-i-1}.","section":"Section 3, Definition 3.2 and Lemma 3.4"},{"comment":"The forward direction argues that if car c_i can park under the Naples rule, then there is an empty spot q between a_i-1 and n, and concludes that c_i can park under the classical rule with preference b_i in T(alpha). This ignores that the set of occupied spots when c_i arrives is different in the two processes: earlier cars may occupy different spots under the Naples rule than under the classical rule, so q need not be empty in the T(alpha) process. The converse direction has the same problem in reverse. The proof needs an invariant relating the partial parking configuration of alpha to that of T(alpha), or a different argument. As written, the characterization of Naples parking functions is not established.","section":"Section 4, proof of Theorem 1.2"}],"minor_comments":[{"comment":"The text says 'tau(a1)=a1=4', but for alpha=(2,4,4,1) the first entry is 2, so the example should read tau(a1)=2.","section":"Example 4.2"},{"comment":"The paragraph following Lemma 3.4 refers to 'the proof of Theorem 3.4', but the result is numbered Lemma 3.4.","section":"Lemma 3.4"},{"comment":"The proof only analyzes the last car. To conclude beta in PF_{n,n-2}, it should also justify that when b_n != n, no earlier car ever uses the full n-1 backward steps; otherwise the earlier cars' parking positions could change when k is reduced. This is likely repairable but should be stated.","section":"Lemma 2.2"},{"comment":"The equivalence between the path condition and the inequality a_i <= min(n,n+k+1-i) is stated without explaining the coordinate convention; the proof checks the bound at the right endpoint of each east step, and this convention should be made explicit in Definition 5.3.","section":"Section 5, proof of Theorem 1.3"},{"comment":"There are several minor typographical issues, including 'Cellabos' for 'Ceballos' and an incomplete author listing in reference [9]; these should be corrected in revision.","section":"General presentation"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe new object here is the k-Naples parking function, which interpolates between classical parking functions (k=0) and all preference lists (k≥n-1). That is a natural idea, and the paper gives a recursive formula (Theorem 1.1), a characterization for k=1 (Theorem 1.2), and a bijection with k-lattice paths (Theorem 1.3). The recursion and the lattice path bijection look right to me; the small cases in Table 1 check out, and the Pollak-style argument for contained parking functions (Lemma 3.4) is a nice adaptation.\n\nThe main soft spot is the proof of Theorem 1.1. The block decomposition—split cars into those parking left of reserved spot i+1 and those parking right—is correct in substance. A car with preference east of i+1 would park in i+1 before ever reaching the left block, because i+1 stays empty; so left-block preferences are indeed exactly PF_{i,k}. Similarly, right-block cars must have preferences at least i+2, and after shifting they are exactly the contained parking functions B_{n-i,k}. But the paper states both identifications in a sentence apiece and never proves the independence. A referee should ask for a lemma that pins down these two equivalences. It's a gap in exposition, not a fatal error—the recursion reproduces the table and the reasoning is recoverable—but it is load-bearing and needs to be written out.\n\nTheorem 1.2 has a more serious proof problem. The map T is a nice idea, and examples support the characterization, but the proof that α being a Naples parking function implies T(α) is a classical parking function does not go through. It argues that each car can park because \"there must be an empty spot between a_i-1 and n,\" but the occupancy pattern in the classical process with preferences T(α) is not the same as in the Naples process with α. Previous cars park differently, so the same spot may not be available. The converse has the same issue. This needs a real proof, probably by induction on cars or via the increasing rearrangement condition.\n\nThe lattice path bijection (Theorem 1.3) is more solid. The proof is a bit informal, especially the \"most optimal\" contradiction, but the condition a_i ≤ min(n, n+k+1-i) is the right one and the construction is clear.\n\nWho is this for? Enumerative combinatorists working on parking functions and lattice paths. It doesn't resolve any long-open problem, but it gives a new family with a computable recursion and a connection to signature Dyck paths. I'd send it to a serious referee, with the expectation of heavy revision on Sections 3 and 4.\n\nBest,\n[Your name]","headline":"A useful new family of parking functions with a plausible recursion, but two proofs need work before the results are fully trustworthy.","tokens_in":123,"tokens_out":9170,"would_cite":true,"duration_ms":726576,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05A15","05A19"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves a recursive formula that counts $k$-Naples parking functions, in which a car whose preferred spot is taken may first back up to $k$ spaces before driving on.","keywords":["parking functions","k-Naples parking functions","backward movement parking rule","contained parking functions","signature Dyck paths","k-lattice paths","recursive enumeration","circle parking argument"],"falsifier":"Brute-force all $7^7$ length-7 preferences under the $1$-Naples rule, record the final parking spot of the seventh car, and compare the number landing in each spot $i+1$ with the summand $\\binom{6}{i}\\min(i+2,7)|PF_{i,1}|(7-i)^{5-i}$ from Theorem 1.1; a mismatch for any $i$ would show the independent-left-block assumption fails.","tokens_in":14263,"feed_emoji":"🚗","tokens_out":14082,"duration_ms":119842,"temperature":0.7,"pith_summary":"The paper introduces $k$-Naples parking functions: parking preferences for $n$ cars in which a car that finds its preferred spot occupied may first check up to $k$ spaces to the west before driving east. Its central result is a recursion that determines the number of these preferences for every length $n$ and every $0\\le k\\le n-1$, interpolating between the classical parking-function count $(n+1)^{n-1}$ at $k=0$ and the full set $n^n$ when $k\\ge n-1$. The paper also proves that a preference is a $1$-Naples parking function exactly when a simple transformation of it is a classical parking function, and it bijects decreasing $k$-Naples parking functions with $k$-lattice paths, a family of signature Dyck paths. A sympathetic reader would care because the recursion turns a new generalization into a sequence that can be computed exactly and connected to known combinatorial families.","feed_headline":"One recursion counts all k-step-backup parking functions","feed_subtitle":"It interpolates between classical parking functions and every possible preference list.","key_machinery":"The load-bearing mechanism is a two-sided decomposition of the parking lot at the place where the last car parks. The cars ending up west of that place form a $k$-Naples parking function of length $i$; the cars ending up east form a contained $k$-Naples parking function, defined as one that would leave an extra spot $0$ west of spot $1$ empty. The count of contained functions is $(n+1)^{n-1}$ for every $k$, obtained by arranging $n+1$ spots on a circle, parking all $n$ cars, and rotating preferences so that spot $0$ is the one left empty; this circle step is what converts the east block into the factor $(n-i+1)^{n-i-1}$. For the $k=1$ characterization the central object is the map $T$ that subtracts one from a preferred spot the moment that spot has already been claimed earlier in the tuple, and for the lattice-path result it is the $k$-lattice path, a Dyck path whose height may exceed the diagonal by up to $k$.","core_discovery":"The central claim is Theorem 1.1: for $0\\le k\\le n-1$, the number of $k$-Naples parking functions of length $n+1$ is $$|PF_{n+1,k}|=\\sum_{i=0}^n \\binom{n}{i}\\min(i+1+k,n+1)|PF_{i,k}|(n-i+1)^{n-i-1}.$$ The proof fixes the spot $i+1$ where the last car parks, splits the earlier $n$ cars into those that end up west and east of that spot, counts the west block as a $k$-Naples parking function of length $i$, the east block as a contained $k$-Naples parking function (one that would leave an extra west spot empty), and counts the last car's allowed preferences as $\\min(i+1+k,n+1)$. For $k=1$ the paper proves that a preference $\\alpha$ is a Naples parking function exactly when the map $T$ that lowers every repeated preferred entry by $1$ sends $\\alpha$ to a classical parking function, and for decreasing preferences it gives a bijection to $k$-lattice paths, i.e. Dyck paths allowed to stay up to $k$ units above the diagonal.","pith_inferences":["The recursion's shape mirrors the set-partition and labeled-forest recurrences, so one could extract asymptotic growth rates for $|PF_{n,k}|$ from its dominant summand; the paper does not carry this out.","The map $T$ may generalize to $k>1$ by lowering entries that have already appeared in a block of size $k$; if such a map exists, it would give membership tests for all $k$, not just $k=1$.","The experimental observation that the largest gain $|PF_{n,k}\\setminus PF_{n,k-1}|$ occurs at $k=1$ suggests a stronger statement: the incremental benefit of backward flexibility is greatest for the very first step, and a proof would likely use the recursion to bound successive differences.","Since $k$-lattice paths with this signature have known counts only for small $k$, the bijection points to a family of lattice-path counts whose uniform enumeration is open; deriving it would also enumerate decreasing $k$-Naples parking functions."],"forward_implications":["For every pair $(n,k)$ with $0\\le k\\le n-1$, the recursion determines $|PF_{n,k}|$ by a finite computation, so no exhaustive test of $n^n$ preferences is needed.","At $k=0$ the formula reduces to the classical recursion for parking functions, and at $k=n-1$ it yields $n^n$, so the two endpoints of the interpolation are consistent.","The closed forms $|PF_{n,n-1}|=n^n$ and $|PF_{n,n-2}|=n^n-n^{n-2}$ pin down the top two diagonals of the enumeration table, leaving the intermediate cases to the recursion.","The transformation $T$ gives a membership test for $1$-Naples parking functions: apply the classical increasing-rearrangement criterion to $T(\\alpha)$.","The bijection in Theorem 1.3 means decreasing $k$-Naples parking functions are counted by the number of signature Dyck paths with signature $(k+1,2,\\ldots,2,1,\\ldots,1)$, matching the known sequences listed for $k=1,2,3$."],"supporting_citations":[{"why":"proves the classical parking-function count and gives the recursion that Theorem 1.1 generalizes.","marker":"[5]"},{"why":"supplies the circle technique used to prove Lemma 3.4 that contained parking functions number $(n+1)^{n-1}$.","marker":"[4]"},{"why":"defines signature Dyck paths, the family with which $k$-lattice paths are identified in Theorem 1.3.","marker":"[3]"},{"why":"introduces the Naples parking rule that this paper extends to $k$ backward steps.","marker":"[1]"}],"fun_headline_variants":["Count all k-step-backup parking functions with one recursion","Cars back up k spots: new counting formula for Naples parking","k-Naples: a recursion that spans all backup allowances","Generalized parking: recursion for backward-moving cars","From classical to complete freedom: count via recursion"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The recursion's count of the west block assumes that the cars that end up in the first $i$ spots have preferences forming a $k$-Naples parking function of length $i$ on their own, with no car preferring a spot east of the cut and then backing into that block.","fun_headline_variants_meta":{"raw":{"variants":["Count all k-step-backup parking functions with one recursion","Cars back up k spots: new counting formula for Naples parking","k-Naples: a recursion that spans all backup allowances","Generalized parking: recursion for backward-moving cars","From classical to complete freedom: count via recursion"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000611,"raw_usage":{"total_tokens":2923,"prompt_tokens":1102,"completion_tokens":1821,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":718,"completion_tokens_details":{"reasoning_tokens":1741}},"tokens_in":718,"tokens_out":1821,"duration_ms":13288,"temperature":1.0,"reasoning_tokens":1741,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:02:32.565928+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Brute-force all $7^7$ length-7 preferences under the $1$-Naples rule, record the final parking spot of the seventh car, and compare the number landing in each spot $i+1$ with the summand $\\binom{6}{i}\\min(i+2,7)|PF_{i,1}|(7-i)^{5-i}$ from Theorem 1.1; a mismatch for any $i$ would show the independent-left-block assumption fails.","supporting_citations":[{"cited_title":"Konheim and Benjamin Weiss, An occupancy discipline and applications , Siam Journal on Applied Mathematics - SIAMAM 14 (196611).↑1, 2, 6","cited_arxiv_id":null,"evidence_quote":"proves the classical parking-function count and gives the recursion that Theorem 1.1 generalizes."},{"cited_title":"10 (1974), 10–22","cited_arxiv_id":null,"evidence_quote":"supplies the circle technique used to prove Lemma 3.4 that contained parking functions number $(n+1)^{n-1}$."},{"cited_title":"Gonz´ alez D’Le´ on,Signature catalan combinatorics , Journal of Combinatorics 10 (2019), 725–773.↑4, 10, 12","cited_arxiv_id":null,"evidence_quote":"defines signature Dyck paths, the family with which $k$-lattice paths are identified in Theorem 1.3."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"introduces the Naples parking rule that this paper extends to $k$ backward steps."}],"review_version":1}