Fairouz Beggas^[a], Margherita Maria Ferrari^[b] and Norma Zagaglia Salvi ^[c]

Combinatorial Interpretations and Enumeration of Particular Bijections

Pages:
Received: 23 June 2015
Accepted in revised form: 19 July 2016
Mathematics Subject Classification (2010): 05A05, 05A15, 05A19.
Keywords: Permutation, derangement, species, linear species, permutation species, uniform species, derivative of a species, isomorphic species.
Author address:
[a]: University of Lyon, LIRIS UMR5205 CNRS, Claude Bernard Lyon 1 University, 43 Bd du 11 Novembre 1918, Villeurbanne, F-69622, France
[b], [c]: Politecnico di Milano, IDipartimento di Matematica, P.zza Leonardo da Vinci 32, Milano, 20133, Italy

Abstract: Let \(n\) be a nonnegative integer. We call widened permutation a bijection between two \((n+1)\)-sets having \(n\) elements in common. A widened permutation is a widened permutation without fixed points. In this paper we determine combinatorial interpretations of these functions in the context of the theory of species of Joyal. In particular, we prove that the species of the widened permutations is isomorphic to the derivative of the species of permutations. Looking at the generating series we obtain enumerative results, which are also obtained in a direct way. Finally, we prove that the sequence of widened derangement numbers turns out to coincide with the integer sequence A000255 of the On-Line Encyclopedia of Integer Sequences..

References

[1] M. Bóna, Combinatorics of permutations, CRC Press, Boca Raton, 2012. MR2919720
[2] L. de Francesco Albasini and N. Zagaglia Salvi, On the Adjacent Cycle Derangements, ISRN Discrete Mathematics vol. 2012 (2012), 1-12.
[3] M. Hornák,D. Mazza and N. Zagaglia Salvi, Edge Colorings of the Direct Product of Two Graphs, Graphs and Combinatorics vol. 31, 4 (2015), 975-992. MR3357668
[4] A. Joyal, Une théorie combinatoire des séries formelles, Advances in mathematics vol. 42, 1 (1981), 1-82. MR0633783
[5] E. Munarini, A combinatorial interpretation of the generalized Fibonacci numbers, Advances in Applied Mathematics vol. 19, 3 (1997), 306-318. MR1469307
[6] N.J.A. Sloane, The on-line encyclopedia of integer sequences.
[7] R.P. Stanley, Enumerative combinatorics (Vol. 1), Cambridge University Press, Cambridge, 1997. MR1442260