Riv. Mat. Univ. Parma, Vol. 8, No. 2, 2017

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

Combinatorial interpretations and enumeration of particular bijections

Pages: 161-169
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.
[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, FL 2012. MR2919720
[2]
L. de Francesco Albasini and N. Zagaglia Salvi, On the adjacent cycle derangements, ISRN Discrete Mathematics 2012 (2012), Article ID 340357, 12 pages. DOI: 10.5402/2012/340357
[3]
M. Hornák,D. Mazza and N. Zagaglia Salvi, Edge colorings of the direct product of two graphs, Graphs Combin. 31 (2015), 975-992. MR3357668
[4]
A. Joyal, Une théorie combinatoire des séries formelles, Adv. in Math. 42 (1981), 1-82. MR0633783
[5]
E. Munarini, A combinatorial interpretation of the generalized Fibonacci numbers, Adv. in Appl. Math. 19 (1997), 306-318. MR1469307
[6]
N. J. A. Sloane, The on-line encyclopedia of integer sequences, published electronically at http://oeis.org, 2016.
[7]
R. P. Stanley, Enumerative combinatorics, Vol. 1, Cambridge University Press, Cambridge 1997. MR1442260

Home Riv.Mat.Univ.Parma