[seqfan] Re: Permutations avoiding a pair sum

[William Keith]

On Feb 25, 2010, at 9:06 AM, rhhardin at att.net wrote:

> Is there an obvious proof that the (Empirical) below can be omitted?
> I don't see a mapping that would prove it.
> 
> %C A000001 (Empirical) If a(n,k) is the number of permutations of 1..n with no adjacent pair
>         summing to n+k, then a(n,k)=a(n,k+1) for n+k even.

For a given n and k, these are the permutations of 1..n that avoid the subwords nk, (n-1)(k+1), (n-2)(k+2), ... , kn.  If n+k is even, the subword( (n+k)/2 )( (n+k)/2 ) which does not happen anyway.  Then for sums to n+k+1, the subwords to be avoided are n(k+1), (n-1)(k+2), ... , (k+1)n.

In the first list of subwords, the difference between the two elements is always at least 2 since the sum is even.  Switch the 'k' letter for the letter k+1 and you will get a member of the second list, which maps those that violate one rule to those that violate the other.


Example: n=10, avoid the sum 16.  Cannot have subwords 10 6, 9 7, 7 9, 6 10.  For avoiding 17, cannot have subwords 10 7, 9 8, 8 9, 7 10.  Patterns map.

William Keith