cp's OEIS Frontend

Number of peaks at even level in all Dyck paths of semilength n+1. Example: a(2)=4 because UDUDUD, UDUU*DD, UU*DDUD, UU*DU*DD, UUUDDD, where U=(1,1), D=(1,-1) and the peaks at even level are shown by *. - Emeric Deutsch, Dec 05 2003

Also number of long ascents (i.e., ascents of length at least two) in all Dyck paths of semilength n+1. Example: a(2)=4 because in the five Dyck paths of semilength 3, namely UDUDUD, UD(UU)DD, (UU)DDUD, (UU)DUDD and (UUU)DDD, we have four long ascents (shown between parentheses). Here U=(1,1) and D=(1,-1). Also number of branch nodes (i.e., vertices of outdegree at least two) in all ordered trees with n+1 edges. - Emeric Deutsch, Feb 22 2004

Number of lattice paths from (0,0) to (n,n) with steps E=(1,0) and N=(0,1) which touch or cross the line x-y=1. Example: For n=2 these are the paths EENN, ENEN, ENNE and NEEN. - Herbert Kociemba, May 23 2004

Narayana transform (A001263) of [1, 3, 5, 7, 9, ...] = (1, 4, 15, 56, 210, ...). Row sums of triangles A136534 and A136536. - Gary W. Adamson, Jan 04 2008

Starting with offset 1 = the Catalan sequence starting (1, 2, 5, 14, ...) convolved with A000984: (1, 2, 6, 20, ...). - Gary W. Adamson, May 17 2009

Also number of peaks plus number of valleys in all Dyck n-paths. - David Scambler, Oct 08 2012

Apparently counts UDDUD in all Dyck paths of semilength n+2. - David Scambler, Apr 22 2013

Apparently the number of peaks strictly left of the midpoint in all Dyck paths of semilength n+1. - David Scambler, Apr 30 2013

For n>0, a(n) is the number of compositions of n into at most n parts if zeros are allowed as parts (so-called "weak" compositions). - L. Edson Jeffery, Jul 24 2014

Number of paths in the half-plane x >= 0, from (0,0) to (2n,2), and consisting of steps U=(1,1) and D=(1,-1). For example, for n=2, we have the 4 paths: UUUD, UUDU, UDUU, DUUU. - José Luis Ramírez Ramírez, Apr 19 2015

For n>1, 1/a(n) is the probability that when a stick is broken up at n points independently and uniformly chosen at random along its length any triple of pieces of the n+1 pieces can form a triangle. The corresponding probability for the existence of at least one triple is A339392(n)/A339393(n). - Amiram Eldar, Dec 04 2020

a(n) is the number of lattice paths of 2n steps taken from the step set {U=(1,1), D=(1,-1)} that start at the origin, never go below the x-axis, and end strictly above the x-axis; more succinctly, proper left factors of Dyck paths. For example, a(2)=4 counts UUUU, UUUD, UUDU, UDUU. - David Callan and Emeric Deutsch, Jan 25 2021

From Gus Wiseman, Jul 21 2021: (Start)

Also the number of integer compositions of 2n+1 with alternating sum -1, where the alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i. For example, the a(1) = 1 through a(3) = 15 compositions are:

(1,2) (2,3) (3,4)

(1,3,1) (1,4,2)

(1,1,1,2) (2,4,1)

(1,2,1,1) (1,1,2,3)

(1,2,2,2)

(1,3,2,1)

(2,1,1,3)

(2,2,1,2)

(2,3,1,1)

(1,1,1,3,1)

(1,2,1,2,1)

(1,3,1,1,1)

(1,1,1,1,1,2)

(1,1,1,2,1,1)

(1,2,1,1,1,1)

The following relate to these compositions.

- The unordered version is A000070.

- Allowing any negative alternating sum gives A000346.

- The opposite (positive 1) version is A000984.

- The version for reverse-alternating sum is also A001791 (this sequence).

- Taking alternating sum -2 instead of -1 gives A002054.

- The shifted version for alternating sum 0 is counted by A088218 and ranked by A344619.

- Ranked by A345910 (reverse: A345912).

Equivalently, a(n) counts binary numbers with 2n+1 digits and one more 0 than 1's. For example, the a(2) = 4 binary numbers are: 10001, 10010, 10100, 11000.

(End)

The diagonal of a square n X n matrix where cells of the first row are the nonnegative integers and cells of subsequent rows are sums of cells of the previous row up to and including n. - Torlach Rush, Apr 24 2024

For n>=1, a(n) is the independence number of the odd graph O_{n+1}. - Miquel A. Fiol, Jul 07 2024

Counts binary rooted trees (with out-degree <= 2), embedded in plane, with n labeled end nodes of degree 1. Unlabeled version gives Catalan numbers A000108.

Define a "downgrade" to be the permutation which places the items of a permutation in descending order. We are concerned with permutations that are identical to their downgrades. Only permutations of order 4n and 4n+1 can have this property; the number of permutations of length 4n having this property are equinumerous with those of length 4n+1. If a permutation p has this property then the reversal of this permutation also has it. a(n) = number of permutations of length 4n and 4n+1 that are identical to their downgrades. - Eugene McDonnell (eemcd(AT)mac.com), Oct 26 2003

Number of broadcast schemes in the complete graph on n+1 vertices, K_{n+1}. - Calin D. Morosan (cd_moros(AT)alumni.concordia.ca), Nov 28 2008

Hankel transform is A137565. - Paul Barry, Nov 25 2009

The e.g.f. of 1/a(n) = n!/(2*n)! is (exp(sqrt(x)) + exp(-sqrt(x)) )/2. - Wolfdieter Lang, Jan 09 2012

From Tom Copeland, Nov 15 2014: (Start)

Aerated with intervening zeros (1,0,2,0,12,0,120,...) = a(n) (cf. A123023 and A001147), the e.g.f. is e^(t^2), so this is the base for the Appell sequence with e.g.f. e^(t^2) e^(x*t) = exp(P(.,x),t) (reverse A059344, cf. A099174, A066325 also). P(n,x) = (a. + x)^n with (a.)^n = a_n and comprise the umbral compositional inverses for e^(-t^2)e^(x*t) = exp(UP(.,x),t), i.e., UP(n,P(.,t)) = x^n = P(n,UP(.,t)), e.g., (P(.,t))^n = P(n,t).

Equals A000407*2 with leading 1 added. (End)

a(n) is also the number of square roots of any permutation in S_{4*n} whose disjoint cycle decomposition consists of 2*n transpositions. - Luis Manuel Rivera Martínez, Mar 04 2015

Self-convolution gives A076729. - Vladimir Reshetnikov, Oct 11 2016

For n > 1, it follows from the formula dated Aug 07 2013 that a(n) is a Zumkeller number (A083207). - Ivan N. Ianakiev, Feb 28 2017

For n divisible by 4, a(n/4) is the number of ways to place n points on an n X n grid with pairwise distinct abscissae, pairwise distinct ordinates, and 90-degree rotational symmetry. For n == 1 (mod 4), the number of ways is a((n-1)/4) because the center point can be considered "fixed". For 180-degree rotational symmetry see A006882, for mirror symmetry see A000085, A135401, and A297708. - Manfred Scheucher, Dec 29 2017

T(n,k) is the number of lattice paths from (0,0) to (n,n) with steps E = (1,0) and N = (0,1) which touch but do not cross the line x - y = k and only situated above this line; example: T(3,2) = 5 because we have EENNNE, EENNEN, EENENN, ENEENN, NEEENN. - Philippe Deléham, May 23 2005

The matrix inverse of this triangle is the triangular matrix T(n,k) = (-1)^(n+k)* A085478(n,k). - Philippe Deléham, May 26 2005

Essentially the same as A050155 except with a leading diagonal A000108 (Catalan numbers) 1, 1, 2, 5, 14, 42, 132, 429, .... - Philippe Deléham, May 31 2005

Number of Grand Dyck paths of semilength n and having k downward returns to the x-axis. (A Grand Dyck path of semilength n is a path in the half-plane x>=0, starting at (0,0), ending at (2n,0) and consisting of steps u=(1,1) and d=(1,-1)). Example: T(3,2)=5 because we have u(d)uud(d),uud(d)u(d),u(d)u(d)du,u(d)duu(d) and duu(d)u(d) (the downward returns to the x-axis are shown between parentheses). - Emeric Deutsch, May 06 2006

Riordan array (c(x),x*c(x)^2) where c(x) is the g.f. of A000108; inverse array is (1/(1+x),x/(1+x)^2). - Philippe Deléham, Feb 12 2007

The triangle may also be generated from M^n*[1,0,0,0,0,0,0,0,...], where M is the infinite tridiagonal matrix with all 1's in the super and subdiagonals and [1,2,2,2,2,2,2,...] in the main diagonal. - Philippe Deléham, Feb 26 2007

Inverse binomial matrix applied to A124733. Binomial matrix applied to A089942. - Philippe Deléham, Feb 26 2007

Number of standard tableaux of shape (n+k,n-k). - Philippe Deléham, Mar 22 2007

From Philippe Deléham, Mar 30 2007: (Start)

This triangle belongs to the family of triangles defined by: T(0,0)=1, T(n,k)=0 if k<0 or if k>n, T(n,0)=x*T(n-1,0)+T(n-1,1), T(n,k)=T(n-1,k-1)+y*T(n-1,k)+T(n-1,k+1) for k>=1. Other triangles arise by choosing different values for (x,y):

(0,0) -> A053121; (0,1) -> A089942; (0,2) -> A126093; (0,3) -> A126970

(1,0) -> A061554; (1,1) -> A064189; (1,2) -> A039599; (1,3) -> A110877;

(1,4) -> A124576; (2,0) -> A126075; (2,1) -> A038622; (2,2) -> A039598;

(2,3) -> A124733; (2,4) -> A124575; (3,0) -> A126953; (3,1) -> A126954;

(3,2) -> A111418; (3,3) -> A091965; (3,4) -> A124574; (4,3) -> A126791;

(4,4) -> A052179; (4,5) -> A126331; (5,5) -> A125906. (End)

The table U(n,k) = Sum_{j=0..n} T(n,j)*k^j is given in A098474. - Philippe Deléham, Mar 29 2007

Sequence read mod 2 gives A127872. - Philippe Deléham, Apr 12 2007

Number of 2n step walks from (0,0) to (2n,2k) and consisting of step u=(1,1) and d=(1,-1) and the path stays in the nonnegative quadrant. Example: T(3,0)=5 because we have uuuddd, uududd, ududud, uduudd, uuddud; T(3,1)=9 because we have uuuudd, uuuddu, uuudud, ududuu, uuduud, uduudu, uudduu, uduuud, uududu; T(3,2)=5 because we have uuuuud, uuuudu, uuuduu, uuduuu, uduuuu; T(3,3)=1 because we have uuuuuu. - Philippe Deléham, Apr 16 2007, Apr 17 2007, Apr 18 2007

Triangular matrix, read by rows, equal to the matrix inverse of triangle A129818. - Philippe Deléham, Jun 19 2007

Let Sum_{n>=0} a(n)*x^n = (1+x)/(1-mx+x^2) = o.g.f. of A_m, then Sum_{k=0..n} T(n,k)*a(k) = (m+2)^n. Related expansions of A_m are: A099493, A033999, A057078, A057077, A057079, A005408, A002878, A001834, A030221, A002315, A033890, A057080, A057081, A054320, A097783, A077416, A126866, A028230, A161591, for m=-3,-2,-1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15, respectively. - Philippe Deléham, Nov 16 2009

The Kn11, Kn12, Fi1 and Fi2 triangle sums link the triangle given above with three sequences; see the crossrefs. For the definitions of these triangle sums, see A180662. - Johannes W. Meijer, Apr 20 2011

4^n = (n-th row terms) dot (first n+1 odd integer terms). Example: 4^4 = 256 = (14, 28, 20, 7, 1) dot (1, 3, 5, 7, 9) = (14 + 84 + 100 + 49 + 9) = 256. - Gary W. Adamson, Jun 13 2011

The linear system of n equations with coefficients defined by the first n rows solve for diagonal lengths of regular polygons with N= 2n+1 edges; the constants c^0, c^1, c^2, ... are on the right hand side, where c = 2 + 2*cos(2*Pi/N). Example: take the first 4 rows relating to the 9-gon (nonagon), N = 2*4 + 1; with c = 2 + 2*cos(2*Pi/9) = 3.5320888.... The equations are (1,0,0,0) = 1; (1,1,0,0) = c; (2,3,1,0) = c^2; (5,9,5,1) = c^3. The solutions are 1, 2.53208..., 2.87938..., and 1.87938...; the four distinct diagonal lengths of the 9-gon (nonagon) with edge = 1. (Cf. comment in A089942 which uses the analogous operations but with c = 1 + 2*cos(2*Pi/9).) - Gary W. Adamson, Sep 21 2011

Also called the Lobb numbers, after Andrew Lobb, are a natural generalization of the Catalan numbers, given by L(m,n)=(2m+1)*Binomial(2n,m+n)/(m+n+1), where n >= m >= 0. For m=0, we get the n-th Catalan number. See added reference. - Jayanta Basu, Apr 30 2013

From Wolfdieter Lang, Sep 20 2013: (Start)

T(n, k) = A053121(2*n, 2*k). T(n, k) appears in the formula for the (2*n)-th power of the algebraic number rho(N):= 2*cos(Pi/N) = R(N, 2) in terms of the odd-indexed diagonal/side length ratios R(N, 2*k+1) = S(2*k, rho(N)) in the regular N-gon inscribed in the unit circle (length unit 1). S(n, x) are Chebyshev's S polynomials (see A049310):

rho(N)^(2*n) = Sum_{k=0..n} T(n, k)*R(N, 2*k+1), n >= 0, identical in N > = 1. For a proof see the Sep 21 2013 comment under A053121. Note that this is the unreduced version if R(N, j) with j > delta(N), the degree of the algebraic number rho(N) (see A055034), appears.

For the odd powers of rho(n) see A039598. (End)

Unsigned coefficients of polynomial numerators of Eqn. 2.1 of the Chakravarty and Kodama paper, defining the polynomials of A067311. - Tom Copeland, May 26 2016

The triangle is the Riordan square of the Catalan numbers in the sense of A321620. - Peter Luschny, Feb 14 2023

In any generalized Fibonacci sequence {f(i)}, Sum_{i=0..4n+1} f(i) = a(n)*f(2n+2). - Lekraj Beedassy, Dec 31 2002

The continued fraction expansion for F((2n+1)*(k+1))/F((2n+1)*k), k>=1 is [a(n),a(n),...,a(n)] where there are exactly k elements (F(n) denotes the n-th Fibonacci number). E.g., continued fraction for F(12)/F(9) is [4, 4,4]. - Benoit Cloitre, Apr 10 2003

See A135064 for a possible connection with Galois groups of quintics.

Sequence of all positive integers k such that continued fraction [k,k,k,k,k,k,...] belongs to Q(sqrt(5)). - Thomas Baruchel, Sep 15 2003

All positive integer solutions of Pell equation a(n)^2 - 5*b(n)^2 = -4 together with b(n)=A001519(n), n>=0.

a(n) = L(n,-3)*(-1)^n, where L is defined as in A108299; see also A001519 for L(n,+3).

Inverse binomial transform of A030191. - Philippe Deléham, Oct 04 2005

General recurrence is a(n) = (a(1)-1)*a(n-1) - a(n-2), a(1) >= 4, lim_{n->infinity} a(n) = x*(k*x+1)^n, k =(a(1)-3), x=(1+sqrt((a(1)+1)/(a(1)-3)))/2. Examples in OEIS: a(1)=4 gives A002878. a(1)=5 gives A001834. a(1)=6 gives A030221. a(1)=7 gives A002315. a(1)=8 gives A033890. a(1)=9 gives A057080. a(1)=10 gives A057081. - Ctibor O. Zizka, Sep 02 2008

Let r = (2n+1), then a(n), n>0 = Product_{k=1..floor((r-1)/2)} (1 + sin^2 k*Pi/r); e.g., a(3) = 29 = (3.4450418679...)*(4.801937735...)*(1.753020396...). - Gary W. Adamson, Nov 26 2008

a(n+1) is the Hankel transform of A001700(n)+A001700(n+1). - Paul Barry, Apr 21 2009

a(n) is equal to the permanent of the (2n) X (2n) tridiagonal matrix with sqrt(5)'s along the main diagonal, i's along the superdiagonal and the subdiagonal (i is the imaginary unit), and 0's everywhere else. - John M. Campbell, Jun 09 2011

Conjecture: for n > 0, a(n) = sqrt(Fibonacci(4*n+3) + Sum_{k=2..2*n} Fibonacci(2*k)). - Alex Ratushnyak, May 06 2012

Pisano period lengths: 1, 3, 4, 3, 2, 12, 8, 6, 12, 6, 5, 12, 14, 24, 4, 12, 18, 12, 9, 6, ... . - R. J. Mathar, Aug 10 2012

The continued fraction [a(n); a(n), a(n), ...] = phi^(2n+1), where phi is the golden ratio, A001622. - Thomas Ordowski, Jun 05 2013

Solutions (x, y) = (a(n), a(n+1)) satisfying x^2 + y^2 = 3xy + 5. - Michel Lagneau, Feb 01 2014

Conjecture: except for the number 3, a(n) are the numbers such that a(n)^2+2 are Lucas numbers. - Michel Lagneau, Jul 22 2014

Comment on the preceding conjecture: It is clear that all a(n) satisfy a(n)^2 + 2 = L(2*(2*n+1)) due to the identity (17 c) of Vajda, p. 177: L(2*n) + 2*(-1)^n = L(n)^2 (take n -> 2*n+1). - Wolfdieter Lang, Oct 10 2014

Limit_{n->oo} a(n+1)/a(n) = phi^2 = phi + 1 = (3+sqrt(5))/2. - Derek Orr, Jun 18 2015

If d[k] denotes the sequence of k-th differences of this sequence, then d[0](0), d[1](1), d[2](2), d[3](3), ... = A048876, cf. message to SeqFan list by P. Curtz on March 2, 2016. - M. F. Hasler, Mar 03 2016

a(n-1) and a(n) are the least phi-antipalindromic numbers (A178482) with 2*n and 2*n+1 digits in base phi, respectively. - Amiram Eldar, Jul 07 2021

Triangulate (hyperbolic) 2-space such that around every vertex exactly 7 triangles touch. Call any 7 triangles having a common vertex the first layer and let the (n+1)-st layer be all triangles that do not appear in any of the first n layers and have a common vertex with the n-th layer. Then the n-th layer contains 7*a(n-1) triangles. E.g., the first layer (by definition) contains 7 triangles, the second layer (the "ring" of triangles around the first layer) consists of 28 triangles, the third layer (the next "ring") consists of 77 triangles, and so on. - Nicolas Nagel, Aug 13 2022

Binary representation of the Kempner-Mahler number Sum_{k>=0} 1/2^(2^k) = A007404.

Also a(n) = A(n) mod 2 where A is any of A001700, A005573, A007854, A026641, A049027, A064063, A064088, A064090, A064092, A064325, A064327, A064329, A064331, A064613, A076026, A105523, A123273, A126694, A126930, A126931, A126982, A126983, A126987, A127016, A127053, A127358, A127360, A127361, A127363. - Philippe Deléham, May 26 2007

a(n) = (product of digits of n; n in binary notation) mod 2. This sequence is a transformation of the Thue-Morse sequence (A010060), since there exists a function f such that f(sum of digits of n) = (product of digits of n). - Ctibor O. Zizka, Feb 12 2008

a(n-1), n >= 1, the characteristic sequence for powers of 2, A000079, is the unique solution of the following formal product and formal power series identity: Product_{j>=1} (1 + a(j-1)*x^j) = 1 + Sum_{k>=1} x^k = 1/(1-x). The product is therefore Product_{l>=1} (1 + x^(2^l)). Proof. Compare coefficients of x^n and use the binary representation of n. Uniqueness follows from the recurrence relation given for the general case under A147542. - Wolfdieter Lang, Mar 05 2009

a(n) is also the number of orbits of length n for the map x -> 1-cx^2 on [-1,1] at the Feigenbaum critical value c=1.401155... . - Thomas Ward, Apr 08 2009

A054525 (Mobius transform) * A001511 = A036987 = A047999^(-1) * A001511 = the inverse of Sierpiński's gasket * the ruler sequence. - Gary W. Adamson, Oct 26 2009 [Of course this is only vaguely correct depending on how the fuzzy indexing in these formulas is made concrete. - R. J. Mathar, Jun 20 2014]

Characteristic function of A000225. - Reinhard Zumkeller, Mar 06 2012

Also parity of the Catalan numbers A000108. - Omar E. Pol, Jan 17 2012

For n >= 2, also the largest exponent k >= 0 such that n^k in binary notation does not contain both 0 and 1. Unlike for the decimal version of this sequence, A062518, where the terms are only conjectural, for this sequence the values of a(n) can be proved to be the characteristic function of A000225, as follows: n^k will contain both 0 and 1 unless n^k = 2^r-1 for some r. But this is a special case of Catalan's equation x^p = y^q-1, which was proved by Preda Mihăilescu to have no nontrivial solution except 2^3 = 3^2 - 1. - Christopher J. Smyth, Aug 22 2014

Image, under the coding a,b -> 1; c -> 0, of the fixed point, starting with a, of the morphism a -> ab, b -> cb, c -> cc. - Jeffrey Shallit, May 14 2016

Number of nonisomorphic Boolean algebras of order n+1. - Jianing Song, Jan 23 2020

Number of balanced strings of length n: let d(S) = #(1's) - #(0's), # == count in S, then S is balanced if every substring T of S has -2 <= d(T) <= 2.

Number of "fold lines" seen when a rectangular piece of paper is folded n+1 times along alternate orthogonal directions and then unfolded. - Quim Castellsaguer (qcastell(AT)pie.xtec.es), Dec 30 1999

Also the number of binary strings with the property that, when scanning from left to right, once the first 1 is seen in position j, there must be a 1 in positions j+2, j+4, ... until the end of the string. (Positions j+1, j+3, ... can be occupied by 0 or 1.) - Jeffrey Shallit, Sep 02 2002

a(n-1) is also the Moore lower bound on the order of a (3,n)-cage. - Eric W. Weisstein, May 20 2003 and Jason Kimberley, Oct 30 2011

Partial sums of A016116. - Hieronymus Fischer, Sep 15 2007

Equals row sums of triangle A152201. - Gary W. Adamson, Nov 29 2008

From John P. McSorley, Sep 28 2010: (Start)

a(n) = DPE(n+1) is the total number of k-double-palindromes of n up to cyclic equivalence. See sequence A180918 for the definitions of a k-double-palindrome of n and of cyclic equivalence. Sequence A180918 is the 'DPE(n,k)' triangle read by rows where DPE(n,k) is the number of k-double-palindromes of n up to cyclic equivalence. For example, we have a(4) = DPE(5) = DPE(5,1) + DPE(5,2) + DPE(5,3) + DPE(5,4) + DPE(5,5) = 0 + 2 + 2 + 1 + 1 = 6.

The 6 double-palindromes of 5 up to cyclic equivalence are 14, 23, 113, 122, 1112, 11111. They come from cyclic equivalence classes {14,41}, {23,32}, {113,311,131}, {122,212,221}, {1112,2111,1211,1121}, and {11111}. Hence a(n)=DPE(n+1) is the total number of cyclic equivalence classes of n containing at least one double-palindrome.

(End)

From Herbert Eberle, Oct 02 2015: (Start)

For n > 0, there is a red-black tree of height n with a(n-1) internal nodes and none with less.

In order a red-black tree of given height has minimal number of nodes, it has exactly 1 path with strictly alternating red and black nodes. All nodes outside this height defining path are black.

Consider:

mrbt5 R

/ \

/ \

/ \

/ B

/ / \

mrbt4 B / B

/ \ B E E

/ B E E

mrbt3 R E E

/ \

/ B

mrbt2 B E E

/ E

mrbt1 R

E E

(Red nodes shown as R, blacks as B, externals as E.)

Red-black trees mrbt1, mrbt2, mrbt3, mrbt4, mrbt5 of respective heights h = 1, 2, 3, 4, 5; all minimal in the number of internal nodes, namely 1, 2, 4, 6, 10.

Recursion (let n = h-1): a(-1) = 0, a(n) = a(n-1) + 2^floor(n/2), n >= 0.

(End)

Also the number of strings of length n with the digits 1 and 2 with the property that the sum of the digits of all substrings of uneven length is not divisible by 3. An example with length 8 is 21221121. - Herbert Kociemba, Apr 29 2017

a(n-2) is the number of achiral n-bead necklaces or bracelets using exactly two colors. For n=4, the four arrangements are AAAB, AABB, ABAB, and ABBB. - Robert A. Russell, Sep 26 2018

Partial sums of powers of 2 repeated 2 times, like A200672 where is 3 times. - Yuchun Ji, Nov 16 2018

Also the number of binary words of length n with cuts-resistance <= 2, where, for the operation of shortening all runs by one, cuts-resistance is the number of applications required to reach an empty word. Explicitly, these are words whose sequence of run-lengths, all of which are 1 or 2, has no odd-length run of 1's sandwiched between two 2's. - Gus Wiseman, Nov 28 2019

Also the number of up-down paths with n steps such that the height difference between the highest and lowest points is at most 2. - Jeremy Dover, Jun 17 2020

Also the number of non-singleton integer compositions of n + 2 with no odd part other than the first or last. Including singletons gives A052955. This is an unsorted (or ordered) version of A351003. The version without even (instead of odd) interior parts is A001911, complement A232580. Note that A000045(n-1) counts compositions without odd parts, with non-singleton case A077896, and A052952/A074331 count non-singleton compositions without even parts. Also the number of compositions y of n + 1 such that y_i = y_{i+1} for all even i. - Gus Wiseman, Feb 19 2022

This sequence, with first term a(0) deleted, appears to be determined by the conditions that the diagonal and first superdiagonal of U are {1,1,1,1,...} and {2,3,4,5,...,n+1,...} respectively, where A=LU is the LU factorization of the Hankel matrix A given by [{a(1),a(2),...}, {a(2),a(3),...}, ..., {a(n),a(n+1),...}, ...]. - John W. Layman, Jul 21 2000

Also the number of base 3 n-digit numbers (not starting with 0) with digit sum n. For the analogous sequence in base 10 see A071976, see example. - John W. Layman, Jun 22 2002

Also number of paths in an n X n grid from (0,0) to the line x=n-1, using only steps U=(1,1), H=(1,0) and D=(1,-1) (i.e., left factors of length n-1 of Motzkin paths, palindromic Motzkin paths of length 2n-2 or 2n-1). Example: a(3)=5, namely, HH, UD, HU, UH and UU. Also number of ordered trees with n edges and having nonroot nodes of outdegree at most 2. - Emeric Deutsch, Aug 01 2002

Number of symmetric Dyck paths of semilength 2n-1 with no peaks at even level. Example: a(3)=5 because we have UDUDUDUDUD, UDUUUDDDUD, UUUUUDDDDD, UUUDUDUDDD and UUUDDUUDDD, where U=(1,1) and D=(1,-1). Also number of symmetric Dyck paths of semilength 2n with no peaks at even level. Example: a(3)=5 because we have UDUDUDUDUDUD, UDUUUDUDDDUD, UUUDUDUDUDDD, UUUUUDUDDDDD and UUUDDDUUUDDD. - Emeric Deutsch, Nov 21 2003

a(n) is the sum of the (n-1)-st central trinomial coefficient and its predecessor. Example: a(4) = 6 + 7 and (1 + x + x^2)^3 = ... + 6*x^2 + 7*x^3 + ... . - David Callan, Feb 07 2004

a(n) is the number of UDU-free paths of n upsteps (U) and n downsteps (D) that start U (n>=1). Example: a(2)=2 counts UUDD, UDDU. - David Callan, Aug 18 2004

a(n) is also the number of Grand-Dyck paths of semilength n starting with an up-step and avoiding the pattern DUD. - David Bevan, Nov 19 2019

Hankel transform of a(n+1) = [1,2,5,13,35,96,...] gives A000012 = [1,1,1,1,1,1,...]. - Philippe Deléham, Oct 24 2007

Equals row sums of triangle A136787 starting (1, 2, 5, 13, 35, ...). - Gary W. Adamson, Jan 21 2008

a(n) is the number of permutations on [n] that avoid the patterns 1-23-4 and 1-3-2, where the omission of a dash in a pattern means the permutation entries must be adjacent. Example: a(4) = 13 counts all 14 (Catalan number) (1-3-2)-avoiding permutations on [4] except 1234. - David Callan, Jul 22 2008

a(n) is also the number of involutions of length 2n-2 which are invariant under the reverse-complement map and have no decreasing subsequences of length 4. - Eric S. Egge, Oct 21 2008

Hankel transform is A010892. - Paul Barry, Jan 19 2009

a(n) is the number of Dyck words of semilength n with no DUUU. For example, a(4) = 14-1 = 13 because there is only one Dyck 4-word containing DUUU, namely UDUUUDDD. - Eric Rowland, Apr 21 2009

Inverse binomial transform of A024718. - Philippe Deléham, Dec 13 2009

Let w(i, j, n) denote walks in N^2 which satisfy the multivariate recurrence

w(i, j, n) = w(i - 1, j, n - 1) + w(i, j - 1, n - 1) + w(i + 1, j - 1,n - 1) with boundary conditions w(0,0,0) = 1 and w(i,j,n) = 0 if i or j or n is < 0. Let alpha(n) the number of such walks of length n, alpha(n) = Sum_{i = 0..n, j=0..n} w(i, j, n). Then a(n+1) = alpha(n). - Peter Luschny, May 21 2011

Number of length-n strings [d(0),d(1),d(2),...,d(n-1)] where 0 <= d(k) <= k and abs(d(k) - d(k-1)) <= 1 (smooth factorial numbers, see example). - Joerg Arndt, Nov 10 2012

a(n) is the number of n-multisets of {1,...,n} containing no pair of consecutive integers (e.g., 111, 113, 133, 222, 333 for n=3). - David Bevan, Jun 10 2013

a(n) is also the number of n-multisets of [n] in which no integer except n occurs exactly once (e.g., 111, 113, 222, 223, 333 for n=3). - David Bevan, Nov 19 2019

Number of minimax elements in the affine Weyl group of the Lie algebra so(2n+1) or the Lie algebra sp(2n). See Panyushev 2005. Cf. A245455. - Peter Bala, Jul 22 2014

The shifted, signed array belongs to an interpolated family of arrays associated to the Catalan A000108 (t=1), and Riordan, or Motzkin sums A005043 (t=0), with the interpolating (here t=-2) o.g.f. G(x,t) = (1-sqrt(1-4x/(1+(1-t)x)))/2 and inverse o.g.f. Ginv(x,t) = x(1-x)/(1+(t-1)x(1-x)) (A057682). See A091867 for more info on this family. - Tom Copeland, Nov 09 2014

Alternatively, this sequence corresponds to the number of positive walks with n steps {-1,0,1} starting at the origin, ending at any altitude, and staying strictly above the x-axis. - David Nguyen, Dec 01 2016

Let N be a squarefree number with n prime factors: p_1 < p_2 < ... < p_n. Let D be its set of divisors, E the subset of D X D made of the (d_1, d_2) for which, provided that we know which p_i are in d_1, which p_i are in d_2, d_1 <= d_2 is provable without needing to know the numerical values of the p_i. It appears that a(n+1) is the number of (d_1, d_2) in E such that d_1 and d_2 are coprime. - Luc Rousseau, Aug 21 2017

Number of ordered rooted trees with n non-root nodes and all non-root nodes having outdegrees 1 or 2. - Andrew Howroyd, Dec 04 2017

a(n) is the number of compositions (ordered partitions) of n where there are A001006(k-1) sorts of part k (see formula by Andrew Howroyd, Dec 04 2017). - Joerg Arndt, Jan 26 2024

Also numbers k such that the binary digital mean dm(2, k) = (Sum_{i=1..d} 2*d_i - 1) / (2*d) = 0, where d is the number of digits in the binary representation of k and d_i the individual digits. - Reikku Kulon, Sep 21 2008

From Reikku Kulon, Sep 29 2008: (Start)

Each run of values begins with 2^(2k + 1) + 2^(k + 1) - 2^k - 1. The initial values increase according to the sequence {2^(k - 1), 2^(k - 2), 2^(k - 3), ..., 2^(k - k)}.

After this, the values follow a periodic sequence of increases by successive powers of two with single odd values interspersed.

Each run ends with an odd increase followed by increases of {2^(k - k), ..., 2^(k - 2), 2^(k - 1), 2^k}, finally reaching 2^(2k + 2) - 2^(k + 1).

Similar behavior occurs in other bases. (End)

Numbers k such that A000120(k)/A070939(k) = 1/2. - Ctibor O. Zizka, Oct 15 2008

Subsequence of A053754; A179888 is a subsequence. - Reinhard Zumkeller, Jul 31 2010

A000120(a(n)) = A023416(a(n)); A037861(a(n)) = 0.

A001700 gives number of terms having length 2*n in binary representation: A001700(n-1) = #{m: A070939(a(m))=2*n}. - Reinhard Zumkeller, Jun 08 2011

The number of terms below 2^k is A079309(floor(k/2)) for k > 1. - Amiram Eldar, Nov 21 2020

Also a(n) = 2nd elementary symmetric function of binomial(n,0), binomial(n,1), ..., binomial(n,n).

Also a(n) = one half the sum of the heights, over all Dyck (n+2)-paths, of the vertices that are at even height and terminate an upstep. For example with n=1, these vertices are indicated by asterisks in the 5 Dyck 3-paths: UU*UDDD, UU*DU*DD, UDUU*DD, UDUDUD, UU*DDUD, yielding a(1)=(2+4+2+0+2)/2=5. - David Callan, Jul 14 2006

Hankel transform is (-1)^n*(2n+1); the Hankel transform of sum(k=0..n, C(2*n,k) ) - C(2n,n) is (-1)^n*n. - Paul Barry, Jan 21 2007

Row sums of the Riordan matrix (1/(1-4x),(1-sqrt(1-4x))/2) (A187926). - Emanuele Munarini, Mar 16 2011

From Gus Wiseman, Jul 19 2021: (Start)

For n > 0, a(n-1) is also the number of integer compositions of 2n with nonzero alternating sum, where the alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i. These compositions are ranked by A053754 /\ A345921. For example, the a(3-1) = 22 compositions of 6 are:

(6) (1,5) (1,1,4) (1,1,1,3) (1,1,1,1,2)

(2,4) (1,2,3) (1,1,3,1) (1,1,2,1,1)

(4,2) (1,4,1) (1,2,1,2) (2,1,1,1,1)

(5,1) (2,1,3) (1,3,1,1)

(2,2,2) (2,1,2,1)

(3,1,2) (3,1,1,1)

(3,2,1)

(4,1,1)

(End)

a(n) = number of permutations in S_{n+2} containing exactly one 312 pattern. E.g., S_3 has a_1 = 1 permutations containing exactly one 312 pattern, and S_4 has a_2 = 5 permutations containing exactly one 312 pattern, namely 1423, 2413, 3124, 3142, and 4231. This comment is also true if 312 is replaced by any of 132, 213, or 231 (but not 123 or 321, for which see A003517). [Comment revised by N. J. A. Sloane, Nov 26 2022]

Number of valleys in all Dyck paths of semilength n+1. Example: a(2)=5 because UD*UD*UD, UD*UUDD, UUDD*UD, UUD*UDD, UUUDDD, where U=(1,1), D=(1,-1) and the valleys are shown by *. - Emeric Deutsch, Dec 05 2003

Number of UU's (double rises) in all Dyck paths of semilength n+1. Example: a(2)=5 because UDUDUD, UDU*UDD, U*UDDUD, U*UDUDD, U*U*UDDD, the double rises being shown by *. - Emeric Deutsch, Dec 05 2003

Number of peaks at level higher than one (high peaks) in all Dyck paths of semilength n+1. Example: a(2)=5 because UDUDUD, UDUU*DD, UU*DDUD, UU*DU*DD, UUU*DDD, the high peaks being shown by *. - Emeric Deutsch, Dec 05 2003

Number of diagonal dissections of a convex (n+3)-gon into n regions. Number of standard tableaux of shape (n,n,1) (see Stanley reference). - Emeric Deutsch, May 20 2004

Number of dissections of a convex (n+3)-gon by noncrossing diagonals into several regions, exactly n-1 of which are triangular. Example: a(2)=5 because the convex pentagon ABCDE is dissected by any of the diagonals AC, BD, CE, DA, EB into regions containing exactly 1 triangle. - Emeric Deutsch, May 31 2004

Number of jumps in all full binary trees with n+1 internal nodes. In the preorder traversal of a full binary tree, any transition from a node at a deeper level to a node on a strictly higher level is called a jump. - Emeric Deutsch, Jan 18 2007

a(n) is the total number of nonempty Dyck subpaths in all Dyck paths (A000108) of semilength n. For example, the Dyck path UUDUUDDD has Dyck subpaths stretching over positions 1-8 (the entire path), 2-3, 2-7, 4-7, 5-6 and so contributes 5 to a(4). - David Callan, Jul 25 2008

a(n+1) is the total number of ascents in the set of all n-permutations avoiding the pattern 132. For example, a(2) = 5 because there are 5 ascents in the set 123, 213, 231, 312, 321. - Cheyne Homberger, Oct 25 2013

Number of increasing tableaux of shape (n+1,n+1) with largest entry 2n+1. An increasing tableau is a semistandard tableau with strictly increasing rows and columns, and set of entries an initial segment of the positive integers. Example: a(2) = 5 counts the five tableaux (124)(235), (123)(245), (124)(345), (134)(245), (123)(245). - Oliver Pechenik, May 02 2014

a(n) is the number of noncrossing partitions of 2n+1 into n-1 blocks of size 2 and 1 block of size 3. - Oliver Pechenik, May 02 2014

Number of paths in the half-plane x>=0, from (0,0) to (2n+1,3), and consisting of steps U=(1,1) and D=(1,-1). For example, for n=2, we have the 5 paths: UUUUD, UUUDU, UUDUU, UDUUU, DUUUU. - José Luis Ramírez Ramírez, Apr 19 2015

From Gus Wiseman, Aug 20 2021: (Start)

Also the number of binary numbers with 2n+2 digits and with two more 0's than 1's. For example, the a(2) = 5 binary numbers are: 100001, 100010, 100100, 101000, 110000, with decimal values 33, 34, 36, 40, 48. Allowing first digit 0 gives A001791, ranked by A345910/A345912.

Also the number of integer compositions of 2n+2 with alternating sum -2, where the alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i. For example, the a(3) = 21 compositions are:

(35) (152) (1124) (11141) (111113)

(251) (1223) (12131) (111212)

(1322) (13121) (111311)

(1421) (14111) (121112)

(2114) (121211)

(2213) (131111)

(2312)

(2411)

The following pertain to these compositions:

- The unordered version is A344741.

- Ranked by A345924 (reverse: A345923).

- A345197 counts compositions by length and alternating sum.

- A345925 ranks compositions with alternating sum 2 (reverse: A345922).

(End)