Marinada '25

[lang=hr] Jednom drugom prilikom, na matematičkom kampu, održavao se turnir u stolnom tenisu. Posebno neosrednji igrač bio je Artur koji je na kraju krajeva pobijedio na čitavom turniru. Kao proslavu, Artur je odlučio počastiti sebe i prijatelje Igorovim sokom. Artur je imao $16$ boca Igorovog soka. Jedna boca bila je visine $1$dm, druga $2$dm, treći $3$dm, $\dots$ , šesnaesti $16$dm. Artur se zatim, u svojoj čarobnoj briljantnosti, zapitao: Na koliko se načina mogu poredati boce Igorovog soka slijeva nadesno tako da bude najviše dva uzastopna pada u visini boca u čitavom nizu? [/lang] [lang=en] How many permutations \(a_1,a_2,\dots,a_{16}\) of the set \(\{1,2,3,\dots,16\}\) are there in which there are at most two consecutive descending elements? (An element \(a_i\) is called \emph{descending} if \(a_i>a_{i+1}\).) \textbf{Example.} For \(4\) elements, the permutation \(4,3,2,1\) is not allowed because it contains \(3\) consecutive descents, while \(1,4,3,2\) is allowed because it has at most two consecutive descents. [/lang]