Skip to main content
MathOverflow

Return to Answer

Post Timeline

added 773 characters in body
Source Link
Badam Baplan
Badam Baplan
  • 1k
  • 8
  • 15

A nice example is Parking Functions. This is a well-known topic in combinatorics with connections ranging from spanning trees of graphs to non-crossing partitions to hyperplane arrangements to priority queues.
Our wise man will realize that the ostensibly linear setting I describe below would be significantly easier to handle if he lent us a placeholder camel which could offer us cyclic symmetry. This camel-on-loan will provide the structure to do a trivial calculation, and in the end, we can simply pluck out all the solutions that didn't involve it, discarding the rest.

(Although I could be cheeky and state the entire problem in terms of camels, I'll try to resist and be faithful to the normal presentation).

The situation for n = 12 is shown below. Supposing the next four shoppers $s_7$ thru $s_{10}$ were all both planning to park at space $8$ and get breakfast at Subway, they'll land at the $8$th, $10$th, and $11$th spots respectively, and the $10$th shopper will find a sandwich elsewhere. [![enter image description here][1]][1]enter image description here

To calculate the size of $P(n)$, you can scratch your head for a while thinking about the problem linearly, or you can exercise an "add one subtract one" trick — let's take the old wise man up on his offer and throw a camel into the mix:

Consider adding another space $n+1$ to the parking lot which glues"glues" together the two ends (so now shoppers that can't park in their preferred spot will go around in a circle til they find a place). That means that in our new arrangement, everyone can always park! Moreover, there's always one space left empty. Preferences for this augmented lot are encoded as $n$-tuples taking values as residue classes modulo $n+1$, so there are $(n+1)^n$ of them. The placement of the single unoccupied parking space is equidistributed, so $(n+1)^{n-1}$ preference tuples leave the $n+1$ spot vacant. We lastly verify that each of these preference tuples leaving the $n+1$ spot vacant, when taken at face-value, is a parking function:

Actually if I squint hard enough this almost seems vaguelyvaguely reminiscent of the general methodology of proving something about a topological space $X$ by porting a result on some compactification of $X$. [1]: https://i.sstatic.net/TzhH2.jpg$X.$

A nice example is Parking Functions.

The situation for n = 12 is shown below. Supposing the next four shoppers $s_7$ thru $s_{10}$ were all both planning to park at space $8$ and get breakfast at Subway, they'll land at the $8$th, $10$th, and $11$th spots respectively, and the $10$th shopper will find a sandwich elsewhere. [![enter image description here][1]][1]

To calculate the size of $P(n)$, you can scratch your head for a while thinking about the problem linearly, or you can exercise an "add one subtract one" trick:

Consider adding another space $n+1$ to the parking lot which glues together the two ends (so now shoppers that can't park in their preferred spot will go around in a circle til they find a place). That means that in our new arrangement, everyone can always park! Moreover, there's always one space left empty. Preferences for this augmented lot are encoded as $n$-tuples taking values as residue classes modulo $n+1$, so there are $(n+1)^n$ of them. The placement of the single unoccupied parking space is equidistributed, so $(n+1)^{n-1}$ preference tuples leave the $n+1$ spot vacant. We lastly verify that each of these preference tuples leaving the $n+1$ spot vacant, when taken at face-value, is a parking function:

Actually if I squint hard enough this almost seems vaguely reminiscent of the general methodology of proving something about a topological space $X$ by porting a result on some compactification of $X$. [1]: https://i.sstatic.net/TzhH2.jpg

A nice example is Parking Functions. This is a well-known topic in combinatorics with connections ranging from spanning trees of graphs to non-crossing partitions to hyperplane arrangements to priority queues.
Our wise man will realize that the ostensibly linear setting I describe below would be significantly easier to handle if he lent us a placeholder camel which could offer us cyclic symmetry. This camel-on-loan will provide the structure to do a trivial calculation, and in the end, we can simply pluck out all the solutions that didn't involve it, discarding the rest.

(Although I could be cheeky and state the entire problem in terms of camels, I'll try to resist and be faithful to the normal presentation).

The situation for n = 12 is shown below. Supposing the next four shoppers $s_7$ thru $s_{10}$ were all both planning to park at space $8$ and get breakfast at Subway, they'll land at the $8$th, $10$th, and $11$th spots respectively, and the $10$th shopper will find a sandwich elsewhere. enter image description here

To calculate the size of $P(n)$, you can scratch your head for a while thinking about the problem linearly, or you can exercise an "add one subtract one" trick — let's take the old wise man up on his offer and throw a camel into the mix:

Consider adding another space $n+1$ to the parking lot which "glues" together the two ends (so now shoppers that can't park in their preferred spot will go around in a circle til they find a place). That means that in our new arrangement, everyone can always park! Moreover, there's always one space left empty. Preferences for this augmented lot are encoded as $n$-tuples taking values as residue classes modulo $n+1$, so there are $(n+1)^n$ of them. The placement of the single unoccupied parking space is equidistributed, so $(n+1)^{n-1}$ preference tuples leave the $n+1$ spot vacant. We lastly verify that each of these preference tuples leaving the $n+1$ spot vacant, when taken at face-value, is a parking function:

Actually if I squint hard enough this almost seems vaguely reminiscent of the general methodology of proving something about a topological space $X$ by porting a result on some compactification of $X.$

Source Link
Badam Baplan
Badam Baplan
  • 1k
  • 8
  • 15

A nice example is Parking Functions.

Imagine a shopping plaza with $n$ parking spaces laid out linearly in front of the stores. In the morning, $n$ shoppers $s_i$ file into the plaza one at a time ($s_1$ arrives, then $s_2$, then $s_3$, etc.) each one having a strong preference for parking space $p_i$ in front of the store they are visiting.

The problem is that the parking lot is narrow — the flow of traffic is one way — and the shoppers are rather shortsighted and obstinate: shopper $s_i$ drives up to their preferred space $p_i$, and if they find it occupied, they keep going to the first available $p$ such that $p > p_i$; if no such $p$ exists, they get frustrated and shop elsewhere.

The situation for n = 12 is shown below. Supposing the next four shoppers $s_7$ thru $s_{10}$ were all both planning to park at space $8$ and get breakfast at Subway, they'll land at the $8$th, $10$th, and $11$th spots respectively, and the $10$th shopper will find a sandwich elsewhere. [![enter image description here][1]][1]

We can encode the preferences of the shoppers with an $n$-tuple $(p_1, p_2, \ldots, p_n)$. Now we denote by $P(n)$ the set of $n$-tuples encoding situations in which all $n$ shoppers will find a place to park — the parking functions of length $n$.

To calculate the size of $P(n)$, you can scratch your head for a while thinking about the problem linearly, or you can exercise an "add one subtract one" trick:

Consider adding another space $n+1$ to the parking lot which glues together the two ends (so now shoppers that can't park in their preferred spot will go around in a circle til they find a place). That means that in our new arrangement, everyone can always park! Moreover, there's always one space left empty. Preferences for this augmented lot are encoded as $n$-tuples taking values as residue classes modulo $n+1$, so there are $(n+1)^n$ of them. The placement of the single unoccupied parking space is equidistributed, so $(n+1)^{n-1}$ preference tuples leave the $n+1$ spot vacant. We lastly verify that each of these preference tuples leaving the $n+1$ spot vacant, when taken at face-value, is a parking function:

Suppose you considered a parking function as encoding preferences for the augmented circular lot. Since it was a parking function, the shoppers don't need to loop around in order to park, and the resultant arrangement leaves the $n+1$ space empty. Conversely, a preference tuple on the augmented lot that results in the $n+1$ space unoccupied was such that no shopper had a preference for the $n+1$ space, and no shopper ever did a loop around the lot (since they park as soon as possible), hence it's a parking function.

Thus we find $P(n) = (n+1)^{n-1}$ by thinking about an extra space gluing the ends of the parking lot together, and then showing that all the ways of avoiding that extra structure are the very objects we are enumerating.

Actually if I squint hard enough this almost seems vaguely reminiscent of the general methodology of proving something about a topological space $X$ by porting a result on some compactification of $X$. [1]: https://i.sstatic.net/TzhH2.jpg

Post Made Community Wiki by Badam Baplan