A178525 -id:A178525 - cp's OEIS frontend

A192304 0-sequence of reduction of (2n-1) by x^2 -> x+1.

1, 1, 6, 13, 31, 64, 129, 249, 470, 869, 1583, 2848, 5073, 8961, 15718, 27405, 47535, 82080, 141169, 241945, 413366, 704261, 1196831, 2029248, 3433441, 5798209, 9774534, 16451149, 27646975, 46397824

Offset: 1

Clark Kimberling, Jun 27 2011

See A192232 for definition of "k-sequence of reduction of [sequence] by [substitution]".

Cf. A192232, A178525.

c[n_] := 2 n - 1; (* odd numbers, A005408 *)
Table[c[n], {n, 1, 15}]
q[x_] := x + 1;
p[0, x_] := 1; p[n_, x_] := p[n - 1, x] + (x^n)*c[n + 1]
reductionRules = {x^y_?EvenQ -> q[x]^(y/2),
   x^y_?OddQ -> x q[x]^((y - 1)/2)};
t = Table[
  Last[Most[
    FixedPointList[Expand[#1 /. reductionRules] &, p[n, x]]]], {n, 0,
   30}]
Table[Coefficient[Part[t, n], x, 0], {n, 1, 30}]  (* A192304 *)
Table[Coefficient[Part[t, n], x, 1], {n, 1, 30}]  (* A178525 *)
(* Peter J. C. Moses, Jun 20 2011 *)

Empirical g.f.: x*(1-2*x+4*x^2-x^3)/(1-3*x+x^2+3*x^3-x^4-x^5). - Colin Barker, Feb 08 2012

A178526 Triangle read by rows: T(n,k) is the number of nodes of cost k in the Fibonacci tree of order n.

Original entry on oeis.org

1, 1, 0, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 3, 2, 1, 1, 2, 3, 5, 3, 1, 1, 2, 3, 5, 8, 5, 1, 1, 2, 3, 5, 8, 13, 8, 1, 1, 2, 3, 5, 8, 13, 21, 13, 1, 1, 2, 3, 5, 8, 13, 21, 34, 21, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 34, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 55, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 89

Offset: 0

Emeric Deutsch, Jun 16 2010

A Fibonacci tree of order n (n>=2) is a complete binary tree whose left subtree is the Fibonacci tree of order n-1 and whose right subtree is the Fibonacci tree of order n-2; each of the Fibonacci trees of order 0 and 1 is defined as a single node. In a Fibonacci tree the cost of a left (right) edge is defined to be 1 (2). The cost of a node of a Fibonacci tree is defined to be the sum of the costs of the edges that form the path from the root to this node.
The sum of the entries in row n is A001595(n) = 2F(n+1) - 1, where F(m)=A000045(m) (the Fibonacci numbers).
Sum(k*T(n,k), 0<=k<=n)=A178525(n).
Daniel Forgues, Aug 10 2012: (Start)
The falling diagonals are, starting from the rightmost one, with index 0:
  d_0(i) = F(i-1), i >= 0;
  d_j(i) = F(i+1), j >= 1, i >= 0.
Equivalently, as a single expression:
  d_j(i) = F(i+1-2*0^j), j >= 0, i >= 0. (End)

			In the Fibonacci tree /\ of order 2 we have a node of cost 0 (the root), a node of cost 1 (the left leaf), and a node of cost 2 (the right leaf).
Triangle starts:
1;
1,0;
1,1,1;
1,1,2,1;
1,1,2,3,2;
1,1,2,3,5,3;
1,1,2,3,5,8,5;

D. E. Knuth, The Art of Computer Programming, Vol. 3, 2nd edition, Addison-Wesley, Reading, MA, 1998, p. 417.

Y. Horibe, An entropy view of Fibonacci trees, Fibonacci Quarterly, 20, No. 2, 1982, 168-178.

Cf. A000045, A001595, A178525.

with(combinat): T := proc (n, k) if k < n then fibonacci(k+1) elif k = n then fibonacci(n-1) else 0 end if end proc: for n from 0 to 12 do seq(T(n, k), k = 0 .. n) end do; # yields sequence in triangular form

T(n,k)=F(k+1) if kn; here F(m)=A000045(m) (the Fibonacci numbers).
G.f.: (1-tz+tz^2)/[(1-z)(1-tz-t^2*z^2)].
The enumerating polynomials P[n] of row n are given by P[0]=1, P[n]=P[n-1]+F(n-1)*(t^{n-1}+t^n) for n>=1, where F(m)=A000045(m) (the Fibonacci numbers).

cp's OEIS Frontend

A192304 0-sequence of reduction of (2n-1) by x^2 -> x+1.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

A178526 Triangle read by rows: T(n,k) is the number of nodes of cost k in the Fibonacci tree of order n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Formula