Combinatorics, Probability and Computing


Counting Certain Pairings in Arbitrary Groups


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


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)