Simple algorithm/method to generate the sequence

Go To StackoverFlow.com

3

http://oeis.org/A005773

I looked into that page but most of the abbreviations didn't make any sense.

G.f.: 2x/(3x-1+sqrt(1-2x-3x^2)) - Len Smiley (smiley(AT)math.uaa.alaska.edu).

Does G.f implies generating function?. Substituting any values for x almost yields a square root of a negative number(imaginary). How does it generate the sequence? Any help would be welcome.

Edit: The bottom of the page has some examples using specialized languages like Mathematica,Maple,etc., which I am not familiar with. Any explanation with languages like C,Java or Python would be really helpful.

2012-04-04 19:17
by toddlermenot
This isn't really a programming question. But yes, g.f. stands for generating function; the coefficients of the Taylor series of that expression generate the terms of the sequence. You can use one of the other formulae (say one of the recurrences) instead - DSM 2012-04-04 19:23
Thanks for your comment,DSM. I do agree this falls somewhere between math and programming - toddlermenot 2012-04-04 19:28
off topic -- belongs on math.S - Jason S 2012-04-05 02:02


5

If you have a sequence {a0, a1, a2, a3, ... } then its generating function is

f(x) = sum aj x^j

For example, the sequence {1, 1, 1, 1, ... } has

f(x) = 1 + x + x^2 + x^3 + ...

Conveniently, this function has a closed expression

f(x) = 1 / (1 - x)

and so we say that 1 / (1 - x) is the generating function for {1, 1, 1, 1, ... }.

For your function 2x / (3x - 1 + sqrt(1 - 2x - 3x^2)) you need to expand this function in its Taylor sequence about x0 = 0 and then you will have the terms of the sequence.

If you use Wolfram Alpha, you'll see the first few terms are

1, 1, 2, 5, 13, 35, 96, 267, ...

and then if you use OEIS you'll get

A005773 Number of directed animals of size n (or directed n-ominoes in standard position).

which is right back to where you started showing that this generating function really does generate this sequence.

There's a really fun book called generatingfunctionology dedicated to this subject that you can download for free. Enjoy!

2012-04-04 19:29
by jason
Thank you for the awesome reply - toddlermenot 2012-04-04 19:43


1

Yes, G.f. means generating function. The series expansion of this expression at x = 0 gives a power series in x whose coefficients are the sequence.

Wolfram Alpha's expansion

My input was

Series[2x/(3x-1+Sqrt[1-2x-3x^2]), {x, 0, 10}]
2012-04-04 19:29
by jmhl
Thank you. Wolfram Alpha is very handy - toddlermenot 2012-04-04 19:44
Ads