Abstract:
The difference specification of a substitution $s\in S_n$ may be defined as an unordered multiset of differences $\Delta_i\equiv(s(i)-i)(\operatorname{mod}n)$, $1\le i\le n$; the number of unappeared differences is called a deficit of substitution. We find formulas for the number of all possible difference specifications and for the number of difference specifications for substitutions with given deficit. Under some conditions exact and asymptotic distributions of the deficit are found.
Key words:difference characteristics, difference specifications of substitutions, deficits of equivalence classes of substitutions.