Permutation Invariant Parking Assortments

DOI10.54550/ECA2024V4S1R4MaRDI QIDQ6415911zbMATH OpenFDO

Authors Douglas Chen, Pamela E. Harris, J. Carlos Martínez Mori, Eric Pabón-Cancel, Gabriel Sargent

Publication date 2 November 2022

Full work available at URL https://doi.org/10.54550/ECA2024V4S1R4

Exact enumeration problems, generating functions (05A15) Combinatorial identities, bijective combinatorics (05A19) Group actions on combinatorial structures (05E18)

Abstract: We introduce parking assortments, a generalization of parking functions with cars of assorted lengths. In this setting, there are

n i n m a t h b b N

cars of lengths

m a t h b f y = (y_{1}, y_{2}, l d o t s, y_{n}) i n m a t h b b N^{n}

entering a one-way street with

m = s u m_{i = 1}^{n} y_{i}

parking spots. The cars have parking preferences

m a t h b f x = (x_{1}, x_{2}, l d o t s, x_{n}) i n [m]^{n}

, where

[m] := 1, 2, l d o t s, m

, and enter the street in order. Each car

i i n [n]

, with length

y_{i}

and preference

x_{i}

, follows a natural extension of the classical parking rule: it begins looking for parking at its preferred spot

x_{i}

and parks in the first

y_{i}

contiguously available spots thereafter, if there are any. If all cars are able to park under the preference list

m a t h b f x

, we say

m a t h b f x

is a parking assortment for

m a t h b f y

. Parking assortments also generalize parking sequences, introduced by Ehrenborg and Happ, since each car seeks for the first contiguously available spots it fits in past its preference. Given a parking assortment

m a t h b f x

for

m a t h b f y

, we say it is permutation invariant if all rearrangements of

m a t h b f x

are also parking assortments for

m a t h b f y

. While all parking functions are permutation invariant, this is not the case for parking assortments in general, motivating the need for a characterization of this property. Although obtaining a full characterization for arbitrary

n i n m a t h b b N

and

m a t h b f y i n m a t h b b N^{n}

remains elusive, we do so for

n = 2, 3

. Given the technicality of these results, we introduce the notion of minimally invariant car lengths, for which the only invariant parking assortment is the all ones preference list. We provide a concise, oracle-based characterization of minimally invariant car lengths for any

n i n m a t h b b N

. Our results around minimally invariant car lengths also hold for parking sequences.

This page was built for publication: Permutation Invariant Parking Assortments

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6415911)