B Permutations and combinations

  • Thread starter Kaushik
  • Start date
130
10
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?
 
10,810
4,349
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.
 
130
10
Go to Khan Academy, they should have some good videos on it.
Thanks for your suggestion!
 

Klystron

Gold Member
469
504
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.
 
130
10
130
10
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!
 
10,810
4,349
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.
 
130
10
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?
 

fresh_42

Mentor
Insights Author
2018 Award
11,423
7,848
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

Science Advisor
Gold Member
2018 Award
5,048
1,773
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.
 
10,810
4,349
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

Gold Member
469
504
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.
 
130
10
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

Science Advisor
Gold Member
2018 Award
5,048
1,773
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

Science Advisor
Gold Member
2018 Award
5,048
1,773
I think I see what you are doing and I agree with your answer (if my assumptions are correct).
 
130
10
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 any one 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.
 
130
10
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

Science Advisor
Gold Member
2018 Award
5,048
1,773
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.
 
130
10
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

Science Advisor
Gold Member
2018 Award
5,048
1,773
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.
 
130
10
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

Science Advisor
Gold Member
2018 Award
5,048
1,773
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.
 
130
10
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.
 

Want to reply to this thread?

"Permutations and combinations" You must log in or register to reply here.

Related Threads for: Permutations and combinations

  • Posted
Replies
1
Views
3K
Replies
6
Views
20K
Replies
14
Views
8K
Replies
4
Views
746
Replies
3
Views
6K
  • Posted
Replies
5
Views
629
Replies
2
Views
2K

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top