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

פונקציית חנייה היא עצם מתמטי בענף הקומבינטוריקה.

הגדרה ויישומים

פונקציית חניה באורך $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$ מקומות חניה, כאשר לכל נהג יש מקום חניה מועדף. כל נהג נוסע עד להגעה למקום המועדף עליו, ולאחר מכן חונה במקום הפנוי הראשון. פונקציית חניה מתארת העדפות עבורן כל המכוניות יכולות לחנות. ${\mathbb{ℝ}}^{yin}$ לדוגמה, פונקציית החניה (2,1,2,1) מתארת העדפות שבהן הנהג הראשון והשלישי מעדיפים שניהם את המקום השני, בעוד ששני הנהגים האחרים מעדיפים שניהם את המקום הראשון. הנהג הראשון חונה במקום 2, השני במקום 1, והשלישי במקום 3 (מכיוון שמשבצת 2 תפוסה). הנהג הרביעי מתחיל לחפש מקום פנוי במקום 1, אך לא מוצא אותו עד במקום 4; כל המקומות הקודמים היו תפוסים. הרצף (3,3,1,3) אינו פונקציית חניה: נהגים רבים מדי מעדיפים את מקום חניה 3, כך שהנהג האחרון מתחיל לחפש מקום חניה לאחר שכבר עבר את המקום הפנוי היחיד, ולא יוכל לחנות.

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

ספירה קומבינטורית

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

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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