6.042/18.] Mathematics for Computer Science March 25, 2005 Srini devadas and Eric Lehman Lecture notes Counting I 20480135385502964448038317100483217350139411301757632573310834796474093988247331000042995311646021 489445991866915676240992320823442159736864701926558009491235489891226286638496243997123475922766310 1082662032430379651370981343725465635515786486911360429008011992802180260018518399140676002660747477 1178480894769706178994993357488339305865392371136561161717891377378967014058543691283470191452333763 25312735168323969385132736449099460404801899691496144868973001582369723512867530925837137092461352 1301505129234077811069011379004413273708409441724662473145938511692347461528694321112363996867296665 311567111143866433882194387033212743797135532281568144289442668749634882748772321203608477245851154 14700294527212035876862144080505804577801451363100687085294554388684914788187914221617225825463410 1578271047286257499433886416728346102570234812492069149555081209500937323979062628024592126283973285 1638243921852176243192354423599683112377778821124969496324513659871524235419137845566925526349897794 1763580219131985963102365467093944574943904211122071282111436136198284156509153762966803189291934419 1826227795601842231029694481537935186538427961342771739200836518623079253949270880194077636406984249 1843971862675102037201420483705294821292260444219072156548742117556762205879324301480722103490379204 239695119372213452617723751063894238550185506715307256928471643910402330509436090832146695147140581 2781394568268599801096354514236819200476921806991073328226570752354316203179475308159734538249013238 2796605196713610405408019518123409613014408404185674264418295415734449641399492376623917486974923202 2931016394761975263190347519826739812561799439134876321981265318093271863219511972558779880288252979 2933458058294405155197296531759294031623121975837277121544322119128823105119602413424619187112552264 3075514410490975920315348538435812677179412835694778589186642402623566100109631217114906129219461111 3111474985252793452860017543921171224890199542344178981567867632129631786799908189853102753335981319 3145621587936120118438701561037982609283819276045881475910170375733378486169913237476341764299813987 314890125562888110319854956323175554652286776760448149436716871371161932035 315769310532511128432199356921683746370196174237128176063831682536571306791 Two different subsets of the ninety 25-digit numbers shown above have the same sum For example, maybe the sum of the numbers in the first column is equal to the sum of the numbers in the second column. Can you find two such subsets? This is a very difficult computational problem. But we'll prove that such subsets must exist! This is the sort of weird conclusion one can reach by tricky use of counting, the topic of this chapter Counting seems easy enough: 1, 2, 3, 4, etc. This explicit approach works well for counting simple things, like your toes, and for extremely complicated things for which there's no identifiable structure. However, subtler methods can help you count many things in the vast middle ground, such as The number of different ways to select a dozen doughnuts when there are five vari eties available The number of 16-bit numbers with exactly 4 ones Counting is useful in computer science for several reason Determining the time and storage required to solve a computational problem-a central objective in computer science- often comes down to solving a counting6.042/18.062J Mathematics for Computer Science March 25, 2005 Srini Devadas and Eric Lehman Lecture Notes Counting I 20480135385502964448038 3171004832173501394113017 5763257331083479647409398 8247331000042995311646021 489445991866915676240992 3208234421597368647019265 5800949123548989122628663 8496243997123475922766310 1082662032430379651370981 3437254656355157864869113 6042900801199280218026001 8518399140676002660747477 1178480894769706178994993 3574883393058653923711365 6116171789137737896701405 8543691283470191452333763 1253127351683239693851327 3644909946040480189969149 6144868973001582369723512 8675309258374137092461352 1301505129234077811069011 3790044132737084094417246 6247314593851169234746152 8694321112363996867296665 1311567111143866433882194 3870332127437971355322815 6814428944266874963488274 8772321203608477245851154 1470029452721203587686214 4080505804577801451363100 6870852945543886849147881 8791422161722582546341091 1578271047286257499433886 4167283461025702348124920 6914955508120950093732397 9062628024592126283973285 1638243921852176243192354 4235996831123777788211249 6949632451365987152423541 9137845566925526349897794 1763580219131985963102365 4670939445749439042111220 7128211143613619828415650 9153762966803189291934419 1826227795601842231029694 4815379351865384279613427 7173920083651862307925394 9270880194077636406984249 1843971862675102037201420 4837052948212922604442190 7215654874211755676220587 9324301480722103490379204 2396951193722134526177237 5106389423855018550671530 7256932847164391040233050 9436090832146695147140581 2781394568268599801096354 5142368192004769218069910 7332822657075235431620317 9475308159734538249013238 2796605196713610405408019 5181234096130144084041856 7426441829541573444964139 9492376623917486974923202 2931016394761975263190347 5198267398125617994391348 7632198126531809327186321 9511972558779880288252979 2933458058294405155197296 5317592940316231219758372 7712154432211912882310511 9602413424619187112552264 3075514410490975920315348 5384358126771794128356947 7858918664240262356610010 9631217114906129219461111 3111474985252793452860017 5439211712248901995423441 7898156786763212963178679 9908189853102753335981319 3145621587936120118438701 5610379826092838192760458 8147591017037573337848616 9913237476341764299813987 3148901255628881103198549 5632317555465228677676044 8149436716871371161932035 3157693105325111284321993 5692168374637019617423712 8176063831682536571306791 Two different subsets of the ninety 25­digit numbers shown above have the same sum. For example, maybe the sum of the numbers in the first column is equal to the sum of the numbers in the second column. Can you find two such subsets? This is a very difficult computational problem. But we’ll prove that such subsets must exist! This is the sort of weird conclusion one can reach by tricky use of counting, the topic of this chapter. Counting seems easy enough: 1, 2, 3, 4, etc. This explicit approach works well for counting simple things, like your toes, and for extremely complicated things for which there’s no identifiable structure. However, subtler methods can help you count many things in the vast middle ground, such as: • The number of different ways to select a dozen doughnuts when there are five vari￾eties available. • The number of 16­bit numbers with exactly 4 ones. Counting is useful in computer science for several reasons: • Determining the time and storage required to solve a computational problem— a central objective in computer science— often comes down to solving a counting problem