היי לכולם, אשמח לקבל עזרה עם השאלה הבאה:
מצאו נוסחה סגורה למספר הווקטורים הטרינאריים באורך n עם מספר זוגי של אפסים.
אני מבין שאני צריך להפריד למיקריים לפי תנאי כלשהו, אני פשוט לא מצליח להבין איזה תנאי בדיוק.
תודה לכולם על העזרה.
היי לכולם, אשמח לקבל עזרה עם השאלה הבאה:
מצאו נוסחה סגורה למספר הווקטורים הטרינאריים באורך n עם מספר זוגי של אפסים.
אני מבין שאני צריך להפריד למיקריים לפי תנאי כלשהו, אני פשוט לא מצליח להבין איזה תנאי בדיוק.
תודה לכולם על העזרה.
היי גלעד,
נסמן ב-F(n) את מספר הווקטורים הטרינאריים באורך n עם מספר זוגי של אפסים. נסתכל על הספרה האחרונה בווקטור:
אם הספרה האחרונה היא 1 או 2, אז ב-n-1 המקומות הראשונים יש כבר מספר זוגי של אפסים. לכן מספר האפשרויות הוא F(n-1).
אם הספרה האחרונה היא 0, אז ב-n-1 המקומות הראשונים יש כבר מספר אי-זוגי של אפסים. לכן מספר האפשרויות הוא 3^{n-1}-F(n-1).
סה"כ נקבל (כאשר n\geq1):
עם תנאי העצירה הבא: F(0)=1, שכן הווקטור הריק מקיים את הנדרש.