MVR4
I/UnrankKSubsets:6%%"rG%"nG%"kG6"F(F(@)529$""!1-%)binomialG6$9%9&F,-%'RETURNG6#
%2r~is~out~of~rangeG/F2F--F56#7"2F,-F06$,&F2"""!""F@F3-F56#-F"6%F,F?F3-F56#7$-%
#opG6#-F"6%,&F,F@F=FAF?,&F3F@FAF@F2F(F(6",
I*CountRuns:6$F&F'F(F(F(@)52F,F@2F2F@-F56#F-2F,F2FX/F,F@-F56#F@-F56#,&*&F2F@-FQ
6$,&F,F@FAF@F2F@F@*&,(F,F@F2FAF@F@F@-FQ6$F^oF?F@F@F(F(FP,
I/RankPartitions:6%%#ssGF&F'6#%(lastEltGF(F(C%@$/&F,Fgn,(F2F@F3FAF@F@FX>8$-%%no
psG6#F,@%/&F,6#F_pF@-F56#-Fco6%7#-FJ6#&F,6#;F@,&F_pF@FAF@F?FO-F56#,&-%0CountPar
titionsG6$F?FOF@-Fco6%-%$mapG6$:6#%"xGF(6$%)operatorG%&arrowGF(F^oF(F(F,,&F2F@F
3FAF3F@F(F(FP,
I1RandomPermCycles:FS6'%$rnoGF%%%eastG%%westG%#rnGF(F(@%Fen@%0F2F@F9-F56#7#F@C$
>F_p,$-%%randGF(#F@".++++++"@%2F_p*&-%(StirCycGFboF@-F\t6$F,F2FAC$>8&-FdrFbo-F5
6#7$-FJ6#FatF,C&>8(-Fes6#;F@F^o>8%-FjtF(>8'-FdrF]o-F56#-%'subsopG6$/F_uF,7$-FJ6
#Fbu&Fbu6#F_uF(F(FP,
I,IntegerPtns:FSF(F(F(@'5FUFZFX3Fen/F2F@Ffn-F56#,&-F_vFboF@-F_v6$,&F,F@F2FAF2F@
F(F(FP,
I2UnrankIntegerPtns:F$6#%#uuGF(F(@)5F+1-F_vF1F,F43Fdv/F3F@F^s2F,-F_vFgqC$>F_p-F
\w6%F,F?FO-F56#7$,&&F_pFgnF@F@F@-FJ6$;""#-FapFfpF_pC$>F_p-F\w6%,&F,F@FgwFAFcrF3
-F56#7$F`x-FJFfpF(F(FP,
I/RandomIntCombo:6$F&F'6'FgrFhrFir%)zeroListG%"iGFPFPC$>8$,$-FesFP#"""".++++++"
@'/9%F[z-F56#7#9$/Fcz""!C%>8'7"?(8(F[zF[zF_z%%trueG>Fhz7$-FJ6#FhzFez-F5F`[l@%2F
gy*&-%/CountIntCombosG6$,&FczF[z!""F[zF_zF[z-Ff[l6$FczF_zFi[lC%>8&-F_yFg[l>&F^\
l6#F[z,&F[zF[zFa\lF[z-F56#F^\lC%>8%-F_y6$Fcz,&F_zF[zFi[lF[z>Fh\l7$Fez-FJ6#Fh\l-
F5F_]lFPFPFP,
I/RandomKSubsets:FS6%FgrFhrFirF(F(@'55F+2F2F-FZ-F5F(3/F,F-F8F9C$>F_pFcs@%2F_p*&
F2F@F,FAC$>F_u-Fa]lFbo-F56#7$-FJF^vF,C$>Fat-Fa]lF]o-F5FgtF(F(FP,
I)RankRuns:Feo6$%%listGFdyF(F(C$>F_p-%)ListRunsGF1?(F_uF@F@-FQF1F\[l@$/F,&F_pF^
v-F56#,&F_uF@FAF@F(F(FP,
I1CountOrderedPtns:FSF(F(F(@'5F+FWFX5Fj]lFdvFfn-F56#,&-F[`l6$F,F?F@-F[`lF]oF@F(
F(FP,
I/RankIntegerPtn:6#Ffo6%%$ptsG%#nnGFdyF(F(C%>F_pF`p>F_u-%$addG6$&F,Fgt/Fat;F@F_
p@'/F_pF@FX2&F,6#FdxF\p-F56#-Ff`l6#7$,&F\pF@FAF@-FJ6$;FdxF_pF,-F56#,&-%&CountG6
%""(Fj_lF_blF@-Ff`l6#7#F`blF@F(F(FP,
I%Rank:6$%&famnoG%'objectGF(F(F(@/Fen-F56#-%,RankKSubsetG6%F2-%$maxG6#-FJ6#F2-F
apF\dl/F,Fdx-F56#-%/RankPermCyclesG6%F2F]dl-%,CountCyclesGF\dl/F,""$-F56#-%,Ran
kSetPtnsG6%F2F]dlFhcl/F,""%-F56#-Fco6%F2-F`al6$Fdy/FdyF2F]dl/F,""&-F56#-%0RankO
rderedPtnsGFbel/F,""'-F56#-F[_l6%F2F]dl-%(NumRunsG6$F]dlF2-F56#-Ff`lF\dlF(F(FP,
I'Random:6%F`clF&F'F(F(F(@/Fen-F56#-Fa]lF1F^dl-F56#-FdrF1Ffdl-F56#-%.RandomSetP
tnsGF1F]el-F56#-%0RandomPartitionGF1Ffel-F56#-%1RandomOrderedPtnGF1F\fl-F56#-%)
RandRunsGF1-F56#-%2RandomIntegerPtnsGF1F(F(FP,
I*lasterror6&"%<"*FfclFgdl%"kGF(,
I(StirSet:FSF(6#%)rememberGF(@%FVFX@%Fen@%F]sFXFfn-F56#,&-FjhlFboF@*&F2F@-FjhlF
]oF@F@F(F(FP,
I+UnrankRuns:F$6#F^_lF(F(C%@$5F+1Fd_lF,F4>F_pFa_l-F56#&F_p6#,&F,F@F@F@F(F(FP,
I&Count:FjflF(F(F(@/Fen-F56#F/F^dl-F56#-F\tF1Ffdl-F56#-FjhlF1F]el-F56#-FfqF1Ffe
l-F56#-F[`lF1F\fl-F56#Fd_l-F56#FcwF(F(FP,
I0ListPermsCycles:FS6(FhrFir%$outG%"jG%'eastopG%'westopGF\ilF(C%>Fjt:6$%"yGF]\m
F(F`rF(7$-FJFbpF2F(F(>8):Fc\mF(F`rF(7$-FJ6#-Fgu6$/F2,&F@F@F`pF@F,&F,F\dlF(F(@'F
bvF9Fen-F56#7#F`sC'>F_p-Fi[mFbo>F_u-Fi[mF]o>Fat-F[r6%FjtF_pF,?(FbuF@F@F^oF\[l>F
at7$Fft-FJ6#-F[r6%Fh\mF_uFbuFj^lF(F(FP,
I.UnrankSetPtns:F$6%%#rpG%#rmGF_wF(F(@)5F+1F^[mF,F4FdwF^s2F,-FjhlFgq-F56#7$-FJ6
#-Fe^mF[xF3C&>F_p-%&floorG6#*&,&F,F@F^_mFAF@-FjhlF>FA>F_u-%$modG6$F[`mF\`m>Fat7
$-FJ6#-Fe^m6%F_uF?F3,&F_pF@F@F@Fj^lF(F(FP,
I)ListRuns:FS60%(OldWestG%(OldEastG%+numOldWestG%+numOldEastG%+newWestEltG%+new
EastEltG%(NewWestG%(NewEastG%(wbufferG%(ebufferGFdyF]\m%#iiG%#jjGF(F(@'FbvF9Fcv
Fc]mC+>F_p-Fb_lFbo>FatFao>8*F;@$2F-Fat?(8.F@F@FatF\[lC&>8,&F_p6#Fabm>Fjt7$F,-FJ
6#Fdbm>F]bm7$-FJ6#F]bmFjt@$2F2F,?(8/FdxF@F^oF\[l@$2&Fdbm6#,&FbcmF@FAF@&Fdbm6#Fb
cmC$>Fjt7%-FJ6#&Fdbm6#;F@FgcmF,-FJ6#&Fdbm6#;FbcmF^o>F]bmF\cm>F_u-Fb_lF]o>FbuF\o
>8+F;@$2F-Fbu?(80F@F@FbuF\[lC&>8-&F_u6#F`em>Fh\m7$-FJ6#FcemF,>F\em7$-FJ6#F\emFh
\m?(81FdxF@F^oF\[l@$2&Fcem6#F_fm&Fcem6#,&F_fmF@FAF@C$>Fh\m7%-FJ6#&Fcem6#;F@Fffm
F,-FJ6#&Fcem6#;F_fmF^o>F\em7$Fh\mF\fm-F56#7$F]cmF\fmF(F(FP,
I-ListKSubsets:FS6%FhrFirF_\mF\ilF(C$>Fat:6$Fd\m%"mGF(F`rF(Fe\mF(F(@'Fe]lF95Fj]
lF8-F56#7#F;C&>F_p-FigmF]o>F_u-FigmFbo>F_u-F[r6%FatF_uF,-F56#7$F^yFf^lF(F(FP,
I.PartitionList:FS6$%%EastG%%WestGF(F(@'FbvF9FenFc]mC%@%552F^oF@2F?F@FZ>F_uF;>F
_u-F[r6$:F^rF(F`rF(7$Ff\mF@F(F(-FaimFbo@%1F2F[w>F_p-F[r6$:6#Fd\mF(F`rF(-F[r6$:F
^rF(F`rF(FcjlF(F(F,F(F(-FaimFjv>F_pF;-F56#7$Ff^lF^yF(F(FP,
I%List:FjflF(F(F(@/Fen-F56#-FigmF1F^dl-F56#-Fi[mF1Ffdl-F56#-%,ListSetPtnsGF1F]e
l-F56#-FaimF1Ffel-F56#-%0ListOrderedPtnsGF1F\fl-F56#Fa_l-F56#-%0ListIntegerPtns
GF1F(F(FP,
I)RandRuns:FS6$FgrF^_lF(F(C%>F_p-Fes6#;F@-FQF^t>F_u-Fb_lF^t-F56#&F_u6#-F_pF(F(F
(FP,
I0CountPartitions:FSF(F(F(@'FbvFXFenFfn-F56#,&-FfqFboF@-FfqFjvF@F(F(FP,
I/RankPermCycles:Feo6%Ffam%#ttGF_wF(F(@'5/F3F2/F3F-FX/Fa]mF2-F56#-Fbdl6%-Fgu6$/
F2%%NULLGF,F?FOC(-%'memberG6%F2F,F_p>F_uF,>&F_uFfp&F_uF\dl>F_u7#-FJ6$;F@F?F_u>F
at-FbdlFf`m-F56#,(FatF@*&FaqF@-F\tF>F@F@-F\tFgqF@F(F(F(,
I&hello:F(F(F(F(CQ-%'lprintG6#%!G-F_anF(-%&printG6#%EThis~is~the~Maple~package~
"EastWest"G-Fdan6#%:Version~of~August~7,~1999GF^an-Fdan6#%YIt~accompanies~the~l
ecture~notes~"East~Side,~West~Side,"G-Fdan6#%0by~Herbert~WilfGF^anF^an-Fdan6#%h
nProgrammed~by~H.~Wilf~with~the~assistance~of~Joanna~NordlichtG-Fdan6#%]pBoth~t
he~notes~and~this~package~can~be~downloaded~from~<http://www.cis.upenn.edu>.GF^
anF^an-F_an6#%[r~This~package~performs~any~of~42~tasks,~namely:~any~one~of~six~
functions~on~any~of~seven~combinatorial~families.GFban-F_an6#%8~The~six~functio
ns~are:GFban-F_an6#%]o~~1.~Count~-~~returns~the~number~of~objects~of~the~specif
ied~size~G-F_an6#%T~~~~~~~~~~~~~~~~~Call:~~Count(family~number,~n,~k):G-F_an6#%
^o~~2.~List~~-~~returns~a~list~of~all~objects~of~the~specified~size,~G-F_an6#%e
n~~~~~~~~~~~~~~in~the~standard~encoding~for~the~family~~~~~G-F_an6#%S~~~~~~~~~~
~~~~~~~Call:~~List(family~number,~n,~k):G-F_an6#%\o~~3.~Random-~~returns~a~sing
le~object,~chosen~uniformly~at~randomG-F_an6#%in~~~~~~~~~~~~~~from~the~members~
of~the~family~of~the~given~sizeG-F_an6#%U~~~~~~~~~~~~~~~~~Call:~~Random(family~
number,~n,~k):G-F_an6#%]o~~4.~Rank~~-~~returns~the~rank~of~the~input~object~on~
the~list~of~G-F_an6#%do~~~~~~~~~~~~~~all~members~of~the~family~of~the~size~of~t
he~input~object~~G-F_an6#%\o~~~~~~~~~~~~~~~~~Call:~~Rank(family~number,~object~
to~be~ranked):G-F_an6#%[o~~5.~Unrank-~~returns~the~member~of~the~family~of~give
n~rank~in~G-F_an6#%\o~~~~~~~~~~~~~~the~list~of~all~members~of~the~family~of~giv
en~sizeG-F_an6#%en~~~~~~~~~~~~~~~~~Call:~~Unrank(family~number,~n,~k,~rank):G-F
_an6#%[o~~6.~Successor-~returns~the~object~that~immediately~follows~the~G-F_an6
#%\p~~~~~~~~~~~~~~given~object~on~the~list~of~all~members~of~the~family~of~give
n~sizeG-F_an6#%hn~~~~~~~~~~~~~~~~~Call:~~Successor(family~number,n,k,~object):G
F^an-F_an6#%V~The~seven~combinatorial~families/their~encodings~areGFban-F_an6#%
L~~1.~k-subsets~of~an~n-set/list~of~members~G-F_an6#%hn~~2.~permutations~of~n~l
etters~with~k~cycles/array~of~values~G-F_an6#%co~~3.~partitions~of~a~set~of~n~e
lements~with~k~classes/class~vector~arrayG-F_an6#%in~~4.~partitions~of~the~inte
ger~n~into~k~parts/array~of~parts~~G-F_an6#%\p~~5.~ordered~partitions~of~the~in
teger~n~into~k~nonnegative~parts/array~of~parts~G-F_an6#%in~~6.~permutations~of
~n~letters~with~k~runs~up/array~of~values~G-F_an6#%co~~7.~partitions~of~the~int
eger~n~whose~largest~part~is~k/array~of~parts~GF^anF^anFh]lF(F(F(,
I0ListOrderedPtns:FS6'F^\mF_\mFhrFirFdyF(F(C&>F_p:6#%"sGF(F`rF(7$F-Ff\mF(F(>F_u
:F]hnF(F`rF(7$,&F@F@F\pF@-FJ6$;FdxF`pF,F(F(@'Fdv-F56#7#7#F,Fj]l-F56#7#7#-%$seqG
6$F-/Fjt;F@F2C$>Fat-F[r6$F_p-Ff\nFd`l>Fbu-F[r6$F_u-Ff\nF]o-F56#7$F[vFftF(F(FP,
I1UnrankPartitions:F$F^wF(F(@)5F+1Fa[mF,F4FdwF^s2F,FeqC$>F_p-FajnF[x-F56#7$F^yF
@C$>F_p-Fajn6%,&F,F@FeqFAFcrF3-F56#-F[r6$:F^rF(F`rF(FcjlF(F(F_pF(F(FP,
I(StirCyc:FSF(F\ilF(@'FVFXFen@%F]sFXFfn-F56#,&F[tF@*&F^oF@-F\tF]oF@F@F(F(FP,
I'Unrank:6&F`clF&F'F%F(F(F(@/Fen-F56#-F"6%9'F2F3F^dl-F56#-%2UnrankPermsCyclesGF
g\oFfdl-F56#-Fe^mFg\oF]el-F56#-FajnFg\oFfel-F56#-%2UnrankOrderedPtnsGFg\oF\fl-F
56#-FgilFg\o-F56#-F\wFg\oF(F(FP,
I0RankPermsCycles:6%FfoF&F'6%FfamFh^nF_wFPFP@'5/9&F_z/Fd^oFez-F56#Fez/&Fcz6#F_z
F_z-F56#-F]^o6%-Fgu6$/F_zFe_nFczF[]l,&Fd^oF[zFi[lF[zC(-Fh_n6%F_zFczFgy>Fh\lFcz>
&Fh\l6#Fgy&Fh\lFj^o>Fh\l7#-FJ6$;F[zF[]lFh\l>F^\l-F]^o6%Fh\lF[]lFd^o-F56#,(F^\lF
[z*&,&FgyF[zFi[lF[zF[z-F\t6$F[]lFd^oF[zF[z-F\t6$F[]lFb_oF[zFPFPFP,
I0RandomPartition:FS6&FgrFhrFirF_rF(F(C$>F_pFcs@%Fen@%4FdvF9F^s@%2F_p*&Fc^nF@-F
fqF^tFAC%>Fat-FiglFbo>Fat7$FftF@Fj^lC%>F_u-FiglFjv>F_u-F[r6$:F^rF(F`rF(FcjlF(F(
F_u-F5F^vF(F(FP,
I.RandomSetPtns:FS6$Fgr%&classGF(F(@%Fen@%F]sF9F^sC$>F_pFcs@%2F_p*&FdilF@-FjhlF
^tFA-F56#7$-FJ6#-FeglFboF2C$>F_u-Fes6#Fdin-F56#7$-FJ6#-FeglF]o-F_uF(F(F(FP,
I,CountCycles:6#%%permG6'%"cGFdy%#prG%#i0GF&F(F(C'>F_pF->Fat,$F,FA>Fjt-FapFgt?(
F_uF@F@FjtF\[l@$2&FatF^vF-C'>F_pFg`m>Fceo,$FceoFA>FbuF_u>F_uFceo?(F(F@F@F(0F_uF
buC$>Fceo-%$absG6#Fceo>F_uFceo-F5FfpF(F(F(,
I0RankOrderedPtns:FeoF(F(F(C$@$/F\pF2FX@%/F\pF--F56#,&-F[`lF>F@-F[fl6%&F,6#;Fdx
F3F2FOF@-F56#-F[fl6%7$F_bl-FJ6#F`goF?F3F(F(FP,
I0ListIntegerPtns:FS6&FhrFirF^\mF_\mF\ilF(C%>Fat:FjjmF(F`rF(-%(applyopG6%:6#%"t
GF(F`rF(FcjlF(F(F@F,F(F(>Fbu:Fc\mF(F`rF(7$F2Ff\mF(F(@'551F,F-1F2F-FZF9FenFc]mC%
>F_p-F\]nFbo>F_u-F\]nFjv-F56#7$-FJ6#-F[r6$FatF_p-FJ6#-F[r6%FbuF_uF2F(F(FP,
I2UnrankPermsCycles:F$Fg^mF(F(@)5F+1F[[mF,F4FdwF^s2F,Fj`n-F56#7$-FJ6#-F\]oF[xF2
C(>F_p-Fh_m6#*&,&F,F@Fj`nFAF@Fi`nFA>F_u-F_`m6$F_[pFi`n>Fat-F\]oFf`m>Fat7$Fft&Fa
t6#Fg`m>Fg[pF2Fj^lF(F(FP,
I,ListSetPtns:FS6'FhrFirFdyF\\m%%EWopGF\ilF(C$>Fjt:F_hmF(F`rF(Fe\mF(F(@%Fen@%F]
sF9Fc]mC'>F_p-F_\nFbo>F_u-F_\nF]o>Fbu-F[r6%FjtF_pF2?(FatF@F@F2F\[l>Fbu7$F[v-FJ6
#-F[r6%FjtF_uFat-F5F\vF(F(FP,
I+_BinomialBFdxF(,
I1RandomOrderedPtn:FS6'FgrFhrFirFcyFdyF(F(C$>F_pFcs@'Fdv-F56#F[inFj]lC%>FbuF;?(
FjtF@F@F2F\[l>Fbu7$F[vF-Fb]p@%2F_p*&Fe`lF@-F[`lF^tFAC%>Fat-F]hlF]o>&FatFgn,&F@F
@Fi^pF@Fj^lC%>F_u-F]hlFd`l>F_u7$F-Ff^lFdboF(F(F(,
I+_BinomialKF@F(,
I+_BinomialNFdxF(,
I(NumRuns:6$F&Fedo6&%%runsGFdy%&firstG%'secondGF(F(C%>F_pF@?(F_uF@F@F^oF\[lC%>F
at&F2F^v>Fbu&F26#,&F_uF@F@F@@$2FbuFat>F_pFg`mFbfoF(F(FP,
I2RandomIntegerPtns:FSFc]lF(F(C$>F_pFcs@%Fen@%F]sF9F^s@%2F_p*&FhvF@-F_vF^tFAC%>
F_u-FehlFbo>&F_uFgn,&F@F@FdapF@FdboC$>Fat-FehlFjv-F56#7$F2FftF(F(FP,
I2UnrankOrderedPtns:F$6%F_wFcyFdyF(F(@+5F+1Fd[mF,F4Few-F56#7#F2F8C%>F_uF;?(FatF
@F@F3F\[l>F_u7$Ff^lF-Fdbo2F,F]goC$>F_p-Ff]oFE-F56#7$F_x-FJ6#&F_pFagoC$>F_p-Ff]o
6%,&F,F@F]goFAF2FO-F56#7$F-F^yF(F(FP,
I,RankSetPtns:Feo6$FfamF_wF(F(@%Fj^nFXC$-Fh_n6%F3F,F_p@%3/Fa]mF3/F_pF2-F56#-F[e
l6%7#-FJ6$Fb`nF,F?FOC$>F_u-F[el6%F[epF?F3-F56#,(F_uF@F^_mF@*&,&Fa]mF@FAF@F@F\`m
F@F@F(F(FP,
I0RankIntegerPtns:Feo6#Fj`lF(F(C%>F_pF`p@$/F\pF@FX@%5FfalFgal-F56#-Fgep6%7$FOF`
blF?FO-F56#,&FgwF@-Fgep6%F\clFcrF3F@F(F(F(,
I*Successor:6&F`clF&F'FaclF(F(F(-F56#-F`\o6&F,F2F3,&F@F@-F]cl6$F,Fh\oF@F(F(FP,
I,RankKSubset:Feo6#%%cutnGF(F(C$>F_p:6#%"wGF(F`rF(7#-FJ6$;F@,&F`pF@FAF@F,F(F(@'
F\_nFX/&F,6#F3F2-F56#,&-Ffcl6%-F_pFbpF?FOF@F=F@-F56#-FfclFEF(F(FP