[seqfan] Re: Permutations avoiding a pair sum
wjk26 at drexel.edu
Thu Feb 25 16:46:47 CET 2010
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.
More information about the SeqFan