Is Permutation and Combination Challenging to Learn?

[Kaushik]

TL;DR

Is 'Permutation and combination' hard to understand ?

Summary: Is 'Permutation and combination' hard to understand ?

I am facing difficulties in understanding this concept. So I would like to ask some questions to enhance my knowledge in this topic.
My questions are-

1. Does it require time to grasp this concept?
2. Is it normal to get confused?
3. How was your experience learning this topic?
4. Can I get any good source where I can learn this topic?
5. Any good video on this topic would also help?

 

[jedishrfu]

Yes, it takes some time to get straight.

Yes, it’s confusing at first.

It’s very useful in estimating probabilities and number of ways things can be combined or ordered.

Go to Khan Academy, they should have some good videos on it.

In mathematics, it’s often called combinatorics.

 

[Kaushik]

Go to Khan Academy, they should have some good videos on it.

Thanks for your suggestion!

 

[fresh_42]

Yes, it’s confusing at first.

At first? I still hate counting ... especially in all cases where it is not $n!$ or $\binom n k$.

 

[Klystron]

Understanding combinatorics does take study and practice but worth the effort.

I use a simple memory trick (mnemonic).
Combinatorics -- combination -- element order is not important.
Permutation -- mutation means change -- order is important.

 

[Kaushik]

At first? I still hate counting ... especially in all cases where it is not $n!$ or $\binom n k$.

True!

 

[Kaushik]

Understanding combinatorics does take study and practice but worth the effort.

I use a simple memory trick (mnemonic).
Combinatorics -- combination -- element order is not important.
Permutation -- mutation means change -- order is important.

Thanks!

 

[jedishrfu]

I remember attempting to compute the number of sudoku patterns and always failing to consider some symmetry which decreases the count or other rule flexibility that increases the count.

I was trying to prove the minimum of 17 numbers are needed at the start to create an unambiguous puzzle.

I also tried to prove that starting with a single solution generating all permutations allowed would match all possible solutions too. Failed there, lost in the complexity of the puzzle.

 

[Kaushik]

Combinatorics -- combination -- element order is not important.
Permutation -- mutation means change -- order is important.

Can we say that permutation is always greater than or equal to combinations?

 

[jedishrfu]

Can we say that permutation is always greater than or equal to combinations?

No they are two different concepts that can be used together or separately.

 

[fresh_42]

I remember attempting to compute the number of sudoku patterns and always failing to consider some symmetry which decreases the count or other rule flexibility that increases the count.

I was trying to prove the minimum of 17 numbers are needed at the start to create an unambiguous puzzle.

I also tried to prove that starting with a single solution generating all permutations allowed would match all possible solutions too. Failed there, lost in the complexity of the puzzle.

I remember a paper (seminar or diploma or something) about sudokus, IIRC about computational complexity. It was definitely thicker than just a few pages.

 

[FactChecker]

The basic concepts are easy. And if one could do brute force counting rapidly, the problems would be easy. But in reality, the problems and examples often require a great number of tricks, bookkeeping, and ingenuity to do the counting. That can be hard.

 

[jedishrfu]

One of the interesting things I was exploring was how to create a program to generate sudokus. Initially, I thought it had to plunk in numbers and try to maintain the rules.

However, in doing so I realized that's like trying to generate a random deck of cards by generating a card number and searching your list to see if it's there and if so generate another.

As you can imagine it takes longer and longer to fill the list with 52 random distinct numbers.

The better way is to generate a list from 1 to 52 and select two cards randomly from the list and swap them. After 10 to 20 swaps your deck is pretty well shuffled and it was a fixed time to do so.

Similarly for sudoku, starting with a solved matrix you can do the various symmetry transformations to create a new matrix that is guaranteed to be solved. In display of the , the puzzle you pick 17 or more random positions to display and leave the others blank left for the game user to fill in and of course the program knows the answer already.

 

[Klystron]

Can we say that permutation is always greater than or equal to combinations?

Very thought provoking question. Studying the twelve-fold way should help the OP arrive at an answer depending on what is being counted. This excerpt from wikipedia defines (added bold):

Insofar as an area can be described by the types of problems it addresses, combinatorics is involved with

• the enumeration (counting) of specified structures, sometimes referred to as arrangements or configurations in a very general sense, associated with finite systems,
• the existence of such structures that satisfy certain given criteria,
• the construction of these structures, perhaps in many ways, and
• optimization, finding the "best" structure or solution among several possibilities, be it the "largest", "smallest" or satisfying some other optimum criterion.

Suggest you post the particular formulae you are studying perhaps with sample problems you are solving. The mathematicians on PhysicsForums can help you analyze the process, help devise proofs, and correct errors. Look below this thread for prior threads with similar titles.

 

[Kaushik]

Question
A person invites 10 guests at a dinner party and place them so that 4 are on one round table and the remaining 6 are on the other round table.Find the number of ways in which he can arrange them.

My attempt-
In first table with 4 seats, people can sit in $1 * 9 * 8 * 7$ ways. In the second table with 6 seats there are 6 people remaining who are yet to be seated. So those 6 guests can be seated in $1 * 5 * 4 * 3 * 2* 1$ ways.
So Total arrangements = $\frac{9!}{(6!)}*5!$

What am I doing wrong?

 

[FactChecker]

Before looking at your work, I should point out that the question is stated very ambiguously. What constitutes an "arrangement"? Do the positions at the tables count or just which table each is at? Are we allowed to change which table a person is at or not?

Now, looking at your work, what were your assumptions regarding those questions? In any case, the first factor of '1' looks very out of place. Can you explain where each factor of 1*9*8*7 comes from? They look wrong. It is hard to say what you are doing wrong when you are not describing in detail what you are doing. If you are doing what I think you are doing, then your answer looks correct.

 

[FactChecker]

I think I see what you are doing and I agree with your answer (if my assumptions are correct).

 

[Kaushik]

Are we allowed to change which table a person is at or not?

I think we are allowed to change which table a person is sitting at, i.e he can sit at anyone of the 2 tables.

In any case, the first factor of '1' looks very out of place.

As it is a circular arrangement, the arrangement of the first person will not change anything , i.e, whatever seat he is placed at, he will have the same view. So the arrangement of the people matters from the second person. Hence, 1.

 

[Kaushik]

Can you explain where each factor of 1*9*8*7 comes from?

As 1 person is fixed, there are 9 remaining people and 3 seats. Hence, $9*8*7$

 

[FactChecker]

Suppose you work it from another direction. For each seat in a fixed order, select a person to sit there. Then divide by the number of ways to rotate table 1 and table 2. I think that gives a different answer, which I feel more confident of.

 

[Kaushik]

Suppose you work it from another direction. For each seat in a fixed order, select a person to sit there. Then divide by the number of ways to rotate table 1 and table 2. I think that gives a different answer, which I feel more confident of.

Can you please elaborate?

 

[FactChecker]

You have 10 seats, $S_1, S_2, ..., S_{10}$. You can select people to sit in each one: 10 in $S_1$, 9 in $S_2$, ..., 1 in $S_{10}$. How many possibilities does that give you? But then you can rotate the first table around to 4 different positions and the second table around to 6 different positions. So how do you adjust for that?

PS: If this is a homework problem, then I may have already said too much. We are only allowed to give guidance hints and must let you do all the work.

 

[Kaushik]

Answer

• Why do we use $\binom{10}4$ instead of $9!/6!$?
• If order matters here, why do we use combination instead of permutation?

 

[FactChecker]

You have still not defined the problem precisely. Does it only matter which table people are at or does the seating position at the tables matter? At the small table, is the seating of persons A,B,C,D the same as D,C,B,A? (clockwise versus counterclockwise?), or are those different? Does the exact seat matter, or only who people are sitting next to. Is a rotation of the seats considered the same (A,B,C,D same as B,C,D,A)? Please contribute to this by defining the problem precisely.

 

[Kaushik]

At the small table, is the seating of persons A,B,C,D the same as D,C,B,A? (clockwise versus counterclockwise?),

No. But A,B,C,D is same as B,C,D,A

Does the exact seat matter, or only who people are sitting next to

No. All seats are identical.

Does it only matter which table people are at or does the seating position at the tables matter?

I'm sorry. I am not able to understand this question.

 

[FactChecker]

Ok. I would start by 1) counting it as though exact seating mattered. 2) Then divide by cases where multiple seating arrangements will be considered equivalent.

1) Counting as though exact seating matters
There are 10 seats for 10 people. The people can be put in them in 10! ways.

2) Divide by cases where multiple seating arrangements will be considered equivalent.
The seating at the small table (4 seats) will be considered equivalent if they are just rotations of each other. ABCD = BCDA = CDAB = DABC. So divide by 4.
Similarly, the seating at the large table (6 seats) will be considered equivalent if they are just rotations of each other. So divide by 6.

Final answer: 10!/(4*6).

Note: This is the same as 10!/4! that some people got. I couldn't exactly follow the logic of the people who got 10!/4! in one step.
Note: If clockwise and counterclockwise are also considered equivalent, then divide by 8 and 12 rather than 4 and 6.

 

[Kaushik]

Ok. I would start by 1) counting it as though exact seating mattered. 2) Then divide by cases where multiple seating arrangements will be considered equivalent.

1) Counting as though exact seating matters
There are 10 seats for 10 people. The people can be put in them in 10! ways.

2) Divide by cases where multiple seating arrangements will be considered equivalent.
The seating at the small table (4 seats) will be considered equivalent if they are just rotations of each other. ABCD = BCDA = CDAB = DABC. So divide by 4.
Similarly, the seating at the large table (6 seats) will be considered equivalent if they are just rotations of each other. So divide by 6.

Final answer: 10!/(4*6).

Note: This is the same as 10!/4! that some people got. I couldn't exactly follow the logic of the people who got 10!/4! in one step.
Note: If clockwise and counterclockwise are also considered equivalent, then divide by 8 and 12 rather than 4 and 6.

Thanks!

 

[Kaushik]

Question - Find the number of ways in which 6 gentlemen and 3 ladies can be seated around a table so that every gentleman may have a lady by his side.

I tried it using your approach.
Consider, GLGGLGGLG (G-> Gentleman L-> Lady)
1)The gentlemen can be seated in $6!$ ways.
2)The 3 ladies can sit in any of the 3 spots between the gentlemen in $3!$ ways.
3)The ladies and gentlemen can be switched.
4)They can be rotated in 9 ways which are all equivalent.
Hence, $\frac{(6!)(3!)(2)}{9}$
Is this correct? If not, where did I commit my mistake?

 

[Kaushik]

Question - Find the number of ways in which 6 gentlemen and 3 ladies can be seated around a table so that every gentleman may have a lady by his side.

I tried it using your approach.
Consider, GLGGLGGLG (G-> Gentleman L-> Lady)
1)The gentlemen can be seated in $6!$ ways.
2)The 3 ladies can sit in any of the 3 spots between the gentlemen in $3!$ ways.
3)The ladies and gentlemen can be switched.
4)They can be rotated in 9 ways which are all equivalent.
Hence, $\frac{(6!)(3!)(2)}{9}$
Is this correct? If not, where did I commit my mistake?

When I wrote it down, I noticed that they are equivalent 6 times and not 9. So it must be $\frac{(6!)(3!)(2)}{6}$. But am I supposed to write down everything and see or will I get used to it by time (problem solving).