• Support PF! Buy your school textbooks, materials and every day products Here!

Proving that k! is the number of ways we can order k items

  • Thread starter number0
  • Start date
  • #1
104
0

Homework Statement



How do you prove that k! is the number of ways we can order k items?


Homework Equations





The Attempt at a Solution



I tried mathematical induction... but I keep getting stuck on how to show that (k + 1)! is the

number of ways we can order (k +1) items?

Can anyone help? Thanks.
 

Answers and Replies

  • #2
vela
Staff Emeritus
Science Advisor
Homework Helper
Education Advisor
14,632
1,268
This might not be rigorous enough but it may be enough for you to get started:

Take 1 item. How many ways can you place it into k+1 slots? Now by the induction hypothesis, how many ways can you fill the remaining k slots with the remaining k items?
 
  • #3
Gokul43201
Staff Emeritus
Science Advisor
Gold Member
7,051
17
I tried mathematical induction... but I keep getting stuck on how to show that (k + 1)! is the

number of ways we can order (k +1) items?

Can anyone help? Thanks.
So you have k objects that you can "line up" in (k!) different ways. Now add one more object to the collection. What are the different ways in which you can position this new object among the existing line of k objects?
 
  • #4
104
0
Both you guys gave me good help, but I am still stuck.

This is what I got so far...

1) There is k+1 ways to place it into k slots.

How am I suppose to use the inductive hypothesis?
 
  • #5
Gokul43201
Staff Emeritus
Science Advisor
Gold Member
7,051
17
Both you guys gave me good help, but I am still stuck.

This is what I got so far...

1) There is k+1 ways to place it into k slots.

How am I suppose to use the inductive hypothesis?
It's not clear what the "it" is that you refer to above, or which step of the inductive process you are at.

I suggest you wipe the slate clean and start at the beginning.

What's the first step in a proof by induction?
 
  • #6
104
0
It's not clear what the "it" is that you refer to above, or which step of the inductive process you are at.

I suggest you wipe the slate clean and start at the beginning.

What's the first step in a proof by induction?
By it, I am referring to k+1. So there is k+1 ways to place k+1 into a set that contains k elements.
 
  • #7
Gokul43201
Staff Emeritus
Science Advisor
Gold Member
7,051
17
By it, I am referring to k+1.
By "k+1", do you mean "the (k+1)th object"?

If so, you are correct, but can you explain more clearly how there are k+1 ways to position this object?
 
  • #8
104
0
By "k=1", do you mean "the (k+1)th object"?

If so, you are correct, but can you explain more clearly how there are k+1 ways to position this object?
Well... take k = 3 for example. So k + 1 = 4. Then:

1 2 3 4
1 2 4 3
1 4 2 3
4 1 2 3

. Thus there are four ways?
 
  • #9
vela
Staff Emeritus
Science Advisor
Homework Helper
Education Advisor
14,632
1,268
Say the (k+1)th object is in the first spot. How many ways are there to arrange objects 1 through k in the remaining spots?
 
  • #10
104
0
Say the (k+1)th object is in the first spot. How many ways are there to arrange objects 1 through k in the remaining spots?
Oh! k times. Then the logic proof can goes as follows:

since k + 1 can be placed in k amount of positions, we can use the inductive hypothesis to multiply k + 1 by k! to get (k + 1)! ?

I am not sure about it;/
 
  • #11
vela
Staff Emeritus
Science Advisor
Homework Helper
Education Advisor
14,632
1,268
What you wrote has numerous mistakes, but I suspect it may just be you being sloppy. For example, you said "k + 1 can be placed in k amount of positions," yet in your previous post, you argued that the (k+1)-th item can go into k+1 spots. Can you clarify exactly what you're thinking?
 
  • #12
104
0
What you wrote has numerous mistakes, but I suspect it may just be you being sloppy. For example, you said "k + 1 can be placed in k amount of positions," yet in your previous post, you argued that the (k+1)-th item can go into k+1 spots. Can you clarify exactly what you're thinking?
Okay I reread my post and it was sloppy. This is what it was suppose to mean:

If we insert a k+1 element into the set, then there will be k + 1 amount of ways to position k + 1. From the inductive hypothesis, we can multiply k + 1 ways by k! to get (k + 1)! ways of arranging a set.

Is this almost right?
 
Last edited:
  • #13
Gokul43201
Staff Emeritus
Science Advisor
Gold Member
7,051
17
Say the (k+1)th object is in the first spot. How many ways are there to arrange objects 1 through k in the remaining spots?
This is no longer a proof by induction, is it?

I'm going to step out of this thread - don't want this to become a case of too many cooks.

But before I leave, I should perhaps add that the discussion in post #8 is on the right track. All you (number0) need to do is make that argument using general terms, rather than a specific example. And then you are one step away from completing the proof by induction.
 
Last edited:
  • #14
vela
Staff Emeritus
Science Advisor
Homework Helper
Education Advisor
14,632
1,268
Okay I reread my post and it was sloppy. This is what it was suppose to mean:

If we insert a k+1 element into the set, then there will be k + 1 amount of ways to position k + 1. From the inductive hypothesis, we can multiply k + 1 ways by k! to get (k + 1)! ways of arranging a set.

Is this almost right?
Yup, that's the idea. You just have to fill in the rest of the pieces of a proof by induction.
This is not a proof by induction, is it?
Well, it's an element of the proof. The induction hypothesis allows you to assume there are k! ways to arrange the k remaining elements.
I'm going to step out of this thread - don't want this to become a case of too many cooks.
I don't think it's necessary for you to stop posting here. It would be one thing if we were proposing two completely different ways to solve this, but we're essentially saying the same things.
 

Related Threads on Proving that k! is the number of ways we can order k items

Replies
1
Views
1K
Replies
5
Views
526
Replies
4
Views
2K
Replies
6
Views
1K
  • Last Post
Replies
3
Views
1K
Replies
2
Views
485
Top