[seqfan] Basis in subsets of permutations described in A293783

Vladimir Shevelev shevelev at bgu.ac.il
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
{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 

Best regards,

More information about the SeqFan mailing list