|
| |
|
|
A097472
|
|
Number of different candle trees having a total of m edges.
|
|
0
| |
|
|
1, 3, 10, 31, 96, 296, 912, 2809, 8651, 26642, 82047, 252672, 778128, 2396320, 7379697, 22726483, 69988378, 215535903, 663763424, 2044122936, 6295072048, 19386276329, 59701891739, 183857684514, 566207320575, 1743689586432
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,2
|
|
|
COMMENTS
| A candle tree is a graph on the plane square lattice Z X Z whose edges have length one with the following properties: (a) It contains a line segment ("trunk") of length from 0 to m on the vertical axis, its lowest node is at the origin. (b) It contains horizontal line segments ("branches"); each of them intersects the trunk. (c) Each branch is allowed to have "candles", which are vertical edges of length 1, whose lower node is on a branch.
|
|
|
REFERENCES
| Alexander Malkis, "Polyedges, polyominoes and the 'Digit' game", diploma thesis in computer science, Universitaet des Saarlandes, Germany
|
|
|
LINKS
| Alexander Malkis, Polyedges, polyominoes and the 'Digit' game
|
|
|
FORMULA
| a(n) = sum_{s, d, k>=0 with s+d+k=m} binom(s+2d+1, s)*binom(s, k); generating function = 1/(x^4 + 2x^3 - x^2 - 3x + 1); a(n+4) = 3a(n+3)+a(n+2)-2a(n+1)-a(n)
a(n)=sum(m=1..n, sum(k=1..n-m+1, binomial(k,n-m-k+1)*binomial(k+2*m-1,2*m-1)))+1; [From Vladimir Kruchinin kru(AT)ie.tusur.ru, May 12 2011]
a(0)=1, a(1)=3, a(2)=10, a(3)=31, a(n)=3*a(n-1)+a(n-2)-2*a(n-3)-a(n-4) [From Harvey P. Dale, June 14 2011]
|
|
|
MATHEMATICA
| CoefficientList[Series[1/(x^4+2x^3-x^2-3x+1), {x, 0, 30}], x] (* or *) LinearRecurrence[{3, 1, -2, -1}, {1, 3, 10, 31}, 30] (* From Harvey P. Dale, June 14 2011 *)
|
|
|
PROG
| (Maxima)
a(n):=sum(sum(binomial(k, n-m-k+1)*binomial(k+2*m-1, 2*m-1), k, 1, n-m+1), m, 1, n)+1; [From Vladimir Kruchinin kru(AT)ie.tusur.ru, May 12 2011]
|
|
|
CROSSREFS
| Bisection of A060945 and |A077930|.
Sequence in context: A192337 A106517 A055217 * A068094 A100058 A002160
Adjacent sequences: A097469 A097470 A097471 * A097473 A097474 A097475
|
|
|
KEYWORD
| easy,nice,nonn
|
|
|
AUTHOR
| Alexander Malkis (alexander.malkis(AT)imdea.org), Sep 18 2004
|
|
|
EXTENSIONS
| Link and email address updated Alexander Malkis (Alexander.Malkis(AT)imdea.org), Sep 02 2010
|
| |
|
|
