Draft:Bpow35

I have a d-digit positive integer where

• each digit from 1 to d appears exactly once,

and in which

• each digit (except for the leftmost) differs from one further to the left by +1 or -1.

For example, if d = 3, the only numbers satisfying the conditions are, in increasing order, 123, 213, 231 and 321. Find a formula in terms of d for the number of integers satisfying these conditions.

(More difficult problem: Instead of the first condition, suppose I only tell you that the d digits are distinct. Now how many integers satisfy the conditions?)

Problem by Alberto L Delgado, from the now extinct Bradley Problem of the Week.