Urinal-choice permutations

JBL

Don't know if these are truly open, but there are no formulas for them in the OEIS:

1) Define a "standard urinal-choice permutation" of length $n$ to be a permutation $w = w_1 \ldots w_n$ of $[n] = \{1, \ldots, n\}$ such that $w_1$ is arbitrary and $w_i$ is chosen so as to maximize $\min \{|w_1 - w_i|, |w_2 - w_i|, \ldots, |w_{i - 1} - w_i|\}$ . (Equivalently, we choose each successive entry to be as far as possible from the nearest of all preceding entries.) How many standard urinal-choice permutations are there of length $n$ ?

For example, the 8 such permutations of length 4 are
1423
1432
2413
2431
3124
3142
4123
4132.
The associated sequence is A095236.

2) Define a "modified urinal-choice permutation" of length $n$ to be a permutation $w = w_1 \ldots w_n$ of $[n]$ such that $w_1$ is arbitrary and $w_i$ is chosen so as to maximize $|w_1 - w_i| + |w_2 - w_i| + \ldots + |w_{i - 1} - w_i|$ . (Equivalently, we choose each successive entry to be as far as possible on average from all preceding entries.) How many modified urinal-choice permutations are there of length $n$ ?

For example, the 6 such permutations of length 4 are
1423
1432
2413
3142
4123
4132.
The associated sequence is A095698. It is conjectured that if $a_n$ is the number of such permutations then for $k\geq1$ , $a_{2k} = a_{2k - 1} + 2^{k - 1}$ and $a_{2k + 1} = 2a_{2k - 1} + a_{2k}$ , so it might be nice to both prove this and solve the recurrence.

Related sequences (also in need of formulas) are A095239 (circular permutations) and A095240 (exhibiting foresight).

**Posted:** Fri May 15, 2009 5:31 pm

_________________
Joel
Hi Deeps! <3

JBL

This is the solution for modified urinal-choice permutations, henceforth abbreviated MUCPs.

Let $U_n$ be the number of MUCPs of length $n$ , and let $a_{n, i}$ be the number of MUCPs of length $n$ beginning with $i$ . Note that $|1 - i| + |n - i| = n - 1$ for any $i \in \{2, \ldots, n - 1\}$ , so if at any point we've already included both $1$ and $n$ in our permutation, the sequence of choices we can make from that point onwards is the same as if we erased both $1$ adn $n$ and acted as if we were working on permutations of length $n - 2$ .

Note that if $w$ is a MUCP and $w_1 = 1$ then $w_2 = n$ , while if $w_1 = n$ then $w_2 = 1$ . Thus $a_{n, 1} = a_{n, n} = U_{n - 2}$ .

If $w$ is a MUCP and $w_1 = i$ with $1 < i < \frac {n + 1}{2}$ then $w_2 = n$ and $w_3 = 1$ and so $a_{n, i} = a_{n - 2, i - 1}$ . Similarly, if $\frac {n + 1}{2} < i < n$ then $w_2 = 1$ and $w_3 = n$ and so $a_{n, i} = a_{n - 2, i - 1}$ .

Finally, if $w$ is a MUCP, $n \geq 3$ is odd and $w_1 = \frac {n + 1}{2}$ then we have $\{w_2, w_3\} = \{1, n\}$ in either order. Thus $a_{n, i} = 2a_{n - 2, i - 1}$ . Since $a_{1, 1} = 1$ we have $a_{n, i} = 2^{i - 1}$ and so also $a_{n, i} = a_{n - 2, i - 1} + 2^{i - 2}$ .

Putting all this together, we have for $n \geq 2$ that
$\begin{align*} U_{2n} & = \sum_{i = 1}^{2n} a_{2n, i} \\ & = 2U_{2n - 2} + \sum_{i = 2}^{2n - 1} a_{2n - 2, i - 1} \\...$
and for $n \geq 1$ that
$\begin{align*} U_{2n + 1} & = \sum_{i = 1}^{2n + 1} a_{2n + 1, i} \\ & = 2U_{2n - 1} + 2^{n - 1} + \sum_{i = 2}^{2n} ...$
Since $U_{2} = 2$ this immediately gives $U_{2n} = 2 \cdot 3^{n - 1}$ for $n \geq 1$ . Solving the recursion for the odd terms is only modestly more difficult and gives $U_{2n + 1} = 2\cdot 3^n - 2^n$ .

**Posted:** Sat May 16, 2009 7:52 am

_________________
Joel
Hi Deeps! <3

JBL

Also of interest may be circular urinal-choice permutations: the $i$ th entry is chosen to be the midpoint of the longest interval that does not contain any previously chosen entry, where we consider $1$ and $n$ to be adjacent. This is sequence A095239, which begins 1, 2, 6, 8, 40, 96, 168, 384, 1728, 15360, etc. Ignoring cyclic symmetry, this is 1, 1, 2, 2, 8, 16, 24, 48, 192, 1536, ..., which is not given by any sequence in the OEIS.

**Posted:** Mon Jun 15, 2009 5:17 pm

_________________
Joel
Hi Deeps! <3