You are not logged in.

- Topics: Active | Unanswered

**doraeyee_u_v****Member**- Registered: 2006-05-02
- Posts: 13

The integers 1,2,...,n are arranged in order a1,a2,...an, so that each term ak is either larger than all aj with j<k or else it is smaller than all aj with j<k. For example, the order 3,2,4,1 satisfies these conditions for n=4.

In how many different way can this be done?

Offline

**yttrium88****Member**- Registered: 2005-12-01
- Posts: 20

It seems like, if you have your n integers arranged in a row, you will have to choose some starting number, and then pick a number that borders on it for the second number in the series. Then pick a number than is a neigbor on the side of that group. It just continues to build up on the original number picked, like a one-dimesional pearl building on a piece of sand. How's that for a math metaphore!

Offline

**doraeyee_u_v****Member**- Registered: 2006-05-02
- Posts: 13

can anyone else be able to find out the pattern of this series is please?

Offline

**Ricky****Moderator**- Registered: 2005-12-04
- Posts: 3,791

Let A be the set of numbers already in the sequence. Let s be the sup of A, and i be the inf of A. Then the next number in the sequence must be either i-1 or s+1. So it would seem to be 2^n. But there lies a problem with your starting number. If you pick say 2 as your first number, and then 1, there is only one way to place the rest of the numbers, no matter what size n.

How to put this into an equation, I'm not sure. I'll have to think about it some more.

"In the real world, this would be a problem. But in mathematics, we can just define a place where this problem doesn't exist. So we'll go ahead and do that now..."

Offline

**doraeyee_u_v****Member**- Registered: 2006-05-02
- Posts: 13

what is sup and inf?

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,905

s is sup of A if s>all members of A.

s is inf of A if s<all members of A.

Very interesting question.

I've founded a function, but I just don't have time to post a proof.

The first function is the number of sequances with length n and starting number k:

Then the number we're looking for is:

Good. Now just have to simplify it...

Ha-ha-haaaa!!!

*Last edited by krassi_holmz (2006-05-14 13:21:50)*

IPBLE: Increasing Performance By Lowering Expectations.

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,905

G(1)=1;

G(2)=2;

12

21

G(3)=4;

123

213

231

321

G(4)=8

1234;

2134;

2314;

2341;

3214;

3241;

3421;

4321;

G(n) = 2^n!!!

Now we just have to prove it by induction.

IPBLE: Increasing Performance By Lowering Expectations.

Offline

**Ricky****Moderator**- Registered: 2005-12-04
- Posts: 3,791

So I was right! Even though I thought I was wrong...

"In the real world, this would be a problem. But in mathematics, we can just define a place where this problem doesn't exist. So we'll go ahead and do that now..."

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,905

No. You was right without being wrong.

IPBLE: Increasing Performance By Lowering Expectations.

Offline