How many arrangements of $s$ selections from $r$ possibilities have at least one skip backwards? Say we're selecting $s$ apples and placing them in $r$ different bags (order of placement matters). There are $r^s$ possible orders of placement. 
Is there a convenient way to calculate how many distinct arrangements of these include at least one skip backwards? Meaning a placement in a "higher" bag followed by a lower bag with at least one bag in between (bag "c" or "d" followed by bag "a", for example).
 A: It's easier to start by counting the number which don't contain a skip backwards.  In this case, the allowable transitions between successive bag numbers is encoded in the $r\times r$ matrix $A=(a_{ij})$, with $a_{ij}=1$ if $j\ge i-1$ and $0$ otherwise.  The number of valid placement sequences of length $s$, starting with bag $i$ and ending with bag $j$, is the $(i,j)$ entry in the matrix $A^{s-1}$, so the total number of placement sequences is the sum of the elements in $A^{s-1}$.  Thus the solution to the original problem is given by
$$r^s - \mathbf{u}A^{s-1}\mathbf{u}^T,$$
where $u$ is the row vector $(1,\ldots,1)$.
While this seems only semi-tractable, it's worth noting that the characteristic polynomial of $A$ turns out to have a nice closed form.  One can show by induction that 
$$\textrm{charpoly}(A) = \sum_{i\ge 0}(-1)^i\binom{r+1-i}{i}z^{r-i}.$$
It follows that if you fix $r$, then the sequence $\mathbf{u}A^{s-1}\mathbf{u}^T$ satisfies the corresponding linear recurrence.
For example, if $r=7$, the characteristic polynomial is $z^7-7 z^6+15 z^5-10 z^4+z^3$; the corresponding sequence of placement counts with no back-skips is $$7, 34, 143, 560, 2108, 7752, 28101, 100947, 360526, 1282735, 4552624,\ldots$$
which satisfies the recurrence $a_n=7 a_{n-1}-15 a_{n-2}+10a_{n-3}-a_{n-4}$. 
