How many ways to rearrange distinct objects (factorial)

[zeion]

Homework Statement

Hello.
This is the gist of the question:

I have 0 < k < n and I need a formula to show the number of sets of exactly k integers, each chosen from 1, ... , n.

Homework Equations

n! is the number of distinct ways to rearrange n objects into n slots.

The Attempt at a Solution

Basically I need to fit n different objects into k slots. So there are more objects to choose from than slots. So the number of distinct ways to fit n objects into k slots is given by n(n-1) ... (n-k+1).

The solution says I have to divide by k! but I don't understand why.

 

[tiny-tim]

hi zeion!

suppose you want the number of ways of choosing three letters from the 7 letters A B C D E F G …

you're saying there's 7 ways of choosing the first one, 6 of the second, then 5 of the third, total 7*6*5

but for example your 7*6*5 ways include ABC BCA CAB CBA BAC and ACB, which are all the same choice …

so you have to divide by the number of ways of arranging k items, ie k!, to give the famous binomial formula n!/k!(n-k)!

 

[zeion]

This is very confusing..
Why does k! equal the number of ways that are repeated?

 

[tiny-tim]

hi zeion!

(just got up :zzz: …)

because if for example k = 5, then one of the sets is ABCDE

but your method gives ACBDE ADBCE etc also, and that would be multiple-counting (counting the same set over and over again)

so you have to divide by the number of ways of rearranging ABCDE …

that's 5 ways for the first letter, 4 for the second, etc, = 5!

 

[HallsofIvy]

This is very confusing..
Why does k! equal the number of ways that are repeated?

You need to know the "fundamental principle of counting":
If there are m way one thing can happen and n ways another thing can happen (and they happen "independently") there there are mn (m times n) ways both can happen.

For example, if I have 4 shirts and 3 pairs of pants, there are 3(4)= 12 ways to choose one shirt and one pair of pants to wear ("independently" here meaning no shirt does clashes with any of the pants!).

If I have to choose one letter from A, B, C to write and one letter from P, Q to follow it, there are 3(2)= 6 ways: AP, AQ, BP, BQ, CP, and CQ.

If I have to write all 5 letters A, B, C, D, E, in some order, there are 5 letters to choose to go first. After I have chosen that, there are 4 letters left so there are 4 choices. That means there are 5(4)= 20 choices for the first two letters. After I have chosen those, there are 3 letters left to pick for the third letter. There are 3 ways of doing that so there are 5(4)(3)= (20)(3)= 60 ways of choosing the first 3 letters. That leaves 2 choices for the
fourth letters so 5(4)(3)(2)= (60)(2)= 120 choices for the first four letters. Finally, there is only one letter to "pick" for the fifth letter so there are 5(4)(3)(2)(1)= 5!= 120 ways to order five letters (or five of anything).

Frankly, I am amazed that you were given a problem like this with first having learned that "the number of ways to arrange n distinct things is n!".

 

[Outlined]

the answer is
$$n \choose k$$

should be in your book.

 

[zeion]

the answer is
$$n \choose k$$

should be in your book.

Thanks that was so helpful.