<< (It all seems very obvious to me, but this is the kind of thing where obviousness is not easily communicated.) >> Amen to that! Gareth's solution looks pretty much along the same lines as mine. I was congratulating myself that I hadn't overlooked anything too elementary here ... [FCPU -- Fred's conscious serial processing unit] -- So you've amused yourself showing why there are (n-1)! vectors. Now get back to typesetting that draft! [FDPU -- Fred's subconscious parallel processing unit] -- There's a better way to look at this. Stop chickening out: go seek an alternative characterisation of permutations P (mod n) ? [FCPU] -- OK, OK; on further reflection ... Recap: << Given n > 0 integer, evaluate the number f(n) of integer vectors P of length n such that 0 < P_(i+1) - P_i < n for all i , and (P_i - P_j) mod n /= 0 for all i /= j , and sum_i P_i = n(n-1)/2 .
Reducing such a vector modulo n yields a particular representative R = P (mod n) == (P_i mod n) from an equivalence class numbering n permutations Q , where Q ~ R when (Q_i - R_i)mod n = k for all i ; The equivalent operation on inverse permutations is cyclic right-shift: Q ~ R when 1/Q = 1/R >> k . Lacking a name for this operation, I suggest `modulation': denoted Q (+) k == ( (Q_i + k)mod n ) for permutation Q of length n , and integer k . An arbitrary permutation Q is converted into a unique vector P satisfying the first two constraints via the following procedure: P := Q; for i in [1..n-1] do if P_i < P_(i-1) then for j in [i..n-1] do P_j := P_j + n; g := g+1; and then the third via for i in [0..n-1] do if P_i := P_i - g; Above g counts the number of component increments: reducing modulo n yields better-behaved function g(Q) = ( sum_{Q_i < Q_{i-1}} (n-i) )mod n . A simple argument establishes the symmetry g(Q (+) 1) = g(Q) + 1 , whence more generally g(Q (+) k) = ( g(Q) + k )mod n . The special permutation representative is R = P mod n ; for all k (mod n) , taking Q = R (+) k yields the same vector P via procedure above. Hence number of P equals number of classes, which is n!/n = (n-1)! QED. And now for the rider / kicker / punchline: CONJECTURE: vector P satisfies the problem constraints iff g(R) = 0 , where permutation R = P mod n ? Which would be the very characterisation FDPU was nagging about -- if only FCPU (or anyone else) could prove it! As a corollary, g(R (+) k) = k ? Dunno yet whether it's useful -- but it's surely intriguing! Fred Lunnon On 3/29/15, Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
On 29/03/2015 02:22, Fred Lunnon wrote:
While pootling around the arcane labyrinth of multi-dimensional sodalite, I encountered a combinatorial puzzle which seems of independent interest, and reasonably straightforward --- more than can be said for numerous other heffalump-traps lately encountered over the course of that tortuous expedition!
Given n > 0 integer, evaluate the number f(n) of integer vectors P of length n such that 0 < P_(i+1) - P_i < n for all i , and (P_i - P_j) mod n /= 0 for all i /= j , and sum_i P_i = n(n-1)/2 .
For example when n = 4 there are f(4) = 6 such vectors: [ 0, 1, 2, 3 ], [ -1, 1, 2, 4 ], [ -2, 1, 3, 4 ], [ -1, 0, 2, 5 ], [ -2, 0, 3, 5 ], [ -3, 0, 3, 6 ].
The explicit function f(n) is surprisingly simple; but the proof is not immediately obvious.
I have one, obtained pretty much by doing the "most obvious" thing at each stage. I suspect that the following may not be easy to follow, for which I apologize. (It all seems very obvious to me, but this is the kind of thing where obviousness is not easily communicated.)
The second condition says that P mod n is a permutation of {0,...,n-1} mod n. Let Q be the unique permutation of {0,...,n-1} all of whose entries agree mod n with P. Then the third condition says that the entries of R := P-Q (which are of course all multiples of n) add up to 0.
The first condition says: consider adjacent entries a,b in Q and their corresponding entries u,v in R; then if a<b then u=v; otherwise v=u+n. Given Q, this nails down P completely *except* that we may change all its entries by the same multiple of n, changing the sum of R by an arbitrary multiple of n^2. There is clearly at most one such that makes the sum of R equal to 0; so f(n) is the number of Q for which there is in fact one such; equivalently, the number of Q for which a choice of P (*any* choice of P) has sum(R) a multiple of n^2.
So, suppose we begin by taking P(n-1) = Q(n-1) and then working backwards according to the previous paragraph. It's easy to see that the resulting sum of R equals n times the sum of all the "decreasing positions" in Q; that is, the i such that Q(i) < Q(i-1). Hence, f(n) is the number of Q for which the sum of decreasing positions is a multiple of n.
This is a simple enough condition that it's painless to compute f(n) for small n, and the result strongly suggests f(n) = (n-1)! when n>0. In other words, 1/n of all possible Q are acceptable. So maybe there's a simple operation that always increases the sum of decreasing positions by 1 mod n.
And yes, there is. The operation in question is: decrease each entry in Q by 1 (mod n, so that 0 becomes n-1). To see that this does the trick, first of all consider the permutations to "wrap around", noting that the extra transition introduced between the first and last entries has index 0 (mod n) so that our "sum of decreasing positions" is unchanged mod n when we include it. And now note that when we decrease every entry in Q by 1 (mod n), the "decreasing positions" don't change *except* that where we previously had (say) a,0,b we now have a-1,n-1,b-1 and we have moved a "decreasing position" one place to the right and therefore changed the "sum of decreasing positions" by +1 mod n.
And we're done.
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun