Interesting sequences (Catalan, maybe?)

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
joshz
Posts: 1466
Joined: Tue Nov 11, 2008 2:51 am UTC
Location: Pittsburgh, PA

Interesting sequences (Catalan, maybe?)

Postby joshz » Tue Jan 27, 2009 9:47 pm UTC

For my math class, I have to find an "interesting" sequence to do a project on. It can't be too well-known, because my math teacher wants people to learn about new sequences. (so that probably means no Fibonacci, Collatz, etc.)

Does anyone know of any sequences that would be interesting for me to research?

Thanks!
Last edited by joshz on Fri Jan 30, 2009 12:30 am UTC, edited 1 time in total.
You, sir, name? wrote:If you have over 26 levels of nesting, you've got bigger problems ... than variable naming.
suffer-cait wrote:it might also be interesting to note here that i don't like 5 fingers. they feel too bulky.

User avatar
A_of_s_t
Posts: 180
Joined: Tue Aug 26, 2008 5:10 am UTC
Contact:

Re: Interesting sequences

Postby A_of_s_t » Tue Jan 27, 2009 9:54 pm UTC

Use an infinite series to find the area under a curve. That's always fun.

EDIT: Actually, that's called a Reimann sum and is well known IIRC.
Check out my web interzones powered by Web 3.0 technology running on Mozzarella Foxfire:
Spoiler:
Image
Image
Image

User avatar
joshz
Posts: 1466
Joined: Tue Nov 11, 2008 2:51 am UTC
Location: Pittsburgh, PA

Re: Interesting sequences

Postby joshz » Tue Jan 27, 2009 9:57 pm UTC

Well, that's not really a sequence, just a way of analyzing sequences.
You, sir, name? wrote:If you have over 26 levels of nesting, you've got bigger problems ... than variable naming.
suffer-cait wrote:it might also be interesting to note here that i don't like 5 fingers. they feel too bulky.

User avatar
A_of_s_t
Posts: 180
Joined: Tue Aug 26, 2008 5:10 am UTC
Contact:

Re: Interesting sequences

Postby A_of_s_t » Tue Jan 27, 2009 9:59 pm UTC

My mistake, I got series and sequences mixed up -- a noob mistake.
Check out my web interzones powered by Web 3.0 technology running on Mozzarella Foxfire:
Spoiler:
Image
Image
Image

User avatar
Cleverbeans
Posts: 1378
Joined: Wed Mar 26, 2008 1:16 pm UTC

Re: Interesting sequences

Postby Cleverbeans » Tue Jan 27, 2009 10:02 pm UTC

Are there any restrictions on the sequences like they must be integers or real valued? Are you allowed to study a class of sequences or does it have to be a specific sequence?
"Labor is prior to, and independent of, capital. Capital is only the fruit of labor, and could never have existed if labor had not first existed. Labor is the superior of capital, and deserves much the higher consideration." - Abraham Lincoln

User avatar
joshz
Posts: 1466
Joined: Tue Nov 11, 2008 2:51 am UTC
Location: Pittsburgh, PA

Re: Interesting sequences

Postby joshz » Tue Jan 27, 2009 10:03 pm UTC

Cleverbeans wrote:Are there any restrictions on the sequences like they must be integers or real valued?
Not AFAIK--just a sequence.
Are you allowed to study a class of sequences or does it have to be a specific sequence?
I *think* a specific sequence-it's a fairly small project. 1/2 a poster board and a 3-4 slide powerpoint.
You, sir, name? wrote:If you have over 26 levels of nesting, you've got bigger problems ... than variable naming.
suffer-cait wrote:it might also be interesting to note here that i don't like 5 fingers. they feel too bulky.

User avatar
rhino
Posts: 123
Joined: Fri Dec 08, 2006 3:43 pm UTC
Location: Cambridge, UK

Re: Interesting sequences

Postby rhino » Tue Jan 27, 2009 10:18 pm UTC

It's very well-known, but you could look at the sequence.
1, 1/4, 1/9, 1/16, 1/25, ...
And show that it sums to pi2/6

There is loads of history behind this problem so there's plenty to discuss that's of interest to a casual audience.
In my opinion, the nicest proof of this uses Fourier analysis, but there's a risk that this is either too simple (if you're at university) or too hard (if you're at school).
There is also a pretty but "informal" derivation of the result by Euler which is more elementary here
Wiki also has a formal proof of the result which is between the two arguments above in terms of the machinery required.

As an alternative, you could rattle off a proof that 1/2, 1/4, 1/8, 1/16, ... sums to 1
And then abuse the same proof to "show" that 1, 2, 4, 8, 16, 32, 64, ... "sums" to -1
Which could serve as a preamble to some discussion of p-adic numbers

Edit: typos
Last edited by rhino on Tue Jan 27, 2009 11:16 pm UTC, edited 1 time in total.

User avatar
joshz
Posts: 1466
Joined: Tue Nov 11, 2008 2:51 am UTC
Location: Pittsburgh, PA

Re: Interesting sequences

Postby joshz » Tue Jan 27, 2009 10:23 pm UTC

I like it, but I think the math is too complicated (high school sophomore, advanced class), and there's not enough I can do with it--just that proof, which probably isn't that interesting to average people.
You, sir, name? wrote:If you have over 26 levels of nesting, you've got bigger problems ... than variable naming.
suffer-cait wrote:it might also be interesting to note here that i don't like 5 fingers. they feel too bulky.

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Interesting sequences

Postby jestingrabbit » Wed Jan 28, 2009 12:09 am UTC

You could do something with Grandi's series,

http://en.wikipedia.org/wiki/Grandi%27s_series

use it to illustrate that mathematicians can come at the same question from very different angles ie you can say that if s= 1-1+1-1+1... then 1-s=s, so s=1/2, but the sequence of partial sums isn't Cauchy, but it is Cesaro summable.

But its not very sequencey.
Last edited by jestingrabbit on Wed Jan 28, 2009 12:18 am UTC, edited 1 time in total.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

User avatar
joshz
Posts: 1466
Joined: Tue Nov 11, 2008 2:51 am UTC
Location: Pittsburgh, PA

Re: Interesting sequences

Postby joshz » Wed Jan 28, 2009 12:16 am UTC

Interesting, but I'm not sure I would be able to squeeze enough out of it for it to work well.
Spoiler:
Image
You, sir, name? wrote:If you have over 26 levels of nesting, you've got bigger problems ... than variable naming.
suffer-cait wrote:it might also be interesting to note here that i don't like 5 fingers. they feel too bulky.

User avatar
joshz
Posts: 1466
Joined: Tue Nov 11, 2008 2:51 am UTC
Location: Pittsburgh, PA

Re: Interesting sequences

Postby joshz » Wed Jan 28, 2009 1:29 am UTC

Do you think Pascal's triangle would count as a sequence?
You, sir, name? wrote:If you have over 26 levels of nesting, you've got bigger problems ... than variable naming.
suffer-cait wrote:it might also be interesting to note here that i don't like 5 fingers. they feel too bulky.

Buttons
Posts: 858
Joined: Wed May 02, 2007 3:27 pm UTC
Location: Somerville

Re: Interesting sequences

Postby Buttons » Wed Jan 28, 2009 2:13 am UTC

The Catalan numbers are probably a good choice.

If that's too simple, perhaps the Robbins numbers: 1, 1, 2, 7, 42, 429, 7436,.... These are known to count a few different families of objects (like alternating sign matrices or totally symmetric self-complementary plane partitions), but no bijections are known between these families. They're relatively new (~30 years old), and I'm sure your teacher hasn't heard of them. They also allow for lots of pretty pictures, especially the plane partitions and fully packed loop configurations.

In general, this is probably a good resource.

User avatar
joshz
Posts: 1466
Joined: Tue Nov 11, 2008 2:51 am UTC
Location: Pittsburgh, PA

Re: Interesting sequences

Postby joshz » Wed Jan 28, 2009 2:20 am UTC

I think you're thinking a bit too complicated. I'm a high school sophomore, remember. :D

I think I'll go with Pascal's triangle, and see if he likes it.
You, sir, name? wrote:If you have over 26 levels of nesting, you've got bigger problems ... than variable naming.
suffer-cait wrote:it might also be interesting to note here that i don't like 5 fingers. they feel too bulky.

User avatar
t0rajir0u
Posts: 1178
Joined: Wed Apr 16, 2008 12:52 am UTC
Location: Cambridge, MA
Contact:

Re: Interesting sequences

Postby t0rajir0u » Wed Jan 28, 2009 2:53 am UTC

Here are some sequences with fairly elementary definitions that are generally not studied at the high school level:

- The Bell numbers.
- Derangements.
- The Stirling numbers (although technically this is not a sequence).
- The Morse-Thue sequence.
- The Beatty sequence associated to the golden ratio [imath]\frac{1 + \sqrt{5}}{2}[/imath]. It has the pretty cool property that [imath]a_n[/imath] is the smallest number that hasn't appeared either as part of the sequence or as one of the values of [imath]a_k + k, k < n[/imath].
- The sequence of numbers whose base-3 expansion contains no 2s. It has the pretty cool property that no three values form an arithmetic sequence. (Write out a few terms in base 10; it's not at all obvious that this is the case.)

The Catalan numbers are a good suggestion, though.

Buttons
Posts: 858
Joined: Wed May 02, 2007 3:27 pm UTC
Location: Somerville

Re: Interesting sequences

Postby Buttons » Wed Jan 28, 2009 2:58 am UTC

Pascal's Triangle isn't really a "sequence", though. Plus, your teacher has certainly heard of it.

User avatar
qinwamascot
Posts: 688
Joined: Sat Oct 04, 2008 8:50 am UTC
Location: Oklahoma, U.S.A.

Re: Interesting sequences

Postby qinwamascot » Wed Jan 28, 2009 8:31 am UTC

If you just browse through the OEIS, you'll eventually come to something you can understand, but isn't too basic. I watched a 2.5 hour talk on the square triangular numbers, so there's plenty you could do with those. Continued fractions could also be used, but they're not a single sequence per se, but a method of representing every real number as a sequence of integers that can be truncated for an approximation of that number.
Quiznos>Subway

User avatar
joshz
Posts: 1466
Joined: Tue Nov 11, 2008 2:51 am UTC
Location: Pittsburgh, PA

Re: Interesting sequences

Postby joshz » Thu Jan 29, 2009 12:31 am UTC

I kind of like the square triangular number idea, but are there any applications?
I *think* that may be kind of along the lines of what he meant by "interesting." (ie. fibonacci series shows up in nature)

btw, I agree with your sig, qinwamascot.
You, sir, name? wrote:If you have over 26 levels of nesting, you've got bigger problems ... than variable naming.
suffer-cait wrote:it might also be interesting to note here that i don't like 5 fingers. they feel too bulky.

Ended
Posts: 1459
Joined: Fri Apr 20, 2007 3:27 pm UTC
Location: The Tower of Flints. (Also known as: England.)

Re: Interesting sequences

Postby Ended » Thu Jan 29, 2009 1:00 am UTC

Another idea: this sequence, i.e. xn+1 = cos(xn). (More precisely, the set of such sequences indexed by the starting value x0). It has an interesting tale of 'discovery' (Prof. Dottie, plus most people have probably done the 'hitting cos(x) over and over again' thing), and at least one nice property (converges to the same x for any x0). It might be interesting to look at the related sequences xn+1 = C*cos(xn), and investigate convergence for different values of {x0, C}.

Not many applications, though.
Generally I try to make myself do things I instinctively avoid, in case they are awesome.
-dubsola

User avatar
joshz
Posts: 1466
Joined: Tue Nov 11, 2008 2:51 am UTC
Location: Pittsburgh, PA

Re: Interesting sequences

Postby joshz » Thu Jan 29, 2009 1:03 am UTC

That's not really a sequence, though, is it? Isn't it just really the one number that's important in that?
You, sir, name? wrote:If you have over 26 levels of nesting, you've got bigger problems ... than variable naming.
suffer-cait wrote:it might also be interesting to note here that i don't like 5 fingers. they feel too bulky.

Ended
Posts: 1459
Joined: Fri Apr 20, 2007 3:27 pm UTC
Location: The Tower of Flints. (Also known as: England.)

Re: Interesting sequences

Postby Ended » Thu Jan 29, 2009 1:08 am UTC

Yes, I suppose it's only really the limit which is interesting. But it's a perfectly valid sequence: xn = cos(n)(x0).
Generally I try to make myself do things I instinctively avoid, in case they are awesome.
-dubsola

User avatar
joshz
Posts: 1466
Joined: Tue Nov 11, 2008 2:51 am UTC
Location: Pittsburgh, PA

Re: Interesting sequences

Postby joshz » Thu Jan 29, 2009 1:11 am UTC

Yeah, but what can I do with it/about it for a project?

Re: triangular square numbers: any applications? or any webpages on it that go into more detail than the first couple google hits?
You, sir, name? wrote:If you have over 26 levels of nesting, you've got bigger problems ... than variable naming.
suffer-cait wrote:it might also be interesting to note here that i don't like 5 fingers. they feel too bulky.

User avatar
doogly
Dr. The Juggernaut of Touching Himself
Posts: 5532
Joined: Mon Oct 23, 2006 2:31 am UTC
Location: Lexington, MA
Contact:

Re: Interesting sequences

Postby doogly » Thu Jan 29, 2009 1:17 am UTC

Buttons wrote:The Catalan numbers are probably a good choice.


Agreed!
LE4dGOLEM: What's a Doug?
Noc: A larval Doogly. They grow the tail and stinger upon reaching adulthood.

Keep waggling your butt brows Brothers.
Or; Is that your eye butthairs?

User avatar
joshz
Posts: 1466
Joined: Tue Nov 11, 2008 2:51 am UTC
Location: Pittsburgh, PA

Re: Interesting sequences

Postby joshz » Thu Jan 29, 2009 1:29 am UTC

Looking at those more, they seem pretty good (the Catalans). I at first didn't like them because the wiki about them was bad, but they seem pretty interesting.

Thanks everyone!

(Also, dèja vu for some reason. Odd.)
You, sir, name? wrote:If you have over 26 levels of nesting, you've got bigger problems ... than variable naming.
suffer-cait wrote:it might also be interesting to note here that i don't like 5 fingers. they feel too bulky.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26767
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Interesting sequences

Postby gmalivuk » Thu Jan 29, 2009 2:48 am UTC

Yeah, while the Catalan numbers may be fairly commonly encountered in math in general, probably not so much in high school. (I first encountered them in college, for example, despite having taken a few college-level classes while still in high school.)
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
PM 2Ring
Posts: 3713
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

Re: Interesting sequences

Postby PM 2Ring » Thu Jan 29, 2009 5:06 pm UTC

I second t0rajir0u's nomination of derangements. The concepts are fairly easy to explain, and you can show the connection between the total number of permutations of n items (= n!) and number of derangements (= !n) and their relationship with e.

I also like his idea of Beatty sequences, and not just the ones for phi.* It's not too hard to show some interesting properties of these sequences using basic algebra & the definition of an irrational.


* But I will agree these are a pretty pair of sequences. :)

User avatar
joshz
Posts: 1466
Joined: Tue Nov 11, 2008 2:51 am UTC
Location: Pittsburgh, PA

Re: Interesting sequences

Postby joshz » Thu Jan 29, 2009 8:50 pm UTC

Yeah, my teacher said the Catalans are too advanced.

Does anyone have anything else about triangular square numbers?
You, sir, name? wrote:If you have over 26 levels of nesting, you've got bigger problems ... than variable naming.
suffer-cait wrote:it might also be interesting to note here that i don't like 5 fingers. they feel too bulky.

Buttons
Posts: 858
Joined: Wed May 02, 2007 3:27 pm UTC
Location: Somerville

Re: Interesting sequences

Postby Buttons » Thu Jan 29, 2009 9:23 pm UTC

joshz wrote:Yeah, my teacher said the Catalans are too advanced.

Does anyone have anything else about triangular square numbers?

Seriously? I've taught fifth graders about the Catalans, but I can't imagine doing the same for triangular squares.

(On a side note, since when is it the job of the teacher to tell the student when something is too advanced for them? Especially when it isn't.)

User avatar
joshz
Posts: 1466
Joined: Tue Nov 11, 2008 2:51 am UTC
Location: Pittsburgh, PA

Re: Interesting sequences

Postby joshz » Thu Jan 29, 2009 9:36 pm UTC

Maybe it was just the page I brought in, but he said I was "jumping into the deep end."
Also, really? These Catalan numbers?
You, sir, name? wrote:If you have over 26 levels of nesting, you've got bigger problems ... than variable naming.
suffer-cait wrote:it might also be interesting to note here that i don't like 5 fingers. they feel too bulky.

User avatar
t0rajir0u
Posts: 1178
Joined: Wed Apr 16, 2008 12:52 am UTC
Location: Cambridge, MA
Contact:

Re: Interesting sequences

Postby t0rajir0u » Thu Jan 29, 2009 10:14 pm UTC

There are some pretty simple ways to understand the Catalan numbers: parenthesized expressions, binary trees, Dyck paths... these are all defined in a fairly elementary way and one can grasp immediately what these structures look like.

Understanding the triangular squares, on the other hand, requires a knowledge of the methods for solving Pell's equations, which is much harder. (It's not to say that there aren't hard things you can do with the Catalan numbers - they are very deep - but you can start simple and stay there if you like.)

User avatar
joshz
Posts: 1466
Joined: Tue Nov 11, 2008 2:51 am UTC
Location: Pittsburgh, PA

Re: Interesting sequences

Postby joshz » Fri Jan 30, 2009 12:07 am UTC

Do you have any links for that?
Because most of the stuff I can find is kinda complicated.

Otherwise, I'll probably need something else.

/me thinks I should be able to find something easier than this. My google-fu sucks.
You, sir, name? wrote:If you have over 26 levels of nesting, you've got bigger problems ... than variable naming.
suffer-cait wrote:it might also be interesting to note here that i don't like 5 fingers. they feel too bulky.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26767
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Interesting sequences

Postby gmalivuk » Fri Jan 30, 2009 12:22 am UTC

I first encountered the sequence working with Dyck paths. Which you can totally talk about without having to name them that.

The MathWorld entry on Catalan numbers has a few graphical representations of other times they pop up.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
joshz
Posts: 1466
Joined: Tue Nov 11, 2008 2:51 am UTC
Location: Pittsburgh, PA

Re: Interesting sequences

Postby joshz » Fri Jan 30, 2009 12:29 am UTC

I think that definitely gives me a place to start with that, without getting too complicated.

So far I have:
http://mathworld.wolfram.com/DyckPath.html
http://mathforum.org/advanced/robertd/catalan.html
http://mathworld.wolfram.com/CatalanNumber.html
http://74.125.47.132/search?q=cache:6om ... ent=safari

Is there anything else pertinent I could look at about them?
You, sir, name? wrote:If you have over 26 levels of nesting, you've got bigger problems ... than variable naming.
suffer-cait wrote:it might also be interesting to note here that i don't like 5 fingers. they feel too bulky.

samspotting
Posts: 36
Joined: Tue Aug 05, 2008 2:26 pm UTC

Re: Interesting sequences (Catalan, maybe?)

Postby samspotting » Sat Jan 31, 2009 6:09 pm UTC

Generating functions from geometric sequence.

User avatar
t0rajir0u
Posts: 1178
Joined: Wed Apr 16, 2008 12:52 am UTC
Location: Cambridge, MA
Contact:

Re: Interesting sequences (Catalan, maybe?)

Postby t0rajir0u » Sat Jan 31, 2009 10:31 pm UTC

Describing the generating function of the Catalan numbers is highly nontrivial (for this audience), so that's probably a bad idea.

User avatar
joshz
Posts: 1466
Joined: Tue Nov 11, 2008 2:51 am UTC
Location: Pittsburgh, PA

Re: Interesting sequences (Catalan, maybe?)

Postby joshz » Sat Jan 31, 2009 10:37 pm UTC

t0rajir0u wrote:Describing the generating function of the Catalan numbers is highly nontrivial (for this audience), so that's probably a bad idea.
What do you mean?
Image
Makes perfect sense to me. And besides, I'll probably spend more time on applications than on the equation itself.
You, sir, name? wrote:If you have over 26 levels of nesting, you've got bigger problems ... than variable naming.
suffer-cait wrote:it might also be interesting to note here that i don't like 5 fingers. they feel too bulky.

Buttons
Posts: 858
Joined: Wed May 02, 2007 3:27 pm UTC
Location: Somerville

Re: Interesting sequences (Catalan, maybe?)

Postby Buttons » Sat Jan 31, 2009 11:09 pm UTC

That's a closed-form expression, not a generating function.

User avatar
joshz
Posts: 1466
Joined: Tue Nov 11, 2008 2:51 am UTC
Location: Pittsburgh, PA

Re: Interesting sequences (Catalan, maybe?)

Postby joshz » Sat Jan 31, 2009 11:32 pm UTC

Okay?

OH! You were replying to samspotting. That makes more sense.
You, sir, name? wrote:If you have over 26 levels of nesting, you've got bigger problems ... than variable naming.
suffer-cait wrote:it might also be interesting to note here that i don't like 5 fingers. they feel too bulky.

User avatar
Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:

Re: Interesting sequences (Catalan, maybe?)

Postby Cosmologicon » Sun Feb 01, 2009 12:14 am UTC

joshz wrote:
t0rajir0u wrote:Describing the generating function of the Catalan numbers is highly nontrivial (for this audience), so that's probably a bad idea.
What do you mean?
Image
Makes perfect sense to me.

That's a closed-form expression, not a generating function, joshz.

User avatar
joshz
Posts: 1466
Joined: Tue Nov 11, 2008 2:51 am UTC
Location: Pittsburgh, PA

Re: Interesting sequences (Catalan, maybe?)

Postby joshz » Sun Feb 01, 2009 12:15 am UTC

Right, but why do I need a generating function?

(And also, I don't really know the difference, seeing as I'm still in high school.)
You, sir, name? wrote:If you have over 26 levels of nesting, you've got bigger problems ... than variable naming.
suffer-cait wrote:it might also be interesting to note here that i don't like 5 fingers. they feel too bulky.

User avatar
t0rajir0u
Posts: 1178
Joined: Wed Apr 16, 2008 12:52 am UTC
Location: Cambridge, MA
Contact:

Re: Interesting sequences (Catalan, maybe?)

Postby t0rajir0u » Sun Feb 01, 2009 12:25 am UTC

The generating function itself has a simple closed-form expression: it is [math]\frac{1 - \sqrt{1 - 4x}}{2x}.[/math] Explaining why this function represents the Catalan numbers requires you to at least have some familiarity with calculus and ideally to have a strong understanding of how power series multiply. The fact that this function exists lets you do a lot of cool things with the Catalan numbers that aren't as easy to do otherwise, like prove certain identities. Again, the whole notion of a generating function is just not appropriate for this audience.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 8 guests