partit

Algoritmul, pas cu pas

„Mulțime ordonată” înseamnă că ordinea contează: 1 2 și 2 1 sunt diferite. Acestea sunt compoziții ale lui $n$, nu partiții neordonate. Gândește-te la cele $m$ unități înșirate, cu $m-1$ „spații” între ele; o compoziție se obține alegând în care spații pui un perete despărțitor — fiecare spațiu e independent prezent sau nu, deci sunt $2^{m-1}$ compoziții. Tabelul are $2^{n-1}$ rânduri, mult prea multe ca să le generezi; cheia e să navighezi prin el numărând, nu listând.