# [seqfan] Basis in subsets of permutations described in A293783

Fri Oct 27 12:22:56 CEST 2017

```Dear Seq Fans,

Consider a subset A of permutations
of {1..n} satisfying  a condition B
separately on the  elements on
odd positions (subset a) and the rest
elements (subset b) .
A permutation which contains two
permutations of elements of subsets
a and b only we call a right permutation.
So, we have |a|!*|b| ! right permutations.
For example, it is clear that |a|+|b|=
1+...+n=n*(n+1)/2 and we are free
to give the value of |a|-|b|. Then we
obtain a condition B on a and b in
the form of values |a| and |b|.
A subset S of permutations in A we
call a basis, if 1) there is no element
in S which is obtained by a right
permutation of another element in S;
2) any element in A\S is a right
permutation of an element from S .

The entries of triangle A293783 give
interesting examples.  Consider, say,
the seventh row
{576,0,720,0,144}. This means that
there are 576 permutations C={c_1..c_7}
of {1..7} for which d(C)=c_1-c_2+c_3-
c_4+c_5-c_6+c_7 = 0, there are
720 permutations for which d(C)=4
and there are 144 permutations with
d(C)=16. Of course, we consider
only even squares, since, evidently
d(C) always has the same parity as
1+...+7=28. I noted and David
Corneth proved (cf. comment in
A293984 with a similar proof) that every
entry of a row is divisible by the last entry
of this row.
Dividing every entry of the 7th row by 144
we obtain (from the right to
the left): {1,0,5,0,4}. 1 means
that there exists only one permutation
which gives the maximal possible square 16
such that all other such permutations are
obtained from it by a right permutations
(separately terms with + and - in alternative
sum). For example, it is {7,1,6,2,5,3,4}
and 7-1+6-2+5-3+4=4^2 and clearly
it is the maximal possible square for n=7.
Thus here the basis contains 1 element.
Further, 5 means that there exists 5 distinct
permutations C with d(C)= 4
such that all other permutations for which
d(C)=4 are obtained from these
5 ones by right permutations.
Of course, these 5 permutations
should not be obtained one from another
by a right permutation. So, here a basis contains 5
elements. For example, a basis is
{{7,6,5,4,3,2,1},{7,6,4,5,3,1,2},{7,5,6,4,2,3,1)
{6,7,5,3,4,2,1},{6,7,5,4,3,1,2}} .
Thus all entries of the second (compressed)
triangle in A293783 indicates the number of
elements in basis of the corresponding
subset.

Best regards,