Problemă de combinatorică

Rezolvând o problemă mult mai simplă, m-am confruntat cu următoarea problemă de combinatorică. Au trecut 9 ani de când eram în clasa a zecea, şi cred că am mai întâlnit-o prin algebra sau informatica din liceu, dar nu îmi amintesc soluţia şi nici nu îmi vine imediat în minte. Dacă o ştie cineva, please comment. Problema de algebră sună cam aşa:

În câte feluri pot fi aranjate câte n, păstrându-şi ordinea, elemente dintr-o mulţime finită cu k elemente?
De exemplu:
- pentru n=3 şi k=2, avem 2:

• {1,1,2}
• {1,2,2}

- pentru n=5 şi k=3, avem 6:

• {1,2,3,3,3}
• {1,2,2,2,3}
• {1,1,1,2,3}
• {1,2,2,3,3}
• {1,1,2,3,3}
• {1,1,2,2,3}

- pentru n=4 şi k=2, avem 3:

• {1,1,1,2}
• {1,1,2,2}
• {1,2,2,2}

Altă problemă care se reduce la aceasta: câte numere naturale de n cifre cu k cifre diferite există?