A000295 -id:A000295 - cp's OEIS frontend

A107907 Numbers having consecutive zeros or consecutive ones in binary representation.

3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77

Offset: 1

Reinhard Zumkeller, May 28 2005

Also positive integers whose binary expansion has cuts-resistance > 1. For the operation of shortening all runs by 1, cuts-resistance is the number of applications required to reach an empty word. - Gus Wiseman, Nov 27 2019

			From _Gus Wiseman_, Nov 27 2019: (Start)
The sequence of terms together with their binary expansions begins:
    3:      11
    4:     100
    6:     110
    7:     111
    8:    1000
    9:    1001
   11:    1011
   12:    1100
   13:    1101
   14:    1110
   15:    1111
   16:   10000
   17:   10001
   18:   10010
(End)

Amiram Eldar, Table of n, a(n) for n = 1..10000

Union of A003754 and A003714.
Complement of A000975.
Cf. A000120, A007088, A070939, A107909, A329862.

Select[Range[100],MatchQ[IntegerDigits[#,2],{_,x_,x_,_}]&] (* Gus Wiseman, Nov 27 2019 *)
Select[Range[80],SequenceCount[IntegerDigits[#,2],{x_,x_}]>0&] (* or *) Complement[Range[85],Table[FromDigits[PadRight[{},n,{1,0}],2],{n,7}]] (* Harvey P. Dale, Jul 31 2021 *)

def A107907(n): return (m:=n-2+(k:=(3*n+3).bit_length()))+(m>=(1<Chai Wah Wu, Apr 21 2025

a(A000247(n)) = A000225(n+2).
a(A000295(n+2)) = A000079(n+2).
a(A000325(n+2)) = A000051(n+2) for n>0.
a(n) = m+1 if m >= floor(2^k/3) otherwise a(n) = m where k = floor(log_2(3*(n+1))) and m = n-2+k. - Chai Wah Wu, Apr 21 2025

Offset changed to 1 by Chai Wah Wu, Apr 21 2025

A126885 T(n,k) = n*T(n,k-1) + k, with T(n,1) = 1, square array read by ascending antidiagonals (n >= 0, k >= 1).

Original entry on oeis.org

1, 1, 2, 1, 3, 3, 1, 4, 6, 4, 1, 5, 11, 10, 5, 1, 6, 18, 26, 15, 6, 1, 7, 27, 58, 57, 21, 7, 1, 8, 38, 112, 179, 120, 28, 8, 1, 9, 51, 194, 453, 543, 247, 36, 9, 1, 10, 66, 310, 975, 1818, 1636, 502, 45, 10, 1, 11, 83, 466, 1865, 4881, 7279, 4916, 1013, 55, 11

Offset: 0

Gary W. Adamson, Dec 30 2006

			Square array begins:
  n\k | 1   2   3   4    5     6      7       8 ...
  -------------------------------------------------
    0 | 1   2   3   4    5     6      7       8 ... A000027
    1 | 1   3   6  10   15    21     28      36 ... A000217
    2 | 1   4  11  26   57   120    247     502 ... A000295
    3 | 1   5  18  58  179   543   1636    4916 ... A000340
    4 | 1   6  27 112  453  1818   7279   29124 ... A014825
    5 | 1   7  38 194  975  4881  24412  122068 ... A014827
    6 | 1   8  51 310 1865 11196  67183  403106 ... A014829
    7 | 1   9  66 466 3267 22875 160132 1120932 ... A014830
    8 | 1  10  83 668 5349 42798 342391 2739136 ... A014831
    ...

Antidiagonal sums are A134195.
Main diagonal gives A062805.
Cf. A000027, A000217, A000295, A000340, A014825, A014827, A014829, A014830, A014831.

T(n, k) := if k = 1 then 1 else n*T(n, k - 1) + k$
create_list(T(n - k + 1, k), n, 0, 20, k, 1, n + 1);
/* Franck Maminirina Ramaharo, Jan 26 2019 */

T(1,k) = k*(k + 1)/2, and T(n,k) = (k - (k + 1)*n + n^(k + 1))/(n^2 - 2*n + 1) elsewhere.
T(n,k) = third entry in the vector M^k * (1, 0, 0), where M is the following 3 X 3 matrix:
  1, 0, 0
  1, 1, 0
  1, 1, n.

Edited and name clarified by Franck Maminirina Ramaharo, Jan 26 2019

A309049 Number T(n,k) of (binary) max-heaps on n elements from the set {0,1} containing exactly k 0's; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 1, 3, 3, 2, 1, 1, 1, 3, 4, 4, 2, 1, 1, 1, 4, 6, 6, 5, 2, 1, 1, 1, 4, 7, 8, 7, 5, 2, 1, 1, 1, 5, 10, 12, 11, 8, 5, 2, 1, 1, 1, 5, 11, 16, 17, 13, 9, 5, 2, 1, 1, 1, 6, 15, 23, 27, 24, 16, 10, 5, 2, 1, 1, 1, 6, 16, 27, 34, 34, 27, 18, 11, 5, 2, 1, 1

Offset: 0

Alois P. Heinz, Jul 09 2019

Also the number T(n,k) of (binary) min-heaps on n elements from the set {0,1} containing exactly k 1's.

The sequence of column k satisfies a linear recurrence with constant coefficients of order A063915(k).

			T(6,0) = 1: 111111.
T(6,1) = 3: 111011, 111101, 111110.
T(6,2) = 4: 110110, 111001, 111010, 111100.
T(6,3) = 4: 101001, 110010, 110100, 111000.
T(6,4) = 2: 101000, 110000.
T(6,5) = 1: 100000.
T(6,6) = 1: 000000.
T(7,4) = T(7,7-3) = A000108(3) = 5: 1010001, 1010010, 1100100, 1101000, 1110000.
Triangle T(n,k) begins:
  1;
  1, 1;
  1, 1,  1;
  1, 2,  1,  1;
  1, 2,  2,  1,  1;
  1, 3,  3,  2,  1,  1;
  1, 3,  4,  4,  2,  1,  1;
  1, 4,  6,  6,  5,  2,  1,  1;
  1, 4,  7,  8,  7,  5,  2,  1,  1;
  1, 5, 10, 12, 11,  8,  5,  2,  1, 1;
  1, 5, 11, 16, 17, 13,  9,  5,  2, 1, 1;
  1, 6, 15, 23, 27, 24, 16, 10,  5, 2, 1, 1;
  1, 6, 16, 27, 34, 34, 27, 18, 11, 5, 2, 1, 1;
  ...

Alois P. Heinz, Rows n = 0..200, flattened
Eric Weisstein's World of Mathematics, Heap
Wikipedia, Binary heap

Columns k=0-10 give: A000012, A110654, A114220 (for n>0), A326504, A326505, A326506, A326507, A326508, A326509, A326510, A326511.
Row sums give A091980(n+1).
T(2n,n) gives A309050.
Rows reversed converge to A000108.
Cf. A000225, A000295, A003095, A024358, A056971, A063915, A137560, A168542, A202019, A309051, A309052.

b:= proc(n) option remember; `if`(n=0, 1, (g-> (f-> expand(
      x^n+b(f)*b(n-1-f)))(min(g-1, n-g/2)))(2^ilog2(n)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n)):
seq(T(n), n=0..14);

b[n_] := b[n] = If[n == 0, 1, Function[g, Function[f, Expand[x^n + b[f]*b[n - 1 - f]]][Min[g - 1, n - g/2]]][2^Floor[Log[2, n]]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, n}]][b[n]];
T /@ Range[0, 14] // Flatten (* Jean-François Alcover, Oct 04 2019, after Alois P. Heinz *)

Sum_{k=0..n}    k  * T(n,k) = A309051(n).
Sum_{k=0..n} (n-k) * T(n,k) = A309052(n).
Sum_{k=0..2^n-1} T(2^n-1,k) = A003095(n+1).
Sum_{k=0..2^n-1} (2^n-1-k) * T(2^n-1,k) = A024358(n).
Sum_{k=0..n} (T(n,k) - T(n-1,k)) = A168542(n).
T(m,m-n) = A000108(n) for m >= 2^n-1 = A000225(n).
T(2^n-1,k) = A202019(n+1,k+1).

A000460 Eulerian numbers (Euler's triangle: column k=3 of A008292, column k=2 of A173018).

Original entry on oeis.org

1, 11, 66, 302, 1191, 4293, 14608, 47840, 152637, 478271, 1479726, 4537314, 13824739, 41932745, 126781020, 382439924, 1151775897, 3464764515, 10414216090, 31284590870, 93941852511, 282010106381, 846416194536, 2540053889352, 7621839388981, 22869007827143

Offset: 3

N. J. A. Sloane, Mira Bernstein, Robert G. Wilson v

There are 2 versions of Euler's triangle:
* A008292 Classic version of Euler's triangle used by Comtet (1974).
* A173018 Version of Euler's triangle used by Graham, Knuth and Patashnik in Concrete Math. (1990).
Euler's triangle rows and columns indexing conventions:
* A008292 The rows and columns of the Eulerian triangle are both indexed starting from 1. (Classic version: used in the classic books by Riordan and Comtet.)
* A173018 The rows and columns of the Eulerian triangle are both indexed starting from 0. (Graham et al.)
Number of permutations of [n] with exactly 2 descents. - Mike Zabrocki, Nov 10 2004

L. Comtet, "Permutations by Number of Rises; Eulerian Numbers." §6.5 in Advanced Combinatorics: The Art of Finite and Infinite Expansions, rev. enl. ed. Dordrecht, Netherlands: Reidel, pp. 51 and 240-246, 1974.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 243.
F. N. David and D. E. Barton, Combinatorial Chance. Hafner, NY, 1962, p. 151.
F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 260.
J. B. Remmel et al., The combinatorial properties of the Benoumhani polynomials for the Whitney numbers of Dowling lattices, Discrete Math., 342 (2019), 2966-2983. See page 2981.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 215.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 3..1000
E. Banaian, S. Butler, C. Cox, J. Davis, J. Landgraf and S. Ponce A generalization of Eulerian numbers via rook placements, arXiv:1508.03673 [math.CO], 2015.
L. Carlitz et al., Permutations and sequences with repetitions by number of increases, J. Combin. Theory, 1 (1966), 350-374.
E. T. Frankel, A calculus of figurate numbers and finite differences, American Mathematical Monthly, 57 (1950), 14-25. [Annotated scanned copy]
Wayne A. Johnson, An Euler operator approach to Ehrhart series, arXiv:2303.16991 [math.CO], 2023.
J. C. P. Miller, Letter to N. J. A. Sloane, Mar 26 1971
O. J. Munch, Om potensproduktsummer [Norwegian, English summary], Nordisk Matematisk Tidskrift, 7 (1959), 5-19. [Annotated scanned copy]
O. J. Munch, Om potensproduktsummer [ Norwegian, English summary ], Nordisk Matematisk Tidskrift, 7 (1959), 5-19.
Nagatomo Nakamura, Pseudo-Normal Random Number Generation via the Eulerian Numbers, Josai Mathematical Monographs, vol 8, pp. 85-95, 2015.
P. A. Piza, Kummer numbers, Mathematics Magazine, 21 (1947/1948), 257-260.
P. A. Piza, Kummer numbers, Mathematics Magazine, 21 (1947/1948), 257-260. [Annotated scanned copy]
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
J. Riordan, Review of Frankel (1950) [Annotated scanned copy]
Sittipong Thamrongpairoj, Dowling Set Partitions, and Positional Marked Patterns, Ph. D. Dissertation, University of California-San Diego (2019).
Eric Weisstein's World of Mathematics, Eulerian Number
Robert G. Wilson v, Letter to N. J. A. Sloane, Apr. 1994
Index entries for linear recurrences with constant coefficients, signature (10,-40,82,-91,52,-12).

Cf. A008292 (classic version of Euler's triangle used by Comtet (1974)).
Cf. A173018 (version of Euler's triangle used by Graham, Knuth and Patashnik in Concrete Math. (1990)).
Cf. A000295.

[3^n-(n+1)*2^n+(1/2)*n*(n+1): n in [3..30]]; // Vincenzo Librandi, Apr 18 2017

[EulerianNumber(n, 2): n in [3..40]]; // G. C. Greubel, Oct 02 2024

A000460:=-z*(-1-z+4*z**2)/(-1+3*z)/(2*z-1)**2/(z-1)**3; # Simon Plouffe in his 1992 dissertation

k = 3; Table[k^(n+k-1) + Sum[(-1)^i/i!*(k-i)^(n+k-1) * Product[n+k+1-j, {j, 1, i}], {i, k-1}], {n, 23}] (* or *)
Array[3^(# + 2) - (# + 3)*2^(# + 2) + (1/2)*(# + 2)*(# + 3) &, 23] (* Michael De Vlieger, Aug 04 2015, after PARI *)

A000460(n) = 3^(n+2)-(n+3)*2^(n+2)+(1/2)*(n+2)*(n+3)

def A000460(n): return 3^n - (n+1)*2^n + binomial(n+1,2)
[A000460(n) for n in range(3,31)] # G. C. Greubel, Oct 02 2024

a(n) = 3^n - (n+1)*2^n + (1/2)*n*(n+1). - Randall L Rathbun, Jan 22 2002
G.f.: x^3*(1+x-4*x^2)/((1-x)^3*(1-2*x)^2*(1-3*x)). - Mike Zabrocki, Nov 10 2004
E.g.f.: exp(x)*(exp(2*x) - (1 + 2*x)*exp(x) + x + x^2/2). - Wolfdieter Lang, Apr 17 2017

More terms from Christian G. Bower, May 12 2000

More terms from Mike Zabrocki, Nov 10 2004

A079583 a(n) = 3*2^n - n - 2.

Original entry on oeis.org

1, 3, 8, 19, 42, 89, 184, 375, 758, 1525, 3060, 6131, 12274, 24561, 49136, 98287, 196590, 393197, 786412, 1572843, 3145706, 6291433, 12582888, 25165799, 50331622, 100663269, 201326564, 402653155, 805306338, 1610612705, 3221225440

Offset: 0

Benoit Cloitre, Jan 25 2003

Row sums of A132110. - Gary W. Adamson, Aug 09 2007
Consider the infinite sequence of strings x(1) = a, x(2) = aba, x(3) = ababbaba, ..., where x(n+1) = x(n).b^{n+1}.x(n), for n >= 1. Each x(n), for n >= 2, has borders x(1), x(2), ..., x(n-1), none of which cover x(n). The length of x(n+1) is 3*2^n-n-2. - William F. Smyth, Feb 29 2012
Number of edges in the rooted tree g[n] (n>=0) defined recursively in the following manner: denoting by P[n] the path on n vertices, we define g[0] =P[2] while g[n] (n>=1) is the tree obtained by identifying the roots of 2 copies of g[n-1] and one of the end-vertices of P[n+1]; the root of g[n] is defined to be the other end-vertex of P[n+1]. Roughly speaking, g[4], for example, is obtained from the planted full binary tree of height 5 by replacing the edges at the levels 1,2,3,4 with paths of lengths 4, 3, 2, and 1, respectively. - Emeric Deutsch, Aug 08 2013

T. Flouri, C. S. Iliopoulos, T. Kociumaka, S. P. Pissis, S. J. Puglisi, W. F. Smyth, W. Tyczynski, New and efficient approaches to the quasiperiodic characterization of a string, Proc. Prague Stringology Conf., 2012, 75-88.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Tomas Flouri, Costas S. Iliopoulos, Solon P. Pissis, W. F. Smyth, On approximate string covering (draft, 2012).
Index entries for linear recurrences with constant coefficients, signature (4,-5,2).

Cf. A000295, A132110, A227712, A083329 (first differences).

I:=[1, 3, 8]; [n le 3 select I[n] else 4*Self(n-1)-5*Self(n-2)+2*Self(n-3): n in [1..40]]; // Vincenzo Librandi, Jun 23 2012

lst={};Do[AppendTo[lst, 3*2^n-n-2], {n, 0, 4!}];lst (* Vladimir Joseph Stephan Orlovsky, Oct 25 2008 *)
LinearRecurrence[{4,-5,2},{1,3,8},40] (* Vincenzo Librandi, Jun 23 2012 *)

a(n)=3<Charles R Greathouse IV, Feb 29 2012

a(0)=1, a(n) = 2*a(n-1) + n;
Binomial transform of [1, 2, 3, 3, 3, ...]. - Gary W. Adamson, Aug 09 2007
G.f.: (x^2-x+1)/((1-2*x)*(1-x)^2) = 3*U(0)x, where U(k) = 1 - (k+2)/(3*2^k - 18*x*4^k/(6*x*2^k - (k+2)/U(k+1))); (continued fraction, 3-step). - Sergei N. Gladkovskii, Jul 04 2012
a(n) = (A227712(n) - 1)/3 - Emeric Deutsch, Feb 18 2016
a(n) = A007283(n) - n - 2. - Miquel Cerda, Aug 07 2016
a(n) = A000225(n) + A000325(n). - Miquel Cerda, Aug 08 2016

A124324 Triangle read by rows: T(n,k) is the number of partitions of an n-set having k blocks of size > 1 (0<=k<=floor(n/2)).

Original entry on oeis.org

1, 1, 1, 1, 1, 4, 1, 11, 3, 1, 26, 25, 1, 57, 130, 15, 1, 120, 546, 210, 1, 247, 2037, 1750, 105, 1, 502, 7071, 11368, 2205, 1, 1013, 23436, 63805, 26775, 945, 1, 2036, 75328, 325930, 247555, 27720, 1, 4083, 237127, 1561516, 1939630, 460845, 10395, 1, 8178

Offset: 0

Emeric Deutsch, Oct 28 2006

Row sums are the Bell numbers (A000110).
It appears that the triangles in this sequence and A112493 have identical columns, except for shifts. - Jörgen Backelin, Jun 20 2022
Equivalent to Jörgen Backelin's observation, the rows of A112493 may be read off as the diagonals of this entry. - Tom Copeland, Sep 24 2022

			T(4,2) = 3 because we have 12|34, 13|24 and 14|23 (if we take {1,2,3,4} as our 4-set).
Triangle starts:
  1;
  1;
  1,    1;
  1,    4;
  1,   11,     3;
  1,   26,    25;
  1,   57,   130,    15;
  1,  120,   546,   210;
  1,  247,  2037,  1750,   105;
  1,  502,  7071, 11368,  2205;
  1, 1013, 23436, 63805, 26775, 945;
  ...

Alois P. Heinz, Rows n = 0..200, flattened
Per Alexandersson and Olivia Nabawanda, Peaks are preserved under run-sorting, arXiv:2104.04220 [math.CO], 2021.
Fufa Beyene and Roberto Mantaci, Merging-Free Partitions and Run-Sorted Permutations, arXiv:2101.07081 [math.CO], 2021.
Tom Copeland, Appell-Bell polynomials: Linking the associated Bell polynomials and the associated reduced inverse refined Eulerian polynomials, 2022.
Tom Copeland, The reduced inverse refined Eulerian polynomials and associated arrays, 2022.
Robin Houston, Adam P. Goucher, and Nathaniel Johnston, A New Formula for the Determinant and Bounds on Its Tensor and Waring Ranks, arXiv:2301.06586 [math.CO], 2023.
O. Nabawanda, F. Rakotondrajao, and A. S. Bamunoba, Run Distribution Over Flattened Partitions, arXiv:2007.03821 [math.CO], 2020.

Columns k=0-10 give: A000012, A000295, A112495, A112496, A112497, A290034, A290035, A290036, A290037, A290038, A290039.

Cf. A000110, A001147, A048993, A124323, A124325, A136394, A112493.

G:=exp(t*exp(z)-t+(1-t)*z): Gser:=simplify(series(G,z=0,36)): for n from 0 to 33 do P[n]:=sort(n!*coeff(Gser,z,n)) od: for n from 0 to 13 do seq(coeff(P[n],t,k),k=0..floor(n/2)) od; # yields sequence in triangular form
# second Maple program:
b:= proc(n) option remember; expand(`if`(n=0, 1, add(
      `if`(i>1, x, 1)*binomial(n-1, i-1)*b(n-i), i=1..n)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n)):
seq(T(n), n=0..15);  # Alois P. Heinz, Mar 08 2015, Jul 15 2017

multinomial[n_, k_List] := n!/Times @@ (k!); b[n_, i_] :=  b[n, i] = Expand[If[n == 0, 1, If[i<1, 0, Sum[multinomial[n, Join[{n-i*j}, Array[i&, j]]]/j!*b[n-i*j, i-1]*If[i>1, x^j, 1], {j, 0, n/i}]]]]; T[n_] := Function[{p}, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][b[n, n]]; Table[T[n], {n, 0, 15}] // Flatten (* Jean-François Alcover, May 22 2015, after Alois P. Heinz *)

E.g.f.: G(t,z) = exp(t*exp(z) - t + (1-t)*z).
T(n,1) = A000295(n) (the Eulerian numbers).
Sum_{k=0..floor(n/2)} k*T(n,k) = A124325(n).
T(2n,n) = A001147(n). - Alois P. Heinz, Apr 06 2018

A125128 a(n) = 2^(n+1) - n - 2, or partial sums of main diagonal of array A125127 of k-step Lucas numbers.

Original entry on oeis.org

1, 4, 11, 26, 57, 120, 247, 502, 1013, 2036, 4083, 8178, 16369, 32752, 65519, 131054, 262125, 524268, 1048555, 2097130, 4194281, 8388584, 16777191, 33554406, 67108837, 134217700, 268435427, 536870882, 1073741793, 2147483616, 4294967263, 8589934558

Offset: 1

Jonathan Vos Post, Nov 22 2006

Essentially a duplicate of A000295: a(n) = A000295(n+1).
Partial sums of main diagonal of array A125127 = L(k,n): k-step Lucas numbers, read by antidiagonals.
Equals row sums of triangle A130128. - Gary W. Adamson, May 11 2007
Row sums of triangle A130330 which is composed of (1,3,7,15,...) in every column, thus: row sums of (1; 3,1; 7,3,1; ...). - Gary W. Adamson, May 24 2007
Row sums of triangle A131768. - Gary W. Adamson, Jul 13 2007
Convolution A130321 * (1, 2, 3, ...). Binomial transform of (1, 3, 4, 4, 4, ...). - Gary W. Adamson, Jul 27 2007
Row sums of triangle A131816. - Gary W. Adamson, Jul 30 2007
A000975 convolved with [1, 2, 2, 2, ...]. - Gary W. Adamson, Jun 02 2009
The eigensequence of a triangle with the triangular series as the left border and the rest 1's. - Gary W. Adamson, Jul 24 2010

			a(1) = 1 because "1-step Lucas number"(1) = 1.
a(2) = 4 = a(1) + [2-step] Lucas number(2) = 1 + 3.
a(3) = 11 = a(2) + 3-step Lucas number(3) = 1 + 3 + 7.
a(4) = 26 = a(3) + 4-step Lucas number(4) = 1 + 3 + 7 + 15.
a(5) = 57 = a(4) + 5-step Lucas number(5) = 1 + 3 + 7 + 15 + 31.
a(6) = 120 = a(5) + 6-step Lucas number(6) = 1 + 3 + 7 + 15 + 31 + 63.
G.f. = x + 4*x^2 + 11*x^3 + 26*x^4 + 57*x^5 + 120*x^6 + 247*x^7 + 502*x^8 + ...

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Dillan Agrawal, Selena Ge, Jate Greene, Tanya Khovanova, Dohun Kim, Rajarshi Mandal, Tanish Parida, Anirudh Pulugurtha, Gordon Redwine, Soham Samanta, and Albert Xu, Chip-Firing on Infinite k-ary Trees, arXiv:2501.06675 [math.CO], 2025. See p. 18.
Index entries for linear recurrences with constant coefficients, signature (4,-5,2).

Cf. A000295, A125127, A125129, A130103.

List([1..40], n-> 2^(n+1) -n-2); # G. C. Greubel, Jul 26 2019

I:=[1, 4, 11]; [n le 3 select I[n] else 4*Self(n-1)-5*Self(n-2)+2*Self(n-3): n in [1..40]]; // Vincenzo Librandi, Jun 28 2012

CoefficientList[Series[1/((1-x)^2*(1-2*x)),{x,0,40}],x] (* Vincenzo Librandi, Jun 28 2012 *)
LinearRecurrence[{4,-5,2},{1,4,11},40] (* Harvey P. Dale, Nov 16 2014 *)
a[ n_] := With[{m = n + 1}, If[ m < 0, 0, 2^m - (1 + m)]]; (* Michael Somos, Aug 17 2015 *)

PARI
```
A125128(n)=2<M. F. Hasler, Jul 30 2015
```

{a(n) = n++; if( n<0, 0, 2^n - (1+n))}; /* Michael Somos, Aug 17 2015 */

[2^(n+1) -n-2 for n in (1..40)] # G. C. Greubel, Jul 26 2019

a(n) = A000295(n+1) = 2^(n+1) - n - 2 = Sum_{i=1..n} A125127(i,i) = Sum_{i=1..n} ((2^i)-1). [Edited by M. F. Hasler, Jul 30 2015]
From Colin Barker, Jun 17 2012: (Start)
a(n) = 4*a(n-1) - 5*a(n-2) + 2*a(n-3).
G.f.: x/((1-x)^2*(1-2*x)). (End)
a(n) = A000225(n) + A000325(n) - 1. - Miquel Cerda, Aug 07 2016
a(n) = A095151(n) - A000225(n). - Miquel Cerda, Aug 12 2016
E.g.f.: 2*exp(2*x) - (2+x)*exp(x). - G. C. Greubel, Jul 26 2019

Edited by M. F. Hasler, Jul 30 2015

A243827 Number A(n,k) of Dyck paths of semilength n having exactly one occurrence of the consecutive step pattern given by the binary expansion of k, where 1=U=(1,1) and 0=D=(1,-1); square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 3, 1, 0, 0, 0, 0, 1, 4, 6, 1, 0, 0, 0, 0, 1, 2, 11, 10, 1, 0, 0, 0, 0, 0, 4, 6, 26, 15, 1, 0, 0, 0, 0, 0, 1, 11, 16, 57, 21, 1, 0, 0, 0, 0, 0, 1, 4, 26, 45, 120, 28, 1, 0, 0, 0, 0, 1, 1, 5, 15, 57, 126, 247, 36, 1, 0, 0

Offset: 0

Alois P. Heinz, Jun 11 2014

			Square array A(n,k) begins:
  0, 0, 0,  0,   0,    0,   0,    0,    0,    0, ...
  1, 1, 1,  0,   0,    0,   0,    0,    0,    0, ...
  0, 0, 1,  1,   1,    1,   1,    0,    0,    0, ...
  0, 0, 1,  3,   4,    2,   4,    1,    1,    1, ...
  0, 0, 1,  6,  11,    6,  11,    4,    5,    5, ...
  0, 0, 1, 10,  26,   16,  26,   15,   21,   17, ...
  0, 0, 1, 15,  57,   45,  57,   50,   78,   54, ...
  0, 0, 1, 21, 120,  126, 120,  161,  274,  177, ...
  0, 0, 1, 28, 247,  357, 247,  504,  927,  594, ...
  0, 0, 1, 36, 502, 1016, 502, 1554, 3061, 1997, ...

Alois P. Heinz, antidiagonals n = 0..140, flattened

Columns k=2-10 give: A000012(n) for n>0, A000217(n-1) for n>0, A000295(n-1) for n>0, A005717(n-1) for n>1, A000295(n-1) for n>0, A014532(n-2) for n>2, A108863, A244235, A244236.
Main diagonal gives A243770 or column k=1 of A243752.
Cf. A243753, A243828, A243829, A243830, A243831, A243832, A243833, A243834, A243835, A243836.

A047520 a(n) = 2*a(n-1) + n^2, a(0) = 0.

Original entry on oeis.org

0, 1, 6, 21, 58, 141, 318, 685, 1434, 2949, 5998, 12117, 24378, 48925, 98046, 196317, 392890, 786069, 1572462, 3145285, 6290970, 12582381, 25165246, 50331021, 100662618, 201325861, 402652398, 805305525, 1610611834, 3221224509

Offset: 0

Henry Bottomley, Jul 04 2000

Convolution of squares (A000290) and powers of 2 (A000079). - Graeme McRae, Jun 07 2006
Antidiagonal sums of the convolution array A213568. - Clark Kimberling, Jun 18 2012
This is the partial sums of A050488. - J. M. Bergot, Oct 01 2012
From Peter Bala, Nov 29 2012: (Start)
This is the case m = 2 of the recurrence a(n) = m*a(n-1) + n^m, m = 1,2,..., with a(0) = 0.
The recurrence has the solution a(n) = m^n*Sum_{i=1..n} i^m/m^i and has the o.g.f. A(m,x)/((1-m*x)*(1-x)^(m+1)), where A(m,x) denotes the m-th Eulerian polynomial of A008292.
For other cases see A000217 (m = 1), A066999 (m = 3) and A067534 (m = 4).
(End)
Convolution of A000225 with A005408. - J. M. Bergot, Sep 19 2017

Vincenzo Librandi, Table of n, a(n) for n = 0..3000
Filippo Disanto, Some Statistics on the Hypercubes of Catalan Permutations, Journal of Integer Sequences, Vol. 18 (2015), Article 15.2.2.
Index entries for linear recurrences with constant coefficients, signature (5,-9,7,-2).

Cf. A000295. A000217, A008292, A066999, A067534.

List([0..30], n-> 6*2^n -(n^2+4*n+6)); # G. C. Greubel, Jul 25 2019

a047520 n = sum $ zipWith (*)
                  (reverse $ take n $ tail a000290_list) a000079_list
-- Reinhard Zumkeller, Nov 30 2012

[ 6*2^n-n^2-4*n-6: n in [0..30]]; // Vincenzo Librandi, Aug 22 2011

RecurrenceTable[{a[0]==0,a[n]==2a[n-1]+n^2},a[n],{n,30}] (* or *) LinearRecurrence[{5,-9,7,-2},{0,1,6,21},31] (* Harvey P. Dale, Aug 21 2011 *)
f[n_]:= 2^n*Sum[i^2/2^i, {i, n}]; Array[f, 30] (* Robert G. Wilson v, Nov 28 2012 *)

vector(30, n, n--; 6*2^n -(n^2+4*n+6)) \\ G. C. Greubel, Jul 25 2019

[6*2^n -(n^2+4*n+6) for n in (0..30)] # G. C. Greubel, Jul 25 2019

a(n) = 6*2^n - n^2 - 4*n - 6 = 6*A000225(n) - A028347(n+2).
a(n) = 2^n*Sum_{i=1..n} i^2 / 2^i. - Benoit Cloitre, Jan 27 2002
a(0)=0, a(1)=1, a(2)=6, a(3)=21, a(n) = 5*a(n-1) - 9*a(n-2) + 7*a(n-3) - 2*a(n-4). - Harvey P. Dale, Aug 21 2011
G.f.: x*(1+x)/((1-x)^3*(1-2*x)). - Harvey P. Dale, Aug 21 2011
a(n) = Sum_{k=0..n-1} A000079(n-k) * A000290(k). - Reinhard Zumkeller, Nov 30 2012
E.g.f.: 6*exp(2*x) -(6 +5*x +x^2)*exp(x). - G. C. Greubel, Jul 25 2019

A095151 a(n+3) = 3a(n+2) - 2a(n+1) + 1 with a(0)=0, a(1)=2.

Original entry on oeis.org

0, 2, 7, 18, 41, 88, 183, 374, 757, 1524, 3059, 6130, 12273, 24560, 49135, 98286, 196589, 393196, 786411, 1572842, 3145705, 6291432, 12582887, 25165798, 50331621, 100663268, 201326563, 402653154, 805306337, 1610612704, 3221225439

Offset: 0

Gary W. Adamson, May 30 2004

A sequence generated from a Bell difference row matrix, companion to A095150.
A095150 uses the same recursion rule but the multiplier [1 1 1] instead of [1 0 0].
For n>0, (a(n)) is row 2 of the convolution array A213568. - Clark Kimberling, Jun 20 2012
For n>0, (a(n)) is row 2 of the convolution array A213568. - Clark Kimberling, Jun 20 2012

			a(6) = 183 = 3*88 -2*41 + 1.

G. C. Greubel, Table of n, a(n) for n = 0..1000
Péter Burcsi, Gabriele Fici, Zsuzsanna Lipták, Rajeev Raman, and Joe Sawada, Generating a Gray code for prefix normal words in amortized polylogarithmic time per word, arXiv:2003.03222 [cs.DS], 2020.
Index entries for linear recurrences with constant coefficients, signature (4,-5,2).

Cf. A000110, A011971, A095149, A095150.

List([0..30], n-> 3*2^n -(n+3)); # G. C. Greubel, Jul 26 2019

[3*2^n -(n+3): n in [0..30]]; // G. C. Greubel, Jul 26 2019

Table[3*2^n -(n+3), {n,0,30}] (* G. C. Greubel, Jul 26 2019 *)

vector(30, n, n--; 3*2^n -(n+3)) \\ G. C. Greubel, Jul 26 2019

[3*2^n -(n+3) for n in (0..30)] # G. C. Greubel, Jul 26 2019

Let M = a 3 X 3 matrix having Bell triangle difference terms (A095149 is composed of differences of the Bell triangle A011971): (fill in the 3 X 3 matrix with zeros): [1 0 0 / 1 1 0 / 2 1 2] = M. Then M^n * [1 0 0] = [1 n a(n)]. E.g. a(4) = 41 since M^4 * [1 0 0] = [1 4 41].
a(n) = 3*2^n -(n+3) = 2*a(n-1) + n +1 = A000295(n+2) - A000079(n). For n>0, a(n) = A077802(n). - Henry Bottomley, Oct 25 2004
From Colin Barker, Apr 23 2012: (Start)
a(n) = 4*a(n-1) - 5*a(n-2) + 2*a(n-3).
G.f.: x*(2-x)/((1-x)^2*(1-2*x)). (End)
a(n) = A125128(n) + A000225(n). - Miquel Cerda, Aug 07 2016
a(n) = 2*A125128(n) - A000325(n) + 1. - Miquel Cerda, Aug 12 2016
a(n) = A125128(n) + A000325(n) + n - 1. - Miquel Cerda, Aug 27 2016
E.g.f.: 3*exp(2*x) - (3+x)*exp(x). - G. C. Greubel, Jul 26 2019
Let Prod_{i=0..n-1} (1+x^{2^i}+x^{2*2^i}) = Sum_{j=0..d} b_j x^j, where d=2^{n+1}-2. Then a(n) = Sum_{j=0..d-1} b_j/b_{j+1} (proved). - Richard Stanley, Aug 27 2019

Edited by Robert G. Wilson v, Jun 05 2004

Deleted a comment and file that were unrelated to this sequence. - N. J. A. Sloane, Aug 17 2025

cp's OEIS Frontend

A107907 Numbers having consecutive zeros or consecutive ones in binary representation.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A126885 T(n,k) = n*T(n,k-1) + k, with T(n,1) = 1, square array read by ascending antidiagonals (n >= 0, k >= 1).

Views

Author

Keywords

Examples

Crossrefs

Programs

Maxima

Formula

Extensions

A309049 Number T(n,k) of (binary) max-heaps on n elements from the set {0,1} containing exactly k 0's; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A000460 Eulerian numbers (Euler's triangle: column k=3 of A008292, column k=2 of A173018).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Magma

Maple

Mathematica

PARI

SageMath

Formula

Extensions

A079583 a(n) = 3*2^n - n - 2.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A124324 Triangle read by rows: T(n,k) is the number of partitions of an n-set having k blocks of size > 1 (0<=k<=floor(n/2)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A125128 a(n) = 2^(n+1) - n - 2, or partial sums of main diagonal of array A125127 of k-step Lucas numbers.

Views

A095151 a(n+3) = 3a(n+2) - 2a(n+1) + 1 with a(0)=0, a(1)=2.