Combinations and Permutations

What are the basic principles of counting? How many ways are there to select or arrange k elements from an n-set (a set with n members)? If the order of the arrangement matters, does the result change? Why? How? What is a combination (https://en.wikipedia.org/wiki/Combination)? What is a permutation (https://en.wikipedia.org/wiki/Permutations)? How do combinations and permutations exemplify the careful thinking required to answer advanced counting questions? What are some of the ways we can use and compute combinations and permutations?

These questions come from the second week of Ma Yu Chun's free on-line TsinghuaX 60240013.x Combinatorial Mathematics (https://www.edx.org/course/combinatorial-mathematics-tsinghuax-60240013x-0) on the edX (http://edx.org) platform (Note: in Wikipedia it is reported that Tsinghua University (https://en.wikipedia.org/wiki/Tsinghua_University) is sometimes called the "MIT of China" due to its specialty in engineering and science).

To help guide the discussion, please download and work out answers to these 23 exercises: http://files.meetup.com/3948532/CombinationsPermutations.May2016.problems.pdf . Many of the problems are easy, but a few will require careful thought. If you have questions or issues with any of the problems, please post a comment below.

Discussing the 23 exercises will be a major part of the meetup. It is recommended that participants spend at least 5-10 minutes on each of the 23 exercises. You do not need to solve the problems, just make enough of an effort that we can productively discuss them together.

Ma Yu Chun's lecture entitled "Combinatorial Trip of a Pingpang Ball" includes 11 videos totaling just over 1½ hours. If you watch the videos and read her slides (both are below), you will find that many of the exercises are trivial. Her lecture provides the basic background material for our topic.

• Ma Yu Chun's slides (66 pages) for all 11 video lectures on Combinations and Permutations ("Combinatorial Trip of a Pingpang Ball") (https://courses.edx.org/c4x/TsinghuaX/60240013.x/asset/edxCM_w2.pdf)

• 9 minute introduction to the basic principles of counting

https://www.youtube.com/watch?v=0pRIQFJksX4

• 12 minute introduction to combinations and permutations including their definition and some basic properties

https://www.youtube.com/watch?v=sSq1uHVeh_o

• 10 minute Models of Combination and Combinatorial Identities

https://www.youtube.com/watch?v=D71Dn8disK4

• 6 minute Circular Permutation and Necklace Permutation

https://www.youtube.com/watch?v=NdMznYfpBe8

• 10 minute Permutations of Multisets

https://www.youtube.com/watch?v=Vguc-AXJ_YY

• 12 minute Combinations of Multisets

https://www.youtube.com/watch?v=hq1zKt9ReJo

• 12 minute Non-adjacent Combinations

https://www.youtube.com/watch?v=LLFmTO3M0Yk

• 4 minute Permutations In The Bell Ring (see Wikipedia's article on change ringing (https://en.wikipedia.org/wiki/Change_ringing) for some background information)

https://www.youtube.com/watch?v=BQqbdHkdytw

• 11 minute Lexicographic Order

https://www.youtube.com/watch?v=HDp4WvvjHLI

• 6 minute Steinhaus–Johnson–Trotter Algorithm (https://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm)

https://www.youtube.com/watch?v=n-K5vdbEqq4

• 5 minute Stirling approximation

https://www.youtube.com/watch?v=J1o8gHlUM5k

https://upload.wikimedia.org/wikipedia/commons/f/f3/Straight_line.png

In the past some members have had difficulties with the videos. Here is a list of links in case the embedded player does not work for you:

http://www.youtube.com/watch?v=0pRIQFJksX4
http://www.youtube.com/watch?v=sSq1uHVeh_o
http://www.youtube.com/watch?v=D71Dn8disK4
http://www.youtube.com/watch?v=NdMznYfpBe8
http://www.youtube.com/watch?v=Vguc-AXJ_YY
http://www.youtube.com/watch?v=hq1zKt9ReJo
http://www.youtube.com/watch?v=LLFmTO3M0Yk
http://www.youtube.com/watch?v=BQqbdHkdytw
http://www.youtube.com/watch?v=HDp4WvvjHLI
http://www.youtube.com/watch?v=n-K5vdbEqq4
http://www.youtube.com/watch?v=J1o8gHlUM5k

https://upload.wikimedia.org/wikipedia/commons/f/f3/Straight_line.png

Note: this is our second session on Ma Yu Chun's course Combinatorial Mathematics (https://www.edx.org/course/combinatorial-mathematics-zu-he-shu-xue-tsinghuax-60240013x-0). To see the event description and problem set from the first session, please go to Combinatorics: The Science of Counting and Arrangements (19 Sep 2015) (https://www.meetup.com/MathCounts/events/224748900/).