A004070 -id:A004070 - cp's OEIS frontend

A103820 Whitney transform of 3^n.

1, 4, 16, 61, 232, 880, 3337, 12652, 47968, 181861, 689488, 2614048, 9910609, 37573972, 142453744, 540083149, 2047610680, 7763081488, 29432076505, 111585473980, 423052651456, 1603914376309, 6080901083296, 23054446378816

Offset: 0

Paul Barry, Feb 16 2005

Partial sums of A030195. The Whitney transform maps the sequence with g.f. g(x) to that with g.f. (1/(1-x))g(x(1+x)).

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (4,0,-3).

Cf. A004070, A030195.

Equals (A108306(n+1) - 1)/5.

I:=[1,4,16]; [n le 3 select I[n] else 4*Self(n-1)-3*Self(n-3): n in [1..30]]; // Vincenzo Librandi, Aug 18 2017

a[0]:=0:a[1]:=1:for n from 2 to 50 do a[n]:=3*a[n-1]+3*a[n-2]+1 od: seq(a[n], n=1..33); # Zerinvary Lajos, Dec 14 2008

Join[{a=0,b=1},Table[c=3*b+3*a+1;a=b;b=c,{n,100}]] (* Vladimir Joseph Stephan Orlovsky, Jan 17 2011 *)
LinearRecurrence[{4, 0, -3}, {1, 4, 16}, 40] (* Vincenzo Librandi, Aug 18 2017 *)

G.f.: 1/((1-x)(1-3x-3x^2));
a(n) = 4a(n-1) - 3a(n-3);
a(n) = Sum_{k=0..n} (Sum_{i=0..n} C(k, i-k))*3^k.
a(n) = 3(a(n-1) + a(n-2)) + 1, n > 1. [Gary Detlefs, Jun 21 2010]

A131247 2*A052509 - A000012.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 5, 3, 1, 1, 7, 7, 3, 1, 1, 9, 13, 7, 3, 1, 1, 11, 21, 15, 7, 3, 1, 1, 13, 31, 29, 15, 7, 3, 1, 1, 15, 43, 51, 31, 15, 7, 3, 1, 1, 17, 57, 83, 61, 31, 15, 7, 3, 1

Offset: 0

Gary W. Adamson, Jun 23 2007

Row sums = A104161 starting (1, 2, 5, 10, 19, 34, 59, ...). Reversal, A131248 is generated from 2*A004070 - A000012.

			First few rows of the triangle:
  1;
  1,  1;
  1,  3,  1;
  1,  5,  3,  1;
  1,  7,  7,  3,  1;
  1,  9, 13,  7,  3,  1;
  1, 11, 21, 15,  7,  3,  1;
  ...

Cf. A052509, A104161, A004070, A131248.

2*A052509 - A000012, where A000012 = (1; 1,1; 1,1,1; ...).

A172021 Start with the triangle A171661, reverse its rows, add missing powers of 2 at beginning of each row.

Original entry on oeis.org

1, 1, 2, 2, 1, 2, 4, 6, 6, 1, 2, 4, 8, 14, 20, 20, 1, 2, 4, 8, 16, 30, 50, 70, 70, 1, 2, 4, 8, 16, 32, 62, 112, 182, 252, 252, 1, 2, 4, 8, 16, 32, 64, 126, 238, 420, 672, 924, 924, 1, 2, 4, 8, 16, 32, 64, 128, 254, 492, 912, 1584, 2508, 3432, 3432

Offset: 1

Mark Dols, Jan 22 2010

Rows sum up to A030662.
Triangle is a (mirrored) interspaced binomial transform of 1^n (see example). - Mark Dols, Jan 24 2010
T(n,k) is the number of k permutations of n (indistinguishable) objects of type I and n (indistinguishable) objects of type II. - Geoffrey Critzer, Mar 15 2010
Equivalently T(n,k) is the number of words length k from an alphabet of 2 letters with at most n occurrences of each letter. - Giovanni Artico, Aug 24 2013
T(n,k) is also the number of ways k persons can be accommodated into 2 rooms with at most n persons per room. - Giovanni Artico, Aug 24 2013

			Triangle begins:
......1
....1,2,2
..1,2,4,6,6
1,2,4,8,14,20,20
From _Mark Dols_, Jan 24 2010: (Start)
Interspaced binomial transform of 1^n:
1...1...1...1...1...1...
..2...2...2...2...2...2.
2...4...4...4...4...4...
..6...8...8...8...8...8.
6.. 14..16..16..16..16..
..20..30..32..32..32..32
20..50..62..64..64..64..
(End)

Cf. A030662, A171661, A171698, A004070.

T(n,k):=POLY_COEFF(SUM(x^i/i!, i, 0, n)^2, x, k)·k!
TABLE(VECTOR(T(v, u), u, 0, 2·v), v, 0, 10)  # Giovanni Artico, Aug 30 2013

seq(PolynomialTools:-CoefficientList((convert(taylor(exp(x),x,n+1),polynom)^2),x)*~[seq(i!,i=0..2 n)],n=0..10) # Giovanni Artico, Aug 30 2013

Table[CoefficientList[Series[(Sum[x^i/i!, {i, 0, m}])^2, {x, 0, 2 m}], x]*Table[n!, {n, 0, 2 m}], {m, 0, 10}] // Grid (* Geoffrey Critzer, Mar 15 2010 *)

E.g.f. for row n is: ( 1 + x + x^2/2! + ... + x^n/n! )^2. - Geoffrey Critzer, Mar 15 2010

Definition rewritten by N. J. A. Sloane, Jan 23 2010

More terms from Mark Dols, Jan 24 2010

A192018 Triangle read by rows: T(n,k) is the number of unordered pairs of nodes at distance k in the binary Fibonacci tree of order n (1<=k<=2n-3; entries in row n are the coefficients of the corresponding Wiener polynomial).

Original entry on oeis.org

1, 3, 2, 1, 6, 6, 5, 3, 1, 11, 13, 14, 12, 10, 5, 1, 19, 24, 30, 31, 31, 28, 19, 7, 1, 32, 42, 56, 66, 74, 78, 77, 61, 32, 9, 1, 53, 71, 98, 124, 152, 175, 196, 203, 180, 118, 49, 11, 1, 87, 118, 166, 218, 284, 349, 419, 485, 525, 502, 384, 207, 70, 13, 1, 142, 194, 276, 370, 499, 645, 812, 998, 1189, 1331, 1349, 1152, 749, 336, 95, 15, 1

Offset: 2

Emeric Deutsch, Jun 21 2011

The binary Fibonacci trees f(k) of order k is a rooted binary tree defined as follows: 1. f(0) has no nodes and f(1) consists of a single node. 2. For k>=2, f(k) is constructed from a root with f(k-1) as its left subtree and f(k-2) as its right subtree. See the Iyer & Reddy references.
Row n contains 2n-3 entries.
T(n,1) = A001911(n-1) (Fibonacci numbers minus 2).
Sum_{k>=1} k*T(n,k) = A192019(n) (the Wiener indices).

			Triangle starts:
   1;
   3,  2,  1;
   6,  6,  5,  3,  1;
  11, 13, 14, 12, 10,  5,  1;
  19, 24, 30, 31, 31, 28, 19,  7,  1;

K. Viswanathan Iyer and K. R. Udaya Kumar Reddy, Wiener index of Binomial trees and Fibonacci trees, Int'l. J. Math. Engin. with Comp., Accepted for publication, Sept. 2009.

B. E. Sagan, Y-N. Yeh and P. Zhang, The Wiener Polynomial of a Graph, Internat. J. of Quantum Chem., 60, 1996, 959-969.
K. Viswanathan Iyer and K. R. Udaya Kumar Reddy, Wiener index of binomial trees and Fibonacci trees, arXiv:0910.4432 [cs.DM], 2009.

Cf. A001911, A192019.

G := z/((1-z)*(1-t*z-t*z^2)): Gser := simplify(series(G, z = 0, 13)): for n to 10 do r[n] := sort(coeff(Gser, z, n)) end do; w[1] := 0: w[2] := t: for n from 3 to 10 do w[n] := sort(expand(w[n-1]+w[n-2]+t*r[n-1]+t*r[n-2]+t^2*r[n-1]*r[n-2])) end do: for n from 2 to 10 do seq(coeff(w[n], t, k), k = 1 .. 2*n-3) end do; # yields sequence in triangular form

The Wiener polynomial w(n,t) of the binary Fibonacci tree of order n satisfies the recurrence relation w(n,t) = w(n-1,t) + w(n-2,t) + t*r(n-1,t) + t*r(n-2) + t^2*r(n-1,t)*r(n-2,t), w(1,t)=0, w(2,t)=t, where r(n,t) is the generating polynomial of the nodes of the binary Fibonacci tree f(n) with respect to the level of the nodes (for example, r(2,t) = 1 + t for the tree / ; see A004070 and the Maple program).

A192019 The Wiener index of the binary Fibonacci tree of order n.

Original entry on oeis.org

1, 10, 50, 214, 802, 2802, 9275, 29580, 91668, 277924, 828092, 2433140, 7067885, 20337318, 58054534, 164602410, 463990190, 1301338150, 3633753815, 10107239160, 28016346216, 77419909800, 213349801560, 586471432104, 1608485221177, 4402406713762

Offset: 2

Emeric Deutsch, Jun 21 2011

nonn

The binary Fibonacci trees f(k) of order k are rooted binary trees defined as follows: 1. f(0) has no nodes and f(1) consists of a single node. 2. For k>=2, f(k) is constructed from a root with f(k-1) as its left subtree and f(k-2) as its right subtree. See the Iyer & Reddy references.

			a(3)=10 because the binary Fibonacci tree of order 3 is basically the path graph A - B - R - C and we have 3 distances equal to 1 (AB, BR, RC), 2 distances equal to 2 (AR and BC) and 1 distance equal to 3 (AC); 3*1 + 2*2 + 1*3 = 10.

K. Viswanathan Iyer and K. R. Udaya Kumar Reddy, Wiener index of Binomial trees and Fibonacci trees, Int'l. J. Math. Engin. with Comp., Accepted for publication, Sept. 2009.

B. E. Sagan, Y-N. Yeh and P. Zhang, The Wiener Polynomial of a Graph, Internat. J. of Quantum Chem., 60, 1996, 959-969.
K. Viswanathan Iyer and K. R. Udaya Kumar Reddy, Wiener index of binomial trees and Fibonacci trees, arXiv:0910.4432 [cs.DM], 2009.

Cf. A192018.

G := z/((1-z)*(1-t*z-t*z^2)): Gser := simplify(series(G, z = 0, 30)): for n to 27 do r[n] := sort(coeff(Gser, z, n)) end do: w[1] := 0: w[2] := t: for n from 3 to 27 do w[n] := sort(expand(w[n-1]+w[n-2]+t*r[n-1]+t*r[n-2]+t^2*r[n-1]*r[n-2])) end do: seq(subs(t = 1, diff(w[n], t)), n = 2 .. 27);

a(n) = Sum_{k>=1} k*A192018(n,k).
The Wiener index of a connected graph is the derivative of the Wiener polynomial W(t) of the graph, evaluated at t=1. The Wiener polynomial w(n,t) of the binary Fibonacci tree of order n satisfies the recurrence relation w(n,t) = w(n-1,t) + w(n-2,t) + t*r(n-1,t) + t*r(n-2) + t^2*r(n-1,t)*r(n-2,t), w(1,t)=0, w(2,t)=t, where r(n,t) is the generating polynomial of the nodes of the binary Fibonacci tree f(n) with respect to the level of the nodes (for example, r(2,t) = 1 + t for the tree / ; see A004070 and the Maple program).
Empirical G.f.: x^2*(x^4-3*x^2+4*x+1)/((x+1)^2*(x^2-3*x+1)^2*(x^2+x-1)^2). [Colin Barker, Nov 17 2012]

A378145 Riordan triangle (1 + x * C(x), x * C(x)), where C(x) is g.f. of A000108.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 2, 4, 3, 1, 5, 10, 8, 4, 1, 14, 28, 23, 13, 5, 1, 42, 84, 70, 42, 19, 6, 1, 132, 264, 222, 138, 68, 26, 7, 1, 429, 858, 726, 462, 240, 102, 34, 8, 1, 1430, 2860, 2431, 1573, 847, 385, 145, 43, 9, 1, 4862, 9724, 8294, 5434, 3003, 1430, 583, 198, 53, 10, 1

Offset: 0

Werner Schulte, Nov 17 2024

			Triangle T(n, k) for 0 <= k <= n starts:
n\k :     0     1     2     3    4    5    6   7  8  9
======================================================
  0 :     1
  1 :     1     1
  2 :     1     2     1
  3 :     2     4     3     1
  4 :     5    10     8     4    1
  5 :    14    28    23    13    5    1
  6 :    42    84    70    42   19    6    1
  7 :   132   264   222   138   68   26    7   1
  8 :   429   858   726   462  240  102   34   8  1
  9 :  1430  2860  2431  1573  847  385  145  43  9  1
  etc.

Cf. A000108, A004070, A120588 (column 0), A068875 (column 1 and row sums), A000007 (alt. row sums).

T(n,k)=if(k==n,1,binomial(2*n-k,n)*(n*(3*k+1)-2*k*(k+1))/((2*n-k)*(2*n-k-1)))

T(n, k) = binomial(2*n-k, n) * (n*(3*k+1) - 2*k*(k+1)) / ((2*n-k) * (2*n-k-1)) if 0 <= k < n and 1 if k = n.
T(n, k) = T(n, k-1) - T(n-1, k-2) for 2 <= k <= n.
(-1)^(n-k) * T(n, k) is matrix inverse of A004070 (seen as a triangle).
Conjecture: Sum_{i=0..n-k} binomial(i+m-1, i) * T(n, i+k) = T(n+m, m+k) for m > 0.
Conjecture: Sum_{k=0..n} (1 + floor(k/2)) * T(n, k) = A000108(n+1).
G.f.: A(x, y) = (1 + x*C(x)) / (1 - y * x*C(x)), where C(x) is g.f. of A000108.

cp's OEIS Frontend

A103820 Whitney transform of 3^n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

A131247 2*A052509 - A000012.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A172021 Start with the triangle A171661, reverse its rows, add missing powers of 2 at beginning of each row.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Derive

Maple

Mathematica

Formula

Extensions

A192018 Triangle read by rows: T(n,k) is the number of unordered pairs of nodes at distance k in the binary Fibonacci tree of order n (1<=k<=2n-3; entries in row n are the coefficients of the corresponding Wiener polynomial).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Formula

A192019 The Wiener index of the binary Fibonacci tree of order n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Formula

A378145 Riordan triangle (1 + x * C(x), x * C(x)), where C(x) is g.f. of A000108.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Formula