Symbolic solution of card matching problems
N. S. Mendelsohn · Bulletin of the American Mathematical Society · 1946
The main problem to be discussed here is the following.Find the number of arrangements of n cards marked 1, 2, • • • , n subject to conditions of the type: the card marked H n shall not be jth, the card marked "k" shall not be rth, and so on.A generalization of this problem is also discussed.A solution of the card matching problem has been given by Kaplansky in [2]. 1 The present solution depends on a somewhat different approach to the problem.Both Kaplansky and I make use of the finite difference operator £, defined by Ef(n) =/(w+l): Kaplansky's solution is based on a symbolic interpretation of the method of inclusion and exclusion; my solution gives a recurrence formula expressing the solution of the problem of matching n cards in terms of the solution of the problems of matching less than n cards.The solution proposed here is capable of giving explicit formulae for several particular cases, for example, the "problème des ménages." Furthermore, it is capable of being extended to problems of considerably greater generality.Suppose we have au a^ • • • , a n cards, all considered distinct, of which a r are marked r.It is required to find the number of arrangements of these cards in which none of the cards marked V' appear in any of p r specified places.As an immediate corollary, we also obtain the number of arrangements in which these conditions are violated (1) exactly s times and (2) at most 5 times.Let prs be the number of places simultaneously forbidden to cards marked rorr, p r8t the number of places simultaneously forbidden to cards marked r, s or t, and so on.The form our solution takes depends on the prst. . .with the largest number of subscripts which does not vanish.We give the following examples.Case I.All £» = 0.The number of suitable arrangements is £•*+• ' ' +On oi.This is obvious.Case II.Some piT^O, but all pij^O.The number of suitable arrangements is Fi(ai; pi)Fi(a2\ £2) • • • Fi(a n ; p n )0\ where F\{a\ p) ~^2 ( -l) r [a, r] [p, r\E a "" r , the summation being carried out with respect to r which ranges from 0 to min (a, p).The symbol [a, r] is used