A136376 -id:A136376 - cp's OEIS frontend

A238343 Triangle T(n,k) read by rows: T(n,k) is the number of compositions of n with k descents, n>=0, 0<=k<=n.

1, 1, 0, 2, 0, 0, 3, 1, 0, 0, 5, 3, 0, 0, 0, 7, 9, 0, 0, 0, 0, 11, 19, 2, 0, 0, 0, 0, 15, 41, 8, 0, 0, 0, 0, 0, 22, 77, 29, 0, 0, 0, 0, 0, 0, 30, 142, 81, 3, 0, 0, 0, 0, 0, 0, 42, 247, 205, 18, 0, 0, 0, 0, 0, 0, 0, 56, 421, 469, 78, 0, 0, 0, 0, 0, 0, 0, 0, 77, 689, 1013, 264, 5, 0, 0, 0, 0, 0, 0, 0, 0, 101, 1113, 2059, 786, 37, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 0

Joerg Arndt and Alois P. Heinz, Feb 25 2014

Counting ascents gives the same triangle.

For n > 0, also the number of compositions of n with k + 1 maximal weakly increasing runs. - Gus Wiseman, Mar 23 2020

			Triangle starts:
00:    1;
01:    1,    0;
02:    2,    0,    0;
03:    3,    1,    0,    0;
04:    5,    3,    0,    0,   0;
05:    7,    9,    0,    0,   0, 0;
06:   11,   19,    2,    0,   0, 0, 0;
07:   15,   41,    8,    0,   0, 0, 0, 0;
08:   22,   77,   29,    0,   0, 0, 0, 0, 0;
09:   30,  142,   81,    3,   0, 0, 0, 0, 0, 0;
10:   42,  247,  205,   18,   0, 0, 0, 0, 0, 0, 0;
11:   56,  421,  469,   78,   0, 0, 0, 0, 0, 0, 0, 0;
12:   77,  689, 1013,  264,   5, 0, 0, 0, 0, 0, 0, 0, 0;
13:  101, 1113, 2059,  786,  37, 0, 0, 0, 0, 0, 0, 0, 0, 0;
14:  135, 1750, 4021, 2097, 189, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0;
15:  176, 2712, 7558, 5179, 751, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0;
...
From _Gus Wiseman_, Mar 23 2020: (Start)
Row n = 5 counts the following compositions:
  (5)          (3,2)
  (1,4)        (4,1)
  (2,3)        (1,3,1)
  (1,1,3)      (2,1,2)
  (1,2,2)      (2,2,1)
  (1,1,1,2)    (3,1,1)
  (1,1,1,1,1)  (1,1,2,1)
               (1,2,1,1)
               (2,1,1,1)
(End)

Joerg Arndt and Alois P. Heinz, Rows n = 0..140, flattened

Columns k=0-10 give: A000041, A241626, A241627, A241628, A241629, A241630, A241631, A241632, A241633, A241634, A241635.
T(3n,n) gives A000045(n+1).
T(3n+1,n) = A136376(n+1).
Row sums are A011782.
Compositions by length are A007318.
The version for co-runs or levels is A106356.
The case of partitions (instead of compositions) is A133121.
The version for runs is A238279.
The version without zeros is A238344.
The version for weak ascents is A333213.
Cf. A008284, A045883, A124765, A124766, A332875, A333215.

b:= proc(n, i) option remember; `if`(n=0, 1, expand(
       add(b(n-j, j)*`if`(j (p-> seq(coeff(p, x, i), i=0..n))(b(n, 0)):
seq(T(n), n=0..20);

b[n_, i_] := b[n, i] = If[n == 0, 1, Sum[b[n-j, j]*If[jJean-François Alcover, Jan 08 2015, translated from Maple *)
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],n==0||Length[Split[#,LessEqual]]==k+1&]],{n,0,9},{k,0,n}] (* Gus Wiseman, Mar 23 2020 *)

Sum_{k=0..n} k * T(n,k) = A045883(n-2) for n>=2.

A238344 Irregular triangle T(n,k) read by rows: T(n,k) is the number of compositions of n with k descents, n>=0, 0<=k<=floor(n/3).

Original entry on oeis.org

1, 1, 2, 3, 1, 5, 3, 7, 9, 11, 19, 2, 15, 41, 8, 22, 77, 29, 30, 142, 81, 3, 42, 247, 205, 18, 56, 421, 469, 78, 77, 689, 1013, 264, 5, 101, 1113, 2059, 786, 37, 135, 1750, 4021, 2097, 189, 176, 2712, 7558, 5179, 751, 8, 231, 4128, 13780, 11998, 2558, 73, 297, 6208, 24440, 26400, 7762, 429

Offset: 0

Joerg Arndt and Alois P. Heinz, Feb 25 2014

Same as A238343, with zeros omitted.
Columns k=0-10 give: A000041, A241626, A241627, A241628, A241629, A241630, A241631, A241632, A241633, A241634, A241635.
Row sums are A011782.
T(3n,n) = A000045(n+1).
T(3n+1,n) = A136376(n+1).

			Triangle starts:
00:    1;
01:    1;
02:    2;
03:    3,     1;
04:    5,     3;
05:    7,     9;
06:   11,    19,      2;
07:   15,    41,      8;
08:   22,    77,     29;
09:   30,   142,     81,      3;
10:   42,   247,    205,     18;
11:   56,   421,    469,     78;
12:   77,   689,   1013,    264,      5;
13:  101,  1113,   2059,    786,     37;
14:  135,  1750,   4021,   2097,    189;
15:  176,  2712,   7558,   5179,    751,     8;
16:  231,  4128,  13780,  11998,   2558,    73;
17:  297,  6208,  24440,  26400,   7762,   429;
18:  385,  9201,  42358,  55593,  21577,  1945,  13;
19:  490, 13502,  71867, 112814,  55867,  7465, 139;
20:  627, 19585, 119715, 221639, 136478, 25317, 927;
...

Joerg Arndt and Alois P. Heinz, Rows n = 0..250, flattened

Cf. A045883.

b:= proc(n, i) option remember; `if`(n=0, 1, expand(
       add(b(n-j, j)*`if`(j (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0)):
seq(T(n), n=0..20);

b[n_, i_] := b[n, i] = If[n == 0, 1, Expand[Sum[b[n-j, j]*If[jJean-François Alcover, Feb 11 2015, after Maple *)

Sum_{k=0..floor(n/3)} k * T(n,k) = A045883(n-2) for n>=2.

A178521 The cost of all leaves in the Fibonacci tree of order n.

Original entry on oeis.org

0, 0, 3, 7, 17, 35, 70, 134, 251, 461, 835, 1495, 2652, 4668, 8163, 14195, 24565, 42331, 72674, 124354, 212155, 360985, 612743, 1037807, 1754232, 2959800, 4985475, 8384479, 14080601, 23614931, 39556030, 66181310, 110608187, 184670693, 308030923, 513334855

Offset: 0

Emeric Deutsch, Jun 14 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 leaf 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 leaf.

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

Colin Barker, Table of n, a(n) for n = 0..1000
Y. Horibe, An entropy view of Fibonacci trees, Fibonacci Quarterly, 20, No. 2, 1982, 168-178.
Index entries for linear recurrences with constant coefficients, signature (2,1,-2,-1).

Cf. A000045, A136376, A354044.

# The function 'fibrec' is defined in A354044.
function A178521(n)
    n < 2 && return BigInt(0)
    a, b = fibrec(n - 1)
    a*n + (n - 1)*b
end
println([A178521(n) for n in 0:35]) # Peter Luschny, May 16 2022

with(combinat); seq(n*fibonacci(n+1)-fibonacci(n), n = 0 .. 35);

Table[n Fibonacci[n + 1] - Fibonacci[n], {n, 0, 40}]  (* Harvey P. Dale, Apr 21 2011 *)
Table[(n - 1) Fibonacci[n] + n Fibonacci[n - 1], {n, 0, 40}] (* Bruno Berselli, Dec 06 2013 *)

concat(vector(2), Vec(x^2*(x+3)/(x^2+x-1)^2 + O(x^50))) \\ Colin Barker, Jul 26 2017

a(n) = n*F(n+1) - F(n), where F(k) = A000045(k).
G.f.: x^2*(x+3)/(x^2+x-1)^2. - Colin Barker, Nov 11 2012
a(n) = Sum_{k=1..n-1} F(k) * L(n-k+1) where F(n) = A000045(n), L(n) = A000032(n). - Gary Detlefs, Dec 29 2012
a(n) = (n-1)*F(n) + n*F(n-1). - Bruno Berselli, Dec 06 2013
a(0) = 0, a(n) = A023607(n-1) + A099920(n-1). - Collin Berman, Dec 12 2016
a(n) = 2*a(n-1) + a(n-2) - 2*a(n-3) - a(n-4). - Wesley Ivan Hurt, Dec 14 2016
a(n) = (n+1)*F(n+1) - F(n+2). - Bruno Berselli, Jul 26 2017
a(n) = (2^(-1-n)*(2*sqrt(5)*((1-sqrt(5))^n - (1+sqrt(5))^n) + (-(1-sqrt(5))^n*(-5+sqrt(5)) + (1+sqrt(5))^n*(5+sqrt(5)))*n))/5. - Colin Barker, Jul 26 2017
a(n) = (-n*sin(c*(-n - 1)) - sin(c*n)*i)/((-i)^(-n)*sqrt(5/4)) where c = arccos(i/2). - Peter Luschny, May 16 2022

A117202 Binomial transform of n*F(n).

Original entry on oeis.org

0, 1, 4, 15, 52, 170, 534, 1631, 4880, 14373, 41810, 120406, 343884, 975325, 2749852, 7713435, 21540304, 59917826, 166094370, 458998523, 1264919720, 3477182961, 9536877614, 26102772910, 71309161752, 194468551225, 529490287924

Offset: 0

Paul Barry, Mar 02 2006

Binomial transform of A045925.
Number of acyclic subgraphs of the wheel graph W_n (on n+1 vertices) with exactly n-1 edges. - Emil R. Vaughan, Jun 12 2007
Equivalently, number of two-component spanning forests of the wheel graph W_n (on n+1 vertices). - Harry Richman, Jul 31 2023
Starting (1, 4, 15, 52, ...) = binomial transform of A136376. - Gary W. Adamson, Sep 03 2008

Indranil Ghosh, Table of n, a(n) for n = 0..1000
Harry Richman, Farbod Shokrieh, and Chenxi Wu, Counting two-forests and random cut size via potential theory, arXiv:2308.03859 [math.CO], 2023. See p. 18.
J. Salas and A. D. Sokal, Transfer Matrices and Partition-Function Zeros for Antiferromagnetic Potts Models. V. Further Results for the Square-Lattice Chromatic Polynomial, J. Stat. Phys. 135 (2009) 279-373; arXiv:0711.1738 [cond-mat.stat-mech], 2007-2009. Mentions this sequence. - _N. J. A. Sloane_, Mar 14 2014
Index entries for linear recurrences with constant coefficients, signature (6,-11,6,-1).

Cf. A001519, A111262.
Cf. A136376.
Cf. A004146 (number of spanning trees of wheel graph).

Table[n Fibonacci[2n-1],{n,0,26}] (* or *) Table[Sum[Fibonacci[2k]*BernoulliB[2n-2k]*Binomial[2n,2k],{k,1,n}],{n,0,26}] (* or *) CoefficientList[Series[x(1-2x+2x^2)/(1-3x+x^2)^2 ,{x,0,26}],x] (* Indranil Ghosh, Feb 26 2017 *)

a(n) = n*fibonacci(2*n-1); \\ Indranil Ghosh, Feb 26 2017

concat(0, Vec(x*(1-2*x+2*x^2) / (1-3*x+x^2)^2 + O(x^30))) \\ Colin Barker, Feb 26 2017

G.f.: x*(1-2x+2x^2)/(1-3x+x^2)^2.
a(n) = 6*a(n-1)-11*a(n-2)+6*a(n-3)-a(n-4).
a(n) = Sum_{k=0..n} C(n,k)*k*F(k).
From Benoit Cloitre, Nov 29 2006: (Start)
a(n) = Sum_{k=1..n} F(2k)*B(2n-2k)*binomial(2n,2k) where F=Fibonacci numbers and B=Bernoulli numbers;
a(n) = n*F(2n-1). (End)
a(n) = (2^(-1-n)*(-(-5+sqrt(5))*(3+sqrt(5))^n + (3-sqrt(5))^n*(5+sqrt(5)))*n) / 5. - Colin Barker, Feb 26 2017
a(n) = (1/sqrt(5)) * n * (((1 + sqrt(5)) / 2)^(2*n-1) - ((1 - sqrt(5)) / 2)^(2*n-1)). - Harry Richman, Jul 31 2023
a(n) = round((1/sqrt(5)) * n * phi^(2n-1)), where phi = (1+sqrt(5))/2 is the golden ratio A001622. - Harry Richman, Jul 31 2023

A133673 a(n) = nL(n) + (n-1)L(n-1) where L(n) is the Lucas number.

Original entry on oeis.org

7, 18, 40, 83, 163, 311, 579, 1060, 1914, 3419, 6053, 10637, 18575, 32262, 55772, 96019, 164711, 281635, 480171, 816536, 1385262, 2345083, 3962185, 6682393, 11251543, 18916026, 31756624, 53243795, 89160619, 149135759, 249187923, 415946572, 693648930

Offset: 2

Parthasarathy Nambi, Dec 29 2007

For n>2, two evens followed by four odds.

			For n=2, a(2) = 7;
For n=21, a(21) = 816536.

Harvey P. Dale, Table of n, a(n) for n = 2..1000
Index entries for linear recurrences with constant coefficients, signature (2,1,-2,-1).

Cf. A000032, A136376, A146005.

Total/@Partition[Times@@@Table[{n,LucasL[n]},{n,30}],2,1] (* or *) LinearRecurrence[{2,1,-2,-1},{7,18,40,83},30](* Harvey P. Dale, Oct 21 2011 *)

From R. J. Mathar, Jul 08 2009, Jul 13 2009: (Start)
G.f.: -x^2*(-7-4*x+3*x^2+x^3)/(x^2+x-1)^2.
a(n) = 2*a(n-1)+a(n-2)-2*a(n-3)-a(n-4).
a(n) = A146005(n) + A146005(n-1). (End)

Typo in A-numbers corrected by R. J. Mathar, Jul 13 2009

More terms from Harvey P. Dale, Oct 21 2011

cp's OEIS Frontend

A238343 Triangle T(n,k) read by rows: T(n,k) is the number of compositions of n with k descents, n>=0, 0<=k<=n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A238344 Irregular triangle T(n,k) read by rows: T(n,k) is the number of compositions of n with k descents, n>=0, 0<=k<=floor(n/3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A178521 The cost of all leaves in the Fibonacci tree of order n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Julia

Maple

Mathematica

PARI

Formula

A117202 Binomial transform of n*F(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A133673 a(n) = n*L(n) + (n-1)*L(n-1) where L(n) is the Lucas number.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A133673 a(n) = nL(n) + (n-1)L(n-1) where L(n) is the Lucas number.