מספר האפשרויות למערך מסודר בסדר לא יורד

נתון מערך בגודל n וערך שלם חיובי max.

ברצוננו לשבץ במערך n מספרים מתוך המספרים 1 עד max, כך שהמספרים יהיו מסודרים במערך בסדר לא יורד (כלומר, סדר עולה, אך יכולים להיות גם מספרים שווים).

דוגמאות:

אם גודל המערך הוא n = 3 ו-max = 2 (כלומר, המספרים האפשריים הם 1,2), אז יש לנו 4 אפשרויות לסדר את המערך כך שהמספרים יהיו בסדר לא יורד:

1. {1,1,1}
2. {1,1,2}
3. {1,2,2}
4. {2,2,2}

אם גודל המערך הוא n = 2 ו-max = 3 (כלומר, המספרים האפשריים הם 1,2,3), אז יש לנו 6 אפשרויות לסדר את המערך כך שהמספרים יהיו בסדר לא יורד:

1. {1,1}
2. {1,2}
3. {1,3}
4. {2,2}
5. {2,3}
6. {3,3}

בהינתן גודל של מערך n ומספר מקסימלי max יש להחזיר את מספר האפשרויות שיש למלא את המערך במספרים מהתחום 1 עד max כך שיהיו מסודרים בסדר לא יורד.

השיטה צריכה להיות רקורסיבית ללא שימוש בלולאות כלל. כך גם כל שיטות העזר (אם תכתבו) לא יכולות להכיל לולאות.