Simple algorithm/method to generate the sequence

Question

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.

Accepted Answer

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!

Simple algorithm/method to generate the sequence

Solution

Problem