249:
301:
preferences for which the first and third drivers both prefer the second space, while the other two drivers both prefer the first space. The first driver parks in space 2, the second in space 1, and the third in space 3 (because space 2 is taken). The fourth driver starts looking for a free space at space 1, but doesn't find it until space 4; all previous spaces were taken. The sequence (3,3,1,3) is not a parking function: too many drivers prefer space 3, so the last driver starts looking for a space after already passing the only free space, and will be unable to park.
300:
parking spaces, with each driver having a preferred parking space. Each driver travels until reaching their preferred space, and then parks in the first available spot. A parking function describes preferences for which all cars can park. For instance, the parking function (2,1,2,1) describes
703:
Much research has studied the number of parking functions of a special form. As a very simple special case, the parking functions that allow each car to park in its own preferred spot are exactly the
386:
698:
585:
540:
445:
649:
611:
481:
412:
158:. That is, it must contain at least one 1, at least two values that are 1 or 2, at least three values that are 1, 2, or 3, etc. Equivalently, if the sequence is
501:
338:
298:
278:
220:
200:
180:
156:
136:
116:
96:
76:
56:
868:; Meyles et al credit the connection between parking functions and ordered Bell numbers to a 2021 bachelor's thesis by Kimberly P. Hadaway of Williams College
542:
choices for the preferences, each of which leaves one vacant space. All spaces are symmetric to each other, so by symmetry, there are
884:
711:. The parking functions that allow each car to park either in its preferred spot or in the next spot are counted by the
613:
as the vacant space. These choices are exactly the parking functions. The parking functions can also be placed in
343:
503:
cars will always be able to park, no matter what preference each driver has for their starting space. There are
312:, a strategy for placing keys into a hash table that closely resembles the one-way parking strategy for cars.
784:
450:
658:
545:
823:
Konheim, Alan G.; Weiss, Benjamin (November 1966), "An occupancy discipline and applications",
506:
417:
248:
810:
766:
8:
712:
652:
628:
590:
460:
391:
858:
744:
486:
323:
283:
263:
205:
185:
165:
141:
121:
101:
81:
61:
41:
801:
159:
850:
832:
796:
754:
806:
762:
454:
253:
651:
vertices, one of which is designated as the root. This bijection, together with
853:; Jordaan, Richter; Kirby, Gordon Rojas; Sehayek, Sam; Spingarn, Ethan (2023),
622:
309:
878:
618:
27:
704:
457:
the following argument for this formula. On a circular one-way road with
260:
The name is explained by the following thought experiment. A sequence of
23:
758:
305:
304:
Parking functions also have a more serious application in the study of
735:
Yin, Mei (2023), "Parking functions: interdisciplinary connections",
708:
614:
836:
863:
749:
225:
For instance, there are 16 parking functions of length three:
655:
for the number of spanning trees, again shows that there are
118:
up to the sequence length, the sequence contains at least
848:
855:
Unit-interval parking functions and the permutohedron
661:
631:
593:
548:
509:
489:
463:
420:
394:
346:
326:
286:
266:
208:
188:
168:
144:
124:
104:
84:
64:
44:
280:
drivers in cars travel down a one-way street having
692:
643:
605:
579:
534:
495:
475:
439:
406:
380:
332:
292:
272:
214:
194:
174:
150:
130:
110:
90:
70:
50:
876:
78:positive integers, each in the range from 1 to
33:
822:
315:
202:th value of the sorted sequence is at most
320:The number of parking functions of length
862:
800:
779:
777:
775:
748:
587:choices for preferences that leave space
247:
783:
877:
772:
730:
728:
98:, with the property that, for every
842:
825:SIAM Journal on Applied Mathematics
734:
13:
816:
725:
14:
896:
789:Journal of Combinatorial Theory
737:Advances in Applied Probability
675:
662:
562:
549:
523:
510:
360:
347:
252:Parking along a one-way road (
16:Generalization of permutations
1:
885:Factorial and binomial topics
802:10.1016/S0021-9800(69)80039-6
787:(1969), "Ballots and trees",
718:
38:A parking function of length
381:{\displaystyle (n+1)^{n-1}.}
7:
693:{\displaystyle (n+1)^{n-1}}
580:{\displaystyle (n+1)^{n-1}}
34:Definition and applications
30:, a branch of mathematics.
10:
901:
241:(1,2,2), (2,1,2), (2,2,1),
238:(1,1,3), (1,3,1), (3,1,1),
235:(1,1,2), (1,2,1), (2,1,1),
232:(3,2,1), (2,1,3), (1,3,2),
229:(1,2,3), (2,3,1), (3,1,2),
535:{\displaystyle (n+1)^{n}}
316:Combinatorial enumeration
440:{\displaystyle 4^{2}=16}
138:values that are at most
22:are a generalization of
182:in the same range, the
849:Meyles, Lucas Chaves;
694:
645:
607:
581:
536:
497:
477:
441:
408:
382:
334:
294:
274:
257:
216:
196:
176:
152:
132:
112:
92:
72:
52:
695:
646:
608:
582:
537:
498:
478:
442:
409:
383:
335:
295:
275:
251:
217:
197:
177:
153:
133:
113:
93:
73:
53:
713:ordered Bell numbers
659:
629:
591:
546:
507:
487:
461:
418:
392:
344:
324:
284:
264:
206:
186:
166:
142:
122:
102:
82:
62:
42:
759:10.1017/apr.2022.49
700:parking functions.
644:{\displaystyle n+1}
606:{\displaystyle n+1}
476:{\displaystyle n+1}
407:{\displaystyle n=3}
690:
641:
603:
577:
532:
493:
473:
437:
404:
378:
330:
290:
270:
258:
212:
192:
172:
148:
128:
108:
88:
68:
48:
851:Harris, Pamela E.
707:, counted by the
496:{\displaystyle n}
388:For instance for
333:{\displaystyle n}
293:{\displaystyle n}
273:{\displaystyle n}
215:{\displaystyle i}
195:{\displaystyle i}
175:{\displaystyle i}
151:{\displaystyle i}
131:{\displaystyle i}
111:{\displaystyle i}
91:{\displaystyle n}
71:{\displaystyle n}
58:is a sequence of
51:{\displaystyle n}
20:Parking functions
892:
869:
867:
866:
846:
840:
839:
831:(6): 1266–1274,
820:
814:
813:
804:
781:
770:
769:
752:
732:
699:
697:
696:
691:
689:
688:
653:Cayley's formula
650:
648:
647:
642:
612:
610:
609:
604:
586:
584:
583:
578:
576:
575:
541:
539:
538:
533:
531:
530:
502:
500:
499:
494:
483:spaces, each of
482:
480:
479:
474:
446:
444:
443:
438:
430:
429:
413:
411:
410:
405:
387:
385:
384:
379:
374:
373:
339:
337:
336:
331:
299:
297:
296:
291:
279:
277:
276:
271:
221:
219:
218:
213:
201:
199:
198:
193:
181:
179:
178:
173:
162:, then for each
157:
155:
154:
149:
137:
135:
134:
129:
117:
115:
114:
109:
97:
95:
94:
89:
77:
75:
74:
69:
57:
55:
54:
49:
900:
899:
895:
894:
893:
891:
890:
889:
875:
874:
873:
872:
847:
843:
837:10.1137/0114101
821:
817:
782:
773:
733:
726:
721:
678:
674:
660:
657:
656:
630:
627:
626:
592:
589:
588:
565:
561:
547:
544:
543:
526:
522:
508:
505:
504:
488:
485:
484:
462:
459:
458:
455:Henry O. Pollak
425:
421:
419:
416:
415:
414:this number is
393:
390:
389:
363:
359:
345:
342:
341:
325:
322:
321:
318:
285:
282:
281:
265:
262:
261:
254:Portobello Road
207:
204:
203:
187:
184:
183:
167:
164:
163:
143:
140:
139:
123:
120:
119:
103:
100:
99:
83:
80:
79:
63:
60:
59:
43:
40:
39:
36:
17:
12:
11:
5:
898:
888:
887:
871:
870:
841:
815:
795:(4): 408–411,
771:
743:(3): 768–792,
723:
722:
720:
717:
687:
684:
681:
677:
673:
670:
667:
664:
640:
637:
634:
623:complete graph
619:spanning trees
602:
599:
596:
574:
571:
568:
564:
560:
557:
554:
551:
529:
525:
521:
518:
515:
512:
492:
472:
469:
466:
436:
433:
428:
424:
403:
400:
397:
377:
372:
369:
366:
362:
358:
355:
352:
349:
329:
317:
314:
310:linear probing
289:
269:
246:
245:
242:
239:
236:
233:
230:
211:
191:
171:
147:
127:
107:
87:
67:
47:
35:
32:
15:
9:
6:
4:
3:
2:
897:
886:
883:
882:
880:
865:
860:
856:
852:
845:
838:
834:
830:
826:
819:
812:
808:
803:
798:
794:
790:
786:
785:Riordan, John
780:
778:
776:
768:
764:
760:
756:
751:
746:
742:
738:
731:
729:
724:
716:
714:
710:
706:
701:
685:
682:
679:
671:
668:
665:
654:
638:
635:
632:
624:
620:
616:
600:
597:
594:
572:
569:
566:
558:
555:
552:
527:
519:
516:
513:
490:
470:
467:
464:
456:
452:
448:
434:
431:
426:
422:
401:
398:
395:
375:
370:
367:
364:
356:
353:
350:
327:
313:
311:
307:
302:
287:
267:
255:
250:
243:
240:
237:
234:
231:
228:
227:
226:
223:
209:
189:
169:
161:
145:
125:
105:
85:
65:
45:
31:
29:
28:combinatorics
25:
21:
854:
844:
828:
824:
818:
792:
788:
740:
736:
705:permutations
702:
451:John Riordan
449:
319:
303:
259:
224:
37:
24:permutations
19:
18:
453:credits to
340:is exactly
306:hash tables
26:studied in
864:2305.15554
750:2107.01767
719:References
709:factorials
256:in London)
683:−
617:with the
615:bijection
570:−
368:−
308:based on
879:Category
244:(1,1,1).
811:0234843
767:4624028
809:
765:
160:sorted
859:arXiv
745:arXiv
625:with
621:on a
833:doi
797:doi
755:doi
881::
857:,
829:14
827:,
807:MR
805:,
791:,
774:^
763:MR
761:,
753:,
741:55
739:,
727:^
715:.
447:.
435:16
222:.
861::
835::
799::
793:6
757::
747::
686:1
680:n
676:)
672:1
669:+
666:n
663:(
639:1
636:+
633:n
601:1
598:+
595:n
573:1
567:n
563:)
559:1
556:+
553:n
550:(
528:n
524:)
520:1
517:+
514:n
511:(
491:n
471:1
468:+
465:n
432:=
427:2
423:4
402:3
399:=
396:n
376:.
371:1
365:n
361:)
357:1
354:+
351:n
348:(
328:n
288:n
268:n
210:i
190:i
170:i
146:i
126:i
106:i
86:n
66:n
46:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
