{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 "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 1 }{CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 256 "" 0 24 0 0 255 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 257 "Helvetica" 0 1 128 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 258 "Helvetica" 0 1 128 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 259 " " 1 18 255 0 0 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 260 "Helvetica" 1 14 128 0 0 1 0 0 2 0 0 0 0 0 0 1 }{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 14 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 265 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 266 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 267 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 268 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 269 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 270 "" 1 14 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 271 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 272 "" 1 14 0 0 0 0 0 0 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 14 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 276 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 277 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 278 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 279 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 280 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 281 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 282 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 283 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 284 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 285 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Tim es" 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 }{PSTYLE "Normal" -1 258 1 {CSTYLE "" -1 -1 "T imes" 1 18 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 } {PSTYLE "Normal" -1 259 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }3 1 0 0 0 0 1 0 1 0 2 2 0 1 }} {SECT 0 {EXCHG {PARA 256 "" 0 "" {TEXT 256 38 "MLC Lab Visit - Combina torics in Maple" }}{PARA 257 "" 0 "" {TEXT 259 43 "Mth 355 Fall 2001 A ssignment 3. Due Oct 17." }}{PARA 0 "" 0 "" {TEXT 260 44 "Mth 355 (a.k .a. Mth 399) Oct 10 2001 Maple 6" }}{PARA 0 "" 0 "" {TEXT 257 16 "Bent E. Petersen" }}{PARA 0 "" 0 "" {TEXT 258 47 "Filename: 355f2001-assig n-003-combinatorics.mws" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 159 "This worksheet contains a few comments on some of M aple's combinatorial functions. There are also a few problems for you. The problems constitute Assignment 3." }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 155 "This worksheet was composed fairly q uickly and is unlikely to be free of errors. If you find a serious err or be sure to mention it in your solution report." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "with(combinat):" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 261 43 "Stirling Numbers of the second kind, S(r ,n)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 151 "S (r,n), denoted by stirling2(r,n) in Maple, is the number of partitions of a set of cardinality r into n (nonempty) subsets. Clearly we m ust have " }{XPPEDIT 18 0 "n <= r;" "6#1%\"nG%\"rG" }{TEXT -1 231 ". \+ You can think of it as the number of ways to place r distinguishabl e objects into n indistinguishable buckets with no bucket empty. By \+ convention there is one partition of the empty set (the empty partitio n) with no subsets." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 126 "S(0,0) = stirling2(0,0); S(4,0) = stirli ng2(4,0); S(4,2) = stirling2(4,2); S(7,3) = stirling2(7,3); S(21,4) = \+ stirling2(21,6);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 91 "The last two entries above show that a direct by-h and count may be difficult or infeasible." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 262 12 "Bell Numbers" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 269 "The Maple functi on call bell(n) returns the n-th Bell number. The n-th Bell number is \+ the number of ways that a set with n elements can be partitioned int o a union of disjoint (nonempty) subsets. For example, the set \{1,2,3 ,4\} and be partioned in the following ways: " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 20 "\{\{1\},\{2\},\{3\},\{4\} \}, " }}{PARA 0 "" 0 "" {TEXT -1 85 "\{\{1,2\},\{3\},\{4\}\}, \{\{2, 3\},\{1\},\{4\}\}, \{\{3,4\},\{1\}\{2\}\}, \{\{1,4\}.\{2\},\{3\}\}, \+ \{\{1,3\},\{2\},\{4\}\}" }}{PARA 0 "" 0 "" {TEXT -1 62 "\{\{1,2\},\{3, 4\}\}, \{\{2,3\},\{4,1\}\}, \{\{3,4\},\{1,2\}\}, \{\{1,4\},\{2,3\} \}," }}{PARA 0 "" 0 "" {TEXT -1 63 "\{\{1,2,3\},\{4\}\}, \{\{2,3,4\}, \{1\}\}, \{\{3,4,1\},\{2\}\}, \{\{4,2,1\},\{3\}\}, " }}{PARA 0 "" 0 "" {TEXT -1 13 "\{\{1,2,3,4\}\}, " }}{PARA 0 "" 0 "" {TEXT -1 42 "so i n 15 ways. Let's see what Maple says" }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "bell(4);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 45 "The Bell \+ numbers grow fairly quickly with n," }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 66 "'bell(8)' = bell(8); 'bel l(10)' = bell(10); 'bell(20)' = bell(20);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 120 "Clearly a direct enumera tion like the one we did above rapidly becomes impractical. From the d efinition it is clear that" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "'bell(r)' = Sum('S(r,n)',n=0..r);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 56 "Let's check this relation for the case enumerated above:" }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "sum( stirling2(4,n),n=0..4);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 339 "There are a number of interpretations of Bell numbers. For example, consider the problem of putting r distin guishable objects into r indistinguishable buckets (in no particular order, since otherwise we could distinguish them). Each arrangement \+ may be considered a partition of the set of objects. Thus the number o f ways is bell(n)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 263 56 "Number of factorizations of a square-free natu ral number" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 363 "A natural number is square-free if it has no square factors. S uch a number is a product of distinct primes. In this case we can find all factorization by partitioning the set of prime factors and multip lying out the ones corresponding to subsets in the partition. Thus the number of factorizations is bell(r) where r is the number of (dis tinct) prime factors." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 105 "For example, 210 is the product of the primes 2, 3, \+ 5 and 7 and so has bell(4) = 15 factorizations. " }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 264 10 "Problem 1." }{TEXT 271 1 " " }{TEXT -1 47 " (by hand) List all the factorizations of 210 ." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 265 37 "Construction of the set of partit ions" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 283 " Sometimes we want an explicit list of all partitions of a set so we ca n perform some operation for each partition by stepping through the li st. Here is a procedure which returns the set of all partitions of the set \{1,2,3,....,n\}. We can easily convert to a list instead (see be low)." }}{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 remember;" }}{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 un ion \{ A union \{\{n\}\} \};" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 17 " \+ for B in A do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 48 " C:= ( A min us \{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 an 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 242 "By using the subs() command we can find the partitions required to solve problem 1. We convert part s(4) to a list first so Maple will not alter the order the partitions appear in. That makes it easier to check our work by visual inspectio n." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "subs(4=7,3=5,2=3,1=2,[op(parts(4))]);" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 52 "We can index over the set of partitions, for example" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "for A in pa rts(3) do A; od;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 66 "If a list is preferred we can easily convert as ab ove. For example" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "L:=[op(parts(3))];" }}}{EXCHG {PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 63 " Now we index over the \+ partitions as for any array. For example" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "for k from 1 to bell (3) do L[k]; od;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 73 "The number of partitions grows rapidly, so be care ful when using parts(n)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "parts(5);" }}}{EXCHG {PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 266 9 "Power Set" }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 135 "In a previous wor ksheet we wrote a procedure to compute the power set of a set. A much \+ easier way is to use Maple's procedure choose():" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "powset:=A-> choose(A);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "powset(\{a,b, c,d\});" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 86 "Another way is just to use Maple's builtin function power set() (but that is less fun)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "powerset(\{a,b,c,d\});" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 95 "Ho wever choose() has more capabilities. Thus we can find all the subsets of a given cardinality" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "choose(\{a,b,c,d,e\},3);" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 57 "Th e procedure choose() also works on lists. For example" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "choose ([a,a,b,b,b,b],3);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "choos e([a,a,b,b,b,c],3);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 44 "We can also compute the list of all sublists" } }{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "choose([a,a,b,b,b,b]);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "choose([a,a,b,b,b,c]);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 52 "The procedure powerset() also works o n lists. Thus" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "powerset([a,a,b,b,b,b]);" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 24 "powerset([a,a,b,b,b,c]);" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 65 "It seems there are always many ways to do any one thing in Maple!" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 235 "Note maple provides a pr ocedure subsets() which allows one to iterate over the power set wit hout actually computing and storing the whole power set. In large calc ulations you will need to know about subsets() (and other iterators) ." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 267 12 "Epimorphisms" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 91 "Let X be a set with cardinality r and let Y be a set with cardinality n. Suppose " }{XPPEDIT 18 0 "n <= r;" "6#1%\" nG%\"rG" }{TEXT -1 51 " and let E(r,n) be the number of epimorphism s f" }{TEXT 268 2 " :" }{TEXT -1 280 " X->Y. Note each epimorphism g ives rise to a partition of X into n subsets indexed by the elemen ts of Y. Composing an epimorphism with a permutation of Y gives ri se to another epimorphism which corersponds to the same partition. Thu s we see that Epi(r,n) = S(r,n) * n!" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "Epi:=(r,n)->stirling2( r,n)*n!;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 68 "Thus the number of epimorphisms of \{1,2,3,4,5,6\} onto \{1,2,3\} is" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 9 "Epi(6,3);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 269 49 "Compositions and Partitions of a \+ Positive Integer" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 212 "A k-composition of a positive integer n is a k-tuple o f positive integers summing to n. The order matters. The Maple functi on call composition(n,k) returns a list of all the k-compositions of n. For example" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "composition(5,3);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 61 "The number of such compos itions is returned by numbcomp(n,k)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "numbcomp(5,3);" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 181 "W e can think of numbcomp(n,k) as the number of ways to put n ones i n k distinguishable buckets with the proviso that each bucket must c ontain at least one one. Think about it." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 270 9 "Problem 2" }{TEXT 272 1 "." } {TEXT -1 129 " Use Maple to verify numbcomp(n,k) = binomial(n-1,k-1) for a few special cases. Then prove it (by hand) for the general cas e.." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 52 "Ma ple uses binomial(n,k) for the binomial numbers." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 253 "A k-partition of a positive integer n is a set of k positive integers summing to n . The order does not matter. The Maple function call partition(n) r eturns a list of all the partitions of n (each given as a list, rath er than a set). For example" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "partition(5);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 49 "The numbe r of partitions is given by numbpart(n)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "numbpart(5);" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 83 "We can get a list of all compositi ons without regard to length by concatening lists" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "allcomp:=pr oc(n)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 12 " local k,L;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "L:=[];" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "f or k from 1 to n do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 37 " L:= [ op(L ),op(composition(n,k)) ];" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "od;" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "return L;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 52 "Thus the list of all compositions of 5 is giv en by" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "allcomp(5); nops(%);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 59 "The number of composition s of n of any length is given by" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "k:='k': sum(binomial(n-1,k- 1),k=1..n);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 145 "Maple returns the list of partitions of n in a uniqu e order. Two procedures encodepart() and decodepart() are availabl e to access the list:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "L:=partition(5);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 49 "'decodepart(5,3)' = decodepart(5,3), 'L[3 ]'=L[3];" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "'encodepart([1, 2,2])'=encodepart([1,2,2]);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" } }{PARA 0 "" 0 "" {TEXT -1 198 "In addition there are procedures first part(), nextpart(), lastpart(), prevpart() and conjpart() which refer to the list of partitions in its canonical order. We can even ask for a random partition" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "randpart(20);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 258 "" 0 "" {TEXT -1 14 "r-permutations" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 156 "The proc edure permute(m,r) returns a list of all r-permutations of \{1,2,. .,m\}. The procedure numbperm(m,r) returns the number of r-permutat ions. Thus" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 28 "permute(5,3); numbperm(5,3);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 155 "Like most Maple fun ctions permute() is polymorphic. If we pass a list L, say permute( L,r), we get all the r-permutaions of the elements of the list L" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 44 "permute([a,b,c,d],3); numbperm([a,b,c,d],3);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 82 "Note permute() a nd numbperm() even work correctly on lists with repeated elements" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 44 "permute([a,b,c,c],3); numbperm([a,b,c,c],3);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 273 37 "Multinomial and \+ Binomial Coefficients" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 78 "The Maple functions multinomial() and binomial =() \+ return what you expect:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "binomial(9,4); 9!/(4!*5!);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "multinomial(8,3,3,2); 8!/(3! *3!*2!);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "expand((x+y+z)^ 6);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 15 "The calculation" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "multinomial(6,1,3,2); multinomial(6 ,2,2,2);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 196 "illustrates (x1+x2+...+xn)^m = sum(multinomial(m,k1...k n)* x1^k1* x2^k2* ....*xn^kn, k1+k2+...+kn = m) , which you should try to prove either by carefully grouping terms, or perhaps by induction. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 258 "" 0 "" {TEXT -1 14 "r-combinations" }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 428 "We can select r obje cts, without regard to order, from a set of n objects (distinguishab le since elements of a set) in C(n,r) = P(n,r)/r! = n!/(r!(n-r)!) w ays, 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 the number of c ombinations 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 let f : X -> \+ \{1,2,...,m\} . Then f determines an ordered partition of X (that i s, a list of nonempty subsets with union X). Suppose the i-th subset, the preimage of i, contains n_i points. How many such 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. Thus 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 191 "Thus, given n \+ distinct objects and m numbered containers, there are multinomial(n ,n_1,...,n_m) ways of placing the objects in the containers, with n_ k objects in the k-th container." }}{PARA 0 "" 0 "" {TEXT -1 0 "" } }{PARA 0 "" 0 "" {TEXT -1 221 "Here's another way to look at it: Given n objects where there are n_k objects of type (color, etc.) k, k =1,...,m, there are multinomial(n,n_1,...,n_m) ways to arrange them \+ in a row (argue by choosing the location)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 101 "Here's an example - the number of strings of length 12 which contain 4 a's, 3 b's, 2 c's and 3 d's i s" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "multinomial(12,4,3,2,3);" }}}{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 274 28 "Partitio ns of Sets Revisited" }}{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 340 "Now consider the number of par titions of A into m subsets A_i, i = 1,...,m, where A_i has \+ cardinality n_i. Let's order the set of sets A_i by cardinality to obtain 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 \+ corresponds 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 distinct 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-arra nging the parts of the list corresponding to a given N_i does not chan ge the corresponding 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 n umber 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 the sequence of N_i's with each repeated according to multiplicity. \+ Here's a procedure to compute this number" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "numbparts:=proc(L1,L 2)" }}{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 226 " Here's an example from our text: The number of ways to divide 43 stude nts into 7 groups such that there are 5 sudents in each of 2 groups, 6 students in each of 3 groups, 7 students in one group, and 8 students in one group is" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 35 "numbparts([5,2],[6,3],[7,1],[8,1]);" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 267 "I f we allocate each group of students to a named group, and the names a re distinct, then we can impose an arbitrary ordering on the names and we are dealing with ordered partitions. Thus the number of ways to as sign grades to 43 students so that 8 students get an A," }}{PARA 0 " " 0 "" {TEXT -1 81 "7 students get an A-, 6 students get B, 6 get C+, \+ 6 get C, 5 get D and 5 get F is" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "multinomial(43,8,7,6,6,6,5,5 );" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 354 "In this context the previous number above is the number of way s 8 students get the same grade, 7 students get the same grade, 6 stud ents get the same grade, 6 students get the same grade, 6 students get the same grade, 5 students get the same grade, and another 5 students get the same grade, and the grades for each group are different, but \+ unspecified." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 275 10 "Problem 3." }{TEXT -1 168 " A small college has 3 dormitories, imaginatively called dorm A, dorm B and dorm C. Each dormitory has a \+ large number of vacancies when 8 new students arrive on campus." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 276 9 "Part (A). " }{TEXT -1 191 " How many ways can we distribute the 8 students among the 3 distinguishable dorms if we assume the students are indistingui shable, that is, we just care how many students end up in each dorm?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 " " }{TEXT 277 9 "Part (B)." }{TEXT -1 251 " How many ways can we distri bute the 8 students among the 3 distinguishable dorms if we assume the students are indistinguishable, that is, we just care how many studen ts end up in each dorm, and if we require that each dorm gets at least one student?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 278 9 "Part (C)." }{TEXT -1 146 " How many way s can we distribute the 8 students among the 3 dorms if we regard the \+ students as distinguishable and the dorms as indistinguishable?" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 279 9 "Part (D)." }{TEXT -1 203 " How many ways can we distribu te the 8 students among the 3 dorms if we regard the students as disti nguishable and the dorms as indistinguishable, and we require that eac h dorm gets at least one student?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 280 9 "Part (E)." }{TEXT -1 158 " How many ways can we distribute the 8 students among the 3 do rms if we regard the students as indistinguishable and we regard the d orms as indistinguishable?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 281 9 "Part (F)." }{TEXT -1 210 " How many ways can we distribute the 8 students among the 3 dorms if w e regard the students as indistinguishable and we regard the dorms as \+ indistinguishable, and we require each dorm gets at least one student? " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 282 9 "Part (G)." }{TEXT -1 98 " How many ways can we dist ribute the 8 distinguishable students among the 3 distinguishable dorm s?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 283 9 "Part (H)." }{TEXT -1 142 " How many ways can we \+ distribute the 8 distinguishable students among the 3 distinguishable \+ dorms if each dorm is to get at least one student?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 284 9 "Pa rt (I)." }{TEXT -1 156 " How many ways can we put 3 students in dorm A , 3 students in dorm B, and the remaining 2 in dorm C? Here we assume \+ the students distinguishable, of course." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 285 10 "Part (J). \+ " }{TEXT -1 208 "How many ways can we put 3 students in one dorm, anot her 3 in another dorm and the remaining 2 in the remaining dorm, but w e don't care which dorms they end up in? Here we assume the students d istinguishable." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 51 "Your answers should probably all come from the list " }}{PARA 259 "" 0 "" {TEXT -1 1 " " }{XPPEDIT 18 0 "[5, 10, 21, 45, 2 80, 560, 966, 1094, 5796, 6561];" "6#7,\"\"&\"#5\"#@\"#X\"$!G\"$g&\"$m *\"%%4\"\"%'z&\"%hl" }{TEXT -1 2 ", " }}{PARA 0 "" 0 "" {TEXT -1 17 "t hough maybe not?" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}} {MARK "3 2 2" 102 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }