Enumerating parking completions using join and split (Q2188834): Difference between revisions

Summary: Given a strictly increasing sequence \(\mathfrak{t}\) with entries from \([n]:=\{1,\ldots,n\}\), a parking completion is a sequence \(\mathfrak{c}\) with \(|\mathfrak{t}|+|\mathfrak{c}|=n\) and \(|\{t\in \mathfrak{t}\mid t\leqslant i\}|+|\{c\in \mathfrak{c}\mid c\leqslant i\}|\geqslant i\) for all \(i\) in \([n]\). We can think of \(\mathfrak{t}\) as a list of spots already taken in a street with \(n\) parking spots and \(\mathfrak{c}\) as a list of parking preferences where the \(i\)-th car attempts to park in the \(c_i\)-th spot and if not available then proceeds up the street to find the next available spot, if any. A parking completion corresponds to a set of preferences \(\mathfrak{c}\) where all cars park.