נוסחת ההיפוך של מביוס

בקומבינטוריקה, נוסחת ההיפוך של מביוס משמשת, בהינתן פונקציה $F$ שניתנת לתיאור בתור סכום מסוים על ערכי פונקציה אחרת $f$ , לתאר בצורה ישירה את הפונקציה $f$ באמצעות סכום של $F$ .

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

הגרסה ה"קלאסית" של הנוסחה היא כדלהלן: בהינתן שתי פונקציות אריתמטיות $f,F$ , אם מתקיים $F(n)=\sum _{d\mid n}f(d)$ לכל $n\geq 1$ , אז ניתן להפוך את הנוסחה ולקבל $f(n)=\sum _{d\mid n}F(n/d)\mu (d)$ , כאשר $\mu$ היא פונקציית מביוס.

אם מסמנים ב- $\mathbf {1}$ את הפונקציה הקבועה שמקיימת $\mathbf {1} (n)=1$ לכל $n$ , ומשתמשים בסימון של קונבולוציית דיריכלה, נוסחת מביוס אומרת שבהינתן $F=f*\mathbf {1}$ , אז $f=F*\mu$ . כלומר $\mathbf {1}$ ו- $\mu$ הם איברים הופכיים ביחס לקונבולוציית דיריכלה.