Transcription of Combinatorics and counting
1 Combinatorics and countingPer Alexandersson2p. alexanderssonIntroductionHere is a collection of counting problems. Questions and suggestionsVersion: 15th February 2021,22:26are welcome vs. independent that weaddthe counts for exclusive situations, andmultiplythe counts forindependent situations. For example, the possible outcomes of a dicethrow are exclusive:(Sides of a dice)=(Even sides)+(Odd sides)The different outcomes of selecting a playing card in a deck of cardscan be seen as a combination ofindependentchoices:(Different cards)=(Choice of color) (Choice of value).Labeled vs. unlabeled setsis a common cause for the following two problems: Count the number of ways to choose2people among4people. Count the number of ways to partition4people into sets of the first example, it is understood that the set of chosen peopleis aspecialset it is thechosen set.
2 We choose two people, andthe other two are not chosen. In the second example, there is nodifference between the two couples. The answer to the first questionis therefore(42), counting the chosen subsets:{12, 13, 14, 23, 24, 34}.The answer to the second question is12!(42), counting the partitions:{12|34, 13|24, 14|23}.That is, the issue is that there is no way to distinguish the two setsin the partition. However, now consider the following two problems: Count the number of ways to choose2people among5people. Count the number of ways to partition5people into a set of size2and a set of this case, the answer to both questions is(53). The reason for thisis that we can distinguish between the two sets in the partition inthe second question, for example,the set of size2is always consider peopleto be unique, and therefore means that in a group ofnpeople, we can talk about the firstperson, the second person, and so on.
3 In a group ofnidenticalobjects, there is no a priori notion of the first and counting3 Overview of formulasEvery row in the table illustrates a type of counting problem, wherethe solution is given by the formula. Conversely, every problem is acombinatorial interpretationof the formula. In this context, agroupof things means an unordered a group ofkobjects fromndifferentobjectsBinomial coefficient(nk)Partitionndifferent objects intomlabeledgroups, withkielements in groupiMultinomial coefficients(nk1,..,km)Partitionndiffere nt objects intoknon-empty groups, where there is no order on thesetsPartitions, Stirling numbersS(n,k)Partitionndifferent objects intoklabeledgroups (which could be empty)Multiplication principleknPartitionnidentical objects intomlabeledgroupsDots and bars(n+m 1m 1)Same, but with non-empty groupsDots and bars(n 1m 1)Orderndifferent objectsPermutationsn!
4 Choose and orderkdifferent objects fromndifferent objectsPermutationsn!(n k)!Choose and ordernobjects, where there arekiidentical objects of typeiMultinomial coefficients(nk1,..,km)Choices for(X,Y)if there arexchoices forXand, independently,ychoices ofYMultiplication-principlex yNumber of elements inA B CInclusion-exclusion|A B C|=|A|+|B|+|C| |A B| |A C| |B C|+|A B C|4p. alexanderssonBinomial- and multinomial coefficientsWhenevern 0and0 k n, we define thebinomial coefficientsasSometimes the notationC(n,k)for(nk)is used.(nk)=n!k!(n k)!.(Binomial coefficients)The binomial coefficients satisfy the following recursion:To choosekobjects among{1, 2,..,n}, we either excluden, and choosekobjects among{1, 2,..,n 1}orwe includen, andchoose additionalk 1objects among{1, 2.}
5 ,n 1}.(nk)=(n 1k)+(n 1k 1).(1)We have thebinomial theorem:(x+y)n=n k=0(nk)xkyn k(Binomial theorem)A generalization of the binomial coefficients are themultinomialcoefficients. Wheneverk1+k2+..+kr=n, they are defined as(nk1,k2,..,kr)=n!k1! kr!.(Multinomial coefficients)Stirling numbersThe Stirling numbersS(n,k)can be computed recursively via atable, where every row is obtained from the previous viaProof:To partition{1, 2, ,n}, intokgroups, we either letnbe in its owngroup, and partition{1, 2,..,n 1}intok 1groups, or we partition{1, 2,..,n 1}intokgroups andchoose which of thekgroupsnbelongs (n,k) =S(n 1,k 1) +k S(n 1,k).and using the fact thatS(n, 1) =S(n,n) = problemsProblem. 1 You are creating a4-digit pin code. How many choices are there inthe following cases?
6 (a) With no restriction.(b) No digit is repeated.(c) No digit is repeated, digit number3is a0.(d) No digit is repeated, and they must appear in increasing order.(e) No digit is repeated,2and5must be 2 How many shuffles are there of a deck of cards, such thatA is notA standard deck has 52 cards, dividedinto four suits ( , , , ). Thereare13cards of each suit,2, 3,.., 10,J,Q,K,A, the Jack, Queen, Kingand Acedirectly on top ofK , andA is not directly on top ofK ?Problem. 3 How many different words can be created by rearranging the lettersinSELFIESTICK? Combinatorics and counting5 Problem. 4 How many flags can we make with7stripes, if we have2white,2red and3green stripes?Problem. 5We have four different dishes, two dishes of each type.
7 In how manyways can these be distributed among8people?Problem. 6In how many ways can8people form couples of two?Problem. 7We go to a pizza party, and there are 5 types of pizza. We havestarved for days, so we can eat 13 slices, but we want to sample eachtype at least once. In how many ways can we do this? Order doesnot 8 How manyrth order partial derivatives doesf(x1,..,xn)have?Problem. 9 How many integer solutions doesx1+x2+ +xn=rhave, withxi 0?Problem. 10 How many integer solutions does the equationx1+x2+x3+x4=15have, if we require thatx1 2,x2 3,x3 10andx4 3?Problem. 11 How many integer solutions are there to the system of inequalitiesx1+x2+x3+x4 15,x1,..,x4 0?Problem. 12 Count the number of non-negative integer solutions to3x1+3x2+3x3+7x4= 13 Compute the number of surjectionsf:A Bif|A|=nand|B|= 14 You are going to an amusement park.
8 There are four attractions,(haunted house, roller coaster, a carousel, water ride). You buy25tokens. Each attraction cost3tokens each ride, except the rollercoaster that costs5. Obviously, you want to ride each ride at leastonce, but the order of the rides does not alexanderssonIn how many ways can you spend your tokens? You may havesome remaining tokens in the end of the 15At an amusement park, you pay for attractions using tokens. Thereare five different attractions which cost3tokens each, and oneattraction which cost5tokens. You have42tokens and you wantto use all of them. How many different selections of attractions arethere?Problem. 16 How many words can you create of length6, from the lettersa,b,canddif you must include each letter at least once, and amust appear exactly 17 Eight different exam questions are to be distributed among threestudents, such that each student receives at least one , two of the questions are very easy and must be given todifferent students.
9 In how many ways can this be done?Problem. 18 Prove thatS(n+1,k+1) S(n,k)whenevern 1and1 k 19 How many words can be made by rearrangingaabbccdd, such thatno a appears somewhere to the right of some c ?Problem. 20 You have2copies of the letter A and and unlimited supply of theletters B , C and D . How many words of length10can youmake from these, such that all theA s are used the third letter is anA, and there is noBappearing between theA s?Mailbox-principleProblem. 21 What is the maximum number of rooks you can place on an8 8chessboard so that no two rooks can attack each other? Combinatorics and counting7 Problem. 22 Alice and Bob are dining at a Chinese restaurant, where there are 10small dishes available. Each dish is priced between 50 and 100 decide to order several dishes each, in such a manner that alldishes are different.
10 Moreover, they want to ensure that the price ofthe dishes Alice chooses have the same total price as the ones that such a choice is 23 LetSbe a subset of{1, 2,.., 2n}such thatShasn+ is quite a challenging problem!Prove that there are different elementsa,binSsuch identitiesIn this section, we prove combinatorial identities by giving an in-terpretation of the different terms and factors involved. The go-tostrategy is that the simpler side of the identity tells some story story,and we add somerefinementor details to the story to get an inter-pretation of the more complicated side. For example, a poker playercan immediately tell you how to prove and interpret the combinato-rial identity52=13+13+13+ left hand side count the number of cards.
