Problem 11901
(American Mathematical Monthly, Vol.123, April 2016) Proposed by D. Knuth (USA).
For n∈ Z+, let [n] = {1, . . . , n}. Define the functions ↑ and ↓ on [n] by ↑ x = min{x + 1, n} and
↓ x = min{x − 1, 1}. How many distinct mappings from [n] to [n] occur as compositions of ↑ and ↓?
Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.
We will show that the mappings from [n] to [n] which can be written as compositions (possibly empty) of ↑ and ↓ are those with following forms,
f(i) = x or f(i) =
x if 1 ≤ i ≤ a,
x+ i − a if a < i ≤ n − b, x+ n + 1 − a − b if n − b < i ≤ n, with 1 ≤ x ≤ n, and, in the second case, with a ≥ 1, b ≥ 1 such that x < a + b ≤ n.
We denote by Fn the set of such mappings. The cardinality of Fn is equal to Xn
x=1
1 +
nX−1 a=1
n−a
X
b=1 a+bX−1
x=1
1 = n +n 2
+ 2n
3
= n(2n2− 3n + 7) 6
The first numbers in this sequence are 1, 3, 8, 18, 35, 61, 98, 148, 213, 295 (A081489 OEIS).
Notice that it is easy to verify that if f ∈ Fn then both ↑ f and ↓ f belongs to Fn. Finally, if f ∈ Fn then it occurs as a composition of ↑ and ↓. In fact, for all i ∈ [n],
↑ · · · ↑
| {z }
x−1
↓ · · · ↓
| {z }
n−1
(i) = ↑ · · · ↑
| {z }
x−1
(1) = x,
and,
↑ · · · ↑
| {z }
x−1
↓ · · · ↓
| {z }
a+b−2
↑ · · · ↑
| {z }
b−1
(i) = ↑ · · · ↑
| {z }
x−1
↓ · · · ↓
| {z }
a+b−2
(i+ b − 1 if 1 ≤ i ≤ n − b, n if n − b < i ≤ n,
= ↑ · · · ↑
| {z }
x−1
1 if 1 ≤ i ≤ a,
i− a + 1 if a < i ≤ n − b, n− a − b + 2 if n − b < i ≤ n,
=
x if 1 ≤ i ≤ a,
x+ i − a if a < i ≤ n − b, x+ n + 1 − a − b if n − b < i ≤ n.
