Combinatorial results for the symmetric inverse semigroup.

DOI10.1007/S00233-007-0732-8MaRDI QIDQ2460069zbMATH OpenOpenAlexFDO

Authors Abdallah Laradji, A. Umar

Publication date 14 November 2007

Published in Semigroup Forum (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00233-007-0732-8

zbMATH Keywords

numbers of fixed pointssymmetric inverse semigroups

Mathematics Subject Classification ID

Factorials, binomial coefficients, combinatorial functions (05A10) Exact enumeration problems, generating functions (05A15) Inverse semigroups (20M18) Semigroups of transformations, relations, partitions, etc. (20M20)

Review text

The main combinatorial object of this paper is \(f(n,r,k)\), which denotes the number of partial one-to-one mappings on \(X_n=\{1,2,\dots,n\}\) with domain and range of size \(r\) and having exactly \(k\) fixed points. A formula is found for \(f(n,r,k)\) as a certain weighted alternating sum of binomial coefficients. This is similar to and indeed represents a generalization of Euler's hat problem, for \(f(n,r,k)\) counts the number of ways that \(r\) of \(n\) people may leave a restaurant with precisely \(k\) picking their own hat. Some combinatorial facts are established, some of which are perhaps new, along with the corresponding asymptotic probabilistic results.

Recommendations

• Further combinatorial results for the symmetric inverse monoid
• Some combinatorial problems in the theory of symmetric inverse semigroups.
• scientific article; zbMATH DE number 5053296
• Some remarks on the combinatorics of \(\mathcal{IS}_n\).
• Some combinatorial properties of the symmetric monoid.

Cited in

(7)

• Combinatorics of nilpotents in symmetric inverse semigroups
• Some combinatorial problems in the theory of symmetric inverse semigroups.
• Some combinatorial properties of the symmetric monoid.
• John Macintosh Howie: work and legacy
• Further combinatorial results for the symmetric inverse monoid
• Combinatorial results for semigroups of order-preserving or order-reversing subpermutations.
• Combinatorial results for order-preserving partial injective contraction mappings

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Combinatorial results for the symmetric inverse semigroup.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2460069)