פונקציית חניה

**פונקציית חנייה** היא עצם מתמטי ובעיה במתמטיקה בכלל ובקומבינטוריקה בפרט. (נקראת גם בשמות **בעיית הנהגים הגחמנים**, **בעיית הנשים הגחמניות** או **בעיית החניה**) הבעיה עוסקת במספר הדרכים לשבץ n עצמים ב-n מקומות, כאשר לכל עצם יש מקום מועדף, ועצם שהמקום המועדף עליו תפוס, מוסט באופן עקבי כלפי מעלה.

פונקציה, המתאימה נהגים למקומות החניה, כך שלכל נהג יש מקום חניה, קרויה **פונקציית חניה**. הדיון בפונקציות כאלה החל במאמר של קונהיים ווייס משנת 1966.

## הגדרה ויישומים
פונקציית חניה באורך n היא רצף של n מספרים טבעיים, כל אחד בטווח שבין 1 ל- n, עם המאפיין שעבור כל i מ-1 ועד n, הרצף מכיל לפחות i ערכים שהם לכל היותר i. כלומר, הוא חייב להכיל לפחות 1 אחד, לפחות שני ערכים שהם 1 או 2, לפחות שלושה ערכים שהם 1, 2 או 3 וכו'. באופן שקול, אם הרצף ממוין, אז עבור כל אחד i באותו הטווח, הערך ה-i של הרצף הממוין הוא לכל היותר i.

לדוגמה, ישנן 16 פונקציות חניה באורך שלוש:

: (1,2,3), (2,3,1), (3,1,2),
: (3,2,1), (2,1,3), (1,3,2),
: (1,1,2), (1,2,1), (2,1,1),
: (1,1,3), (1,3,1), (3,1,1),
: (1,2,2), (2,1,2), (2,2,1),
: (1,1,1).

[ממוזער|חניה לאורך כביש חד סטרי ([שוק פורטובלו|פורטובלו רואד בלונדון)]]
השם מוסבר על ידי הניסוי המחשבתי הבא. רצף של n נהגים במכוניות נוסעים ברחוב חד סטרי ובו n מקומות חניה, כאשר לכל נהג יש מקום חניה מועדף (ללא קשר להעדפות של הנהגים השונים). כל נהג נוסע עד להגעה למקום המועדף עליו, ולאחר מכן חונה במקום הפנוי הראשון ואם הוא תפוס, הוא ממשיך בנסיעה ומחפש מקום חניה אחר. הנהג אינו יכול לחזור אחורנית - ואם הוא לא מצא מקום פנוי, הוא יאלץ לוותר על החניה ולהתרחק מהמקום.  

הבעיה: אם כל נהג בוחר את ההעדפה שלו בנפרד, כמה אפשרויות יש שעבורן כל הנהגים יחנו בסוף התהליך? 

פונקציית חניה מתארת העדפות עבורן כל המכוניות יכולות לחנות.  לדוגמה, פונקציית החניה (2,1,2,1) מתארת העדפות שבהן הנהג הראשון והשלישי מעדיפים שניהם את המקום השני, בעוד ששני הנהגים האחרים מעדיפים שניהם את המקום הראשון. הנהג הראשון חונה במקום 2, השני במקום 1, והשלישי במקום 3 (מכיוון שמשבצת 2 תפוסה). הנהג הרביעי מתחיל לחפש מקום פנוי במקום 1, אך לא מוצא אותו עד במקום 4; כל המקומות הקודמים היו תפוסים. הרצף (3,3,1,3) אינו פונקציית חניה: נהגים רבים מדי מעדיפים את מקום חניה 3, כך שהנהג האחרון מתחיל לחפש מקום חניה לאחר שכבר עבר את המקום הפנוי היחיד, ולא יוכל לחנות. 

###### דוגמה
נניח שבחניון ישנם 3 מקומות חניה ומגיעים אליו 3 נהגים. הנהג הראשון מעדיף את המקום 2, ושני הנהגים הבאים מעדיפים את המקום 1. הנהג הראשון יתפוס את המקום 2; אחריו יתפוס הנהג השני את המקום 1; הנהג השלישי לא יוכל לחנות במקום המועדף עליו, אבל יוכל לחנות במקום זאת במקום 3. הבחירות 2,1,1 מאפשרות חניה מסודרת.

לעומת זאת, אם הנהג הראשון מעדיף את המקום 1 ושני האחרים מעדיפים את 3, אז הראשון יחנה במקום 1, השני יסע למקום 3 ויחנה בו, והשלישי, שיסע בתחילה למקום 3, יאלץ לוותר ולעזוב. הבחירות 1,3,3 אינן מאפשרות חניה מסודרת.

לפונקציות חניה יש גם יישום שימושי יותר בחקר טבלאות גיבוב המבוססות על גיבוב ליניארי, אסטרטגיה להצבת מפתחות בטבלת גיבוב הדומה מאוד לאסטרטגיית חניה חד-סטרית עבור מכוניות.

## פתרון הבעיה – ספירה קומבינטורית
לבעיה זו נמצא פתרון אלגנטי, ג'ון ריורדן מייחס אותו לזכותו  של הנרי פולק ממעבדות בל בתחילת שנות ה-60 של המאה ה-20, והוא כזה:

מספר פונקציות החניה באורך n הוא בדיוק (n+1)^{n-1}.לדוגמה עבור n=3 המספר הזה הוא 4^2=16.

סדרה \ (a_1, a_2, a_3,...,a_n) של מספרים בתחום 1 עד n תקרא פונקציית חניה, אם כאשר לכל \ 1 \leq i \leq n, הנהג ה-\ i בוחר במקום החניה ה\ a_i בתור מקום מועדף, כל הנהגים מוצאים חניה.

נוסיף לחניון מקום חניה וירטואלי,  \ n + 1, ונאפשר לבחור בו כמקום מועדף. נסגור את החניון במעגל. (כלומר, לאחר מקום החניה ה- \ n + 1, מגיעים למקום החניה הראשון). כעת, כל הנהגים יכולים לחנות, משום שכל נהג ממשיך לחפש ואינו נוטש, ויש יותר מקומות מנהגים.

רשימה של העדפות (כמתואר מלמעלה) היא פונקציית חניה, אם ורק אם אף נהג אינו חונה במקום חניה ה \ n + 1 :

* אם אחד הנהגים עזב את החניון, מישהו יצטרך לחנות לאחר מקום החניה ה \ n , ולכן יחנה במקום החניה ה \ n + 1  (כי הוא הראשון אחרי ה \ n ).
* אם מישהו חונה במקום החניה ה \ n + 1 , זאת אומרת שמישהו הגיע למקום החניה ה \ n  והוא היה תפוס, ולכן היה אמור לעזוב את החניון, או שמישהו בחר במקום ה \ n + 1 , אבל בפונקציית חניה זה לא אפשרי (הרי \ 1 \leq a_i \leq n).

נשים לב שהזזה ציקלית של הרשימה, מזיזה ציקלית את התוצאה הסופית של המעגל. כלומר, תהי \ (b_1, b_2, b_3,...,b_n) רשימת העדפות של הנהגים. (כלומר, לכל \ 1 \leq i \leq n ,\ 1 \leq b_i \leq n + 1 הוא המקום חניה המועדף על הנהג ה\ i), ותהי \ (p_1, p_2, p_3,...,p_n) רשימת הסיום במקרה זה (כלומר, בסוף התהליך סיים הנהג ה \ i , במקום ה \ p_i  ). אזי רשימת הסיום של רשימת ההעדפות \ (b_1 + j, b_2 + j, b_3 + j,...,b_n + j) \pmod{(n + 1)} היא  \ (p_1 + j, p_2 + j, p_3 + j,...,p_n + j) \pmod{(n + 1)}

כלומר, כל פונקציית חניה מופיעה ברשימות של ההעדפות האפשריות  \ n + 1  פעמים:

* פעם אחת בתור פונקציית חניה (מתקבל מעגל בו במקום ה \ n + 1  הוא ריק).
*  \ n  פעמים בתור עזיבת חניון של אחד הנהגים (שהרי, ניתן לסובב את המעגל n פעמים, כך שהמקום ה \ n + 1  יהיה לא ריק). נשים לב שבמקרה כזה תתקבל פונקציית חניה תקנית בה כל ההעדפות קטנות מ \ n + 1  משום שאילו אחת ההעדפות הייתה המקום ה \ n + 1  מקום זה היה נתפס, ולא הייתה מתקבלת פונקציית חניה.

כעת נסתכל על מספר הרשימות של ההעדפות האפשריות עם מקום החניה הנוסף: ישנן \ {(n + 1)}^{n} כאלה (כי לכל נהג יש  \ n + 1  אפשרויות למקום מועדף, ויש  \ n  נהגים.

מכיוון, שכל פונקציית חניה מופיעה  \ n + 1  פעמים במספר הרשימות של ההעדפות האפשריות, ישנן בסה"כ  \frac{n + 1} = {(n + 1)}^{n - 1}  פונקציות חניה, כלומר ישנן \ {(n + 1)}^{n - 1}  רשימות העדפות המאפשרות לכולם לחנות לפי הכללים.

ניתן גם להראות העתקה חד חד ערכית ועל בין פונקציות החניה לבין העצים הפורשים של גרף שלם עם n+1 קודקודים, שאחד מהם מסומן כשורש. חיבור זה, יחד עם נוסחת קיילי למספר העצים הפורשים, מראה שוב שיש (n+1)^{n-1} פונקציות חניה.

## הערות שוליים

קטגוריה:אובייקטים מתמטיים
קטגוריה:קומבינטוריקה