עצרת כפולה

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

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

הגדרה

הגדרתה המתמטית של העצרת הכפולה: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n!! = \prod_{k=0}^m (n-2k) = n (n-2) (n-4) \cdots } כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle m=\lceil n/2 \rceil - 1.} .

מהגדרה זו נגזר (כמכפלה ריקה) שהערך של עצרת כפולה של 0: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0!! = 1} .

לדוגמה, לחישוב עצרת כפולה של 9:  הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 9!!=1 \times 3 \times 5 \times7\times9 =945} .

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n!! = \prod_{k=1}^{n/2} (2k) = n(n-2)\cdots 2.}

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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, ....

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

1, 3, 15, 105, 945, 10395, 135135, ....

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

מאחר שעצרת כפולה מערבת רק כחצי מהאיברים של עצרת רגילה, הערך שלה אינו גדול בהרבה משורש של עצרת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sqrt{(n!)}} , והיא קטנה בהרבה מפעמיים עצרת (הרכבת שתי פונקציות עצרת, אחת על השנייה) הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (n!)!} .

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n! = n!! \cdot (n-1)!!\,}

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n!! = \frac{n!}{(n-1)!!} = \frac{(n+1)!}{(n+1)!!}\,}

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

עבור מספרים זוגיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=2k} כאשר k ≥ 0 העצרת הכפולה ניתן לפישוט כ:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n!! = 2^k k!.}

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n!! = \frac{(2k)!}{2^k k!} = \frac{n!}{(n-1)!!}.}

בביטוי זה המכנה הראשון שווה להפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (2k)!!} ומבטל את הזוגיים במונה.

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (2k-1)!! = \frac {_{2k}P_k} {2^k} = \frac {{(2k)}^{\underline k}} {2^k}.}

הרחבות

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

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n!! = n \times (n-2)!!}

ולקבל

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n!! = \frac{(n+2)!!}{n+2}.}

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (-n)!! \times n!! = (-1)^{(n-1)/2} \times n.}

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

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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)}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle = 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}} \,.}

קובץ:Chord diagrams K6 matchings.svg

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

קובץ:Unordered binary trees with 4 leaves.svg

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

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (2k)!!= \sqrt{ \frac{2}{\pi} } \prod_{i=1}^k (2i) = 2^k k! \sqrt{ \frac{2}{\pi} } \,,}

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0!! = \sqrt{ \frac{2}{\pi} } \approx 0.7978845608... \,.}

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle V_n=\frac{2 (2\pi)^{(n-1)/2}}{n!!} R^n.}

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

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

• בשידוך של גרף שלם של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_{n+1}} עבור n אי זוגי. בגרף כזה לכל קודקוד יש n אפשרויות שידוך, ולאחר שבוחרים שידוך לקודקוד אחד עם אחר נותר לבחור שידוך ליתר הקודקודים מלבד שני אלו ששודכו. לדוגמה בגרף שלם של ארבעה קודקודים, א', ב', ג' וד' יש שלושה שידוכים מושלמים: א+ב וג+ד, א+ג וב+ד, וא+ד וב+ג.
• תמורות סטירלינג הן תמורות של רב-קבוצה (multiset) של המספרים 1,1, 2,2..., k, k שבה כל זוג מספרים שווים מופרד רק על ידי מספר גדול יותר, כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle k=(n+1)/2} . שני העותקים של k חייבים להיות סמוכים; הסרתם מותיר בעיה של תמורה שבה האיבר המקסימלי הוא k-1 עם n מקומות שבהם הסמוך ל-k יכול להיות ממוקם. מבנייה רקורסיבית זו ניתן להוכיח באינדוקציה שתמורות סטירלינג נספרות על ידי פרמוטציות כפולות.
• עצי ערימה שבהם k+1 קודקודים בעלי ערכים של 0, 1, ...k שבהם השורש הוא 0, כל קודקוד אחר הוא בעל ערך גבוה יותר מקודקוד האב, ולצאצאיו של כל קודקוד יש סדר מוגדר. טיול אוילר בעץ (עם קשתות כפולות) מניב תמורת סטירלינג, וכל תמורת סטירלינג מתארת עץ בדרך זו.
• עצים בינאריים חסרי שורש עם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (n+5)/2} עלים ממוספרים. כל עץ כזה יכול להיווצר מעץ עם עלה אחד פחות, באמצעות פיצול אחד מ-n קשתות העץ, והפיכת הקודקוד החדש להיות האב של העלה.
• בעצים בינאריים בעלי שורש, עם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (n+3)/2} עלים. במקרה זה בדומה לעצים חסרי שורש, אך מספר הקשתות שאותו ניתן לפצל הוא זוגי, ובנוסף לפיצול של קשת ניתן להוסיף קודקוד לעץ עם עלה אחד פחות באמצעות הוספת שורש ששני בניו הם העץ הקטן יותר והעלה החדש.

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

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

הערות שוליים

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

33152276עצרת כפולה