Combinatoric discussion

Put the theorems, problems, homework or anything else related to combinatoric here. We're here to help if we can.

Find the number of ways to place 3 rooks on 8×8 chessboard without any 2 rooks attacking each other.

Note: rotational position or mirror the board considered different.

"The selection of n objects out of a total of m objects, regardless of order, can be done in m!/[n!(m-n)!] way."

We have to select 3 unique files out of 8, so that's 8!/3!5! = 56 ways.

Meanwhile select 3 unique rank out of 8, so that's also 8!/3!5! = 56 ways.

So there's a way to place a rook. 56×56 = 3,136 solution

I honestly wish I was a lot better at combinatorics. My algebra skills are pretty good, and geometry I’m relatively good at. Number theory is my passion but I’m not good at it yet, but combinatorics has always been fascinating to me. Any more combinatorics problems and I’d love to attempt them, and probably fail lol

Theory 1

"The selection of n objects out of a total of m objects, regardless of order, can be done in C(m,n) = m!/[n!(m-n)!] ways."

This theory is useful in combinatorial studies.

Ok! I'll start with this problem, it's not difficult.

Problem 1:

To buy a sandwich. If you want to choose 1 type of sauce from 3 types, 1 type of meat from 4 types, and 2 types of vegetables from 5 types, how many differen ways of sandwich can you choose?

Choosing 2 vegetables out of 5 can be done in only 5!/2!3! = 10 ways.

The meaning of 5! is a number of the ways to permutation 5 different objects, but this is only selecting 2 and the order doesn't matter. Therefore, theory 1 must be used.

For example. cabage = A, cucumber = C, onion = O, carrot = R, tomato = T.

There are 10 ways to choose from: (A,C), (A,O), (A,R), (A,T), (C,O), (C,R), (C,T), (O,R), (O,T), (R,T)

Theory 2.1

"Permutations of n objects on a line have n! different ways."

Theory 2.2

Permutations of n objects on a circle have (n-1)! different ways"

Look at this question, Theory 2.1 can help.

Problem 2: How many ways can 4 men and 2 women be stand in a line? if

2.1 No additional conditions.

2.2 Two women must stand next to each other.

Oh, our intentions don't match. In lining up, I assumed that everyone was different. Not just men and women.

The way you think about it, you will get the answer of 2.1, 2.2 is 10 and 5 respectively.

find a new answer assuming all people are different.

That correct!

Ok. Here are solution

2.1) "6! = 720" It is a permutation of 6 object on a line, have 6! ways

2.2) "2(5!) = 240" Looking at women next to each other as one group. Therefore, it is a permutation of 5 object, have 5! ways. In addition, the 2 women we looked at were groups. can switch positions among themselves So all permutations are 2×5!

How many ways can you arrange the word MATHEMATICS so that the first letter is a vowel and the last is a consonant?

nice question. I will do it tomorrow.

Theory 3

Definition: A repeating set is a set with interleaving members, e.g. M={a,b,c,c,a} is a set that has a total of 5 members, can be written for ease of use by specifying the number of repetitions in front of each member, e.g. M={2·a, b, 2·c} . In general the iterative set is of the form M={r₁·a₁, r₂·a₂,..., rₙ·aₙ} when n, r₁, r₂,..., rₙ is a positive integer and a₁, a₂,...,aₙ  are different member.

Let  M={r₁·a₁, r₂·a₂,..., rₙ·aₙ} and  r=r₁+r₂+...+rₙ

"The number of permutations of the set M is P(r₁, r₂,..., rₙ) = r! / (r₁!r₂!...rₙ!)"

Member of the letter in the word "MATHEMATICS" is within the set {2·M,2·A,2·T, H,E,I,C,S}

from condition "...the first letter is a vowel and the last is a consonant" I can divide the case as follows.

Case 1: first letter is A and the last is (M or T) ; So the middle 9 letters are permutation members in the set {1·M?, 1·A ,2·T?, H,E,I,C,S} which have 9!/2! ways. and then decide that the last one will be M or T in 2 ways. So there are 2×(9!/2!)=9! different ways to arrange 11 letters.

Case 2: first letter is A and the last IS NOT (M or T) ; So the middle 9 letters are permutation members in the set {2·M, 1·A ,2·T, H?,E,I,C?,S?} which have 9!/2!2! ways. and then decide that the first one and last one will be H,C or S in 3 ways. So there are 3×(9!/2!2!)=3×9!/4 different ways to arrange 11 letters.

Case 3: first letter is (E or I) and the last is (M or T) ; So the middle 9 letters are permutation members in the set {1·M?, 2·A ,2·T?, H,E?,I?,C,S} which have 9!/2!2! ways. and then decide that the first one and last one will be (E,I) or (M,T) in 4 ways. So there are 4×(9!/2!2!)=9! different ways to arrange 11 letters.

Case 4: first letter is (E or I) and the last IS NOT (M or T) ; So the middle 9 letters are permutation members in the set {2·M,2·A,2·T , H?,E?,I?,C?,S?} which have 9!/2!2!2! ways. and then decide that the first one and last one will be (E,I) or (H,C,S) in 2×3=6 ways. So there are 6×(9!/2!2!2!) =3×9!/4 different ways to arrange 11 letters.

SUM OF ALL CASE = 9! + 3×9!/4 + 9! + 3×9!/4 = 7×9!/2 ways (about 1.27×10⁶)

Edited : Permutations of the rook within a 3×3 grid can be made in 3!=6 more ways, so the total number of ways must be 3,136×6 = 16,816 ways.

Problem 3:

The result of 200! how many digits of 0 are there at the end.

ex. 8! = 40,320 has 1 digit of 0 at the end.

One way there would be a zero is when 5 and 2 are multiplied together. There are many more multiples of 2 than multiples of 5, so we can assume that there are sufficient even numbers. There are 200/5=40 multiples of 5 from 1-200. We also have to consider numbers with more than one factor of 5. 25, 50, 75, 100, 125, 150, 175, and 200 all have two factors of 5. There are eight of these, so add that to the number of trailing zeroes. 40+8=48

125 has three factors of 5, so we will add one more trailing zero. 48+1=49.

There are 49 trailing zeros to the number 200!

That true!