The stable defective Kreweras number formula

Exact stable formula for every defective Kreweras number

Let $m,n\geq1$, let $\lambda\vdash m$ have length $k$, and put

$$\mu_j=\#\{i:\lambda_i=j\} \qquad(1\leq j\leq m).$$

For a nondecreasing preference list $\mathbf{x}=(x_1,\ldots,x_m)$, define its predefect by

$$\operatorname{pdft}(\mathbf{x}) =\max_{1\leq i\leq m}(x_i-i).$$

Following Definition 3.5 of the cited paper, $\operatorname{Krew}_{d,n}(\lambda)$ counts nondecreasing lists in $[n+1]^m$ whose positive multiplicities, arranged in decreasing order, form $\lambda$ and which satisfy

$$\max\{\operatorname{pdft}(\mathbf{x}),0\}=d.$$

We prove that, for every $d\geq0$ and every $n\geq m+d-1$,

$$\boxed{\displaystyle \operatorname{Krew}_{d,n}(\lambda) =\frac{m+dk}{m+d}\, \frac{1}{m+d+1} \binom{m+d+1} {m+d+1-k,\mu_1,\ldots,\mu_m}.}$$

In particular, the value is independent of $n$ throughout the entire conjectured stable range.

The marked cycle lemma

We use the following classical cycle lemma. Suppose that $b_1,\ldots,b_N$ are integers satisfying

$$b_i\leq1, \qquad \sum_{i=1}^N b_i=r>0.$$

Among the $N$ cyclic shifts, counted by their marked starting positions even when the word is periodic, exactly $r$ have every nonempty partial sum strictly positive.

For completeness, set

$$P_0=0, \qquad P_j=\sum_{i=1}^j b_i, \qquad M=\min_{0\leq j<N}P_j.$$

For each integer $q$ with $M\leq q\leq M+r-1$, let $j_q<N$ be the last index satisfying $P_{j_q}=q$. Such an index exists: after reaching its minimum, the walk eventually reaches $P_N=r$, and upward increments are at most $1$. No subsequent value $P_i$ with $j_q<i\leq N$ can be at most $q$; otherwise, before reaching $r>q$, the walk would have to revisit $q$, contradicting the choice of $j_q$. Every wrapped value satisfies

$$r+P_i\geq r+M>q.$$

Consequently, the cyclic shift starting immediately after $j_q$ has strictly positive partial sums. Conversely, if a shift starting after $j$ has this property, then $j$ is the last occurrence of $P_j$, and a minimum must occur no later than $j$. Applying strict positivity to the corresponding wrapped minimum gives

$$M\leq P_j<M+r.$$

Thus $j=j_q$ for exactly one of the $r$ indicated levels. This proves the marked cycle lemma.

Cumulative enumeration by occupancy words

For $d\geq0$, let $F_d(\lambda)$ denote the number of nondecreasing lists having multiplicity partition $\lambda$ and satisfying

$$\operatorname{pdft}(\mathbf{x})\leq d.$$

Every such list satisfies

$$x_i\leq i+d, \qquad x_m\leq m+d.$$

Therefore, whenever $n\geq m+d-1$, the requirement $x_i\in[n+1]$ imposes no additional restriction. Put

$$N=m+d+1, \qquad r=d+1, \qquad \alpha_t=\#\{i:x_i=t\} \quad(1\leq t\leq N).$$

The multiset of the $\alpha_t$ consists of the $k$ parts of $\lambda$ and $N-k$ zeros. In particular,

$$\sum_{t=1}^N\alpha_t=m, \qquad \alpha_N=0.$$

Write

$$A_t=\sum_{j=1}^t\alpha_j, \qquad S_t=A_t-t.$$

For $0\leq t<N$, the inequalities $x_i\leq i+d$ for every $i$ are equivalent to

$$A_t\geq t-d, \qquad\text{or equivalently}\qquad S_t\geq-d>-r.$$

Indeed, if $A_t<t-d$, then the $(t-d)$th list entry is greater than $t$, violating its required upper bound. Conversely, if $x_i>i+d$, taking $t=i+d<N$ gives $A_t<i=t-d$. At the endpoint,

$$S_N=m-N=-r.$$

Now reverse the occupancy word and set

$$b_j=1-\alpha_{N+1-j} \qquad(1\leq j\leq N).$$

These integers satisfy $b_j\leq1$ and $\sum_{j=1}^N b_j=r$. Moreover, their partial sums satisfy

$$\sum_{j=1}^s b_j =r+S_{N-s} \qquad(1\leq s\leq N).$$

Thus $\mathbf{x}$ has predefect at most $d$ exactly when every partial sum of the reversed word is strictly positive. Strict positivity of the first partial sum also forces $\alpha_N=0$, so no additional terminal restriction is needed.

There are

$$\binom{N}{N-k,\mu_1,\ldots,\mu_m}$$

distinct occupancy words with the prescribed multiplicity multiset. The marked cycle lemma and double counting of pairs consisting of a word and a marked cyclic starting position therefore give

$$\boxed{\displaystyle F_d(\lambda) =\frac{d+1}{m+d+1} \binom{m+d+1}{m+d+1-k,\mu_1,\ldots,\mu_m}.}$$

Counting marked starts makes this argument valid without any aperiodicity assumption, including when some parts of $\lambda$ coincide.

Extraction of the exact predefect

Set $F_{-1}(\lambda)=0$. For every $d\geq0$,

$$\operatorname{Krew}_{d,n}(\lambda) =F_d(\lambda)-F_{d-1}(\lambda).$$

For $d=0$, this immediately gives

$$\operatorname{Krew}_{0,n}(\lambda) =\frac{1}{m+1} \binom{m+1}{m+1-k,\mu_1,\ldots,\mu_m}.$$

For $d\geq1$, the cumulative formula yields

$$\begin{aligned} F_d(\lambda)-F_{d-1}(\lambda) &=\frac{(d+1)(m+d)!} {(m+d+1-k)!\prod_{j=1}^m\mu_j!} -\frac{d(m+d-1)!} {(m+d-k)!\prod_{j=1}^m\mu_j!}\\ &=\frac{(m+dk)(m+d-1)!} {(m+d+1-k)!\prod_{j=1}^m\mu_j!}\\ &=\frac{m+dk}{m+d}\, \frac{1}{m+d+1} \binom{m+d+1} {m+d+1-k,\mu_1,\ldots,\mu_m}, \end{aligned}$$

which is precisely the conjectured formula.

The stability threshold cannot be lowered uniformly. For $\lambda=(1^m)$, all entries are strictly increasing, so $x_i-i$ is nondecreasing and exact predefect $d$ requires

$$x_m=m+d.$$

There are

$$\operatorname{Krew}_{d,n}(1^m) =\binom{m+d-1}{m-1}>0$$

in the stable range, whereas none of these lists exists if $n=m+d-2\geq1$.

The parameter $d$ here is the predefect parameter in Definition 3.5, not the actual number of cars failing to park when $m\neq n$. The source assumes $m,n\geq1$; the displayed rational formula is not defined for the empty-partition case $m=d=0$.

This proves Conjecture 3.15 of Rebecca E. Garcia, Pamela E. Harris, Alex Moon, Aaron Ortiz, Lauren J. Quesada, Cynthia Marie Rivera Sánchez, Dwight Anderson Williams II, and Alexander N. Wilson, The defective parking space and defective Kreweras numbers, arXiv:2405.14635v4, published in Discrete Mathematics 349 (2026), Article 115164, doi:10.1016/j.disc.2026.115164.