Checkout Registers and Customers

Date: 02/27/2001 at 23:17:52
From: Phillip Kirkman
Subject: Permutations

I have two checkout registers, and twenty customers. What formula will 
find how many different ways I can arrange them? Order does matter.  

I've tried two checkouts and three people and have 24 different 
ways I can arrange them. I also tried the same with four people and 
got 121 ways to arrange them, and five people and 478 ways to arrange 
them. 

I don't know what the formula is... Help!

Date: 02/28/2001 at 08:05:01
From: Doctor Anthony
Subject: Re: Permutations

This type of problem can be modelled in the following way:

Ten balls are numbered 1,2, ... ,10. In how many ways can these balls be 
dropped into five different slots, any number into a slot, and with 
order being important?

We let f(10,5) represent the required number of ways.

Suppose that a distribution of 9 of the numbers gives f(9,5) possible 
distributions, and suppose this gives

  i(1) numbers in box 1, i(2) numbers in box 2 and so on, so that

  i(1) + i(2) + i(3) + i(4) + i(5) = 9

Then the 10th object can go into box 1 in [i(1)+1] ways
                                 box 2 in [i(2)+1] ways  and so on.

So that  [i(1)+1] + [i(2)+1] + ..... + [i(5)+1] = 9 + 5 = 14 ways

Since this number is independent of the particular distribution of the 
nine numbers, we have the relation

       f(10,5) = 14.f(9,5)
               = 14.13.f(8,5)
               = 14.13.12.f(7,5)
               = 14.13.12.11.f(6,5)
               = 14.13.12.11.10.f(5,5)
               = etc, etc, ....
               = 14.13.12.11.10.9.8.7.6.5       [f(1,5) = 5]
               = 3632428800
               = P(14,10)
               
If m = the number of boxes and n = the number of numbered balls, then 
the required number of ways = P(m+n-1,n)

This can also be written  [m]^n = m(m+1)(m+2).....(m+n-1)
  
In the question of the twenty customers and two checkouts, the number 
of arrangements is

    P(2+20-1,20) = P(21,20) = 5.109 x 10^19

We can check your work with 3, 4 and 5 customers.

With 3 customers  P(2+3-1,3) = P(4,3) = 24   agrees with your answer
With 4 customers P(2+4-1,4) = P(5,4) = 120   differs by 1
With 5 customers P(2+5-1,5) = P(6,5) = 720   no agreement

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/