Normal approximations, as provided by permutational central limit theorems, conditionally can be arbitrarily bad. Such approximations therefore are poorly suited to the construction of critical values for Pitman (permutation) tests. A classical remedy consists in substituting a beta approximation (over the appropriate conditional interval range) for the normal one. Whereas deriving permutational extreme values for usual, nonserial statistics is generally straightforward, the corresponding problem for serial statistics (e.g., autocorrelation coefficients), however, appears somewhat more difficult. This problem, which is shown to reduce to a particular case of the well-known travelling salesman problem, is explicitly solved here for the autocorrelation coefficient of order one, allowing for a simple computation of permutational critical values for Pitman tests against serial dependence. The case of higher order autocorrelations is, however, of a different nature and requires another approach.