# On the Adjacent Cycle Derangements

Authors: Luisa de Francesco Albasini; Norma Zagaglia Salvi
Journal: ISRN Discrete Mathematics
 (2012)

---

## Abstract

A derangement, that is, a permutation without fixed points, of a finite set is said to be an adjacent cycle when all its cycles are formed by a consecutive set of integers. In this paper we determine enumerative properties of these permutations using analytical and bijective proofs. Moreover a combinatorial interpretation in terms of linear species is provided. Finally we define and investigate the case of the adjacent cycle derangements of a multiset.


---

## Body

## 1. Introduction

Let[n]={1,2,…,n}, and let Sn denote the set of permutations of [n]. We will use both the one-line notation of a permutation of Sn and its decomposition as a product of cycles. It will be convenient to write each cycle ending with its smallest element and order cycles by increasing smallest elements.For exampleα=3176452=(3721)(654).In [1] the authors define an adjacent cycle of a permutation to be a cycle in which the elements form a consecutive set of integers.We generalize the notion defining a permutation ofSn to be adjacent cycle (a.c. for short) when in every cycle the elements form a consecutive set of integers. In other words every cycle of k elements, having i as the smallest element, is represented by the sequence (i+1,i+2,…,i+k,i).In [2] it is proved that the adjacent cycle permutations of [n] turn out to be fixed by the bijection that associates to a permutation π of [n] the permutation π′ whose one-line form is obtained from the canonical form of π by removing all inner parentheses.For example, letπ=23146785=(231)(4)(6785).Notice that we omit commas between the integers in a cycle or in a sequence, unless it leads to ambiguity.We will denote byPna and Dna the set of adjacent cycle permutations and the set of adjacent cycle derangements of [n], respectively, and pna=|Pna| and dna=|Dna| their cardinalities; moreover, Dk,na represents the set of adjacent cycle derangements having k cycles and dk,na=|Dk,na| its cardinality.We say that an adjacent cycle permutationα of [n] is extended to n+1,…,n+h, where h≥1, when n+1,…,n+h are inserted in this order in the last cycle of α before its last element. Clearly we obtain an adjacent cycle permutation of [n+h].For example, the extension of the permutationα=(21)(453) of [5] to 6,7,8 determines the new permutation (21)(456783) of [8].LetFn denote the nth Fibonacci number, with initial conditions F0=0, F1=1.We now outline the contents of this paper. In Section2 we determine properties of the adjacent cycle permutations and adjacent cycle derangements of [n], using analytical and bijective proofs.In Section3 we prove a relation involving the Fibonacci numbers, which seems new. In Section 4 we present a combinatorial interpretation of the adjacent cycle permutations in terms of linear species; as a consequence we are able to calculate the enumerative results previously obtained in a direct way. In the last section we define and investigate the derangements of a multiset.


## 2. Adjacent Cycle Permutations and Adjacent Cycle Derangements

In this section we investigate the adjacent cycle permutations and adjacent cycle derangements of the set[n], for a positive integer n. First we determine the number of adjacent cycle derangements having a fixed number of cycles.Theorem 2.1.
For positive integersn and k such that 1≤k≤n one has
(2.1)dk,na=(n-k-1k-1).Proof.
An adjacent cycle derangementπ of the set [n] with k cycles is defined by inserting k-1 dividers in the positions between two consecutive integers of the sequence (1,2,…,n), so that the numbers of integers before the first divider, between two consecutive dividers, and after last divider are greater than 1. As a consequence we have to exclude the positions between 1 and 2 and between n-1 and n and the k-2 positions that immediately follow every divider, but the last one; in other words, we have to exclude k among the n-1 possible positions. Thus the number turns out to be equal to
(2.2)(n-k-1k-1).In the more general case of adjacent cycle permutations of[n], the number pk,n of the adjacent cycle permutations having k cycles is obtained by choosing k-1 among the n-1 possible positions. See also [2].Proposition 2.2.
The number of adjacent cycle permutations of[n] having k cycles, where 1≤k≤n, is (n-1k-1), and the number of all adjacent cycle permutations is Σk=1n(n-1k-1)=2n-1.Proposition 2.3.
For every positive integern one has
(2.3)dna=∑k=1⌊n/2⌋‍(n-k-1k-1)=Fn-1.Proof.
Note that the maximum number of cycles of an adjacent cycle derangement of[n] is obtained by setting the length of all cycles equal to 2, with possibly one cycle of length 3, if n is odd. Then the maximum value of k is ⌊n/2⌋, and therefore we obtain
(2.4)dna=∑k=1⌊n/2⌋‍(n-k-1k-1).
Moreover(2.5)dna=∑k=1⌊n/2⌋‍((n-1-k-1k-1)+(n-1-k-1k-2))=∑k=1⌊(n-1)/2⌋‍(n-1-k-1k-1)+∑h=1[(n-2)/2]‍(n-2-h-1h-1)=dn-1a+dn-2a.
Thus dna satisfies the same recursive relation of the Fibonacci numbers. It is immediate to verify that d1a=0 and d2a=1; then dna=Fn-1.Another proof of (2.4) may be obtained in a bijective way.Theorem 2.4.
For every integern>2 one has
(2.6)Dna≅Dn-1a+Dn-2a.
Hence dna=dn-1a+dn-2a, where the initial conditions satisfy d1a=0 and d2a=1; thus dna=Fn-1.Proof.
Letπ be an element of Dna. We have two cases to consider.(1)
nbelongs to a cycle of π with more than 2 elements. Then π is the extension to n of a permutation π′∈Dn-1a.(2)
n belongs to a cycle ρ having 2 elements. The π is the product of an a.c. derangement α∈Dn-2a and the cycle ρ=(n,n-1).
The setsDn-1a and Dn-2a are clearly disjoint; then Dna≅Dn-1a+Dn-2a. By equating the cardinalities we obtain dna=dn-1a+dn-2a, where the initial conditions hold d1a=0 and d2a=1. Then dna=Fn-1.Example 2.5.
Let us consider the case of the set[4]={1,2,3,4}.
The a.c. permutations are the following23 permutations represented in canonical form:
(2.7)(1)(2)(3)(4),(1)(32)(4),(1)(2)(43),(1)(342),(21)(3)(4),(21)(43),(231)(4),(2341).
The a.c. derangements are (2 1)(4 3), (2 3 4 1). Their number d4a coincides with the Fibonacci number F3.
The a.c. permutations having a fixed number of cycles, for instance 2, arep4,2a=(31)=3, while the number of a.c. derangements having 2 cycles is d4,2a=(11)=1.Another bijective proof of the results of Theorem2.4 is obtained in the following theorem.Proposition 2.6.
Letn be a positive integer. Then
(2.8)Dna≅Dn-1a+Dn-2a+⋯+D2a+D1a;dna≅dn-1a+dn-2a+⋯+d2a+1.
Moreover dn+1a=dna+dn-1a, with d2a=d3a=1.Proof.
Letα∈Dna, and let α(n)=i, where 3≤i≤n-1. Then α is the product of an a.c. derangement of {1,2,…,i-1} and the cycle (i+1,i+2,…,n,i). The cases i=2 and i=n are excluded because they imply a cycle of length 1. In particular D1a={γ}, where γ=(2,3,…,n,1).
The setsDja, 2≤j≤n-1 and {γ} are disjoint; then equating the cardinalities we obtain dn+1a=dn-1a+dn-2a+⋯+d2a+1.
In a similar way we havedna and, by subtraction, last result.


## 3. Fibonacci Numbers

In this section we determine a relation involving the Fibonacci numbers.Denote byAi the set of a.c. permutations of [n] fixing the integer i.Proposition 3.1.
For every positiven,
(3.1)|Ai|={2n-2fori∈{1,n}2n-3fori∈{2,…,n-1}.Proof.
Fori equal to 1 or to n an a.c. permutation π of Ai is the product of the unitary cycle (i) and an a.c. permutation of a set of cardinality n-1. Then by Proposition 2.2 the number of these permutations is 2n-2.
Fori∉{1,n} the permutation π is the product of an a.c. permutation of the set [i-1] by the cycle (i) and an a.c. permutation of the set {i+1,…,n} having cardinality n-i. Then the number of these permutations is 2i-2·2n-i-1=2n-3.Denote(3.2)sh=Σ1≤i1≤⋯≤ih≤n|Ai1∩Ai2∩⋯∩Aih|.Theorem 3.2.
For every positive integern one has the identity
(3.3)Fn-1=s0-s1+s2-⋯+(-1)nsn,
where s0 denotes the number of all the adjacent cycle permutations of [n].Proof.
The identity follows from the inclusion-exclusion principle, the relations (3.1) and (3.2), and the condition that s0=2n-1, by Proposition 2.2.As an example consider the casen=4. Then S0=23, S1=|A1|+|A2|+|A3|+|A4| = 22+2+2+22=12, S2=|A1∩A2|+|A1∩A3|+|A1∩A4| + |A2∩A3|+|A2∩A4|+|A3∩A4| = 2+1+2+1+1+2=9, S3=4, S4=1.ThenF3=8-12+9-4+1=2.


## 4. A Combinatorial Interpretation

In this section we give an interpretation of the adjacent cycle permutations and the adjacent cycle derangements of a finite set in terms of linear species of particular linear partitions.See [3] for the fundamental notions of the theory of species.We recall that alinearly ordered set or a linear order〈L,≤〉 is a set L together with a linear order relation ≤. We will write simply L for 〈L,≤〉 and |L| for its cardinality.Ak-interval of L is a subset of the form
(4.1)[x;y]={u∈L:x≤u≤y}
having exactly k elements.LetLin be the category of finite linearly ordered sets and order bijections, and let Set be the category of finite sets and functions.Alinear species of combinatorial structures is a functor S:Lin→Set.Thecardinality of a linear species S is the formal geometric series(4.2)|S|=Σn≥0|S[n]|tn,
where [0]=∅ and [n]={1,2,…,n} for n>0.Alinear partitionπ of a finite linear order L is a family of nonempty disjoint intervals, called blocks, whose union is L. For an integer h, we will say that a block B is an h-block of π when B has cardinality h.LetS and T be two linear species, with T[∅]=∅. The composition S∘T is the species equivalent to giving a partition π of L, a structure of species T on each block of π, and a structure of species S on π.Thegeometric species or uniform speciesG is the species defined by G[L]={*} (a singleton), for all finite linear orders L.The cardinality ofG is the geometric series
(4.3)G(t)=Σn≥0tn=11-t.
The linear species G-1 is defined by
(4.4)(G-1)[L]={∅forL=∅{*}forL≠∅
for every L∈Lin. Its cardinality is the series
(4.5)(G-1)(t)=11-t-1=t1-t.
For an integer h, the h-geometric species Gh is defined as the singleton on every linear order L of cardinality h and as the empty set in all other cases:
(4.6)Gh[L]={{*}for|L|=h∅for|L|≠h.
Thus the cardinality of Gh is the series Gh(t)=th.


### 4.1. The Linear Species of Adjacent Cycle Permutations

LetP be the linear species of the linear partitions. Giving a linear partition of a finite linear order L is equivalent to giving a partition π of L, a structure of a nonempty linear order on each block of π, and a geometric structure on π. Therefore we have the isomorphism
(4.7)P=G∘(G-1).Then, passing to the cardinalities and setting|P|=P(t)=Σpntn, the relation (4.7) becomes
(4.8)P(t)=11-t∘t1-t=1-t1-2t=1+t+2t2+22t3+⋯.Expanding the series, we obtain(4.9)pn={2n-1forn>01forn=0.From the definition it follows that an adjacent cycle permutation of[n] corresponds to a linear partition of the linear order L=[1,2,…,n] in which the blocks are nonempty.For example, the linear partitions of[1,2,3] are
(4.10){[1],[2],[3]},{[1],[2,3]},{[1,2],[3]},{[1,2,3]}.
The corresponding a.c. permutations of {1,2,3} in cyclic form are
(4.11){(1)(2)(3),(1)(32),(2,1)(3),(2,3,1)}.
Then the number of a.c. permutations coincides with the number of linear partitions of [1,2,…,n].


### 4.2. The Linear Species of the Adjacent Cycle Permutations withh Cycles

LetPh be the linear species of the linear partitions with h blocks, and let ph,n be the cardinality of Ph[L] when |L|=n.Giving a structure of speciesPh on a finite linear order L is equivalent to giving a partition π of L, a structure of linear order with at least 1 element on each block of π, and a structure of a linear order with h elements on π. Therefore we have
(4.12)Ph=Gh∘(G-G1).Passing to the cardinalities we have(4.13)th∘(11-t-1)=th·(11-t)h=th·Σk≥0(h+k-1k)tk=Σ(h+k-1k)tk+h.Fork+h=n, we obtain
(4.14)ph,n=(n-1h-1).In the previous section we interpretedP as the linear species of a.c. permutations; now we interpret Ph as the linear species of a.c. permutations with h cycles.From Proposition2.2 we have ph,n=(n-1h-1). This value coincides with the coefficient of tk+h in the previous generating function when k+h=n.


### 4.3. The Linear Species of Adjacent Cycle Derangements

An adjacent cycle derangement of[n] is an a.c. permutation without fixed points.The linear speciesΔa of the a.c. derangements of a finite set corresponds to giving a finite linear order L, a partition π of L, a structure of linear order of cardinality at least 2 on each block of π of L, and a geometric structure on π. Therefore
(4.15)Δa=(G-1)∘(G-G1-G2).
Passing to the cardinalities we obtain
(4.16)Σn≥0dnatn=t1-t∘(11-t-1-t)=t21-t-t2.
As t/(1-t-t2)=Σk≥0Fk·tk is the series of the Fibonacci numbers with initial conditions F0=0, F1=1, then
(4.17)dna=Fn-1.


### 4.4. The Linear Species of the Adjacent Cycle Derangements withh Cycles

LetΔha be the linear species of the a.c. derangements with h cycles, and let dh,na be the cardinality of Δha[L] when |L|=n.In order to give a structure of speciesΔha on a finite linear order L one has to give a partition π of L, a structure of linear order with at least 2 elements on each block of π, and a structure of a linear order with h elements on π. Therefore we have
(4.18)Δha=Gh∘(G-G1-G2).Passing to the cardinalities we have(4.19)th∘(11-t-1-t)=t2h·(11-t)h=t2h·Σk≥0(h+k-1k)tk=Σk≥0(h+k-1k)tk+2h.Fork+2h=n, we obtain
(4.20)dh,na=(n-h-1h-1),
which coincides with the result of Theorem 2.1.In [4] the above-mentioned species were investigated in a different context.


## 4.1. The Linear Species of Adjacent Cycle Permutations

LetP be the linear species of the linear partitions. Giving a linear partition of a finite linear order L is equivalent to giving a partition π of L, a structure of a nonempty linear order on each block of π, and a geometric structure on π. Therefore we have the isomorphism
(4.7)P=G∘(G-1).Then, passing to the cardinalities and setting|P|=P(t)=Σpntn, the relation (4.7) becomes
(4.8)P(t)=11-t∘t1-t=1-t1-2t=1+t+2t2+22t3+⋯.Expanding the series, we obtain(4.9)pn={2n-1forn>01forn=0.From the definition it follows that an adjacent cycle permutation of[n] corresponds to a linear partition of the linear order L=[1,2,…,n] in which the blocks are nonempty.For example, the linear partitions of[1,2,3] are
(4.10){[1],[2],[3]},{[1],[2,3]},{[1,2],[3]},{[1,2,3]}.
The corresponding a.c. permutations of {1,2,3} in cyclic form are
(4.11){(1)(2)(3),(1)(32),(2,1)(3),(2,3,1)}.
Then the number of a.c. permutations coincides with the number of linear partitions of [1,2,…,n].


## 4.2. The Linear Species of the Adjacent Cycle Permutations withh Cycles

LetPh be the linear species of the linear partitions with h blocks, and let ph,n be the cardinality of Ph[L] when |L|=n.Giving a structure of speciesPh on a finite linear order L is equivalent to giving a partition π of L, a structure of linear order with at least 1 element on each block of π, and a structure of a linear order with h elements on π. Therefore we have
(4.12)Ph=Gh∘(G-G1).Passing to the cardinalities we have(4.13)th∘(11-t-1)=th·(11-t)h=th·Σk≥0(h+k-1k)tk=Σ(h+k-1k)tk+h.Fork+h=n, we obtain
(4.14)ph,n=(n-1h-1).In the previous section we interpretedP as the linear species of a.c. permutations; now we interpret Ph as the linear species of a.c. permutations with h cycles.From Proposition2.2 we have ph,n=(n-1h-1). This value coincides with the coefficient of tk+h in the previous generating function when k+h=n.


## 4.3. The Linear Species of Adjacent Cycle Derangements

An adjacent cycle derangement of[n] is an a.c. permutation without fixed points.The linear speciesΔa of the a.c. derangements of a finite set corresponds to giving a finite linear order L, a partition π of L, a structure of linear order of cardinality at least 2 on each block of π of L, and a geometric structure on π. Therefore
(4.15)Δa=(G-1)∘(G-G1-G2).
Passing to the cardinalities we obtain
(4.16)Σn≥0dnatn=t1-t∘(11-t-1-t)=t21-t-t2.
As t/(1-t-t2)=Σk≥0Fk·tk is the series of the Fibonacci numbers with initial conditions F0=0, F1=1, then
(4.17)dna=Fn-1.


## 4.4. The Linear Species of the Adjacent Cycle Derangements withh Cycles

LetΔha be the linear species of the a.c. derangements with h cycles, and let dh,na be the cardinality of Δha[L] when |L|=n.In order to give a structure of speciesΔha on a finite linear order L one has to give a partition π of L, a structure of linear order with at least 2 elements on each block of π, and a structure of a linear order with h elements on π. Therefore we have
(4.18)Δha=Gh∘(G-G1-G2).Passing to the cardinalities we have(4.19)th∘(11-t-1-t)=t2h·(11-t)h=t2h·Σk≥0(h+k-1k)tk=Σk≥0(h+k-1k)tk+2h.Fork+2h=n, we obtain
(4.20)dh,na=(n-h-1h-1),
which coincides with the result of Theorem 2.1.In [4] the above-mentioned species were investigated in a different context.


## 5. Adjacent Cycle Derangements of a Multiset

LetM={1a12a2⋯mam} be a multiset, where ai, the multiplicity of the element i, satisfies the condition ai≥1. Recall, [5, page 24], that the intercalation product α⊺β of two permutations α and β of M is obtained by the two-line notation of α and β, setting beside these two-line representations and sorting the columns into nondecreasing order of the top line.It is known that every permutationπ of M has a unique representation as the intercalation of cycles
(5.1)π=(x11⋯x1n1y1)⊺(x21⋯x2n2y2)⊺⋯⊺(xi1⋯xtntyt),
where t≥0,
(5.2)y1≤y2≤⋯≤yt,(5.3)yi<xijfor1≤j≤ni,1≤i≤t.
In other words in this representation, said canonical, the smallest element of each cycle is at the end of the cycle and is smaller than every other element; moreover the sequence (5.2) of last elements is in nondecreasing order.Now if we drop the parentheses and the⊺’s in this representation, we obtain a sequence which represents a permutation π′ in one-line form. Namely the one-line representation of π′ is
(5.4)x11⋯x1n1y1x21⋯x2n2y2⋯xi1⋯xtntyt.
This procedure determines a function g:M→M such that g(π)=π′, which turns out to be a bijection.In [2] it is proved that a permutation π is g-fixed if and only if in every cycle the elements form a nondecreasing sequence of integers but the last element which is lesser than every other in the cycle. In the case in which M is a set we recognize the notion of adjacent cycle permutation.Now we define a permutation of a multisetadjacent cycle when in every cycle two consecutive elements a,b satisfy the condition that either b=a+1 or b=a.In particular an a.c. permutation without1-cycles is an a.c. derangement.In relation to the multisetM={1,2a2,…,mam}, where ai≥1, for 2≤i≤m, denote by Da(M) and Dka(M) the sets of a.c. derangements of M and a.c. derangements of M having k cycles, respectively, and da(M) and dka(M) their cardinalities.Theorem 5.1.
LetM={1,2a2,…,mam} be a multiset, where ai≥1, for 2≤i≤m. Then
(5.5)Da(M)≅Da(M′)+Da(M′′),
where M′={1,2a2,…,(m-1)am-1} and M′′={1,2a2,…,(m-1)am-1-1}; it implies da(M)=da(M′)+da(M′′).Proof.
Letπ be an element of Da(M). Denote m1,m2,…,mam the am elements of M coinciding with m. We have two cases to consider.(1)
mam belongs to a cycle of π with more than 2 distinct elements. Then π is the extension to m1,m2,…,mam of a permutation π′∈Da(M′).(2)
mam belongs to a permutation ρ having 2 distinct elements. Then π is product of a cycle α∈Da(M′′) and the cycle ρ=(m1,m2,…,mam,m-1).
The setsDa(M′) and Da(M′′) are clearly disjoint; then Da(M)≅Da(M′)+Da(M′′). Equating the cardinalities we obtain da(M)=da(M′)+da(M′′).Note that ifM is the set [n+1], then M′=[n], M′′=[n-1], and the initial conditions hold d1a=0, d2a=1; thus we obtain the results of Theorem 2.4.Proposition 5.2.
LetM={1,2a2,…,mam} be a multiset, where ai≥1, for 2≤i≤m. Then
(5.6)Da(M)≅Da(Mm-1)+Da(Mm-2)+⋯+Da(M2)+Da(M1),(5.7)da(M)=da(Mm-1)+da(Mm-2)+⋯+da(M2)+da(M1).Proof.
Clearly the setsDa(Mi) form a partition of Da(M), and there is a bijection between Da(M) and Da(Mm-1)+Da(Mm-2)+⋯+Da(M2)+Da(M1). Equating the cardinalities we obtain the relation (5.7).In the case of the set[n] we obtain Proposition 2.6.In Proposition2.2 it is proved that the number of a.c. permutations of [n] is 2n-1; now we prove that this number coincides with the number of a.c. derangements of particular multisets.Theorem 5.3.
Letm≥2 be an integer and M={1,2a2,…,mam} a multiset, where ai>1 for 2≤i≤m-1 and am≥1. Then
(5.8)Da(M)≅P([m-1])
and da(M)=2m-2.Proof.
Letα be an a.c. permutation of the ordered set {1,2,…,m-1}, having k cycles; then α is obtained by inserting k-1 dividers in the positions between an integer and its consecutive in the sequence (1,2,…,m-1). Let f be the map that associates to α the a.c. permutation α′ of M such that if in α there is a divider between t and t+1 then in α′ a divider is inserted before last and last but one of the elements t. Because the multiplicity of every element of M, but the first and possibly the last one, is greater than 1, then between two distinct dividers there are at least two distinct elements and the permutation turns out to be a derangement.
Conversely, letβ be an a.c. derangement of M having k cycles. We may represent β by inserting k-1 suitable dividers in the positions before last element of the sequence i,…,i, having ai elements, 1≤i≤m. In correspondence of every possible divider before last i we insert a divider between i and i-1 in the sequence (1,2,…,m-1). Thus we obtain an a.c. permutation of the set [m-1] having k cycles. This implies that there is a bijection between Da(M) and P([m-1]). Passing to the cardinalities we obtain the enumerative result.Note that the result of Theorem5.3 does not depend on the multiplicities, but only on the condition that they are greater than 1 (but a1=1 and possibly am).For instance, form=4 the a.c. permutations of [3] are
(5.9)(1)(2)(3),(1)(32),(21)(3),(231).
The corresponding a.c. derangements of M={1,23,32,42} are
(5.10)(221)(32)(443),(221)(33442),(22231)(443),(22233441).Proposition 5.4.
LetM1={1,2a2,…,mam} and M2={1,2a2,…,(m-1)am-1,mbm} be two multisets, where ai>1, for 2≤i≤m-1, am,bm≥1, am≠bm. Then da(M1)=da(M2).Proof.
By Theorem5.3 the values of da(M1) and da(M2) do not depend on the multiplicity of m.As particular case we obtain the following result.Proposition 5.5.
LetM={1,2,…,n-1,(n)h} be a multiset, where h>1. Then dka(M)=(n-k-1k-1) and da(M)=Fn-1.Proof.
An a.c. derangementα of the multiset M={1,2,…,n-1,(n)h}, where h>1, with k cycles of length greater than 1 coincides with the number of a.c. derangement of the set {1,2,…,n} with k cycles. Then dka(M) and da(M) follow from Theorem 2.1 and Proposition 2.3.For instance, letM={1,2,3,4,5,6,6,6} and Q={1,2,3,4,5,6}. In order to obtain the a.c. derangements of M we have to consider the three positions 2-3,3-4,4-5. Assign 1 or 0 to a position when there is or there is not a divider; we obtain that the possible sequences are (0,0,0), (0,0,1), (0,1,0), (1,0,0), and (1,0,1). The corresponding derangements are (23456661), (2341)(6665), (231)(56664), (21)(456663), and (21)(43)(6665).Lemma 5.6.
LetM={1,2a,b1,b2,…,bk} be a multiset, where a>1.
Thenda(M)=Fk+2.Proof.
The set of a.c. derangements ofM is partitioned into the sets P1,…,Pk, where Pi, 1≤i≤k, is the set of the derangements which contain the cycle (2a-11) extended to the i elements 2,b1,…,bi-1, and one of the derangements of the set {bi,…,bk}. The case i=1 corresponds to the derangement (2a1). Thus the number of a.c. derangements is Fk+Fk-1+⋯+F2+F1+F1. Then the result follows.Theorem 5.7.
LetM={1,2a2,…,mam,b1,b2,…,bk} be a multiset, where ai>1 for 2≤i≤m.
Thenda(M)=2m-2·Fk+2.Proof.
The proof is by induction onm. For m=2 the result follows from Lemma 5.6.
Now assume the result holds for every integer lesser thanm.
Note that the elements ofDa(M) can be partitioned into two sets D1 and D2, where D1 consists on the set of the derangements which are the product of the cycle formed by the elements of the multiset M1={1,2a2-1} and the derangements of the multiset M2={2,3a3,…,mam,b1,b2,…,bk}, while D2 is formed by the derangements obtained from the elements of M2, where the first cycle now contains the elements of M1.
It implies thatda(M)=2da(M2) and, by the induction assumption, da(M)=2·2m-3·Fk+2=2m-2Fk+2.Theorem 5.8.
LetM={1,2,…,k,c1a1,…,cmam} be a multiset where ai>1, 1≤i≤m, k>2, and m>1.
Then(5.11)da(M)=2m-1·Fk.Proof.
The proof is by induction onm.
Letm=2. Then the set of derangements is partitioned into the set of derangements of {1,2,…,k,c1a1-1} with the addition of the cycle (c2a2,c1) and the set of derangements obtained by extending last cycle of every derangement of {1,2,…,k,c1a1-1} to the elements c2a2,c1.
Both the sets have cardinalityFk by Proposition 5.5; then the number of derangements is 2Fk.
Now we prove the result assuming it holds for every integer lesser thanm.
The set of derangements ofM is partitioned into the set D1 of derangements of M1={1,2,…,k,c1a1,…,cm-1am-1-1} with the addition of the cycle (cmamcm-1) and the set D2 of derangements obtained from D1 by the extension of last cycle of every derangement to the elements cm-1, cmam. By the assumption hypothesis |D1|=2m-2·Fk, and, since |D1|=|D2|, we obtain the result.



---

*Source: 340357-2012-12-02.xml*