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

[number0]

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.

 

[vela]

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?

 

[Gokul43201]

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?

 

[number0]

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?

 

[Gokul43201]

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?

 

[number0]

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.

 

[Gokul43201]

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?

 

[number0]

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?

 

[vela]

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?

 

[number0]

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;/

 

[vela]

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?

 

[number0]

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?

 

[Gokul43201]

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.

 

[vela]

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.