Permutations and combinations

In summary, permutation and combination can be difficult to understand at first, but with time and practice, it becomes easier. It is a useful concept in estimating probabilities and number of ways things can be combined or ordered. Good sources for learning this topic include Khan Academy and various online videos. It's important to remember the difference between permutations and combinations, and there are various mnemonic devices that can aid in remembering this. The concept of combinatorics can be applied to many different areas, but it often involves counting and optimization techniques.
  • #1
Kaushik
282
17
TL;DR Summary
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?
 
Physics news on Phys.org
  • #2
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.
 
  • Informative
Likes Kaushik
  • #3
jedishrfu said:
Go to Khan Academy, they should have some good videos on it.
Thanks for your suggestion!
 
  • #4
jedishrfu said:
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##.
 
  • Like
Likes Kaushik
  • #5
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.
 
  • Like
Likes jedishrfu and Kaushik
  • #6
fresh_42 said:
At first? I still hate counting ... especially in all cases where it is not ##n!## or ##\binom n k##.
True!
 
  • #7
Klystron said:
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!
 
  • Like
Likes Klystron
  • #8
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.
 
  • Like
Likes Kaushik and Klystron
  • #9
Klystron said:
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?
 
  • #10
Kaushik said:
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.
 
  • Like
Likes Kaushik
  • #11
jedishrfu said:
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.
 
  • Like
Likes jedishrfu
  • #12
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.
 
  • Like
Likes Kaushik
  • #13
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.
 
  • #14
Kaushik said:
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.
 
  • Like
Likes Kaushik
  • #15
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?
 
  • #16
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.
 
  • Like
Likes Spinnor and Kaushik
  • #17
I think I see what you are doing and I agree with your answer (if my assumptions are correct).
 
  • Like
Likes Kaushik
  • #18
FactChecker said:
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.
FactChecker said:
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.
 
  • #19
FactChecker said:
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##
 
  • #20
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.
 
  • Like
Likes Kaushik
  • #21
FactChecker said:
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?
 
  • #22
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.
 
  • Like
Likes Kaushik
  • #23
Answer
  • Why do we use ##\binom{10}4## instead of ## 9!/6! ##?
  • If order matters here, why do we use combination instead of permutation?
 
  • #24
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.
 
  • Like
Likes Kaushik
  • #25
FactChecker said:
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
FactChecker said:
Does the exact seat matter, or only who people are sitting next to
No. All seats are identical.
FactChecker said:
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.
 
  • #26
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.
 
Last edited:
  • Informative
Likes Kaushik
  • #27
FactChecker said:
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!
 
  • #28
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?
 
  • #29
Kaushik said:
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).
 

What is the difference between permutations and combinations?

Permutations are arrangements of a set of objects in a specific order, while combinations are selections of objects from a set without regard to order.

How do you calculate the number of permutations?

The number of permutations of a set of n objects is given by n factorial (n!). This can be calculated by multiplying all the numbers from 1 to n.

What is the formula for calculating combinations?

The number of combinations of n objects taken r at a time is given by nCr = n! / (r!(n-r)!), where nCr is read as "n choose r".

What is the difference between with and without replacement in permutations and combinations?

With replacement means that an object can be chosen more than once, while without replacement means that an object can only be chosen once.

How are permutations and combinations used in real life?

Permutations and combinations are used in various fields such as mathematics, statistics, and computer science. In real life, they can be used to calculate the number of possible outcomes in a game or to determine the probability of an event occurring.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
703
  • Set Theory, Logic, Probability, Statistics
Replies
8
Views
723
  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
1K
  • Science and Math Textbooks
Replies
8
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
535
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
4K
  • Set Theory, Logic, Probability, Statistics
Replies
8
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
6
Views
1K
  • General Math
Replies
1
Views
685
Back
Top