In 2019, the authors of the current paper conducted a survey research on human-generated permutations [Nagata and Takei, Bull. OUPS 2019]. In the following year, they analyzed the data from
a different perspective and observed that people tend to generate certain types of permutations, then
defined types NAP (nearly arithmetic progression) and pNAP (pseudo-nearly arithmetic progression)
of permutations as mathematical abstractions of such tendency [Nagata and Takei, Bull. OUPS 2020].
Then, in [Nagata and Takei, Bull. OUPS 2021], the number of permutations of these types were bounded
by asserting that the set of the inverse permutations of S´os type, which are defined as the translation
of so-called S´os permutations [S´os, Ann. Univ. Sci. Budapest. E¨otv¨os, Sect. Math. 1958] by a constant,
include the set of the permutations of NAP type and are included in the set of the permutations of
pNAP type. Especially, the authors obtained a lower bound of the number of the permutations of pNAP
type as the number of the permutations of S´os type whose explicit formula is obtained from the number
of S´os permutations in [Sur´anyi, Ann. Univ. Sci. Budapest. E¨otv¨os, Sect. Math. 1958], [Shutov, Chebyshevskii Sb. 2014], [Bockiting-Conrad, Kashina, Petersen and Tenner, Amer. Math. Monthly 2021], with
the assertion by computer experiments that the set of the inverses of S´os type-permutations is indeed
the same as the set of the permutations of pNAP type as long as the degree n of the permutations is
not greater than 50. Thus, a remaining problem of major interest is bounding the number of pNAP
permutations from above. In this paper, we address this problem. One of our results is that pNAP and
the inverses of S´os permutations satisfy essentially identical recurrence relation. It gives immediately an
upper bound (n − 1)n2 of the number of permutations of pNAP type. We note that the upper bound is
of the same order in n as the lower bound, the number of the inverses of S´os type-permutations. Furthermore, using the recurrence relation, an efficient algorithm for the enumeration of pNAP permutations
is given and used to enlarge the upper limit of the degrees n for which the observed property “pNAP is
inverse-S´os-type” is confirmed to 1300 from 50 in our previous paper.
ある型の置換の個数についてII
ある型の置換の個数について II
(1.79MB)
