Baltić V.  

Različiti pristupi prebrojavanju permutacija sa ograničenjima

We will give a survey of techniques for counting the number of restricted permutations satisfying the conditions -k ≤ p(i)-i ≤ r (for arbitrary natural numbers k and r) and p(i)-i I (for an arbitrary set I). We will introduce pure expanding of the permanent, Stanley's Transfer-matrix method, Factorization in Free Monoids, counting based on the finite state automata and our technique for generating a system of linear recurrence equations that enumerate the number of restricted permutations. We will demonstrate all approaches on two examples and we will establish the connections with other combinatorial structures as compositions and subsets with some additional restrictions.