######################################################################
##CouponCollector: Save this file as CouponCollector #
## To use it, stay in the #
##same directory, get into Maple (by typing: maple ) #
##and then type: read REK #
##Then follow the instructions given there #
## #
##Written by Doron Zeilberger, Rutgers University , #
#zeilberg at math dot rutgers dot edu #
######################################################################
#Created: May 8, 2012
print(`Created: May 8, 2012`):
print(` This is CouponCollector, `):
print(`a short Maple program that accompanies (11 years later) the article `):
print(` How Many Single, Double, Triples, Etc. Should the`):
print(`Coupon Collector Expect`):
print(`http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/coupon.html .`):
print(`by Doron Zeilberger`):
print(`It was written in response to a query by Der Spiegel mathematics`):
print(`correspondent, Holger DAMBECK.`):
print(`This Maple program implements the Foata-Han-Lass formula`):
print(``):
print(`Please report bugs to zeilberg at math dot rutgers dot edu`):
print(``):
print(`The most current version of this program`):
print(` is available from`):
print(`http://www.math.rutgers.edu/~zeilberg/tokhniot/CouponCollector .`):
print(`For a list of the procedures type Hilfe();, for help with`):
print(`a specific procedure, type Hilfe(procedure_name); .`):
print(``):
with(combinat):
Hilfe:=proc()
if args=NULL then
print(`The main procedures are: `):
print(` FHL, FHLstory `):
elif nops([args])=1 and op(1,[args])=FHL then
print(`Implements the Foata-Han-Lass formula`):
print(`FHL(m,N): inputs positive integers m and N and outputs a list`):
print(`of length N whose i-th entry is the expected number of kinds`):
print(`of cards for which he has exactly i copies of, for example,`):
print(`type: FHL(540,10);`):
elif nops([args])=1 and op(1,[args])=FHLstory then
print(`A verbose version of FHL(m,N).`):
print(`FHLstory(m,N): inputs positive integers m and N and outputs a list`):
print(`of length N whose i-th entry is the expected number of kinds`):
print(`of cards for which he has exactly i copies of, for example,`):
print(`type: FHLstory(540,10);`):
else
print(`There is no ezra for`,args):
fi:
end:
#FHL(m,N): inputs positive integers m and N and outputs a list
#of length N whose i-th entry is the expected number of kinds
#of cards for which he has exactly i copies of, for example,
#type: FHL(540,10);
FHL:=proc(m,N) local f,t,j:
option remember:
f:=t-1+m!/mul(j-t,j=2..m):
f:=taylor(f,t=0,N+1):
[seq(coeff(f,t,j),j=1..N)]:
end:
#FHLstory(m,N): a verbose version of FHL(m,N)
FHLstory:=proc(m,N) local gu,j:
print(`How Many Single, Doubles, Triples ...`, N , `-copies`):
print(`Should the Coupon Collector Expect with `, m, `kinds of coupons`):
print(``):
print(`By Shalosh B. Ekhad `):
print(``):
gu:=evalf(FHL(m,N)):
print(`There are`, m, `equiprobable baseball (or soccer) cards`):
print(`placed at random in chewing gums. Suppose that a collector`):
print(`keeps buying them until he (or she) has all the cards`):
print(`The EXPECTED number of cards that he needs to buy is`):
print(``):
print(evalf(m*add(1/j,j=1..m))):
print(``):
print(`When the collection is complete (of course it would be sooner or later!)`):
print(`then, according to the Foata-Han-Lass formula, given a short proof`):
print(`by Doron Zeilberger in`):
print(`http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/coupon.pdf ,`):
print(`the collector should EXPECT to have `):
print(``):
print(gu[1], `kinds of cards that he only has one copy of`):
print(``):
for j from 2 to N do
print(gu[j], `kinds of cards that he has`, j, `copies of`):
od:
print(`WARNING: these are all expectations (averages), in real life`):
print(`he (or she) may finish the collection sooner (or later), `):
print(`and have different distributions of duplicates. But if there`):
print(`are many collectors, the above numbers are the`):
print(`averages among all these people.`):
end: