עצרת כפולה

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

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

הגדרה

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

$$n!!=\prod _{k=0}^m(n-2k)=n(n-2)(n-4)\cdots$$

כאשר $m=\lceil \frac{n}{2}\rceil -1$ .

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

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

$n!!=\{\begin{array}{ll}\prod _{k=1}^{\frac{n}{2}}(2k)=n(n-2)\cdots 2& :n=2m\\ \prod _{k=1}^{\frac{n+1}{2}}(2k-1)=n(n-2)\cdots 1& :n=2m-1\end{array}$

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

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

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

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

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

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

$n!!=\{\begin{array}{ll}{2}^{k}k!& :n=2(k-1)\\ \frac{(2k)!}{2^{k}k!}& :n=2k-1\end{array}$

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

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

$(2k-1)!!=\frac{{}_{2k}{P}_k}{2^k}=\frac{(2k{)}^{\underset{\_}{k}}}{2^k}$

הרחבות

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

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

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

ולקבל

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

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

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

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

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

$\begin{array}{rl}z!!& =z(z-2)\cdots (3)=2^{\frac{z-1}{2}}\left(\frac{z}{2}\right)\left(\frac{z-2}{2}\right)\cdots \left(\frac{3}{2}\right)\\ & =2^{\frac{z-1}{2}}\frac{\mathrm{\Gamma }(\frac{z}{2}+1)}{\mathrm{\Gamma }(\frac{1}{2}+1)}=\sqrt{\frac{2^{z+1}}{\pi }}\mathrm{\Gamma }(\frac{z}{2}+1)=\left(\frac{z}{2}\right)!\sqrt{\frac{2^{z+1}}{\pi }}\end{array}$

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

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

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

$\begin{array}{r}(2k)!!=\sqrt{\frac{2}{\pi }}\prod _{i=1}^k(2i)=2^{k}k!\sqrt{\frac{2}{\pi }}\\ 0!!=\sqrt{\frac{2}{\pi }}\approx 0.7978845608\dots \end{array}$

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

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

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

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

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

הערות שוליים

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