How many permutations of group size n from group size k?

dci

New member
Joined
Jun 16, 2019
Messages
5
Greetings. As a past 50 year old adult, I'm now studying Python programming online for personal reward. Although this question is not directly related, in my study I stumbled upon code dealing with permutations and combinations. The following problem came to my mind spontaneously as I was taking a nice afternoon walk.

Question:
How many permutations or ways to pull a set (e.g. team) of size n from a group of elements (e.g. people) of size k.

Example #1: 3 people named A, B, C form permutations of a doubles tennis team.
AB, AC, BC makes 3 possible doubles team combinations.

Example #2: 4 people named A, B, C, D form permutations of a doubles tennis team.
AB, AC, AD, BC, BD, CD makes 6 possible doubles team combinations.

Example #3: 5 people named A, B, C, D, E form permutations of a three man basketball team.
ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, CDE makes 10 possible team combinations.

How to formulate an equation to describe this situation? And how to solve it?

(Reworded) How many permutations of group size n from group size k?

So if there was a much larger set of people numbered in the hundreds, and you wanted to pull out a group to form teams or something, how many combinations could be formed? What is the general formula for such things?

So far I can figure it out with small numbers by running through the actual combinations, but have limited math skills and yet don't know how to describe this sort of thing with math symbols and formulas. I know this has something to do with factorial.

For pulling out a group of two members (say, for a doubles tennis team) I came up with this:
Example #1 above: n=2, k=3 and the actual combinations is 3. Maybe that is k!/2 = 6/2 = 3. So maybe some kind of pattern...?
Example #2 above: n=2, k=4 and the actual combinations is 6. Maybe that is k!/4 = 24/4 = 6. But where does this denominator come from...?
Following this idea, for n=2, k=5 and the actual combinations is 10. Maybe that is k!/12 = 120/12 = 10. But where does 12 come from...?
Or maybe I'm way off base...
 

pka

Elite Member
Joined
Jan 29, 2005
Messages
8,319
I stumbled upon code dealing with permutations and combinations. The following problem came to my mind spontaneously as I was taking a nice afternoon walk.
Question: How many permutations or ways to pull a set (e.g. team) of size n from a group of elements (e.g. people) of size k.
Example #1: 3 people named A, B, C form permutations of a doubles tennis team.
AB, AC, BC makes 3 possible doubles team combinations.

Example #3: 5 people named A, B, C, D, E form permutations of a three man basketball team.
ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, CDE makes 10 possible team combinations.
The first task is for you to learn the difference in combinations & permutations.
For making a selection that involves content of the selection we use combinations: content\(\displaystyle \bf \Leftrightarrow \)combinations
Both your examples above require combinations. In those we are concerned with the content of the group.

Now if the selection involves order in any sense then the selecting process requires permutations: order\(\displaystyle \bf{\Leftrightarrow} \)permutations.
For example: How many can we elect four officers from a group of ten:\(\displaystyle 10\cdot 9 \cdot 8\cdot 7 \) ways Permutation.

There are tools on the web: SEE HERE. And also see here

Here are the formulae:
Combinations \(\displaystyle _N\mathcal{C}_k=\binom{N}{k}=\dfrac{N!}{k!\cdot(N-k)!} \)

Permutations \(\displaystyle _N\mathcal{P}_k=\dfrac{N!}{(N-k)!} \)
 

Dr.Peterson

Elite Member
Joined
Nov 12, 2017
Messages
4,125
So far I can figure it out with small numbers by running through the actual combinations, but have limited math skills and yet don't know how to describe this sort of thing with math symbols and formulas. I know this has something to do with factorial.

For pulling out a group of two members (say, for a doubles tennis team) I came up with this:
Example #1 above: n=2, k=3 and the actual combinations is 3. Maybe that is k!/2 = 6/2 = 3. So maybe some kind of pattern...?
Example #2 above: n=2, k=4 and the actual combinations is 6. Maybe that is k!/4 = 24/4 = 6. But where does this denominator come from...?
Following this idea, for n=2, k=5 and the actual combinations is 10. Maybe that is k!/12 = 120/12 = 10. But where does 12 come from...?
Or maybe I'm way off base...
To supplement what pka said, although you used the word "permutations" a lot, everything you described is a combination -- a selection of a set, without regard to order. You do need to start by studying the subject, somewhere like this. It's better to go through a careful explanation of a topic that gives you the necessary concepts and formulas, than to ask random questions -- though your personal investigation is a good start.

As for the pattern you see, you might observe that your denominators, 2, 4, 12, are 2!, 2!2!, and 2!3!.

But a better way to think of it (reasoning rather than guessing) is this: When you choose 2 of 5, you can first make permutations, which can be done in 5*4 ways (5 for the first choice, 4 for the second); that is 5!/3!, because it cancels the last three factors in 5!, leaving 5*4. But each combination corresponds to 2! of those permutations, so we have to divide by 2! to get the answer. The number of combinations is therefore 5!/(3!2!), which is the calculation you found worked.

Note, by the way, that we tend to habitually use n for the size of the set we select from, and k (or r) for the size of the subset we are choosing. That's why pka's formula reversed the letters from your usage.
 

dci

New member
Joined
Jun 16, 2019
Messages
5
pka, thanks for pointing out the difference between combinations and permutations. And thanks for the full formulae. I have much to ponder now.

Dr.Peterson, thanks for the website with easy to understand explanations about combinations and permutations. And your hint about "2, 4, 12, are 2!, 2!2!, and 2!3!" sparked my understanding of the pattern that was emerging from my attempts. Also, the conventional use of n, k (or r) helped me understand pka's formula (though I'm still faltering somewhat there...).

So the original question might be reworded:
How many combinations of subset size k from a set size n ?

I studied high school geometry and algebra, but never took classes in trigonometry or calculus. Several years ago I solved the Rubik's Cube without referring to available online instructions (although it took me several months). With my little tennis doubles team puzzle I knew that using online search and doing a deep dive, I could solve it, but that would be like doing the Rubik's Cube by following the instructions. I rather enjoyed my afternoon walks and trying to figure out the pattern of 2, 4, 12 and working through combinations with my fingers. I suppose this is how the mathematicians of thousands of years past got started before it was all codified formally (building on the "shoulders of giants" and all that).

The reason I finally found this forum and asked here is because one, I was stumped, and two, the actual problem I've been working on is larger and I arrived at the "tennis doubles team combinations" as a smaller part of the much larger question on my mind.

THE BIGGER QUESTION:
Take a normal permutations problem (now I know the right word!) like "how many permutations of students sitting in seats" where the order does matter would be just \(\displaystyle N!\) right? For example there are five seats and five children and what are all the permutations of sitting in those seats? \(\displaystyle 5! = 120\)
(Is this correct?)

But what if there where ten children and five where sitting in the chairs (where the order matters) but five were just milling about standing (where the order doesn't matter)? The problem is:
How many permutations of seat arrangements by choosing a combination of five children from the full group? Include all the children to make combinations with each making permutations of seating arrangements, but don't worry about the permutations of the kids standing about.

In my afternoon walks thinking about this problem (but didn't know the words "permutations and combinations") I arrived at the conclusion that first you figure out the combinations of say, five kids out of set of 10, then multiply that by the permutations of sitting in five chairs.

Now having seen the formulae presented by pka above, I think it might be something like:

\(\displaystyle nCk ⋅ nPk\)
(I mean the formulae associated with these but don't know how to type with LaTeX properly)

No that can't be right. Maybe:

\(\displaystyle nCk ⋅ k!\)

Yes, that seems correct to me. But then what does the formula for \(\displaystyle nPk\) capture?

(I'm thinking through this in real time. Sorry to bother you...)
So \(\displaystyle nPk\) is when you have a larger set n and you want the permutations of the subset k ? But that's my original question...! (The one about children above.)

So maybe \(\displaystyle nCk ⋅ k!\) is the same thing as \(\displaystyle nPk\) and I need to take the actual formulae and use algebra to multiply them together and see if it matches.

I'm starting to get a handle on this maybe but don't know how to use LaTeX to output the formulae I need to describe my thoughts. So I'll stop here... Help...!
 

Dr.Peterson

Elite Member
Joined
Nov 12, 2017
Messages
4,125
Trying to figure things out for yourself is great (until you try to ask questions about it and get the words wrong, so you can't communicate correctly!).

As I think of it (and as most, if not all, sites explaining it do), we start with permutations and derive combinations from them -- the reverse of what you seem to be trying. But your stream-of-consciousness did eventually get to what I'll explain next:

The number of permutations of 5 chosen from 10 is simply 10P5. [That notation is usually fine for typing; I often use P(10,5) to make it a little cleaner; and to use LaTeX, you can just put an underscore before all subscripts, _{10}P_5 (braces are needed around multi-character subscripts), and surround it with MATH or TEX markers using the calculator icon here: \(\displaystyle _{10}P_5\).]

And nPk is simply n(n-1)...(n-k+1), for a total of k factors, which is more neatly written as n!/(n-k)!. That's because there are n choices for the first item chosen, n-1 for the second, and so on for k choices.

The relationship to combinations (which I justified by my example last time) is that nPk = nCk * kPk, because for each of nCk combinations, there are kPk ways to arrange its elements in order. That's what you ended up with, since kPk = k!. From this, we derive the formula nCk = nPk/kPk = nPk/k! = n!/(k!(n-k)!).
 

dci

New member
Joined
Jun 16, 2019
Messages
5
Thanks again for the responses. I learned a lot.

pka gave me the answers to my query, with formulae, but I was not yet able to understand them.

Dr.Peterson helped nudge me along until I grasped the concepts, and lingo or math symbols, and then it really sunk in. Then when I read the mathisfun.com page on combinatorics it all made complete sense.

I'm glad I spent time just walking and thinking and trying to derive the answers to combinations/permutations problems on my own before turning to the world of formal math where all of these things have been considered and perfected over the millennia by mathematicians. Again, it's like solving the Rubik's Cube by deriving algorithms on your own without relying on other people's instructions. Although I didn't solve this one fully on my own, I feel if I'd spent several months on it (as I did to solve the Rubik's Cube) I would have slowly worked my way to a raw solution.

Isn't this how teachers best teach math, logic, or programming? Give the students a puzzle and slowly let them find the logic themselves and then nudge along and introduce the formal symbols and methods?

Thanks again,
dci
 

Dr.Peterson

Elite Member
Joined
Nov 12, 2017
Messages
4,125
I'm glad I spent time just walking and thinking and trying to derive the answers to combinations/permutations problems on my own before turning to the world of formal math where all of these things have been considered and perfected over the millennia by mathematicians. Again, it's like solving the Rubik's Cube by deriving algorithms on your own without relying on other people's instructions. Although I didn't solve this one fully on my own, I feel if I'd spent several months on it (as I did to solve the Rubik's Cube) I would have slowly worked my way to a raw solution.

Isn't this how teachers best teach math, logic, or programming? Give the students a puzzle and slowly let them find the logic themselves and then nudge along and introduce the formal symbols and methods?
Yes, definitely. As I suggested, the only real downside is that in working out something like this on your own, you risk getting the terminology wrong (or just inventing your own, which will be incomprehensible when you come out of your cave and start discussing it). But you might even end up with some ideas better than those we teach.

By the way, I never solved the Rubik's cube, but my twin brother did. That doesn't count, does it?
 

dci

New member
Joined
Jun 16, 2019
Messages
5
Sometime being in the cave can be pure joy intellectually!

Thou shalt go thee forth and purchase a Rubik's Cube on Amazon and sit in thy cave alone and speaketh thee to no one until thy solution be there brought forth upon thee.
😜
 

LCKurtz

Junior Member
Joined
May 3, 2019
Messages
70
Pretty good for a human.
But robots are faster:
 

ksdhart2

Senior Member
Joined
Mar 25, 2016
Messages
1,148
When I was five years old, I "solved" a Rubik's Cube by removing all the colored stickers. The goal is to make all the squares on each side the same color... so if every square is white then it's always solved, right?
 

dci

New member
Joined
Jun 16, 2019
Messages
5
LCKurtz, that's amesome!

ksdhart2, at least you did it yourself!
 
Top