¿^creative , ars mathematica ^commons contemporánea Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 10 (2016) 9-1Í Counting even and odd restricted permutations Vladimir Baltic University of Belgrade, Faculty of Organizational Sciences, Jove IliCa 154, 11000 Belgrade, Serbia Dragan Stevanovic * University ofPrimorska, Institute Andrej Marusic, Muzejski trg 2, 6000 Koper, Slovenia and Mathematical Institute of the Serbian Academy of Science and Arts, Knez Mihajlova 36, 11000 Belgrade, Serbia Received 5 May 2014, accepted 15 May 2014, published online 24 January 2015 Abstract Let p be a permutation of the set Nn = {1, 2,... ,n}. We introduce techniques for counting N(n; k, r, I; n), the number of even or odd restricted permutations of Nn satisfying the conditions — k < p(i)—i < r (for arbitrary natural numbers k and r) and p(i) —i £ I (for some set I) and n = 0 for even permutations and n = 1 for odd permutations. Keywords: Even and odd restricted permutations, exact enumeration, recurrences, permanents. Math. Subj. Class.: 05A15, 05A05, 11B37, 15A15 1 Introduction Let p be a permutation of the set Nn = {1, 2,..., n}. So, p(i) refers to the value taken by the function p when evaluated at a point i. A class of permutations in which the positions of the marks after the permutation are restricted can be specified by an n x n (0,1)-matrix A = (aij) in which: 1, if the mark j is permitted to occupy the i-th place; 0, otherwise. The following result is a well known fact on the number of restricted permutations. *The second author was supported by Research Programme P1-0285 and Research Project J1-4021 of the Slovenian Research Agency and Research Grant ON174033 of the Ministry of Education and Science of Serbia. E-mail addresses: baltic@matf.bg.ac.rs (Vladimir Baltic), dragance106@yahoo.com (Dragan Stevanovic) ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/ 10 Ars Math. Contemp. 10 (2016) 31-44 Theorem 1.1 ([1]). The number of restricted permutations is given by the permanent of a square matrix A: per A = a1p(1)a2p(2) • • • anp(n), pesn where p runs through the set Sn of all permutations of Nn. □ Next, we will define strongly and weakly restricted permutations (for more informations see [13]). Definition 1.2. In strongly restricted permutations of Nn, the number r = j=1 aij is uniformly small, i.e., r < K (i = 1,2,..., n), where K is an integer independent of n. In weakly restricted permutations, n — r is uniformly small. Let us briefly overview historical development of the topic of restricted permutations. Probably the most well known example is the derangement problem or "le Probleme des Rencontres" (see [1] or [6]). Most of the restricted permutations considered in current literature deal with pattern avoidance. For surveys of such studies, see [3] or [9]. For a related topic of pattern avoidance in compositions and words see [5]. Detailed introduction to weakly restricted permutations can be found in [1]. A general method of enumeration of permutations with restricted positions was developed by Ka-plansky and Riordan in a series of papers (they developed the theory of rook polynomials for these purposes—see [6], [7], [8], [18]). Lagrange, Lehmer, Mendelsohn, Tomescu and Stanley ([12,13,15,16,20,19]) studied particular types of strongly restricted permutations satisfying the condition |p(i) — i| < d, where d is 1, 2, or 3 (more information on their work can be found in [1]). Lehmer [13] classified some sets of strongly restricted permutations. The first author showed in [1] how to handle all five types of Lehmer's permutations. For the number of restricted permutations in a circular case the following is known: Stanley [19, Example 4.7.7] explored type k = 2 with the transfer-matrix method, Baltic [2] used finite state automata for type k = 2, and Li et al. [14] explored the k = 3 by expanding permanents. An explicit technique for creating a system of the recurrence equations was given in [1], based on a simple mapping p from combinations of Nk+r+1 and some crucial differences between the transfer-matrix Method and the newly proposed technique were given. Krafft and Schaefer in [11] find the closed formula for the strongly restricted permutations of the set Nn satisfying the condition |p(i) — i| < k, where k + 2 < n < 2k + 2. Panholzer [17] and Kl0ve [10] made progress in symmetric cases (Panholzer used finite state automata, while Kl0ve used modified transfer-matrix method based on expanding permanent) and they found the asymptotic expansion and gave bounds for the denominator of corresponding generating functions. Here we pursue the more general, asymmetric cases and the cases where more numbers are forbidden than in the ordinary derangements for even and odd strongly restricted permutations. Our method determines the number of restricted permutations that are even, and the number of restricted permutations that are odd. In Section 2 we introduce a general technique for counting N(n; k, r, I; n), the number of even or odd restricted permutations (N(n; k, r, I; n) is defined in abstract). In Section 3 we illustrate it with several examples. Using a program that implements our technique, we have contributed about a hundred sequences to the Sloane's online encyclopedia of integer sequences [21]. V. Baltic and D. Stevanovic: Counting even and odd restricted permutations 11 2 Counting N(n; k, r, I; n) We established the connection between the number of restricted permutations and the permanent function of a matrix A, per A, in Theorem 1 from the introduction. The Laplace expansion of the permanent function (this is the same as for the determinant function) is computationally inefficient for high dimension because for n x n matrices, the computational effort scales with n!. Therefore, the Laplace expansion is not suitable for large n. However, the matrices obtained in the Laplace expansions for restricted permutations have the regular structure, so called band matrices (a band matrix is a sparse matrix whose nonzero entries are confined to a diagonal band, comprising the main diagonal and zero or more diagonals on either side), and their expansions can be reduced to a system of linear recurrence equations. We present a general technique for counting N(n; k, r, I; n), the number of even or odd (n = 0 for even permutations and n = 1 for odd permutations) restricted permutations satisfying the conditions —k < p(i) - i < r and p(i) - i g I for all i e Nn, where k < r < n, and I is a fixed subset of the set {—k +1, —k + 2,..., r — 1}. Assume that I contains x elements, |11 = x. Our technique proceeds in six steps: 1. Create C, a set of all (k + 1)-element combinations of the set Nfc+r+i containing element k + r + 1 . 2. Create D, a set of all ordered pairs D = (C, n), where C eC and n e {0,1}. 3. Introduce an integer sequence aD (n) for each ordered pair D e D. 4. Apply the mapping ^ (defined below) to each ordered pair. 5. Create a system of linear recurrence equations (later we will see that these equations correspond to the Laplace expansion of a permanent of the matrix A): 6. Solve the system to obtain equations N(n; k,r, I;0) = a((r+1jr+2i...ir+k+1)io)(n) and N(n; k, r, I; 1) = a((r+iir+2,...,r+fc+i),i)(n). We next describe these steps in detail and then prove that N(n; k, r, I; n) is indeed equal to a((r + 1,r+2,...,r + fc+1),n)(n). Definition 2.1. Let C denote a set of all combinations with k + 1 elements of the set Nk+r+1, which contain k + r + 1. We represent these combinations as strictly increasing ordered (k + 1)-tuples. For example, all such combinations with 3 elements of the set N5 = {1, 2, 3,4,5} are represented (in reverse lexicographic order) by: (3,4, 5), (2, 4, 5), (2, 3, 5), (1,4, 5), (1, 3, 5), (1, 2, 5). In examples we will use easier notation: D'e(D) = i D eD! D) 1 ^m(D), D eDm, defined by : Di ^ D and ^ : Dm ^ Dfc+i_m, for m = 0,1,..., x, defined by yi(D) = Di, ^m(D) = SD'. V. Baltic and D. Stevanovic: Counting even and odd restricted permutations 13 We use these mappings to find a system of 2 • (k+r) linear recurrence equations (one equation per ordered pair, i.e. two equations per combination - one corresponding to even permutations and another corresponding to odd permutations): if we have y>i (D) = D' then we have the linear recurrence equation: od (n + 1) = aD> (n) and if we have ^™(D) = (D', D2,..., D'k+1_m) then we have the linear recurrence equation: od (n + 1) = «d; (n) + Od^ (n) +-----+ Od^+1-m (n). The initial conditions are: a((r+1,r+2,...,r+k+1),0)(0) = 1 and aD(0) = 0 for all D = ((r +1,r + 2,...,r + k + 1), 0).' This system can be easily solved, for example by using the standard method based on generating functions. From this system of linear recurrence equations we are able to get a linear recurrence equation and a generating function for N(n; k, r, I; n). We will prove that N(n; k,r,1;0) = a((r+1,r+2,...,r+k+1),0)(n) and N (n; k,r,/;1) = a((r+1,r+2,...,r+fc+1),1)(n). Thus, from the matrix of this system, S, we can find N(n; k, r, I; n) as the element in the first row and the first column of the matrix Sn, i.e., the number of the closed paths in the digraph G whose adjacency matrix is S (this observation is important because we can apply the Transfer matrix method to the matrix S). We apply this observation to determine the computational complexity of our technique: Sn can be computed with repeated squaring [4] in O(log2 n) operations. Hence, our technique evaluates the number of restricted permutations more efficiently than the straightforward techniques of filtering permutations or expanding the permanent per A. All the generating functions that we derive using our technique are rational. We have a system of 2 • (k+r) linear recurrence equations which leads us to the upper bound for the degree d of the denominator polynomial: d < 2 • (k+r). It is sufficient to compute a finite number of values, in particular 2 • (k+r) of them, to find the generating function. Theorem 2.3. For even permutations N (n; k,r, I ;0) = a((r+1,r+2,...,r+k+1),0)(n) and for odd permutations N(n; k, r, I; 1) = a((r+1,r+2,...,r+k+1),1)(n). Proof. We establish the correspondence between combination C = (c1, c2,..., ck) G C and the specific matrix MC = f (C). We introduce a set Mt (for a fixed t) of matrices MC that correspond to the sequences aDo (n) and aD; (n), where D0 = (C, 0) and D1 = (C, 1). Let matrix MC = (mj) satisfies the following conditions: 1) the first k + 1 rows is definied by: {1 j r _ Ci G I ' 1 for j = 1,2,..., c and 0, j + r _ Ci G I j , , , 4 mij = 0 for j > c4; 2) elements in the last t _ (k +1) rows satisfy: mij- = 1 for _k < j _ i < r, j _ i G I and mij = 0 otherwise. Denote by Mt the set of all t x t (t > r) matrices MC for C G C. From the matrix MC G Mt, we can determine the corresponding combination C = (c1,c2,..., ck) G C: let c4 denotes the column of the last one in the i-th row of the matrix M, i = 1,2,..., k +1. 14 Ars Math. Contemp. 10 (2016) 31-44 So, the function f : C ^ Mt, defined by f (C) = MC is a bijection. We associate an n x n matrix A = (aj) defined by: 1, if — k < j — i < r, j — i G I, * 0, otherwise with the strongly restricted permutations satisfying —k < p(i) — i < r and p(i) — i e I. As stated in the introduction, the number of all permutations (even and odd) satisfying —k < p(i) — i < r and p(i) — i e I is equal to per A. Notice that A e Mn with cj = r + i, where 1 < i < k + 1, and thus the combination corresponding to A is (r + 1,r + 2, .. . ,r + k +1). We next observe that the recurrence equations from step 5. (see page 11) correspond to the expansion of the permanent of matrices from Mt by the first row (yi) or by the first column (in cases of all of y^; note that when we skip an element cy, it corresponds to a zero element in the first column). During this expansion we need to take care about the parity of the permutation under construction. First, note that at each step of construction determines the position of the smallest of the remaining elements of the permutation. Let q denote the number of already used elements in the construction of the restricted permutation. Define a monotonically increasing sequence w of positions in the permutation which have not yet been assigned values: w = (wi,w2, . . . , Wn-q), where wi < W2 < • • • < Wn-q. If we make an expansion by the first row (we have one in the first column), it corresponds to p(w1) = q +1 and the parity of the permutation under construction doesn't change because we haven't got any new inversions. If we make an expansion by the first column and if we have 1 in the i-th row (i.e. at the position (i, 1) in the matrix A is 1), it corresponds to p(wj) = q +1. There are i — 1 numbers: p(w1),p(w2),... ,p(wi-1) which made new inversions with p(wj) = q + 1, because all of them have not been assigned yet, so they are all greater than q +1. So, the parity of the permutation under construction depends on the parity of i: • if i is even then there are odd number (i — 1) inversions, so we need to change the parity of the permutation under construction, n' = 1 — n; • if i is odd then there are even number (i — 1) inversions, so we don't need to change the parity of the permutation under construction, n' = n. These observations lead to the main conclusions: N(n; k, r, I; 0) = a((r+ii...ir+fc+i),o)(n) N(n; k, r, I; 1) = a((r+iir+2,...,r+fc+i),i)(n). □ 3 Examples We illustrate the technique from the previous section on two examples. Example 3.1. We find the number of even (odd) permutations of the set Nn, satisfying the condition —1 < p(i) — i < 1 for all i G Nn. It is usually referred to as a permutation of length n within distance 1. V. Baltic and D. Stevanovic: Counting even and odd restricted permutations 15 In this case we have k = r = 1, i.e. k + r +1 = 3 and C = {23,13}. ^(23, 0) = {(23,0), (13,1)}, yi(13,0) = {(23,0)}, ^(23,1) = {(23,1), (13, 0)}, (13,1) = {(23,1)}, from which we get the system of linear recurrence equations: a(23,0)(n + 1) = a(23,0)(n)+ a(i3,i)(n), a(i3,o)(n + 1) = a(23,o)(n), a(23,i)(n + 1) = a(23,i)(n)+ a(i3,o)(n), a(i3,i)(n + 1) = a(23,i)(^iK with the initial conditions a(23 0)(0) = 1, a(i3,0)(0) = 0, a(23,i)(0) = 0, a(i3,i)(0) = 0. If we substitute a(23,0)(n) = an, a(i3,0)(n) = bn, a(23,i)(n) = c„ and a(i3,i)(n) = d„ we have a simpler form: an+i an + dn, bn+i an cn+i cn + bn, dn+i cn • The initial conditions are a0 = 1, b0 = c0 = d0 = 0. For a sequence which is denoted by a lower case letter we will denote the corresponding generating function by the same upper case letter (an ^ A(z), bn ^ B(z), and so on). We find the following system of linear equations (variables are A(z), B(z), C(z), D(z)): = A(z) + D(z), BM= A(z), CM = C (z) + B(z), DM = C (z) z z z z and part of its solution that we are interested in is: A(z) =-—z-j, C(z) =--- . () 1 - 2z + z2 - z4, () 1 - 2z + z2 - z4 From the denominator of these generating functions 1 — 2z + z2 — z4, we can find the linear recurrence equations an = 2an-i — an-2 + an-4 and cn = 2cn-i — cn-2 + cn-4. When we solve these equations we find the general terms of these sequences: an ^ (Fn+i + xn) , cn ^ (Fn+i xn) , where Fn denotes n-th Fibonacci number (F = F2 = 1, Fn+i = Fn + Fn-i; A000045 at [21]), and Xn = cos + ^ sin ^ (A010892 at [21]). The number of even permutations, an, and odd permutations, cn, both satisfying the condition |p(i) - i| < 1, for all i G Nn is determined by previous formulae or by their generating functions A(z) and C(z): n 0 1 2 3 4 5 6 7 8 9 10 On 1 1 1 1 2 4 7 11 17 27 44 cn 0 0 1 2 3 4 6 10 17 28 45 These sequences are A005252 and A024490 at [21]. ■ Example 3.2. We find the number of even (odd) permutations of the set Nn, satisfying the condition p(i) - i G {-2,0, 2}. 16 Ars Math. Contemp. 10 (2016) 31-44 In this case we have k = r = 2, i.e. k + r + 1 = 5, set 1 = {-1,1}, which implies (r + 1 -1) = {2,4} and C = {345,245, 235,145,135,125}, which is separated into sets: C1 = {145,135,125}, C0 = 0, C2X = {345, 235}, C| = {245}. <¿>2(345,0) = {(345,0), (235,0)}, <¿2(245,0) = {(l35,0)}, <2(235,0) = {(l45, l), (125,0)},