עצרת כפולה

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

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

הגדרה

הגדרתה המתמטית של העצרת הכפולה: $$n!!=\prod _{k=0}^{m}(n-2k)=n(n-2)(n-4)\cdots$$ כאשר $m=\lceil n/2\rceil -1.$.

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

לדוגמה, לחישוב עצרת כפולה של 9: $9!!=1\times 3\times 5\times 7\times 9=945$.

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

$n!!=\prod _{k=1}^{n/2}(2k)=n(n-2)\cdots 2.$

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

$n!!=\prod _{k=1}^{(n+1)/2}(2k-1)=n(n-2)\cdots 1.$

סדרת הערכים של עצרת כפולה עבור המספרים הזוגיים 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 – האנציקלופדיה המקוונת לסדרות של מספרים שלמים

עצרת כפולה בהשוואה לעצרת

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

העצרת של מספר n שונה מאפס יכולה להיות מנוסחת כמכפלה של שתי עצרות כפולות:

$n!=n!!\cdot (n-1)!!\,$

מהעברת אגפים נקבל ביטוי רקורסיבי כללי לעצרת כפולה:

$n!!={\frac {n!}{(n-1)!!}}={\frac {(n+1)!}{(n+1)!!}}\,$

כאשר המכנה מצמצם את הגורמים הלא רצויים במונה. (הניסוח האחרון תקף גם כאשר 0=n).

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

$n!!=2^{k}k!.$

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

$n!!={\frac {(2k)!}{2^{k}k!}}={\frac {n!}{(n-1)!!}}.$

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

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

$(2k-1)!!={\frac {_{2k}P_{k}}{2^{k}}}={\frac {{(2k)}^{\underline {k}}}{2^{k}}}.$

הרחבות

הרחבה לשליליים

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

$n!!=n\times (n-2)!!$

ולקבל

$n!!={\frac {(n+2)!!}{n+2}}.$

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

$(-n)!!\times n!!=(-1)^{(n-1)/2}\times n.$

הרחבה למרוכבים

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

$z!!=z(z-2)\cdots (3)=2^{(z-1)/2}\left({\frac {z}{2}}\right)\left({\frac {z-2}{2}}\right)\cdots \left({\frac {3}{2}}\right)$

$=2^{(z-1)/2}{\frac {\Gamma \left({\frac {z}{2}}+1\right)}{\Gamma \left({\frac {1}{2}}+1\right)}}={\sqrt {\frac {2^{z+1}}{\pi }}}\Gamma \left({\frac {z}{2}}+1\right)=\left({\frac {z}{2}}\right)!{\sqrt {\frac {2^{z+1}}{\pi }}}\,.$

15 דיאגרמות של מיתרים שונים של 6 נקודות, או 15 שידוכים של 6 צמתים בגרף שלם

15 עצים בינאריים בעלי שורשים (עם ילדים חסרי סדר) שניתן להגדיר עבור קבוצה של 4 עלים

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

$(2k)!!={\sqrt {\frac {2}{\pi }}}\prod _{i=1}^{k}(2i)=2^{k}k!{\sqrt {\frac {2}{\pi }}}\,,$

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

$0!!={\sqrt {\frac {2}{\pi }}}\approx 0.7978845608...\,.$

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

$V_{n}={\frac {2(2\pi )^{(n-1)/2}}{n!!}}R^{n}.$

שימושים קומבינטורים

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

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

קישורים חיצוניים

• עצרת כפולה, באתר MathWorld (באנגלית)
• סדרת הערכים של עצרת כפולה באתר OEIS – האנציקלופדיה המקוונת לסדרות של מספרים שלמים
• סדרת הערכים של עצרת כפולה עבור המספרים הזוגיים באתר OEIS – האנציקלופדיה המקוונת לסדרות של מספרים שלמים
• סדרת הערכים של עצרת כפולה עבור המספרים האי-זוגיים באתר OEIS – האנציקלופדיה המקוונת לסדרות של מספרים שלמים