Combinatorical Analisys

Get Started. It's Free
or sign up with your email address
Rocket clouds
Combinatorical Analisys by Mind Map: Combinatorical Analisys

1. Different Distributions

1.1. Distribution into simillar classes

1.1.1. All the cases are simillar to different classes distributions, but its result needs to be divided by number of classes factorial as the order is irrelevant

1.2. Distribution into different classes

1.2.1. Number of classes are given

1.2.1.1. Objects are unique

1.2.1.1.1. The answer is r^n

1.2.1.2. Objects are simillar

1.2.1.2.1. The answer is (n+r-1)C(r-1)

1.2.1.3. Groups of simillar objects

1.2.1.3.1. The answer is (n+r-1)C(r-1)*(n1+r1-1)C(r1-1)*...*(nk+rk-1)C(rk-1)

1.2.2. Number of unique objects in classes are given

1.2.2.1. The answer is nM(n1,n2,...nk)

1.2.2.1.1. Step 1: Choose all possible permutations of n Step 2: Divide the result by all the possible permutations of repetitive objects

2. Permutations

2.1. With repetitions

2.1.1. The answer is n!

2.1.1.1. Step 1: There are n positions for the first object, n-1 for second... Step 2: Using product rule we have n*(n-1)...*1 different solutions

2.1.1.1.1. In how many ways we can reorder letters in word "combine"?

2.2. Without repetitions

2.2.1. The answer is n!/(n1!*n2!..*ni!)

2.2.1.1. Step 1: Mark all objects to make them distinguishable Step 2: There are n! ways to reorder them Step 3: Divide n! by (n1!*n2!*...ni!) where n1, n2 ... - number of identical objects to exclude repeated solutions

2.2.1.1.1. In how many ways you can reorder letters in word "combinatorics"?

3. Choosing objects

3.1. Ordered

3.1.1. With repetitions

3.1.1.1. The answer is (nC’r)*r!

3.1.1.1.1. Step 1) Since we can pick one object more than once, we can put n-1 vertical lines in a line and r blanks. Step 2) The lines will represent separators and there are (r+n-1)C(n-1)ways we can shuffle them around n+r-1 spaces. Step 3) We put letters S on blank spaces after shuffling to represent students. Step 4) Since the order matters, we also multiply by the number of possible shufflings of students, or r!.

3.1.2. Without repetitions

3.1.2.1. The answer is nPr

3.1.2.1.1. Step 1) First girl can be picked in n ways, the second – n-1, the third – n-2 (or n-r+1). Step 2) This can be written as n!/(n-r)! .

3.2. Not ordered

3.2.1. With repititions

3.2.1.1. The answer is (n+r-1)Cr

3.2.1.1.1. Step 1) Let r cones be apples, and n-1 be oranges to serve as separators among them to symbolize n different flavors cones can have. Step 2) Lets have n+r-1 plates where to put apples and oranges onto. Step 3) We need to find all possible ways we can put apples on plates, and the free plates will be for oranges (separators of flavors), so all combinations of r out of n+r-1.

3.2.2. Without repititions

3.2.2.1. The answer is nCm

3.2.2.1.1. Step 1 : We can represent choosing n objects from m as permutation with repetition. Step 2: Line up all objects. Then you mark the n you choose. It is the same task as to reorder n objects of one type and m-n of another.