[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
{{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,
Vladimir
More information about the SeqFan
mailing list