# In how many ways can r elements be chosen from [1..n] with repetition, such that adjacent elements are one-step removed?

In case any of you is bored on this Wednesday...

For example, choose 4 from [1,2,3]:

1232 3212 1212 ...

By "one-step removed," I mean if the element is x, then the adjacent element is greater than zero and less than or equal to n, and is either x + 1 or x - 1

I'm totally clueless about how to solve this.

• I think this asks for counting $r-1$ step walks, with steps $\pm1$, on a chain of $n$ vertices. – Marc van Leeuwen Aug 21 '13 at 12:53
• @MarcvanLeeuwen thank you for your comment. Do you think a formula can be devised based on n and r? – גלעד ברקן Aug 21 '13 at 13:38
• Counting walks on bounded regions is somewhat tricky (in any case harder than many combination-type problems). The number of walks on a half-line starting at the end point is still given by a binomial coefficient, but the argument showing that is nontrivial. Here you are not fixing the starting point, and also imposing an upper bound as well, so that looks even more difficult. Try to get some numeric evidence for small values of $n$ and $r$ first. – Marc van Leeuwen Aug 21 '13 at 14:53

Your asking for the number of walks of length $k$ in the directed graph

in the case $n=5$ (and similarly for other $n$). The adjacency matrix has the form $$A=\begin{array}{|ccccc|} \hline 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \\ \hline \end{array}$$ so the number of walks of length $k$ is the sum of the entries of $A^k$.

Joseph Myers has an article which gives a formula for computing this sum of entries:

J. Myers (2008), BMO 2008–2009 Round 1 Problem 1—Generalisation

• Thanks for pointing me/us in that direction. I think I'm starting to visualize it although the math is advanced for me. Do you think there may be a way to extrude the number of only those combinations with consecutive adjacent digits that include all digits (e.g., m=4,n=3 would mean 0121,2101.. but not 1212, etc.)? – גלעד ברקן Aug 25 '13 at 5:45
• Actually, in regards to the comment above, referring to the formulas in the article, I thought something along the lines of subtracting m(n,r-1) from m(n,r), (or do I mean subtracting m(n-1,r) from m(n,r)). – גלעד ברקן Aug 25 '13 at 6:30

For the first element, you have $n$ possibilities, for all ather elements, you have $n-1$ possibilities (since the predecessor is forbidden). So the answer is $$n (n-1)^{r-1}.$$

• It's that simple? Thank you for helping me understand more. – גלעד ברקן Aug 21 '13 at 10:26
• I'm not sure this is correct, but it depends on the exact problem - I think having chosen an element, the next element must be an adjacent one, so you have at most 2 choices (and only 1 if the predecessor is one of the endpoints). In all the examples this is the case, and it's what I think "one-step removed" means. – mdp Aug 21 '13 at 10:30
• This works only if the first and last elements are considered to be "one-step removed". – hmakholm left over Monica Aug 21 '13 at 10:30
• @groovy: Please read the comments of Matt and Henning and then specify in your question what you mean by "one-step removed". – azimut Aug 21 '13 at 10:33
• I think this answer cannot be construed to be correct, even for the original question. The title asks for one-step-removed elements, and I just cannot see how one would interpret that as forbidding to choose the (cyclic) predecessor, especially since predecessors are chosen in each of the examples. – Marc van Leeuwen Aug 21 '13 at 12:50