Math Is Fun Forum

doraeyee_u_v

Member

Registered: 2006-05-02

Posts: 13

series

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?

yttrium88

Member

Registered: 2005-12-01

Posts: 20

Re: series

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!

doraeyee_u_v

Member

Registered: 2006-05-02

Posts: 13

Re: series

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

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: series

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..."

doraeyee_u_v

Member

Registered: 2006-05-02

Posts: 13

Re: series

what is sup and inf?

krassi_holmz

Real Member

Registered: 2005-12-02

Posts: 1,905

Re: series

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.

krassi_holmz

Real Member

Registered: 2005-12-02

Posts: 1,905

Re: series

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.

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: series

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..."

krassi_holmz

Real Member

Registered: 2005-12-02

Posts: 1,905

Re: series

No. You was right without being wrong.

---

IPBLE:  Increasing Performance By Lowering Expectations.