# A second problem

Emeric Deutsch deutsch at duke.poly.edu
Sun Jul 16 21:47:40 CEST 2006

```Dear Seqfans,

I have a second problem.
I am looking at the number T(n,k) of permutations p of [n] such that
#{p(i)-i, i=1,2,...,n}=k (i.e. there are exactly k distinct differences
p(i)-i).

Straightforward counting, using Maple, has given

1;
1,1;
1,2,3;
1,4,12,7;
1,4,38,54,23;
1,8,77,248,303,83;
1,6,160,824,2008,1636,405;
1,11,285,2320,9449,15789,10352,2113;
1,10,476,5564,37237,102726,133293,70916,12657;
It is not in OEIS.

We have T(n,n)=A099152(n), defined as: Number of n by n permutation
matrices in which the sums of the entries of each NorthEast-SouthWest
diagonal are 0 or 1. It seems easy to show that this agrees to the above
definition of T(n,n) (probably first NE-SW has to be changed to NW-SE).

We also have T(n,2)=A065608(n) defined as: Sum of divisors of n minus the
number of divisors of n.

This leads us to a conjecture: Number of permutations p of [n] such
that there are exactly 2 distinct differences p(i)-i (i=1,2,...,n)
is sigma(n)-tau(n).

My hunch is that this is not hard to prove but, so far, I couldn't.
If "we" can prove it, then, unless it is too easy, it may form a joint
proposed problem (Monthly or Math. Magazine)

As a matter of fact, I can relatively easily produce sigma(n)-tau(n)
permutations p of [n] such that #{p(i)-i, i=1,2,...,n}=2, but I
couldn't show that I have exhausted them all.

Let me know if you are interested and then I will send you

Many thanks,
Emeric

P.S. A similar triangle of numbers can be defined by the number A(n,k) of
permutations p of [n] such that #{|p(i)-i|, i=1,2,...,n}=k (i.e.  there
are exactly k distinct distances |p(i)-i)|.
Straightforward counting, using Maple, has given

1;
2;
1,5;
3,11,6,4;
1,28,55,32,4;
3,69,210,330,108;
1,102,846,2177,1590,324;
4,279,2694,11221,17578,7624,888,32;
1,328,7791,54777,135993,123474,37524,2896,96;

Here A(n,n)=A075866(n) (the two definitions are identical).

```