Combinatorics, Probability and Computing

Paper

Counting Certain Pairings in Arbitrary Groups

Y. O. HAMIDOUNEa1

a1 Université Pierre et Marie Curie (Paris 6), Institut de Mathématiques de Jussieu, Combinatoire et Optimisation, Case 189, 4 Place Jussieu, 75005 Paris, France

Abstract

In this paper, we study certain pairings which are defined as follows: if A and B are finite subsets of an arbitrary group, a Wakeford–Fan–Losonczy pairing from B onto A is a bijection φ : BA such that bφ(b) ∉ A, for every bB. The number of such pairings is denoted by μ(B, A).

We investigate the quantity μ(B, A) for A and B, two finite subsets of an arbitrary group satisfying 1 ∉ B, |A| = |B|, and the fact that the order of every element of B is ≥ |B| + 1. Extending earlier results, we show that in this case, μ(B, A) is never equal to 0. Furthermore we prove an explicit lower bound on μ(B, A) in terms of |B| and the cardinality of the group generated by B, which is valid unless A and B have a special form explicitly described. In the case A = B, our bound holds unless B is a translate of a progression.

(Received December 13 2008)

(Revised September 08 2011)

(Online publication October 11 2011)