A008466 -id:A008466 - cp's OEIS frontend

A101220 a(n) = Sum_{k=0..n} Fibonacci(n-k)*n^k.

0, 1, 3, 14, 91, 820, 9650, 140601, 2440317, 49109632, 1123595495, 28792920872, 816742025772, 25402428294801, 859492240650847, 31427791175659690, 1234928473553777403, 51893300561135516404, 2322083099525697299278

Offset: 0

Ross La Haye, Dec 14 2004

In what follows a(i,j,k) denotes a three-dimensional array, the terms a(n) are defined as a(n,n,n) in that array. - Joerg Arndt, Jan 03 2021
Previous name was: Three-dimensional array: a(i,j,k) = expansion of x*(1 + (i-j)*x)/((1-j*x)*(1-x-x^2)), read by a(n,n,n).
a(i,j,k) = the k-th value of the convolution of the Fibonacci numbers (A000045) with the powers of i = Sum_{m=0..k} a(i-1,j,m), both for i = j and i > 0; a(i,j,k) = a(i-1,j,k) + a(j,j,k-1), for i,k > 0; a(i,1,k) = Sum_{m=0..k} a(i-1,0,m), for i > 0. With F = Fibonacci and L = Lucas, then a(1,1,k) = F(k+2) - 1; a(2,1,k) = F(k+3) - 2; a(3,1,k) = L(k+2) - 3; a(4,1,k) = 4*F(k+1) + F(k) - 4; a(1,2,k) = 2^k - F(k+1); a(2,2,k) = 2^(k+1) - F(k+3); a(3,2,k) = 3(2^k - F(k+2)) + F(k); a(4,2,k) = 2^(k+2) - F(k+4) - F(k+2); a(1,3,k) = (3^k + L(k-1))/5, for k > 0; a(2,3,k) = (2 * 3^k - L(k)) /5, for k > 0; a(3,3,k) = (3^(k+1) - L(k+2))/5; a(4,3,k) = (4 * 3^k - L(k+2) - L(k+1))/5, etc..

			a(1,3,3) = 6 because a(1,3,0) = 0, a(1,3,1) = 1, a(1,3,2) = 2 and 4*2 - 2*1 - 3*0 = 6.

G. C. Greubel, Table of n, a(n) for n = 0..385
Eric Weisstein's World of Mathematics, Fibonacci Number
Eric Weisstein's World of Mathematics, Lucas Number

a(0, j, k) = A000045(k).
a(1, 2, k+1) - a(1, 2, k) = A099036(k).
a(3, 2, k+1) - a(3, 2, k) = A104004(k).
a(4, 2, k+1) - a(4, 2, k) = A027973(k).
a(1, 3, k+1) - a(1, 3, k) = A099159(k).
a(i, 0, k) = A109754(i, k).
a(i, i+1, 3) = A002522(i+1).
a(i, i+1, 4) = A071568(i+1).
a(2^i-2, 0, k+1) = A118654(i, k), for i > 0.
Sequences of the form a(n, 0, k): A000045(k+1) (n=1), A000032(k) (n=2), A000285(k-1) (n=3), A022095(k-1) (n=4), A022096(k-1) (n=5), A022097(k-1) (n=6), A022098(k-1) (n=7), A022099(k-1) (n=8), A022100(k-1) (n=9), A022101(k-1) (n=10), A022102(k-1) (n=11), A022103(k-1) (n=12), A022104(k-1) (n=13), A022105(k-1) (n=14), A022106(k-1) (n=15), A022107(k-1) (n=16), A022108(k-1) (n=17), A022109(k-1) (n=18), A022110(k-1) (n=19), A088209(k-2) (n=k-2), A007502(k) (n=k-1), A094588(k) (n=k).
Sequences of the form a(1, n, k): A000071(k+2) (n=1), A027934(k-1) (n=2), A098703(k) (n=3).
Sequences of the form a(2, n, k): A001911(k) (n=1), A008466(k+1) (n=2), A106517(k-1) (n=3).
Sequences of the form a(3, n, k): A027961(k) (n=1), A094688(k) (n=3).
Sequences of the form a(4, n, k): A053311(k-1) (n=1), A027974(k-1) (n=2).
Cf. A001622, A001891, A001924, A023537, A104161, A106517.

A101220:= func< n | (&+[n^k*Fibonacci(n-k): k in [0..n]]) >;
[A101220(n): n in [0..30]]; // G. C. Greubel, Jun 01 2025

Join[{0}, Table[Sum[Fibonacci[n-k]*n^k, {k, 0, n}], {n, 1, 20}]] (* Vaclav Kotesovec, Jan 03 2021 *)

a(n)=sum(k=0,n,fibonacci(n-k)*n^k) \\ Joerg Arndt, Jan 03 2021

def A101220(n): return sum(n^k*fibonacci(n-k) for k in range(n+1))
print([A101220(n) for n in range(31)]) # G. C. Greubel, Jun 01 2025

a(i, j, 0) = 0, a(i, j, 1) = 1, a(i, j, 2) = i+1; a(i, j, k) = ((j+1)*a(i, j, k-1)) - ((j-1)*a(i, j, k-2)) - (j*a(i, j, k-3)), for k > 2.
a(i, j, k) = Fibonacci(k) + i*a(j, j, k-1), for i, k > 0.
a(i, j, k) = (Phi^k - (-Phi)^-k + i(((j^k - Phi^k) / (j - Phi)) - ((j^k - (-Phi)^-k) / (j - (-Phi)^-1)))) / sqrt(5), where Phi denotes the golden mean/ratio (A001622).
i^k = a(i-1, i, k) + a(i-2, i, k+1).
A104161(k) = Sum_{m=0..k} a(k-m, 0, m).
a(i, j, 0) = 0, a(i, j, 1) = 1, a(i, j, 2) = i+1, a(i, j, 3) = i*(j+1) + 2; a(i, j, k) = (j+2)*a(i, j, k-1) - 2*j*a(i, j, k-2) - a(i, j, k-3) + j*a(i, j, k-4), for k > 3. a(i, j, 0) = 0, a(i, j, 1) = 1; a(i, j, k) = a(i, j, k-1) + a(i, j, k-2) + i * j^(k-2), for k > 1.
G.f.: x*(1 + (i-j)*x)/((1-j*x)*(1-x-x^2)).
a(n, n, n) = Sum_{k=0..n} Fibonacci(n-k) * n^k. - Ross La Haye, Jan 14 2006
Sum_{m=0..k} binomial(k,m)*(i-1)^m = a(i-1,i,k) + a(i-2,i,k+1), for i > 1. - Ross La Haye, May 29 2006
From Ross La Haye, Jun 03 2006: (Start)
a(3, 3, k+1) - a(3, 3, k) = A106517(k).
a(1, 1, k) = A001924(k) - A001924(k-1), for k > 0.
a(2, 1, k) = A001891(k) - A001891(k-1), for k > 0.
a(3, 1, k) = A023537(k) - A023537(k-1), for k > 0.
Sum_{j=0..i+1} a(i-j+1, 0, j) - Sum_{j=0..i} a(i-j, 0, j) = A001595(i). (End)
a(i,j,k) = a(j,j,k) + (i-j)*a(j,j,k-1), for k > 0.
a(n) ~ n^(n-1). - Vaclav Kotesovec, Jan 03 2021

New name from Joerg Arndt, Jan 03 2021

A027934 a(0)=0, a(1)=1, a(2)=2; for n > 2, a(n) = 3a(n-1) - a(n-2) - 2a(n-3).

Original entry on oeis.org

0, 1, 2, 5, 11, 24, 51, 107, 222, 457, 935, 1904, 3863, 7815, 15774, 31781, 63939, 128488, 257963, 517523, 1037630, 2079441, 4165647, 8342240, 16702191, 33433039, 66912446, 133899917, 267921227, 536038872, 1072395555, 2145305339

Offset: 0

Clark Kimberling

Number of compositions of n with at least one even part (offset 2). - Vladeta Jovovic, Dec 29 2004
First differences of A008466. a(n) = A008466(n+2) - A008466(n+1). - Alexander Adamchuk, Apr 06 2006
Starting with "1" = eigensequence of a triangle with the Fibonacci series as the left border and the rest 1's. - Gary W. Adamson, Jul 24 2010
An elephant sequence, see A175654. For the corner squares 24 A[5] vectors, with decimal values between 11 and 416, lead to this sequence (without the leading 0). For the central square these vectors lead to the companion sequence A099036 (without the first leading 1). - Johannes W. Meijer, Aug 15 2010
a(n) = Sum_{k=1..n} A108617(n,k) / 2. - Reinhard Zumkeller, Oct 07 2012
a(n) is the number of binary strings that contain the substring 11 or end in 1. a(3) = 5 because we have: 001, 011, 101, 110, 111. - Geoffrey Critzer, Jan 04 2014
a(n-1), n >= 1, is the number of nonexisting (due to the maturation delay) "[male-female] pairs of Fibonacci rabbits" at the beginning of the n-th month. - Daniel Forgues, May 06 2015
a(n-1) is the number of subsets of {1,2,..,n} that contain n that have at least one pair of consecutive integers. For example, for n=5, a(4) = 11 and the 11 subsets are {4,5}, {1,2,5}, {1,4,5}, {2,3,5}, {2,4,5}, {3,4,5}, {1,2,3,5}, {1,2,4,5}, {1,3,4,5}, {2,3,4,5}, {1,2,3,4,5}.  Note that A008466(n) is the number of all subsets of {1,2,..,n} that have at least one pair of consecutive integers. - Enrique Navarrete, Aug 15 2020

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
Patrick Letendre, Polynomials with integer roots, arXiv:1911.00480 [math.NT], 2019. See p. 4.
Toufik Mansour and Mark Shattuck, Pattern avoidance in flattened derangements, Disc. Math. Lett. (2025) Vol. 15, 67-74. See p. 74.
Augustine O. Munagi, Integer Compositions and Higher-Order Conjugation, J. Int. Seq., Vol. 21 (2018), Article 18.8.5.
Denis Neiter and Amsha Proag, Links Between Sums Over Paths in Bernoulli's Triangles and the Fibonacci Numbers, Journal of Integer Sequences, Vol. 19 (2016), Article 16.8.3.
OEIS Wiki, Fibonacci rabbits
Index entries for linear recurrences with constant coefficients, signature (3,-1,-2).

Row sums of triangle A131767. - Gary W. Adamson, Jul 13 2007
a(n) = A101220(1, 2, n+1).
T(n, n) + T(n, n+1) + ... + T(n, 2n), T given by A027926.
Diagonal sums of A055248.
Cf. A000045, A000079, A008466, A059570, A099036, A047967, A000032.

List([0..35], n-> 2^n - Fibonacci(n+1) ); # G. C. Greubel, Sep 27 2019

a027934 n = a027934_list !! n
a027934_list = 0 : 1 : 2 : zipWith3 (\x y z -> 3 * x - y - 2 * z)
               (drop 2 a027934_list) (tail a027934_list) a027934_list
-- Reinhard Zumkeller, Oct 07 2012

[2^n - Fibonacci(n+1): n in [0..35]]; // G. C. Greubel, Sep 27 2019

A027934:= proc(n) local K; K:= Matrix ([[2,0,0], [0,1,1], [0,1,0]])^n; K[1,1]-K[2,2] end: seq (A027934(n), n=0..31); # Alois P. Heinz, Jul 28 2008
a := n -> 2^n - combinat:-fibonacci(n+1): seq(a(n),n=0..31); # Peter Luschny, May 09 2015

nn=31; a:=1/(1-x-x^2); b:=1/(1-2x); CoefficientList[Series[a*x*(1+x*b), {x,0,nn}], x] (* Geoffrey Critzer, Jan 04 2014 *)
LinearRecurrence[{3,-1,-2}, {0,1,2}, 32] (* Jean-François Alcover, Jan 09 2016 *)
nxt[{a_,b_,c_}]:={b,c,3c-b-2a}; NestList[nxt,{0,1,2},40][[;;,1]] (* Harvey P. Dale, Feb 02 2025 *)

a(n)=2^n-fibonacci(n+1) \\ Charles R Greathouse IV, Jun 11 2015

[2^n - fibonacci(n+1) for n in (0..35)] # G. C. Greubel, Sep 27 2019

a(n) = Sum_{j=0..floor(n/2)} Sum_{k=0..n-2*j} binomial(n-j, n-2*j-k). - Paul Barry, Feb 07 2003
From Paul Barry, Jan 23 2004: (Start)
Row sums of A105809.
G.f.: x*(1-x)/((1-2*x)*(1-x-x^2)).
a(n) = 2^n - Fibonacci(n+1). (End) - corrected Apr 06 2006 and Oct 05 2012
a(n) = Sum_{j=0..n} Sum_{k=0..n} binomial(n-k, k+j). - Paul Barry, Aug 29 2004
a(n) = (Sum of (n+1)-th row of the triangle in A108617) / 2. - Reinhard Zumkeller, Jun 12 2005
a(n) = term (1,1) - term (2,2) in the 3 X 3 matrix [2,0,0; 0,1,1; 0,1,0]^n. - Alois P. Heinz, Jul 28 2008
a(n) = 2^n - A000045(n+1). - Geoffrey Critzer, Jan 04 2014
a(n) ~ 2^n. - Daniel Forgues, May 06 2015
From Bob Selcoe, Mar 29 2016: (Start)
a(n) = 2*a(n-1) + A000045(n-2).
a(n) = 4*a(n-2) + A000032(n-2). (End)
a(n) = 2^(n-1) - ( ((1+sqrt(5))/2)^n - ((1-sqrt(5))/2)^n)/sqrt(5). - Haider Ali Abdel-Abbas, Aug 17 2019

Simpler definition from Miklos Kristof, Nov 24 2003
Initial zero added by N. J. A. Sloane, Feb 13 2008
Definition fixed by Reinhard Zumkeller, Oct 07 2012

A128695 Number of compositions of n with parts in N which avoid the adjacent pattern 111.

Original entry on oeis.org

1, 1, 2, 3, 7, 13, 24, 46, 89, 170, 324, 618, 1183, 2260, 4318, 8249, 15765, 30123, 57556, 109973, 210137, 401525, 767216, 1465963, 2801115, 5352275, 10226930, 19541236, 37338699, 71345449, 136324309, 260483548, 497722578, 951030367

Offset: 0

Ralf Stephan, May 08 2007

nonn

			From _Gus Wiseman_, Jul 06 2020: (Start)
The a(0) = 1 through a(5) = 13 compositions:
  ()  (1)  (2)    (3)    (4)      (5)
           (1,1)  (1,2)  (1,3)    (1,4)
                  (2,1)  (2,2)    (2,3)
                         (3,1)    (3,2)
                         (1,1,2)  (4,1)
                         (1,2,1)  (1,1,3)
                         (2,1,1)  (1,2,2)
                                  (1,3,1)
                                  (2,1,2)
                                  (2,2,1)
                                  (3,1,1)
                                  (1,1,2,1)
                                  (1,2,1,1)
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..1000
S. Heubach and T. Mansour, Enumeration of 3-letter patterns in compositions, arXiv:math/0603285 [math.CO], 2006
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

Column k=0 of A232435.
Cf. A091616, A232432.
The matching version is A335464.
Contiguously (1,1)-avoiding compositions is A003242.
Contiguously (1,1)-matching compositions are A261983.
Compositions with some part > 2 are A008466
Compositions by number of adjacent equal parts are A106356.
Compositions where each part is adjacent to an equal part are A114901.
Compositions with adjacent parts coprime are A167606.
Compositions with equal parts contiguous are A274174.
Patterns contiguously matched by compositions are A335457.
Patterns contiguously matched by a given partition are A335516.
Cf. A005251, A032020, A131044, A178470, A242882, A333175, A335455.

b:= proc(n, t) option remember; `if`(n=0, 1, add(`if`(abs(t)<>j,
       b(n-j, j), `if`(t=-j, 0, b(n-j, -j))), j=1..n))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..40);  # Alois P. Heinz, Nov 23 2013

nn=33;CoefficientList[Series[1/(1-Sum[(x^i+x^(2i))/(1+x^i+x^(2i)),{i,1,nn}]),{x,0,nn}],x] (* Geoffrey Critzer, Nov 23 2013 *)
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!MatchQ[#,{_,x_,x_,x_,_}]&]],{n,13}] (* Gus Wiseman, Jul 06 2020 *)

G.f.: 1/(1-Sum(i>=1, x^i*(1+x^i)/(1+x^i*(1+x^i)) ) ).
a(n) ~ c * d^n, where d is the root of the equation Sum_{k>=1} 1/(d^k + 1/(1 + d^k)) = 1, d=1.9107639262818041675000243699745706859615884029961947632387839..., c=0.4993008137128378086219448701860326113802027003939127932922782... - Vaclav Kotesovec, May 01 2014, updated Jul 07 2020
For n>=2, a(n) = A091616(n) + A003242(n). - Vaclav Kotesovec, Jul 07 2020

A050231 a(n) is the number of n-tosses having a run of 3 or more heads for a fair coin (i.e., probability is a(n)/2^n).

Original entry on oeis.org

0, 0, 1, 3, 8, 20, 47, 107, 238, 520, 1121, 2391, 5056, 10616, 22159, 46023, 95182, 196132, 402873, 825259, 1686408, 3438828, 6999071, 14221459, 28853662, 58462800, 118315137, 239186031, 483072832, 974791728, 1965486047, 3960221519, 7974241118, 16047432332, 32276862265

Offset: 1

Eric W. Weisstein

a(n-1) is the number of compositions of n with at least one part >= 4. - Joerg Arndt, Aug 06 2012

W. Feller, An Introduction to Probability Theory and Its Applications, Vol. 1, 2nd ed. New York: Wiley, p. 300, 1968.

T. D. Noe, Table of n, a(n) for n = 1..300
David Broadhurst, Multiple Landen values and the tribonacci numbers, arXiv:1504.05303 [hep-th], 2015.
Simon Cowell, A Formula for the Reliability of a d-dimensional Consecutive-k-out-of-n:F System, arXiv preprint arXiv:1506.03580 [math.CO], 2015.
Erich Friedman, Illustration of initial terms
T. Langley, J. Liese, and J. Remmel, Generating Functions for Wilf Equivalence Under Generalized Factor Order, J. Int. Seq. 14 (2011) # 11.4.2.
Eric Weisstein's World of Mathematics, Run
Index entries for linear recurrences with constant coefficients, signature (3,-1,-1,-2).

Cf. A000073, A008466, A050232, A050233.

Column 4 of A109435.

R:= PowerSeriesRing(Integers(), 60);
[0,0] cat Coefficients(R!( x^3/((1-2*x)*(1-x-x^2-x^3)) )); // G. C. Greubel, Jun 01 2025

LinearRecurrence[{3, -1, -1, -2}, {0, 0, 1, 3}, 50] (* David Nacin, Mar 07 2012 *)

concat([0,0], Vec(1/(1-2*x)/(1-x-x^2-x^3)+O(x^99))) \\ Charles R Greathouse IV, Feb 03 2015

def a(n, adict={0:0, 1:0, 2:1, 3:3}):
    if n in adict:
        return adict[n]
    adict[n]=3*a(n-1)-a(n-2)-a(n-3)-2*a(n-4)
    return adict[n] # David Nacin, Mar 07 2012

def A050231_list(prec):
    P.= PowerSeriesRing(QQ, prec)
    return P( x^3/((1-2*x)*(1-x-x^2-x^3)) ).list()
a=A050231_list(41); a[1:] # G. C. Greubel, Jun 01 2025

a(n) = 2^n - tribonacci(n+3), see A000073. - Vladeta Jovovic, Feb 23 2003
G.f.: x^3/((1-2*x)*(1-x-x^2-x^3)). - Geoffrey Critzer, Jan 29 2009
a(n) = 2 * a(n-1) + 2^(n-4) - a(n-4) since we can add T or H to a sequence of n-1 flips which has HHH, and H to one which ends in THH and does not have HHH among the first (n-4) flips. - Toby Gottfried, Nov 20 2010
a(n) = 3*a(n-1) - a(n-2) - a(n-3) - 2*a(n-4), a(0)=0, a(1)=0, a(2)=1, a(3)=3. - David Nacin, Mar 07 2012

A011794 Triangle defined by T(n+1, k) = T(n, k-1) + T(n-1, k), T(n,1) = 1, T(1,k) = 1, T(2,k) = min(2,k).

Original entry on oeis.org

1, 1, 2, 1, 2, 3, 1, 3, 4, 5, 1, 3, 6, 7, 8, 1, 4, 7, 11, 12, 13, 1, 4, 10, 14, 19, 20, 21, 1, 5, 11, 21, 26, 32, 33, 34, 1, 5, 15, 25, 40, 46, 53, 54, 55, 1, 6, 16, 36, 51, 72, 79, 87, 88, 89, 1, 6, 21, 41, 76, 97, 125, 133, 142, 143, 144, 1, 7, 22, 57, 92, 148, 176, 212, 221, 231, 232, 233

Offset: 1

N. J. A. Sloane and David Broadhurst

			matrix(10,10,n,k,a(n-1,k-1))
  [ 0 0 0 0 0 0 0 0 0 0 ]
  [ 0 1 1 1 1 1 1 1 1 1 ]
  [ 0 1 2 2 2 2 2 2 2 2 ]
  [ 0 1 2 3 3 3 3 3 3 3 ]
  [ 0 1 3 4 5 5 5 5 5 5 ]
  [ 0 1 3 6 7 8 8 8 8 8 ]
Triangle begins as:
  1;
  1, 2;
  1, 2,  3;
  1, 3,  4,  5;
  1, 3,  6,  7,  8;
  1, 4,  7, 11, 12, 13;
  1, 4, 10, 14, 19, 20, 21;
  1, 5, 11, 21, 26, 32, 33, 34;
  1, 5, 15, 25, 40, 46, 53, 54, 55;
  1, 6, 16, 36, 51, 72, 79, 87, 88, 89;

G. C. Greubel, Rows n = 1..100 of the triangle, flattened
D. J. Broadhurst, On the enumeration of irreducible k-fold Euler sums and their roles in knot theory and field theory, arXiv:hep-th/9604128, 1996.

Columns include A008619 and (essentially) A055802, A055803, A055804, A055805, A055806.
Right-hand columns 1-14 are A000045, A000071, A001911, A001924, A001891, A014162, A053808, A014166, A053809, A053739, A054469, A053295, A054470, A053296.
Essentially a reflected version of A055801.
Sums include: A039834 (signed row), A131913 (row).
Cf. A008466, A074878, A103609.

function T(n,k) // T = A011794(n,k)
  if k eq 1 or n eq 1 then return 1;
  elif n eq 2 then return Min(2, k);
  else return T(n-1,k-1) + T(n-2,k);
  end if;
end function;
[T(n,k): k in [1..n], n in [1..15]]; // G. C. Greubel, Oct 21 2024

T[n_, k_]:= T[n, k]= T[n-1, k-1] + T[n-2, k]; T[n_, 1] = 1; T[1, k_] = 1; T[2, k_] := Min[2, k]; Table[T[n, k], {n,15}, {k,n}]//Flatten (* Jean-François Alcover, Feb 26 2013 *)

T(n,k)=if(n<=0 || k<=0,0, if(n<=2 || k==1, min(n,k), T(n-1,k-1)+T(n-2,k)))

def T(n, k): # T = A011794
    if (k==1 or n==1): return 1
    elif (n==2): return min(2,k)
    else: return T(n-1, k-1) + T(n-2, k)
flatten([[T(n, k) for k in range(1,n+1)] for n in range(1,16)]) # G. C. Greubel, Oct 21 2024

T(n,n) = Fibonacci(n+1). - Jean-François Alcover, Feb 26 2013
From G. C. Greubel, Oct 21 2024: (Start)
Sum_{k=1..n} T(n, k) = A131913(n-1).
Sum_{k=1..n} (-1)^(k-1)*T(n, k) = A039834(n).
Sum_{k=1..floor((n+1)/2)} T(n-k+1,k) = (1/2)*((1-(-1)^n)*A074878((n+3)/2) + (1+(-1)^n)*A008466((n+6)/2)) (diagonal row sums).
Sum_{k=1..floor((n+1)/2)} (-1)^(k-1)*T(n-k+1,k) = (-1)^floor((n-1)/2)*A103609(n) + [n=1] (signed diagonal row sums). (End)

Entry improved by comments from Michael Somos

More terms added by G. C. Greubel, Oct 21 2024

A143291 Triangle T(n,k), n>=2, 0<=k<=n-2, read by rows: numbers of binary words of length n containing at least one subword 10^{k}1 and no subwords 10^{i}1 with i

Original entry on oeis.org

1, 3, 1, 8, 2, 1, 19, 4, 2, 1, 43, 8, 3, 2, 1, 94, 15, 5, 3, 2, 1, 201, 27, 9, 4, 3, 2, 1, 423, 48, 15, 6, 4, 3, 2, 1, 880, 84, 24, 10, 5, 4, 3, 2, 1, 1815, 145, 38, 16, 7, 5, 4, 3, 2, 1, 3719, 248, 60, 24, 11, 6, 5, 4, 3, 2, 1, 7582, 421, 94, 35, 17, 8, 6, 5, 4, 3, 2, 1, 15397, 710, 146, 51, 25, 12, 7, 6, 5, 4, 3, 2, 1

Offset: 2

Alois P. Heinz, Aug 04 2008

T(n,k) = number of subset S of {1,2,...,n+1} such that |S| > 1 and min(S*) = k, where S* is the set {x(2)-x(1), x(3)-x(2), ..., x(h+1)-x(h)} when the elements of S are written as x(1) < x(2) < ... < x(h+1); if max(S*) is used in place of min(S*), the result is the array at A255874. - Clark Kimberling, Mar 08 2015

			T (5,1) = 4, because there are 4 words of length 5 containing at least one subword 101 and no subword 11: 00101, 01010, 10100, 10101.
Triangle begins:
    1;
    3,  1;
    8,  2,  1;
   19,  4,  2, 1;
   43,  8,  3, 2, 1;
   94, 15,  5, 3, 2, 1;
  201, 27,  9, 4, 3, 2, 1;
  423, 48, 15, 6, 4, 3, 2, 1;

Alois P. Heinz, Rows n = 2..142, flattened

Columns k=0-10 give: A008466, A143281, A143282, A143283, A143284, A143285, A143286, A143287, A143288, A143289, A143290.
Row sums are in A000295.
Cf. A141539.

R:= PowerSeriesRing(Integers(), 50);
A143291:= func< n,k | Coefficient(R!( x^k/((x^(k-1) +x-1)*(x^k +x-1)) ), n) >;
[A143291(n,k): k in [2..n], n in [2..12]]; // G. C. Greubel, Jun 01 2025

as:= proc (n, k) option remember;
       if k=0 then 2^n
     elif n<=k and n>=0 then n+1
     elif n>0 then as(n-1, k) +as(n-k-1, k)
     else as(n+1+k, k) -as(n+k, k)
       fi
     end:
T:= (n, k)-> as(n, k) -as(n, k+1):
seq(seq(T(n, k), k=0..n-2), n=2..15);

as[n_, k_] := as[n, k] = Which[ k == 0, 2^n, n <= k && n >= 0, n+1, n > 0, as[n-1, k] + as[n-k-1, k], True, as[n+1+k, k] - as[n+k, k] ]; t [n_, k_] := as[n, k] - as[n, k+1]; Table[Table[t[n, k], {k, 0, n-2}], {n, 2, 14}] // Flatten (* Jean-François Alcover, Dec 11 2013, translated from Maple *)

@CachedFunction
def b(n,k):
    if k==0: return 2^n
    elif n <= k and n>=0: return n+1
    elif n>0: return b(n-1,k) + b(n-k-1,k)
    else: return b(n+k+1,k) - b(n+k,k)
def A143291(n,k): return b(n,k) - b(n,k+1)
print(flatten([[A143291(n,k) for k in range(n-1)] for n in range(2,16)])) # G. C. Greubel, Jun 01 2025

G.f. of column k: x^(k+2) / ((x^(k+1)+x-1)*(x^(k+2)+x-1)).

A143897 Triangle read by rows: T(n,k) = number of AVL trees of height n with k (leaf-) nodes, n>=0, fibonacci(n+2)<=k<=2^n.

Original entry on oeis.org

1, 1, 2, 1, 4, 6, 4, 1, 16, 32, 44, 60, 70, 56, 28, 8, 1, 128, 448, 864, 1552, 2720, 4288, 6312, 9004, 11992, 14372, 15400, 14630, 11968, 8104, 4376, 1820, 560, 120, 16, 1, 4096, 22528, 67584, 159744, 334080, 644992, 1195008, 2158912, 3811904, 6617184

Offset: 0

Alois P. Heinz, Sep 04 2008

			There are 2 AVL trees of height 2 with 3 (leaf-) nodes:
       o       o
      / \     / \
     o   N   N   o
    / \         / \
   N   N       N   N
Triangle begins:
  1
  . 1
  . . 2 1
  . . . . 4 6 4  1
  . . . . . . . 16 32 44 60 70  56  28   8    1
  . . . . . . .  .  .  .  .  . 128 448 864 1552 2720 ...

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 239, Eq 79, A_5.
D. E. Knuth, Art of Computer Programming, Vol. 3, Sect. 6.2.3 (7) and (8).

Alois P. Heinz, Rows n = 0..10, flattened
Ralf Hinze, Functional Pearls: Purely functional 1-2 brother trees, Journal of Functional Programming, 19(6):633-644, 2009, DOI: 10.1017/S0956796809007333.
R. C. Richards, Shape distribution of height-balanced trees, Info. Proc. Lett., 17 (1983), 17-20.
Wikipedia, AVL tree
Index entries for sequences related to rooted trees

Row sums give: A029758.
Column sums give: A006265.
Column sums of first 5 or 6 rows give: A036662 or A134306.
First elements of rows give: A174677.
First, last elements of columns give: A217299, A217300.
Row lengths give: 1+A008466(n).
Column heights give: A217710(k).
Triangle read by columns gives: A217298.
Cf. A000045, A000079.

T:= proc(n,k) local B, z; B:= proc(x,y,d) if d>=1 then x+B(x^2+2*x*y, x, d-1) else x fi end; if n=0 then if k=1 then 1 else 0 fi else coeff(B(z,0,n), z,k) -coeff(B(z,0,n-1), z,k) fi end: fib:= m-> (Matrix([[1,1], [1,0]])^m)[1,2]: seq(seq(T(n,k), k=fib(n+2)..2^n), n=0..6);

t[n_, k_] := Module[{ b, z }, b[x_, y_, d_] := If[d >= 1, x + b[x^2 + 2*x*y, x, d-1], x]; If[n == 0, If[k == 1, 1, 0], Coefficient[b[z, 0, n], z, k] - Coefficient [b[z, 0, n-1], z, k]]]; fib[m_] := MatrixPower[{{1, 1}, {1, 0}}, m][[1, 2]]; Table[Table[t[n, k], {k, fib[n+2], 2^n}], {n, 0, 6}] // Flatten (* Jean-François Alcover, Dec 05 2013, translated from Alois P. Heinz's Maple program *)

See program.

A335464 Number of compositions of n with a run of length > 2.

Original entry on oeis.org

0, 0, 0, 1, 1, 3, 8, 18, 39, 86, 188, 406, 865, 1836, 3874, 8135, 17003, 35413, 73516, 152171, 314151, 647051, 1329936, 2728341, 5587493, 11424941, 23327502, 47567628, 96879029, 197090007, 400546603, 813258276, 1649761070, 3343936929, 6772740076, 13707639491

Offset: 0

Gus Wiseman, Jul 06 2020

nonn

A composition of n is a finite sequence of positive integers summing to n.

Also compositions contiguously matching the pattern (1,1,1).

			The a(3) = 1 through a(7) = 18 compositions:
  (111)  (1111)  (1112)   (222)     (1114)
                 (2111)   (1113)    (1222)
                 (11111)  (3111)    (2221)
                          (11112)   (4111)
                          (11121)   (11113)
                          (12111)   (11122)
                          (21111)   (11131)
                          (111111)  (13111)
                                    (21112)
                                    (22111)
                                    (31111)
                                    (111112)
                                    (111121)
                                    (111211)
                                    (112111)
                                    (121111)
                                    (211111)
                                    (1111111)

Compositions contiguously avoiding (1,1) are A003242.
Compositions with some part > 2 are A008466.
Compositions by number of adjacent equal parts are A106356.
Compositions where each part is adjacent to an equal part are A114901.
Compositions contiguously avoiding (1,1,1) are A128695.
Compositions with adjacent parts coprime are A167606.
Compositions contiguously matching (1,1) are A261983.
Compositions with all equal parts contiguous are A274174.
Patterns contiguously matched by compositions are A335457.
Cf. A005251, A011782, A056986, A032020, A131044, A178470, A242882, A335455, A335458.

b:= proc(n, t) option remember; `if`(n=0, 1, add(`if`(abs(t)<>j,
       b(n-j, j), `if`(t=-j, 0, b(n-j, -j))), j=1..n))
    end:
a:= n-> ceil(2^(n-1))-b(n, 0):
seq(a(n), n=0..40);  # Alois P. Heinz, Jul 06 2020

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],MatchQ[#,{_,x_,x_,x_,_}]&]],{n,0,10}]
(* Second program: *)
b[n_, t_] := b[n, t] = If[n == 0, 1, Sum[If[Abs[t] != j,
     b[n - j, j], If[t == -j, 0, b[n - j, -j]]], {j, 1, n}]];
a[n_] := Ceiling[2^(n-1)] - b[n, 0];
a /@ Range[0, 40] (* Jean-François Alcover, May 21 2021, after Alois P. Heinz *)

a(n) = A011782(n) - A128695(n). - Alois P. Heinz, Jul 06 2020

a(23)-a(35) from Alois P. Heinz, Jul 06 2020

A217298 Triangle read by columns: T(n,k) = number of AVL trees of height n with k (leaf-) nodes, k>=1, A029837(k)<=n<A072649(k).

Original entry on oeis.org

1, 1, 2, 1, 4, 6, 4, 1, 16, 32, 44, 60, 70, 56, 128, 28, 448, 8, 864, 1, 1552, 2720, 4288, 6312, 9004, 11992, 4096, 14372, 22528, 15400, 67584, 14630, 159744, 11968, 334080, 8104, 644992, 4376, 1195008, 1820, 2158912, 560, 3811904, 120, 6617184, 16, 11307904

Offset: 1

Alois P. Heinz, Mar 17 2013

			There are 2 AVL trees of height 2 with 3 (leaf-) nodes:
       o       o
      / \     / \
     o   N   N   o
    / \         / \
   N   N       N   N
Triangle begins:
  1
  . 1
  . . 2 1
  . . . . 4 6 4  1
  . . . . . . . 16 32 44 60 70  56  28   8    1
  . . . . . . .  .  .  .  .  . 128 448 864 1552 2720 ...

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 239, Eq 79, A_5.
D. E. Knuth, Art of Computer Programming, Vol. 3, Sect. 6.2.3 (7) and (8).

Alois P. Heinz, Columns k = 1..1500, flattened
Ralf Hinze, Functional Pearls: Purely functional 1-2 brother trees, Journal of Functional Programming, 19(6):633-644, 2009, DOI: 10.1017/S0956796809007333.
R. C. Richards, Shape distribution of height-balanced trees, Info. Proc. Lett., 17 (1983), 17-20.
Wikipedia, AVL tree
Index entries for sequences related to rooted trees

Triangle read by rows gives: A143897.
Row sums give: A029758.
Column sums give: A006265.
First elements of rows give: A174677.
First, last elements of columns give: A217299, A217300.
Row lengths give: 1+A008466(n).
Column heights give: A217710(k).
Cf. A029837, A072649.

A353400 Number of integer compositions of n with all run-lengths > 2.

Original entry on oeis.org

1, 0, 0, 1, 1, 1, 2, 1, 2, 4, 4, 5, 11, 11, 14, 27, 29, 37, 61, 72, 97, 147, 181, 246, 368, 470, 632, 914, 1198, 1611, 2286, 3018, 4079, 5709, 7619, 10329, 14333, 19258, 26142, 36069, 48688, 66114, 90800, 122913, 167020, 228735, 310167, 421708, 576499, 782803

Offset: 0

Gus Wiseman, May 15 2022

nonn

			The a(7) = 1 through a(12) = 11 compositions:
  1111111   2222       333         22222        1112222       444
            11111111   111222      1111222      2222111       3333
                       222111      2221111      11111222      111333
                       111111111   1111111111   22211111      222222
                                                11111111111   333111
                                                              11112222
                                                              22221111
                                                              111111222
                                                              111222111
                                                              222111111
                                                              111111111111

Alois P. Heinz, Table of n, a(n) for n = 0..1000

The = 2 version is A003242 aerated.
The <= 1 version is A003242 ranked by A333489.
The version for parts instead of run-lengths is A078012, both A353428.
The version for partitions is A100405.
The > 1 version is A114901, ranked by A353427.
The <= 2 version is A128695, matching A335464.
A008466 counts compositions with some part > 2.
A011782 counts compositions.
A106356 counts compositions by number of adjacent equal parts.
A274174 counts compositions with equal parts contiguous.
A329738 counts uniform compositions, partitions A047966.
A329739 counts compositions with all distinct run-lengths.
Cf. A005811, A098859, A165413, A175413, A333755, A351013, A353390, A353391, A353401.

b:= proc(n, h) option remember; `if`(n=0, 1, add(
     `if`(i<>h, add(b(n-i*j, i), j=3..n/i), 0), i=1..n/3))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..50);  # Alois P. Heinz, May 17 2022

Table[Length[Select[Join@@Permutations/@ IntegerPartitions[n],!MemberQ[Length/@Split[#],1|2]&]],{n,0,15}]

a(21)-a(49) from Alois P. Heinz, May 17 2022

cp's OEIS Frontend

A101220 a(n) = Sum_{k=0..n} Fibonacci(n-k)*n^k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

SageMath

Formula

Extensions

A027934 a(0)=0, a(1)=1, a(2)=2; for n > 2, a(n) = 3*a(n-1) - a(n-2) - 2*a(n-3).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A128695 Number of compositions of n with parts in N which avoid the adjacent pattern 111.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A050231 a(n) is the number of n-tosses having a run of 3 or more heads for a fair coin (i.e., probability is a(n)/2^n).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Python

SageMath

Formula

A011794 Triangle defined by T(n+1, k) = T(n, k-1) + T(n-1, k), T(n,1) = 1, T(1,k) = 1, T(2,k) = min(2,k).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

SageMath

Formula

Extensions

A143291 Triangle T(n,k), n>=2, 0<=k<=n-2, read by rows: numbers of binary words of length n containing at least one subword 10^{k}1 and no subwords 10^{i}1 with i

Views

Author

Keywords

Comments

Examples

Links

A027934 a(0)=0, a(1)=1, a(2)=2; for n > 2, a(n) = 3a(n-1) - a(n-2) - 2a(n-3).