{VERSION 4 0 "IBM INTEL NT" "4.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 1 }{CSTYLE "" -1 256 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 257 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 259 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 260 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 261 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 262 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 263 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 264 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 265 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 266 "" 0 24 0 0 255 1 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 267 "Helvetica" 0 1 128 0 0 1 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 268 "Helvetica" 0 1 128 0 0 1 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 269 "" 1 18 255 0 0 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 270 "Helvetica" 1 14 128 0 0 1 0 0 2 0 0 0 0 0 0 1 }{CSTYLE "" -1 271 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 272 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 273 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 274 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 275 "" 1 18 255 0 0 1 0 0 0 0 0 0 0 0 0 0 }{PSTYLE "Norm al" -1 0 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 } 1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Title" -1 256 1 {CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 1 2 2 2 1 1 1 1 }1 1 0 0 12 12 1 0 1 0 2 2 19 1 }{PSTYLE "Author" -1 257 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 8 8 1 0 1 0 2 2 0 1 }} {SECT 0 {EXCHG {PARA 256 "" 0 "" {TEXT 266 34 "MLC Lab Visit - More Co mbinatorics" }{TEXT 269 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 275 52 "Mth 355 Fall 2001 Assignment 5 (at end). Due Oct 31." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 270 44 "Mth 355 (a.k.a. Mth 399) Oct 23 2001 Maple 6" }}{PARA 0 "" 0 "" {TEXT 267 16 "Bent E. Petersen" }} {PARA 0 "" 0 "" {TEXT 268 41 "Filename: 355f2001-assign-05-combinat.mw s" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 269 "Maple has quite a bit of combinatorial support available in the c ombstruct and combinat packages. This Worksheet is a summary of some o f the combinatorial computations you can do with Maple. At the end of \+ the worksheet are a few problems which constitute Assignment 5. " }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "with(combs truct);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "with(combinat); " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 256 12 "Permutations" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 241 "The allstructs() function produces a list of all permu tations of the specified objects. The function iterstructs() allows o ne to iterate over the list of objects which would be returned by all structs(), without first returning the list." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 41 "Here are the 2-permutatio ns of [a,b,c,d]" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "allstructs(Permutation([a,b,c,d]),size=2);" } }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 107 "If the argument provided is an integer n, rather than a list, it is treated as the list [1,...,n]. Thus" }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "allstructs(Permutation( 4),size=2);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 36 "To use an iterator instead is simple" }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 50 "iter1:=it erstructs(Permutation([a,b,c,d]),size=2):" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 28 "while not finished(iter1) do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 20 " nextstruct(iter1);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "od;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 66 "Of course you will want to do something useful inside the do-loop." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 51 "You can also do permutations with repeated objects." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "allstructs(Permutation([a,b,c,c]),size=2);" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 91 "A special keyword, allsizes, is used if you want all r-permutations for each size of \+ r." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "allstructs(Permutation([a,b,c]),size=allsizes);" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 86 "No te the 0-permutation, or empty permutation, is also returned. Be caref ul about that." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 111 "The count() function returns a count of the numbe r of structures of the given type, for example permutations." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "c ount(Permutation([a,b,c]),size=allsizes);" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 35 "count(Permutation([a,b,c]),size=3);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 110 "The dra w() function returns a randomly selected structure of the type specif ied, for example, a permutation." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "draw(Permutation([a,b,c,d]), size=3);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 60 "You can also use randperm() to obtain a random permutati on." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "randperm([a,b,c,d]);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 49 "Note you can not specify \+ the size in randperm()." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 65 "You can also use the permute() function to obtain permutations." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "permute([a,b,c,d],2);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "permute([a,b,c]);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "permute([a,a,b],2);" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 257 12 "Combinations" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 48 "Combinati ons work much the same as permutations." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "allstructs(Combination ([a,b,c,d]),size=2);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 105 "If the argument provided is an integer n, ra ther than a list, it is treated as the set \{1,...,n\}. Thus" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "allstructs(Combination(4),size=2);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 44 "Iterators works as they d o for permutations." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 50 "iter2:=iterstructs(Combination([a,b,c,d]) ,size=2):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "while not fini shed(iter2) do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 20 " nextstruct(iter 2);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "od;" }}}{EXCHG {PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 45 "We can consider lists w ith repeated elements." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "allstructs(Combination([a,b,c,c]),s ize=2);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 192 "Note however, for sets repeated elements do not make sen se. If your data is presented as a set multiple occurences of elements will be treated as single occurences (as is correct). Be careful." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "allstructs(Combination(\{a,b,c,c\}),size=2);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 31 "Again, allsizes \+ is available." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 49 "allstructs(Combination([a,b,c,c]),size=allsize s);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 2 "or" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 49 "allstructs(Combination(\{a,b,c,c\}),size=allsize s);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 108 "Again note the difference btween lists and sets. The set \{a, b,c,c\} is really the same as the set \{a,b,c\}." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 91 "We can obtain ran dom combinations in two different ways (depending on the packages load ed)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "draw(Combination(6),size=3);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "randcomb(6,3);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 37 "We can count without listing as well:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "count(Combination(9),size=4);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 2 "or" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "numb comb(9,4);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "numbcomb([a,a ,b,b,b]); " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "numbcomb([a,a ,b,b,b],2); " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT 264 41 "Generalized Permutations and Combinations" }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 428 "We can se lect r objects, without regard to order, from a set of n objects ( distinguishable since elements of a set) in C(n,r) = P(n,r)/r! = n!/ (r!(n-r)!) ways, because P(n,r) is the number of ways to choose the r objects in order, and if we disregard the order, we clearly have \+ to divide by r!. C(n,r) is called binomial(n,r) in Maple. It is th e number of combinations of n distinct objects taken r at a time. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 632 "Let \+ X be a set of cardinality n where n = n_1 + n_2 + ...+n_m and le t f : X -> \{1,2,...,m\} . Then f determines an ordered partition o f X (that is, a list of nonempty subsets with union X). Suppose the \+ i-th subset, the preimage of i, contains n_i points. How many suc h functions are there? Well, we can select C(n,n_1) elements to map to 1, then C(n-n_1,n_2) elements to map to 2, and so forth. Thu s the number of functions with the preimage of i having cardinality \+ n_i , i = 1,...,m is C(n,n_1)*C(n-n_1,n_2)*...*C(n-n_1-...n_(m-1), n_m) = P(n; n_1,n_2,...n_m); that is, multinomial(n,n_1,...,n_m). \+ " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 16 "Thus, given n " }{TEXT 265 8 "distinct" }{TEXT -1 275 " objects and m n umbered containers, there are multinomial(n,n_1,...,n_m) ways of pla cing the objects in the containers, with n_k objects in the k-th c ontainer (but with no particular order within the containers). Here we are essentially dealing with m combinations." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 315 "Here's another way to lo ok at it: Given n objects where there are n_k objects of type (col or, etc.) k, k=1,...,m, there are multinomial(n,n_1,...,n_m) ways t o arrange them in a row (argue by choosing the location). Here we care about the order - essentially we are dealing with permutations with r eplacement." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 101 "Here's an example - the number of strings of length 12 which c ontain 4 a's, 3 b's, 2 c's and 3 d's is" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "multinomial(12,4,3,2,3 );" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 54 "count(Permutation([a, a,a,a,b,b,b,c,c,d,d,d]),size=12);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 "numbperm([a,a,a,a,b,b,b,c,c,d,d,d],12);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 48 "Note that binomial(n,k) = multinomial(n,k,n-k)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 271 31 "Allocation of Identical Objects" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 429 "Assume we wish to allocate \+ m identical objects to n distinct cells. We can think of the cells as being ordered in a line and seperated by n-1 walls. Then we have m + n -1 locations into which to place the walls and the objects. B ut the objects go into the remaining places after we have placed the w alls. Thus binomial( m+n-1, n-1 ) = binomial( m+n-1, m ) is the numb er of ways we can allocate the objects to the cells." }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 233 "If we have to place at least one object within each cell then n objects are consumed and w e need only consider placing m-n objects. Replacing m by m-n abo ve we see there are binomial( m-1, n-1 ) = binomial( m-1, m-n ) ways ." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 247 "We \+ can think of each cell as being chosen as many times as the number of \+ objects in it. Then we see that the number of ways to choose m objec ts with repetition from a set of n distinct objects is binomial( m+ n-1, n-1 ) = binomial( m+n-1, m )." }}{PARA 0 "" 0 "" {TEXT -1 2 " " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 58 "allstructs(Combination([a ,a,a,b,b,b,c,c,c,d,d,d]),size=2);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "count(Combination([a,a,a,b,b,b,c,c,c,d,d,d]),size=2); " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "binomial(4+2-1,2); bino mial(4+2-1,3);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 172 "In the first two commands we are choosing 2 objects , with repetition, from \{a,b,c,d\}. In the last two commands we are \+ allocating 4 identical objects to 2 distinct cells." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 258 47 "Partitio ns and Compositions of a natural number" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "allstructs(Partition(6 ),size=3);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 78 "We can also use the partition() function provided by th e combinat package." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "partition(6);" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 169 "If we just want t he partitions of length 3 as above then partition(6) makes us work a bit harder than allstructs(Partition(6),size=3) does. Here is one w ay to do it." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 66 "for prt in partition(6) do if nops(prt)=3 then p rint(prt); fi; od;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 48 "Compositions of a number may be easily computed: " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "allstructs(Composition(6),size=3);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 119 "If we just wan t the number of partitions or compositions we use the count() functi on just as we did for permutations." }}{PARA 0 "" 0 "" {TEXT -1 0 "" } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "count(Partition(6),size=3) ;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "count(Composition(6),s ize=3);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 86 "We can also use the functions numbpart() and numbcomp( ) from the combinat package:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "numbpart(6);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "numbcomp(6,3);" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 167 "Be careful - numb comp(n) is not supported and yields an error message and numbpart(n, m) is also not supported, but yields an incorrect answer with no erro r message." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 62 "It is fairly easy to see numbcomp(n, m) = binomial(n-1, \+ m-1)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 89 "We can obtain random part itions in two different ways (depending on the packages loaded)." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "draw(Partition(6),size=3);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "randpart(6);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 63 "Note in randpart() we can not speci fy the size. It works like" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "draw(Partition(6),size=allsizes);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 46 "Here is a sample application of compositions. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 217 "Suppose we want to extre mize 5*x^2+4*y^3+5*z^2 over the solutions of x + y + z=82, with x, y and z all nonzero. Because of the weights (coefficients) we will be dealing with compositions of length 3. How many?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "N:=82:" } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "count(Composition(N),size= 3);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 54 "We can list them explicitly or we can use an iterator." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "w:=lst->5*lst[1]^2+4*lst[2]^3+5*lst[3]^2;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 62 "Initialize minpt, m axpt, minval, maxval fairly arbitrarily -" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 35 "minpt:=draw(Compo sition(N),size=3);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "minva l:=w(minpt);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 35 "maxpt:=draw (Composition(N),size=3);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "maxval:=w(maxpt);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 18 "Set up an iterator" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "iter3:=iterstructs(Com position(N),size=3):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "whi le not finished(iter3) do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 27 " newp t:=nextstruct(iter3);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 19 " newval:= w(newpt);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 25 " if newval < minval t hen" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 17 " minpt:=newpt;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 21 " minval:=w(newpt);" }}{PARA 0 "> " 0 " " {MPLTEXT 1 0 5 " fi;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 25 " if new val > maxval then" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 17 " maxpt:=new pt;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 22 " maxval:=w(newpt); " }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 " fi;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "od:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "minpt, minval;" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 14 "maxpt, maxval;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 64 "So we have a maximum at \+ [1,80,1] and a minimum at [38,6,38]. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 62 "For larger N this simple method ra pidly becomes impractical!" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT 259 7 "Subsets" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "allstructs(Subset(\{a,b,c ,c\}),size=2);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 56 "Actually Subset is just another name for Combinat ion." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 44 "allstructs(Subset(\{a,b,c,c\}),size=allsizes);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 "count(Subset(\{a,b,c,c\}),si ze=allsizes);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 260 8 "Powerset" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 235 "The function call powerset(s) returns the set o f all the subsets of s if s is a set. If s is an integer then t he set of all subsets of \{1,...,s\} is returned. If s is a list t hen the list of all sublists of s is returned." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "powerset(\{ a,b,c\});" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "powerset([a,b, c]);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "powerset(\{a,b,c,c \});" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "powerset([a,b,c,c]) ;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 47 "Note sublists respect order and multiplicities." }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 92 "We can iterate \+ over the power set by using the iterator returned by the function sub sets()." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "iterpow:=subsets(\{a,b,c\}):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "while not iterpow[finished] do iterpow[nextvalue ]() od;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 68 "Of course you will want to do something exciting inside t he do loop." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT 261 35 "Stirling Numbers of the second kind" }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 204 "The function c all stirling2(n,m) returns S(n,m), the Stirling number of the sec ond kind. S(n,m) is the number of ways of partitioning a set of cardi nality n into m (non-empty of course) subsets." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "stirling2(6 ,4);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 262 35 "Bell Numbers and Partitions of Sets" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 179 "By convention there is one partition of the empty set (the empty partition) with no subsets, but for a non-empty set A partitions consist of non-empty sets (onl y) with union A." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 114 "The Bell number bell(n) is the total number of partitio ns of a set of cardinality n into any number of subsets." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "bell (4);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "sum(stirling2(4,k), k=1..4);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 89 "Be careful to distinguish the notion of partitions of a s et and partitions of an integer." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 78 "We can easily write a routine to l ist the partitions of the set \{1,2,3,...,n\}" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "parts:=proc (n)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 34 " local P,A,B,C; option rem ember;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "if n=1 then " }}{PARA 0 " > " 0 "" {MPLTEXT 1 0 10 " P:=\{\{1\}\}" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "elif n=2 then" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 28 " \+ P:=\{ \{\{1\},\{2\}\}, \{\{1,2\}\} \};" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "elif n>2 then" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 8 " P:=\{\}; " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 24 " for A in parts(n-1) do" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 " P:= P union \{ A union \{\{n\} \} \};" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 17 " for B in A do" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 48 " C:= ( A minus \{B\} ) union \+ \{ B union \{n\} \};" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 24 " P:= P union \{ C \};" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 9 " od; " }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 " od;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "else" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 11 " P:= FAIL;" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "fi;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "return P;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 18 "Here is a n example" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 9 "parts(4);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" } }{PARA 0 "" 0 "" {TEXT -1 48 "If you prefer an easier to read list you can try" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "for A in parts(4) do print(A); od;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 263 23 "More Refined P artitions" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 35 "Let A be a set of cardinality n." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 68 "The number of partitions of A into (nonempty) subsets is bell(n)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 79 "The number of partitions of A into m \+ (nonempty) subsets is stirling2(n,m)." }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 340 "Now consider the number of partition s of A into m subsets A_i, i = 1,...,m, where A_i has cardin ality n_i. Let's order the set of sets A_i by cardinality to obtai n a list. The number of such lists is multinomial(n,n_1,...,n_m). If \+ the cardinalities n_1,...,n_m are all distinct then each list corres ponds to one partition. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 358 "If , on the other hand, N_1,...N_k are the dist inct values for the cardinalities n_1,...,n_m and each N_i occurs \+ p_i times (we call the p_i the multiplicities) then re-arranging the parts of the list corresponding to a given N_i does not change the co rresponding partition and so we have to divide by (p_i)! for each i \+ to get the right count. Thus" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 188 "If N_1,...,N_k are distinct, the numbe r of partitions of a set A of cardinality n = p_1*N_1+...+p_k*N_k into partitions consisting of p_i sets of cardinality N_i, i=1,.. .,k, is" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 44 "multinomial(n_1,...,n_m) / ((p_1)!...(p_k)!)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 133 "where n_1,...,n_m is t he sequence of N_i's with each repeated according to multiplicity. He re's a procedure to compute this number" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "numbparts:=proc()" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 " local k,h,C,M,n,p,allcard;" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "if nargs < 2 then" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 14 " return FAIL;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "else" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 8 " C:=[];" }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 8 " M:=[];" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 13 " n:=0; p:=1;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 26 " for k from 1 to \+ nargs do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 26 " C:=[op(C),args[k][1 ]];" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 26 " M:=[op(M),args[k][2]];" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 36 " n:= n + args[k][1] * args[k][ 2];" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 25 " p:= p * (args[k][2])!" } }{PARA 0 "> " 0 "" {MPLTEXT 1 0 5 " od;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 14 " allcard:=[];" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 26 " for k from 1 to nargs do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 27 " f or h from 1 to M[k] do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 34 " all card:=[op(allcard),C[k]];" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 7 " od; " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 5 " od;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "return multinomial(n,op(allcard))/p;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "fi;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end:" }} }{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 139 " The input consists of pairs [N_1, p_1], [N_2, p_2], ... where the N_ k are the subset cardinalities and the p_k are the multiplicities. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 17 "Here' s an example" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "numbparts( [1,2], [3,1] );" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 161 "is the number of \+ partitions of the set \{1,2,3,4,5\} consisting of 3 subsets, 2 of \+ which have 1 element and the third of which, has 3 elements. Let's che ck it." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "for A in parts(5) do if nops(A)=3 then" }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 47 "if nops(A[1])=3 or nops(A[2])=3 or nops(A[3])= 3" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "then print(A); fi; fi; od;" }} }{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 35 "S ure enough there are 10 of them." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 272 20 "Generating Functions" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "x: ='x';" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 149 "In dealing with generating functions we often need to ex tract a certain coefficient of a polynomial. Here is a function which \+ performs this operation" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 63 "getc:=(p,x,n)->coeff(convert(taylor (p,x=0,n+1),`polynom`),x,n);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 332 "Suppose we have 7 blue marbles, 8 gr een marbles and 8 red marbles in an urn (they are always in an urn). How many ways can we draw out 14 marbles consisting of an odd number of blue marbles, an even number of green marbles and a prime number o f red marbles (and with no regard for order) and at least one marble o f each color?." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 26 "The generating function is" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "p:=(x+x^3+x^5+x^7)*(x^ 2+x^4+x^6+x^8)*(x^2+x^3+x^5+x^7);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "getc(p,x,14);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 78 "This is a small enough number that yo u can try to enumerate the possibilities." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 82 "We can use a simple modifi cation of getc() for exponential generating functions:" }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "getx c:=(p,x,n)->(n!)*getc(p,x,n);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 172 "We have 3 red, 3 blue and 3 white ma rbles (in an urn of course). How many ways can we arrange 5 of them \+ in a row so that each color is used at least once (order matters)?" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "q:=(x+(1/2)*x^2+(1/6)*x^3)^3;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "getxc(q,x,5);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 84 "The number of m-compositions of an i nteger n has generating function (expression)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 44 "g:=(Sum(x^k ,k=1..infinity))^m = (x/(1-x))^m;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 63 "So the number of compositions of l ength 4 of 12 is given by" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "getc((x/(1-x))^4,x,12);" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 15 "Le t's check it:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "count(Composition(12),size=4);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 1 " " }}{PARA 0 "" 0 "" {TEXT -1 14 "Here's another " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "getc((x/(1-x))^15,x,22);" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 31 "count(Composition(22),size=15);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 12 "Sure enough!" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 273 8 "Graycode" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 198 "The function call gr aycode(n) returns the list of all integers from 0 to 2^n-1 in gra ycode order, that is, so each successive pair of integers when express ed in binary differ by only one bit." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "gco:=graycode(4);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 56 "for k in gco do printf(\"\\n %04d\", convert(k,binary)); od;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 274 20 "Traditional Problems" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 70 "Some of these proble ms make use of the concepts above and some do not." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 111 "1. How many ways can a committee of 5 women and 4 men be selected from an organizatio n of 12 women and 14 men?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 81 "2. How many strings of length 10 can be formed fro m 4 a's , 3 b's and 3 c's?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 92 "3. If a fair coin is tossed 10 times ho w many ways are there of getting exactly 5 heads?" }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 67 "4. A set has cardinalit y 12. How many subsets have cardinality 4?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 76 "5. A set has cardinality 12. H ow many partitions have 4 (nonempty) sets?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 81 "6. How many 7 (decimal) digit positive numbers have all their digits different?" }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 82 "7. How many 7 (d ecimal) digit positive numbers have at least 2 digits different?" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 92 "8. How ma ny 7 (decimal) digit positive numbers contain 3 distinct pairs of \+ equal digits?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 82 "9. How many integers between 397 and 10483 are divisi ble either by 7 or 11?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 59 "10. How many 6 digit integers have 3, 4 or 9 as a digit?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 72 "11. How many distinct partitions of length 3, 4 or 5 are there o f 32?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 61 "12. How many ways can you permute the letters of MISSISSIPPI?" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 219 "13. An u rn contains 6 red marble, 7 blue marbles and 11 green marbles. Ho w many ways can you select 9 marbles so each color occurs at least o nce, but no more than 5 times? (Hint: Try using a generating function. )" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 274 "14. A partition of a positive integer n is a list of positive integers \+ with sum n. Two partitions are considered identical if they differ o nly in order. A partition is said to be distinct if the integers in it are distinct. Find the number of distinct partitions of 10." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 90 "15. The n umber of partitions of n is the coefficient of x^n in the generati ng function" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "k:='k': x:=' x':g:=product((1-x^k)^(-1),k=1..n);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 99 "16. The number of distinct partitions of n is the coefficient of x^n in the generating function" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "gd:=product((1+x^k),k=1..n);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 99 "In problems 15 and 16 \+ we really should use (formal) infinite products for the generating fun ctions." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "0 1 \+ 1" 51 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }