עצרת כפולה

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

הגדרה[עריכת קוד מקור | עריכה]

הגדרתה המתמטית של העצרת הכפולה:

כאשר .

מהגדרה זו נגזר (כמכפלה ריקה) שהערך של עצרת כפולה של 0: .

לדוגמה, לחישוב עצרת כפולה של 9:  .

עבור n זוגי שווה עצרת כפולה ל:

ואילו עבור n אי-זוגי שווה עצרת כפולה ל:

סדרת הערכים של עצרת כפולה עבור המספרים הזוגיים  n = 0, 2, 4, 6, 8, ... מתחילה ב

1, 2, 8, 48, 384, 3840, 46080, 645120, .... (סדרה A000165 בOEIS)

סדרת הערכים של עצרת כפולה עבור המספרים האי-זוגיים n = 1, 3, 5, 7, ... מתחילה ב

1, 3, 15, 105, 945, 10395, 135135, .... (סדרהA001147 ב OEIS)

עצרת כפולה בהשוואה לעצרת[עריכת קוד מקור | עריכה]

מאחר שעצרת כפולה מערבת רק כחצי מהאיברים של עצרת רגילה, הערך שלה אינו גדול בהרבה משורש של עצרת n!, והיא קטנה בהרבה מפעמיים עצרת (n!)!.

עבור מספרים זוגיים n=2k כאשר k ≥ 0 העצרת הכפולה ניתן לפישוט כ:

עבור מספרים אי-זוגיים n=2k-1 כאשר k ≥ 1 ניתן לבטא את העצרת הכפולה:

בביטוי זה המכנה הראשון שווה ל(2k)!! ומבטל את הזוגיים במונה.

עבור מספרים אי-זוגיים ניתן לבטא את העצרת הכפולה גם באמצעות k-תמורות של 2k כך:

הרחבות[עריכת קוד מקור | עריכה]

הרחבה לשליליים[עריכת קוד מקור | עריכה]

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

ולקבל

באמצעות נוסחת נסיגה הפוכה זו, −1!! = 1, −3!! = −1, ו −5!! = 1/3; מספרים שליליים אי-זוגיים בעלי ערך מוחלט גדול יותר הם שברים.[1] בפרט כאשר n הוא מספר אי-זוגי מתקיים:

הרחבה למרוכבים[עריכת קוד מקור | עריכה]

קיימת דרך אחרת להרחיב את ההגדרה של עצרת כפולה שמאפשרת הגדרה שלה עבור מרוכבים. גישה זו מבוססת על ההבחנה כי עבור מספר אי-זוגי חיובי z מתקיים:

15 דיאגרמות של מיתרים שונים של 6 נקודות, או 15 שידוכים של 6 צמתים בגרף שלם.
15 עצים בינאריים בעלי שורשים (עם ילדים חסרי סדר) שניתן להגדיר עבור קבוצה של 4 עלים

מכך ניתן לגזור הגדרה חלופית ל-z!! עבור מספרים זוגיים אי-שליליים:

כאשר הערך עבור 0!! יהיה:

הביטוי עבור z!! מוגדר עבור מספרים מרוכבים, מלבד מספרים זוגיים שליליים. כאשר משתמשים בהגדרה זו, הנפח של היפר-ספרה n-ממדית שווה ל:

שימושים קומבינטורים[עריכת קוד מקור | עריכה]

עצרת כפולה מופיעה באופן שכיח בבעיות קומבינטורית.

  • בשידוך של גרף שלם של עבור n אי זוגי. בגרף כזה לכל קודקוד יש n אפשרויות שידוך, ולאחר שבוחרים שידוך לקודקוד אחד עם אחר נותר לבחור שידוך ליתר הקודקודים מלבד שני אלו ששודכו. לדוגמה בגרף שלם של ארבעה קוקודים, א', ב', ג' וד' יש שלושה שידוכים מושלמים: א+ב וג+ד, א+ג וב+ד, וא+ד וב+ג.
  • תמורות סטירלינג הן תמורות של רב-קבוצה (multiset) של המספרים 1,1, 2,2..., k, k שבה כל זוג מספרים שווים מופרד רק על ידי מספר גדול יותר, כאשר . שני העותקים של k חייבים להיות סמוכים; הסרתם מותיר בעיה של תמורה שבה האיבר המקסימלי הוא k-1 עם n מקומות שבהם הסמוך ל-k יכול להיות ממוקם. מבנייה רקורסיבית זו ניתן להוכיח באינדוקציה שתמורות סטירלינג נספרות על ידי פרמוטציות כפולות.
  • עצי ערימה שבהם k+1 קודקודים בעלי ערכים של 0, 1, ...k שבהם השורש הוא 0, כל קודקוד אחר הוא בעל ערך גבוה יותר מקודקוד האב, ולצאצאיו של כל קודקוד יש סדר מוגדר. טיול אוילר בעץ (עם קשתות כפולות) מניב תמורת סטירלינג, וכל תמורת סטירלינג מתארת עץ בדרך זו.
  • עצים בינאריים חסרי שורש עם עלים ממוספרים. כל עץ כזה יכול להיווצר מעץ עם עלה אחד פחות, באמצעות פיצול אחד מ-n קשתות העץ, והפיכת הקודקוד החדש להיות האב של העלה.
  • בעצים בינאריים בעלי שורש, עם עלים. במקרה זה בדומה לעצים חסרי שורש, אך מספר הקשתות שאותו ניתן לפצל הוא זוגי, ובנוסף לפיצול של קשת ניתן להוסיף קודקוד לעץ עם עלה אחד פחות באמצעות הוספת שורש ששני בניו הם העץ הקטן יותר והעלה החדש.

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ Callan, David (2009), A combinatorial survey of identities for the double factorial, arXiv:0906.1317 .