A005773 -id:A005773 - cp's OEIS frontend

A035263 Trajectory of 1 under the morphism 0 -> 11, 1 -> 10; parity of 2-adic valuation of 2n: a(n) = A000035(A001511(n)).

1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1

Offset: 1

Karamanos Konstantinos, N. J. A. Sloane

First Feigenbaum symbolic (or period-doubling) sequence, corresponding to the accumulation point of the 2^{k} cycles through successive bifurcations.
To construct the sequence: start with 1 and concatenate: 1,1, then change the last term (1->0; 0->1) gives: 1,0. Concatenate those 2 terms: 1,0,1,0, change the last term: 1,0,1,1. Concatenate those 4 terms: 1,0,1,1,1,0,1,1 change the last term: 1,0,1,1,1,0,1,0, etc. - Benoit Cloitre, Dec 17 2002
Let T denote the present sequence. Here is another way to construct T. Start with the sequence S = 1,0,1,,1,0,1,,1,0,1,,1,0,1,,... and fill in the successive holes with the successive terms of the sequence T (from paper by Allouche et al.). - Emeric Deutsch, Jan 08 2003 [Note that if we fill in the holes with the terms of S itself, we get A141260. - N. J. A. Sloane, Jan 14 2009]
From N. J. A. Sloane, Feb 27 2009: (Start)
In more detail: define S to be 1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1,0,1___...
If we fill the holes with S we get A141260:
1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0,
........1.........0.........1.........1.........0.......1.........1.........0...
- the result is
1..0..1.1.1..0..1.0.1..0..1.1.1..0..1.1.1..0..1.0.1.... = A141260.
But instead, if we define T recursively by filling the holes in S with the terms of T itself, we get A035263:
1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0,
........1.........0.........1.........1.........1.......0.........1.........0...
- the result is
1..0..1.1.1..0..1.0.1..0..1.1.1..0..1.1.1..0..1.1.1.0.1.0.1..0..1.1.1..0..1.0.1.. = A035263. (End)
Characteristic function of A003159, i.e., A035263(n)=1 if n is in A003159 and A035263(n)=0 otherwise (from paper by Allouche et al.). - Emeric Deutsch, Jan 15 2003
This is the sequence of R (=1), L (=0) moves in the Towers of Hanoi puzzle: R, L, R, R, R, L, R, L, R, L, R, R, R, ... - Gary W. Adamson, Sep 21 2003
Manfred Schroeder, p. 279 states, "... the kneading sequences for unimodal maps in the binary notation, 0, 1, 0, 1, 1, 1, 0, 1..., are obtained from the Morse-Thue sequence by taking sums mod 2 of adjacent elements." On p. 278, in the chapter "Self-Similarity in the Logistic Parabola", he writes, "Is there a closer connection between the Morse-Thue sequence and the symbolic dynamics of the superstable orbits? There is indeed. To see this, let us replace R by 1 and C and L by 0." - Gary W. Adamson, Sep 21 2003
Partial sums modulo 2 of the sequence 1, a(1), a(1), a(2), a(2), a(3), a(3), a(4), a(4), a(5), a(5), a(6), a(6), ... . - Philippe Deléham, Jan 02 2004
Parity of A007913, A065882 and A065883. - Philippe Deléham, Mar 28 2004
The length of n-th run of 1's in this sequence is A080426(n). - Philippe Deléham, Apr 19 2004
Also parity of A005043, A005773, A026378, A104455, A117641. - Philippe Deléham, Apr 28 2007
Equals parity of the Towers of Hanoi, or ruler sequence (A001511), where the Towers of Hanoi sequence (1, 2, 1, 3, 1, 2, 1, 4, ...) denotes the disc moved, labeled (1, 2, 3, ...) starting from the top; and the parity of (1, 2, 1, 3, ...) denotes the direction of the move, CW or CCW. The frequency of CW moves converges to 2/3. - Gary W. Adamson, May 11 2007
A conjectured identity relating to the partition sequence, A000041: p(x) = A(x) * A(x^2) when A(x) = the Euler transform of A035263 = polcoeff A174065: (1 + x + x^2 + 2x^3 + 3x^4 + 4x^5 + ...). - Gary W. Adamson, Mar 21 2010
a(n) is 1 if the number of trailing zeros in the binary representation of n is even. - Ralf Stephan, Aug 22 2013
From Gary W. Adamson, Mar 25 2015: (Start)
A conjectured identity relating to the partition sequence, A000041 as polcoeff p(x); A003159, and its characteristic function A035263: (1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, ...); and A036554 indicating n-th terms with zeros in A035263: (2, 6, 8, 10, 14, 18, 22, ...).
The conjecture states that p(x) = A(x) = A(x^2) when A(x) = polcoeffA174065 = the Euler transform of A035263 = 1/(1-x)*(1-x^3)*(1-x^4)*(1-x^5)*... = (1 + x + x^2 + 2x^3 + 3x^4 + 4x^5 + ...) and the aerated variant = the Euler transform of the complement of A035263: 1/(1-x^2)*(1-x^6)*(1-x^8)*... = (1 + x^2 + x^4 + 2x^6 + 3x^8 + 4x^10 + ...).
(End)
The conjecture above was proved by Jean-Paul Allouche on Dec 21 2013.
Regarded as a column vector, this sequence is the product of A047999 (Sierpinski's gasket) regarded as an infinite lower triangular matrix and A036497 (the Fredholm-Rueppel sequence) where the 1's have alternating signs, 1, -1, 0, 1, 0, 0, 0, -1, .... - Gary W. Adamson, Jun 02 2021
The numbers of 1's through n (A050292) can be determined by starting with the binary (say for 19 = 1 0 0 1 1) and writing: next term is twice current term if 0, otherwise twice plus 1. The result is 1, 2, 4, 9, 19. Take the difference row, = 1, 1, 2, 5, 10; and add the odd-indexed terms from the right: 5, 4, 3, 2, 1 = 10 + 2 + 1 = 13. The algorithm is the basis for determining the disc configurations in the tower of Hanoi game, as shown in the Jul 24 2021 comment of A060572. - Gary W. Adamson, Jul 28 2021

Karamanos, Kostas. "From symbolic dynamics to a digital approach." International Journal of Bifurcation and Chaos 11.06 (2001): 1683-1694. (Full version. See p. 1685)
Karamanos, K. (2000). From symbolic dynamics to a digital approach: chaos and transcendence. In Michel Planat (Ed.), Noise, Oscillators and Algebraic Randomness (Lecture Notes in Physics, pp. 357-371). Springer, Berlin, Heidelberg. (Short version. See p. 359)
Manfred R. Schroeder, "Fractals, Chaos, Power Laws", W. H. Freeman, 1991
S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 892, column 2, Note on p. 84, part (a).

Antti Karttunen, Table of n, a(n) for n = 1..65536 (first 10000 terms from T. D. Noe)
Ricardo Gómez Aíza, Symbolic dynamical scales: modes, orbitals, and transversals, arXiv:2009.02669 [math.DS], 2020.
Jean-Paul Allouche, On the morphism 1 -> 121, 2 -> 12221, CNRS France, 2024. See p. 6.
Jean-Paul Allouche, On the morphism 1 -> 121, 2 -> 12221, Preprint, 2024 [Local copy, with permission]
Jean-Paul Allouche, Andre Arnold, Jean Berstel, Srecko Brlek, William Jockusch, Simon Plouffe and Bruce E. Sagan, A sequence related to that of Thue-Morse, Discrete Math., 139 (1995), 455-461.
Jean-Paul Allouche and Michel Mendès France, Automata and Automatic Sequences, in: Axel F. and Gratias D. (eds), Beyond Quasicrystals. Centre de Physique des Houches, vol 3. Springer, Berlin, Heidelberg, pp. 293-367, 1995; DOI https://doi.org/10.1007/978-3-662-03130-8_11.
Jean-Paul Allouche and Michel Mendes France, Automata and Automatic Sequences, in: Axel F. and Gratias D. (eds), Beyond Quasicrystals. Centre de Physique des Houches, vol 3. Springer, Berlin, Heidelberg, pp. 293-367, 1995; DOI https://doi.org/10.1007/978-3-662-03130-8_11. [Local copy]
Jean-Paul Allouche and Jeffrey Shallit, The Ubiquitous Prouhet-Thue-Morse Sequence, in C. Ding. T. Helleseth and H. Niederreiter, eds., Sequences and Their Applications: Proceedings of SETA '98, Springer-Verlag, 1999, pp. 1-16.
Joerg Arndt, Matters Computational (The Fxtbook), pp.9-10, pp.734-738
Scott Balchin and Dan Rust, Computations for Symbolic Substitutions, Journal of Integer Sequences, Vol. 20 (2017), Article 17.4.1.
Benoit Cloitre, Fractal walk on the 130000 first terms (step of unit length moving with angle Pi/3 if 0 and -Pi/3 if 1) starting at (0,0)
F. Michel Dekking, Morphisms, Symbolic Sequences, and Their Standard Forms, Journal of Integer Sequences, Vol. 19 (2016), Article 16.1.1.
B. Derrida, A. Gervois and Y. Pomeau, Iteration of endomorphisms on the real axis and representation of number, Ann. Inst. Henri Poincaré, Section A: Physique Théorique, Vol. XXIX no. 3, 305-356 (1978).
Emeric Deutsch and Bruce E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, arXiv:math/0407326 [math.CO], 2004.
Emeric Deutsch and Bruce E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, J. Num. Theory 117 (2006), 191-215.
Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović, and Ciril Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See page 79. Book's website
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint 2016.
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.
Konstantinos Karamanos, Symbolic Dynamics to a Digital Approach, Int. J. of Bifurcation and Chaos, 11(6), 1683-1694 (2001).
Konstantinos Karamanos and Grégoire Nicolis, Symbolic Dynamics and Entropy Analysis of Feigenbaum Limit Sets, Chaos, Solitons and Fractals 10(7), 1135 - 1150 (1999).
D. Kohel, S. Ling and C. Xing, Explicit Sequence Expansions
Joseph Meleshko, Pascal Ochem, Jeffrey Shallit, and Sonja Linghui Shan, Pseudoperiodic Words and a Question of Shevelev, arXiv:2207.10171 [math.CO], 2022.
Nicholas C. Metropolis, Myron L. Stein and Paul R. Stein, On finite limit sets for transformations on the unit interval, J. Combin. Theory, A 15 (1973), 25-44.
Jeffrey Shallit and Anatoly Zavyalov, Transduction of Automatic Sequences and Applications, arXiv:2303.15203 [cs.FL], 2023, see p. 5.
Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Eric Weisstein's World of Mathematics, Binary carry sequence.
Eric Weisstein's World of Mathematics, Double-free set.
Index entries for characteristic functions
Index entries for sequences related to binary expansion of n
Index entries for sequences that are fixed points of mappings

Parity of A001511. Anti-parity of A007814.
Absolute values of first differences of A010060. Apart from signs, same as A029883. Essentially the same as A056832.
Swapping 0 and 1 gives A096268.
Cf. A033485, A050292 (partial sums), A089608, A088172, A019300, A039982, A073675, A121701, A141260, A000041, A174065, A220466, A154269 (Mobius transform).
Limit of A317957(n) for large n.
Cf. A060572

import Data.Bits (xor)
a035263 n = a035263_list !! (n-1)
a035263_list = zipWith xor a010060_list $ tail a010060_list
-- Reinhard Zumkeller, Mar 01 2012

nmax:=105: for p from 0 to ceil(simplify(log[2](nmax))) do for n from 1 to ceil(nmax/(p+2)) do a((2*n-1)*2^p) := (p+1) mod 2 od: od: seq(a(n), n=1..nmax); # Johannes W. Meijer, Feb 07 2013
A035263 := n -> 1 - padic[ordp](n, 2) mod 2:
seq(A035263(n), n=1..105); # Peter Luschny, Oct 02 2018

a[n_] := a[n] = If[ EvenQ[n], 1 - a[n/2], 1]; Table[ a[n], {n, 1, 105}] (* Or *)
Rest[ CoefficientList[ Series[ Sum[ x^(2^k)/(1 + (-1)^k*x^(2^k)), {k, 0, 20}], {x, 0, 105}], x]]
f[1] := True; f[x_] := Xor[f[x - 1], f[Floor[x/2]]]; a[x_] := Boole[f[x]] (* Ben Branman, Oct 04 2010 *)
a[n_] := If[n == 0, 0, 1 - Mod[ IntegerExponent[n, 2], 2]]; (* Jean-François Alcover, Jul 19 2013, after Michael Somos *)
Nest[ Flatten[# /. {0 -> {1, 1}, 1 -> {1, 0}}] &, {0}, 7] (* Robert G. Wilson v, Jul 23 2014 *)
SubstitutionSystem[{0->{1,1},1->{1,0}},1,{7}][[1]] (* Harvey P. Dale, Jun 06 2022 *)

{a(n) = if( n==0, 0, 1 - valuation(n, 2)%2)}; /* Michael Somos, Sep 04 2006 */

{a(n) = if( n==0, 0, n = abs(n); subst( Pol(binary(n)) - Pol(binary(n-1)), x, 1)%2)}; /* Michael Somos, Sep 04 2006 */

{a(n) = if( n==0, 0, n = abs(n); direuler(p=2, n, 1 / (1 - X^((p<3) + 1)))[n])}; /* Michael Somos, Sep 04 2006 */

def A035263(n): return (n&-n).bit_length()&1 # Chai Wah Wu, Jan 09 2023

(define (A035263 n) (let loop ((n n) (i 1)) (cond ((odd? n) (modulo i 2)) (else (loop (/ n 2) (+ 1 i)))))) ;; (Use mod instead of modulo in R6RS) Antti Karttunen, Sep 11 2017

Absolute values of first differences (A029883) of Thue-Morse sequence (A001285 or A010060). Self-similar under 10->1 and 11->0.
Series expansion: (1/x) * Sum_{i>=0} (-1)^(i+1)*x^(2^i)/(x^(2^i)-1). - Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Feb 17 2003
a(n) = Sum_{k>=0} (-1)^k*(floor((n+1)/2^k)-floor(n/2^k)). - Benoit Cloitre, Jun 03 2003
Another g.f.: Sum_{k>=0} x^(2^k)/(1+(-1)^k*x^(2^k)). - Ralf Stephan, Jun 13 2003
a(2*n) = 1-a(n), a(2*n+1) = 1. - Ralf Stephan, Jun 13 2003
a(n) = parity of A033485(n). - Philippe Deléham, Aug 13 2003
Equals A088172 mod 2, where A088172 = 1, 2, 3, 7, 13, 26, 53, 106, 211, 422, 845, ... (first differences of A019300). - Gary W. Adamson, Sep 21 2003
a(n) = a(n-1) - (-1)^n*a(floor(n/2)). - Benoit Cloitre, Dec 02 2003
a(1) = 1 and a(n) = abs(a(n-1) - a(floor(n/2))). - Benoit Cloitre, Dec 02 2003
a(n) = 1 - A096268(n+1); A050292 gives partial sums. - Reinhard Zumkeller, Aug 16 2006
Multiplicative with a(2^k) = 1 - (k mod 2), a(p^k) = 1, p > 2. Dirichlet g.f.: Product_{n = 4 or an odd prime} (1/(1-1/n^s)). - Christian G. Bower, May 18 2005
a(-n) = a(n). a(0)=0. - Michael Somos, Sep 04 2006
Dirichlet g.f.: zeta(s)*2^s/(2^s+1). - Ralf Stephan, Jun 17 2007
a(n+1) = a(n) XOR a(ceiling(n/2)), a(1) = 1. - Reinhard Zumkeller, Jun 11 2009
Let D(x) be the generating function, then D(x) + D(x^2) == x/(1-x). - Joerg Arndt, May 11 2010
a(n) = A010060(n) XOR A010060(n+1); a(A079523(n)) = 0; a(A121539(n)) = 1. - Reinhard Zumkeller, Mar 01 2012
a((2*n-1)*2^p) = (p+1) mod 2, p >= 0 and n >= 1. - Johannes W. Meijer, Feb 07 2013
a(n) = A000035(A001511(n)). - Omar E. Pol, Oct 29 2013
a(n) = 2-A056832(n) = (5-A089608(n))/4. - Antti Karttunen, Sep 11 2017, after Benoit Cloitre
For n >= 0, a(n+1) = M(2n) mod 2 where M(n) is the Motzkin number A001006 (see Deutsch and Sagan 2006 link). - David Callan, Oct 02 2018
a(n) = A038712(n) mod 3. - Kevin Ryde, Jul 11 2019
Given any n in the form (k * 2^m, k odd), extract k and m. Categorize the results into two outcomes of (k, m, even or odd). If (k, m) is (odd, even) substitute 1. If (odd, odd), denote the result 0.  Example: 5 = (5 * 2^0), (odd, even, = 1). (6 = 3 * 2^1), (odd, odd, = 0). - Gary W. Adamson, Jun 23 2021

Alternative description added to the name by Antti Karttunen, Sep 11 2017

A064189 Triangle T(n,k), 0 <= k <= n, read by rows, defined by: T(0,0)=1, T(n,k)=0 if n < k, T(n,k) = T(n-1,k-1) + T(n-1,k) + T(n-1,k+1).

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 4, 5, 3, 1, 9, 12, 9, 4, 1, 21, 30, 25, 14, 5, 1, 51, 76, 69, 44, 20, 6, 1, 127, 196, 189, 133, 70, 27, 7, 1, 323, 512, 518, 392, 230, 104, 35, 8, 1, 835, 1353, 1422, 1140, 726, 369, 147, 44, 9, 1, 2188, 3610, 3915, 3288, 2235, 1242, 560, 200, 54, 10, 1

Offset: 0

N. J. A. Sloane, Sep 21 2001

Motzkin triangle read in reverse order.
T(n,k) = number of lattice paths from (0,0) to (n,k), staying weakly above the x-axis and consisting of steps U=(1,1), D=(1,-1) and H=(1,0). Example: T(3,1) = 5 because we have HHU, UDU, HUH, UHH and UUD. Columns 0,1,2 and 3 give A001006 (Motzkin numbers), A002026 (first differences of Motzkin numbers), A005322 and A005323, respectively. - Emeric Deutsch, Feb 29 2004
Riordan array ((1-x-sqrt(1-2x-3x^2))/(2x^2), (1-x-sqrt(1-2x-3x^2))/(2x)). Inverse is the array (1/(1+x+x^2), x/(1+x+x^2)) (A104562). - Paul Barry, Mar 15 2005
Inverse binomial matrix applied to A039598. - Philippe Deléham, Feb 28 2007
Triangle T(n,k), 0 <= k <= n, read by rows given by: T(0,0)=1, T(n,k)=0 if k < 0 or if k > n, T(n,0) = T(n-1,0) + T(n-1,1), T(n,k) = T(n-1,k-1) + T(n-1,k) + T(n-1,k+1) for k >= 1. - Philippe Deléham, Mar 27 2007
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 from 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. - Philippe Deléham, Sep 25 2007
Equals binomial transform of triangle A053121. - Gary W. Adamson, Oct 25 2008
Consider a semi-infinite chessboard with squares labeled (n,k), ranks or rows n >= 0, files or columns k >= 0; the number of king-paths of length n from (0,0) to (n,k), 0 <= k <= n, is T(n,k). The recurrence relation given above relates to the movements of the king. This is essentially the comment made by Harrie Grondijs for the Motzkin triangle A026300. - Johannes W. Meijer, Oct 10 2010

			Triangle begins:
  [0]   1;
  [1]   1,    1;
  [2]   2,    2,    1;
  [3]   4,    5,    3,    1;
  [4]   9,   12,    9,    4,   1;
  [5]  21,   30,   25,   14,   5,   1;
  [6]  51,   76,   69,   44,  20,   6,   1;
  [7] 127,  196,  189,  133,  70,  27,   7,  1;
  [8] 323,  512,  518,  392, 230, 104,  35,  8, 1;
  [9] 835, 1353, 1422, 1140, 726, 369, 147, 44, 9, 1;
  ...
From _Philippe Deléham_, Nov 04 2011: (Start)
Production matrix begins:
  1, 1
  1, 1, 1
  0, 1, 1, 1
  0, 0, 1, 1, 1
  0, 0, 0, 1, 1, 1
  0, 0, 0, 0, 1, 1, 1 (End)

See A026300 for additional references and other information.

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened
E. Barcucci, R. Pinzani and R. Sprugnoli, The Motzkin family, P.U.M.A. Ser. A, Vol. 2, 1991, No. 3-4, pp. 249-279.
Paul Barry, On Motzkin-Schröder Paths, Riordan Arrays, and Somos-4 Sequences, J. Int. Seq. (2023) Vol. 26, Art. 23.4.7.
Paul Barry, Moment sequences, transformations, and Spidernet graphs, arXiv:2307.00098 [math.CO], 2023.
Paul Barry, Notes on Riordan arrays and lattice paths, arXiv:2504.09719 [math.CO], 2025. See pp. 16, 29.
Xiaomei Chen, Counting humps and peaks in Motzkin paths with height k, arXiv:2412.00668 [math.CO], 2024. See pp. 3, 7.
Igor Dolinka, James East, Athanasios Evangelou, Desmond FitzGerald, Nicholas Ham, James Hyde, Nicholas Loughlin, and James Mitchell, Idempotent Statistics of the Motzkin and Jones Monoids, arXiv preprint arXiv:1507.04838 [math.CO], 2015.
Igor Dolinka, James East, and Robert D. Gray, Motzkin monoids and partial Brauer monoids, arXiv preprint arXiv:1512.02279 [math.GR], 2015.
Robert Donaghey and Louis W. Shapiro, Motzkin numbers, J. Combin. Theory, Series A, 23 (1977), 291-301.
Ivana Đurđev, Igor Dolinka, and James East, Sandwich semigroups in diagram categories, arXiv:1910.10286 [math.GR], 2019.
Samuele Giraudo, Tree series and pattern avoidance in syntax trees, arXiv:1903.00677 [math.CO], 2019.
Tom Halverson and Theodore N. Jacobson, Set-partition tableaux and representations of diagram algebras, arXiv:1808.08118 [math.RT], 2018.
Toufik Mansour and Mark Shattuck, Enumeration of Catalan and smooth words according to capacity, Integers (2025) Vol. 25, Art. No. A5. See p. 29.
Donatella Merlini and Massimo Nocentini, Algebraic Generating Functions for Languages Avoiding Riordan Patterns, Journal of Integer Sequences, Vol. 21 (2018), Article 18.1.3.
Robin Pemantle and Mark C. Wilson, Twenty Combinatorial Examples of Asymptotics Derived from Multivariate Generating Functions, SIAM Rev., 50 (2008), no. 2, 199-272. See p. 265.
Sheng-Liang Yang, Yan-Ni Dong, and Tian-Xiao He, Some matrix identities on colored Motzkin paths, Discrete Mathematics 340.12 (2017): 3081-3091.
Sheng-Liang Yang and Yuan-Yuan Gao, The Pascal rhombus and Riordan arrays, Fib. Q., 56:4 (2018), 337-347. See Fig. 3.

A026300 (the main entry for this sequence) with rows reversed.
Cf. A001006, A002026, A005322, A005323, A053121.
Row sums give: A005773(n+1) or A307789(n+2).

alias(C=binomial): A064189 := (n,k) -> add(C(n,j)*(C(n-j,j+k)-C(n-j,j+k+2)), j=0..n): seq(seq(A064189(n,k), k=0..n),n=0..10); # Peter Luschny, Dec 31 2019
# Uses function PMatrix from A357368. Adds a row above and a column to the left.
PMatrix(10, n -> simplify(hypergeom([1 -n/2, -n/2+1/2], [2], 4))); # Peter Luschny, Oct 08 2022

T[0, 0, x_, y_] := 1; T[n_, 0, x_, y_] := x*T[n - 1, 0, x, y] + T[n - 1, 1, x, y]; T[n_, k_, x_, y_] := T[n, k, x, y] = If[k < 0 || k > n, 0, T[n - 1, k - 1, x, y] + y*T[n - 1, k, x, y] + T[n - 1, k + 1, x, y]]; Table[T[n, k, 1, 1], {n, 0, 10}, {k, 0, n}] // Flatten (* G. C. Greubel, Apr 21 2017 *)
T[n_, k_] := Binomial[n, k] Hypergeometric2F1[(k - n)/2, (k - n + 1)/2, k + 2, 4];
Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten  (* Peter Luschny, May 19 2021 *)

{T(n, k) = if( k<0 || k>n, 0, polcoeff( polcoeff( 2 / (1 - x + sqrt(1 - 2*x - 3*x^2) - 2*x*y) + x * O(x^n), n), k))}; /* Michael Somos, Jun 06 2016 */

def A064189_triangel(dim):
    M = matrix(ZZ,dim,dim)
    for n in range(dim): M[n,n] = 1
    for n in (1..dim-1):
        for k in (0..n-1):
            M[n,k] = M[n-1,k-1]+M[n-1,k]+M[n-1,k+1]
    return M
A064189_triangel(9) # Peter Luschny, Sep 20 2012

Sum_{k=0..n} T(n, k)*(k+1) = 3^n.
Sum_{k=0..n} T(n, k)*T(n, n-k) = T(2*n, n) - T(2*n, n+2)
G.f.: M/(1-t*z*M), where M = 1 + z*M + z^2*M^2 is the g.f. of the Motzkin numbers (A001006). - Emeric Deutsch, Feb 29 2004
Sum_{k>=0} T(m, k)*T(n, k) = A001006(m+n). - Philippe Deléham, Mar 05 2004
Sum_{k>=0} T(n-k, k) = A005043(n+2). - Philippe Deléham, May 31 2005
Column k has e.g.f. exp(x)*(BesselI(k,2*x)-BesselI(k+2,2*x)). - Paul Barry, Feb 16 2006
T(n,k) = Sum_{j=0..n} C(n,j)*(C(n-j,j+k) - C(n-j,j+k+2)). - Paul Barry, Feb 16 2006
n-th row is generated from M^n * V, where M = the infinite tridiagonal matrix with all 1's in the super, main and subdiagonals; and V = the infinite vector [1,0,0,0,...]. E.g., Row 3 = (4, 5, 3, 1), since M^3 * V = [4, 5, 3, 1, 0, 0, 0, ...]. - Gary W. Adamson, Nov 04 2006
T(n,k) = A122896(n+1,k+1). - Philippe Deléham, Apr 21 2007
T(n,k) = (k/n)*Sum_{j=0..n} binomial(n,j)*binomial(j,2*j-n-k). - Vladimir Kruchinin, Feb 12 2011
Sum_{k=0..n} T(n,k)*(-1)^k*(k+1) = (-1)^n. - Werner Schulte, Jul 08 2015
Sum_{k=0..n} T(n,k)*(k+1)^3 = (2*n+1)*3^n. - Werner Schulte, Jul 08 2015
G.f.: 2 / (1 - x + sqrt(1 - 2*x - 3*x^2) - 2*x*y) = Sum_{n >= k >= 0} T(n, k) * x^n * y^k. - Michael Somos, Jun 06 2016
T(n,k) = binomial(n, k)*hypergeom([(k-n)/2, (k-n+1)/2], [k+2], 4). - Peter Luschny, May 19 2021
The coefficients of the n-th degree Taylor polynomial of the function (1 - x^2)*(1 + x + x^2)^n expanded about the point x = 0 give the entries in row n in reverse order. - Peter Bala, Sep 06 2022

More terms from Vladeta Jovovic, Sep 23 2001

A026300 Motzkin triangle, T, read by rows; T(0,0) = T(1,0) = T(1,1) = 1; for n >= 2, T(n,0) = 1, T(n,k) = T(n-1,k-2) + T(n-1,k-1) + T(n-1,k) for k = 1,2,...,n-1 and T(n,n) = T(n-1,n-2) + T(n-1,n-1).

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 1, 3, 5, 4, 1, 4, 9, 12, 9, 1, 5, 14, 25, 30, 21, 1, 6, 20, 44, 69, 76, 51, 1, 7, 27, 70, 133, 189, 196, 127, 1, 8, 35, 104, 230, 392, 518, 512, 323, 1, 9, 44, 147, 369, 726, 1140, 1422, 1353, 835, 1, 10, 54, 200, 560, 1242, 2235, 3288, 3915, 3610, 2188

Offset: 0

Clark Kimberling

Right-hand columns have g.f. M^k, where M is g.f. of Motzkin numbers.

Consider a semi-infinite chessboard with squares labeled (n,k), ranks or rows n >= 0, files or columns k >= 0; number of king-paths of length n from (0,0) to (n,k), 0 <= k <= n, is T(n,n-k). - Harrie Grondijs, May 27 2005. Cf. A114929, A111808, A114972.

			Triangle starts:
  [0] 1;
  [1] 1, 1;
  [2] 1, 2,  2;
  [3] 1, 3,  5,   4;
  [4] 1, 4,  9,  12,   9;
  [5] 1, 5, 14,  25,  30,  21;
  [6] 1, 6, 20,  44,  69,  76,   51;
  [7] 1, 7, 27,  70, 133, 189,  196,  127;
  [8] 1, 8, 35, 104, 230, 392,  518,  512,  323;
  [9] 1, 9, 44, 147, 369, 726, 1140, 1422, 1353, 835.

Harrie Grondijs, Neverending Quest of Type C, Volume B - the endgame study-as-struggle.
A. Nkwanta, Lattice paths and RNA secondary structures, in African Americans in Mathematics, ed. N. Dean, Amer. Math. Soc., 1997, pp. 137-147.

Reinhard Zumkeller, Rows n = 0..120 of triangle, flattened
M. Aigner, Motzkin Numbers, Europ. J. Comb. 19 (1998), 663-675.
Tewodros Amdeberhan, Moa Apagodu, and Doron Zeilberger, Wilf's "Snake Oil" Method Proves an Identity in The Motzkin Triangle, arXiv:1507.07660 [math.CO], 2015.
J. L. Arregui, Tangent and Bernoulli numbers related to Motzkin and Catalan numbers by means of numerical triangles, arXiv:math/0109108 [math.NT], 2001.
F. R. Bernhart, Catalan, Motzkin and Riordan numbers, Discr. Math., 204 (1999), 73-112.
Henry Bottomley, Illustration of initial terms
M. Buckley, R. Garner, S. Lack, and R. Street, Skew-monoidal categories and the Catalan simplicial set, arXiv preprint arXiv:1307.0265 [math.CT], 2013.
L. Carlitz, Solution of certain recurrences, SIAM J. Appl. Math., 17 (1969), 251-259.
J. L. Chandon, J. LeMaire and J. Pouget, Denombrement des quasi-ordres sur un ensemble fini, Math. Sci. Humaines, No. 62 (1978), 61-80.
Xiang-Ke Chang, X.-B. Hu, H. Lei, and Y.-N. Yeh, Combinatorial proofs of addition formulas, The Electronic Journal of Combinatorics, 23(1) (2016), #P1.8.
I. Dolinka, J. East, A. Evangelou, D. FitzGerald, and N. Ham, Idempotent Statistics of the Motzkin and Jones Monoids, arXiv preprint arXiv:1507.04838 [math.CO], 2015-2016.
Samuele Giraudo, Tree series and pattern avoidance in syntax trees, arXiv:1903.00677 [math.CO], 2019.
Veronika Irvine, Lace Tessellations: A mathematical model for bobbin lace and an exhaustive combinatorial search for patterns, PhD Dissertation, University of Victoria, 2016.
A. Luzón, D. Merlini, M. A. Morón, and R. Sprugnoli, Complementary Riordan arrays, Discrete Applied Mathematics, 172 (2014) 75-87.
A. Roshan, P. H. Jones and C. D. Greenman, An Exact, Time-Independent Approach to Clone Size Distributions in Normal and Mutated Cells, arXiv preprint arXiv:1311.5769 [q-bio.QM], 2013.
M. János Uray, A family of barely expansive polynomials, Eötvös Loránd University (Budapest, Hungary, 2020).
Mark C. Wilson, Diagonal asymptotics for products of combinatorial classes, PDF.
Mark C. Wilson, Diagonal asymptotics for products of combinatorial classes, Combinatorics, Probability and Computing, Volume 24, Special Issue 01,January 2015, pp 354-372.
D. Yaqubi, M. Farrokhi D.G., and H. Gahsemian Zoeram, Lattice paths inside a table. I, arXiv:1612.08697 [math.CO], 2016-2017.

Reflected version is in A064189.
Row sums are in A005773.
T(n,n) are Motzkin numbers A001006.
Other columns of T include A002026, A005322, A005323.
Cf. A099323, A097357, A005043, A059738, A027907, A020474, A059738.

a026300 n k = a026300_tabl !! n !! k
a026300_row n = a026300_tabl !! n
a026300_tabl = iterate (\row -> zipWith (+) ([0,0] ++ row) $
                                zipWith (+) ([0] ++ row) (row ++ [0])) [1]
-- Reinhard Zumkeller, Oct 09 2013

A026300 := proc(n,k)
   add(binomial(n,2*i+n-k)*(binomial(2*i+n-k,i) -binomial(2*i+n-k,i-1)), i=0..floor(k/2));
end proc: # R. J. Mathar, Jun 30 2013

t[n_, k_] := Sum[ Binomial[n, 2i + n - k] (Binomial[2i + n - k, i] - Binomial[2i + n - k, i - 1]), {i, 0, Floor[k/2]}]; Table[ t[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Robert G. Wilson v, Jan 03 2011 *)
t[, 0] = 1; t[n, 1] := n; t[n_, k_] /; k>n || k<0 = 0; t[n_, n_] := t[n, n] = t[n-1, n-2]+t[n-1, n-1]; t[n_, k_] := t[n, k] = t[n-1, k-2]+t[n-1, k-1]+t[n-1, k]; Table[t[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Apr 18 2014 *)
T[n_, k_] := Binomial[n, k] Hypergeometric2F1[1/2 - k/2, -k/2, n - k + 2, 4];
Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Peter Luschny, Mar 21 2018 *)

tabl(nn) = {for (n=0, nn, for (k=0, n, print1(sum(i=0, k\2, binomial(n, 2*i+n-k)*(binomial(2*i+n-k, i)-binomial(2*i+n-k, i-1))), ", ");); print(););} \\ Michel Marcus, Jul 25 2015

T(n,k) = Sum_{i=0..floor(k/2)} binomial(n, 2i+n-k)*(binomial(2i+n-k, i) - binomial(2i+n-k, i-1)). - Herbert Kociemba, May 27 2004
T(n,k) = A027907(n,k) - A027907(n,k-2), k<=n.
Sum_{k=0..n} (-1)^k*T(n,k) = A099323(n+1). - Philippe Deléham, Mar 19 2007
Sum_{k=0..n} (T(n,k) mod 2) = A097357(n+1). - Philippe Deléham, Apr 28 2007
Sum_{k=0..n} T(n,k)*x^(n-k) = A005043(n), A001006(n), A005773(n+1), A059738(n) for x = -1, 0, 1, 2 respectively. - Philippe Deléham, Nov 28 2009
T(n,k) = binomial(n, k)*hypergeom([1/2 - k/2, -k/2], [n - k + 2], 4). - Peter Luschny, Mar 21 2018
T(n,k) = [t^(n-k)] [x^n] 2/(1 - (2*t + 1)*x + sqrt((1 + x)*(1 - 3*x))). - Peter Luschny, Oct 24 2018
The n-th row polynomial R(n,x) equals the n-th degree Taylor polynomial of the function (1 - x^2)*(1 + x + x^2)^n expanded about the point x = 0. - Peter Bala, Feb 26 2023

Corrected and edited by Johannes W. Meijer, Oct 05 2010

A005717 Construct triangle in which n-th row is obtained by expanding (1 + x + x^2)^n and take the next-to-central column.

Original entry on oeis.org

1, 2, 6, 16, 45, 126, 357, 1016, 2907, 8350, 24068, 69576, 201643, 585690, 1704510, 4969152, 14508939, 42422022, 124191258, 363985680, 1067892399, 3136046298, 9217554129, 27114249960, 79818194925, 235128465026, 693085098852, 2044217638456, 6032675068061

Offset: 1

N. J. A. Sloane

Number of ordered trees with n+1 edges, having root of even degree and nonroot nodes of outdegree at most 2. - Emeric Deutsch, Aug 02 2002
The connection to Motzkin numbers comes from the Lagrange inversion formula. - Michael Somos, Oct 10 2003
Number of horizontal steps in all Motzkin paths of length n. - Emeric Deutsch, Nov 09 2003
Number of UHD's in all Motzkin paths of length n+2 (here U=(1,1), H=(1,0) and D=(1,-1)). Example: a(2)=2 because in the nine Motzkin paths of length 4, HHHH, HHUD, HUDH, H(UHD), UDHH, UDUD, (UHD)H, UHHD and UUDD, we have altogether two UHD's (shown between parentheses). - Emeric Deutsch, Dec 26 2003
Number of ordered trees with n+1 edges, having exactly one leaf at even height. Number of Dyck path of semilength n+1, having exactly one peak at even height. Example: a(3)=6 because we have uuu(ud)ddd, u(ud)dudud, udu(ud)dud, ududu(ud)d, u(ud)uuddd and uuudd(ud)d (here u=(1,1),d=(1,-1) and the unique peak at even height is shown between parentheses). - Emeric Deutsch, Mar 10 2004
a(n) is the number of Dyck (n+1)-paths containing exactly one UDU. - David Callan, Jul 15 2004
Number of peaks in all Motzkin paths of length n+1. - Emeric Deutsch, Sep 01 2004
This is a kind of Motzkin transform of A059841 because the substitution x -> x*A001006(x) in the independent variable of the g.f. of A059841 generates 1,0,1,2,6,16,... that is 1,0 followed by this sequence here. - R. J. Mathar, Nov 08 2008
a(n) is the number of lattice paths avoiding N^(>=3) from (0,0) to (n,n). - Shanzhen Gao, Apr 20 2010
a(n+1) is the number of binary strings having n 0's and n 1's and no appearance of 000.  For example, for n = 1, there 2 strings: 01 and 10.  For n = 2, there are 6: 0011, 0101, 0110, 1001, 1010, 1100. - Toby Gottfried, Sep 12 2011
a(n) is the number of paths in the half-plane x>=0, from (0,0) to (n,1), and consisting of steps U=(1,1), D=(1,-1) and H=(1,0). For example, for n=3, we have the 6 paths HHU, HUH, UDU, UUD, UHH, DUU. - José Luis Ramírez Ramírez, Apr 19 2015
a(n) is the number of ways to tile a strip of length 2*n+1 with squares, dominos, and trominos, where the number of trominos is always one more than the number of squares. - Greg Dresden and Anna Kalynchuk, Jul 30 2025

			G.f. = x + 2*x^2 + 6*x^3 + 16*x^4 + 45*x^5 + 126*x^6 + 357*x^7 + ...

Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 78.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

G. C. Greubel, Table of n, a(n) for n = 1..1000 (Terms 1 to 200 computed by T. D. Noe; terms 201 to 1000 by G. C. Greubel, Jan 15 2017)
Kassie Archer and Christina Graves, A new statistic on Dyck paths for counting 3-dimensional Catalan words, arXiv:2205.09686 [math.CO], 2022.
Jean-Luc Baril, Sergey Kirgizov, José L. Ramírez, and Diego Villamizar, The Combinatorics of Motzkin Polyominoes, arXiv:2401.06228 [math.CO], 2024. See page 13.
Emeric Deutsch, Ordered trees with prescribed root degrees, node degrees, and branch lengths, Discrete Mathematics 282 (2004), 89-94.
Ricardo Gómez Aíza, Trees with flowers: A catalog of integer partition and integer composition trees with their asymptotic analysis, arXiv:2402.16111 [math.CO], 2024. See p. 23.
Richard K. Guy, Letter to N. J. A. Sloane, 1987.
Stanislav Krymski and Alexander Okhotin, Longer Shortest Strings in Two-Way Finite Automata, in: Jirásková G., Pighizzini G. (eds) Descriptional Complexity of Formal Systems. DCFS 2020. Lecture Notes in Computer Science, vol 12442. Springer, Cham.
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, Une méthode pour obtenir la fonction génératrice d'une série, arXiv:0912.0072 [math.NT], 2009; FPSAC 1993, Florence. Formal Power Series and Algebraic Combinatorics.
Mark Shattuck, Subword Patterns in Smooth Words, Enum. Comb. Appl. (2024) Vol. 4, No. 4, Art. No. S2R32. See p. 6.
Chenying Wang, Piotr Miska, and István Mező, The r-derangement numbers, Discrete Mathematics 340(7) (2017), 1681-1692.
Eric Weisstein's World of Mathematics, Trinomial Coefficient.

A diagonal of A027907.

Cf. A001006, A002426, A005043, A005773, A076540 (binomial transform).

seq(add(binomial(i, k) *binomial(i-k, k+1), k=0..floor(i/2)), i=1..30); # Detlef Pauly (dettodet(AT)yahoo.de), Nov 09 2001
M:= proc(n) option remember; `if` (n<2, 1, (3*(n-1)*M(n-2) +(2*n+1) *M(n-1))/ (n+2)) end: A005717 := n -> n*M(n-1):
seq(A005717(i), i=1..27); # Peter Luschny, Sep 12 2011
a := n -> simplify(GegenbauerC(n,-n-1,-1/2)):
seq(a(n), n=0..28); # Peter Luschny, May 07 2016

Table[Coefficient[Expand[(1+x+x^2)^n], x, n-1], {n, 1, 40}]
Table[n*Hypergeometric2F1[(1 - n)/2, 1 - n/2, 2, 4], {n, 29}] (* Arkadiusz Wesolowski, Aug 13 2012 *)
Table[GegenbauerC[n,-n-1,-1/2],{n,0,100}] (* Emanuele Munarini, Oct 20 2016 *)

makelist(ultraspherical(n,-n-1,-1/2),n,0,12); /* Emanuele Munarini, Oct 20 2016 */

{a(n) = if( n<0, 0, polcoeff( (1 + x + x^2)^n, n-1))}; /* Michael Somos, Sep 09 2002 */

{a(n) = if( n<0, 0, n * polcoeff( serreverse( x / (1 + x + x^2) + x * O(x^n)), n))}; /* Michael Somos, Oct 10 2003 */

N=10^3;  x='x+'x*O('x^N);
gf = 2*x/(1-2*x-3*x^2+(1-x)*sqrt(1-2*x-3*x^2));
v005717 = Vec(gf);
/* Joerg Arndt, Aug 16 2012 */

def A():
    a, b, n = 0, 1, 1
    while True:
        yield b
        n += 1
        a, b = b, (3*(n-1)*n*a+(2*n-1)*n*b)//((n+1)*(n-1))
A005717 = A()
print([next(A005717) for  in range(29)]) # _Peter Luschny, May 16 2016

a(n) = Sum_{k=1..n} T(k, k-1), where T is the array defined in A025177.
G.f.: 2*x/(1-2*x-3*x^2+(1-x)*sqrt(1-2*x-3*x^2)). - Emeric Deutsch, Aug 14 2002
E.g.f.: exp(x) * I_1(2x), where I_1 is the Bessel function. - Michael Somos, Sep 09 2002
a(n) = A111808(n,n-1). - Reinhard Zumkeller, Aug 17 2005
a(n) = Sum_{k=0..floor((n-1)/3)} (-1)^k * binomial(n,k) * binomial(2n-2-3k, n-1). - David Callan, Jul 03 2006
From Paul Barry, Feb 05 2007: (Start)
a(n) = n*Sum_{k=0..floor((n-1)/2), C(n-1,2k)*C(k)}, C(n) = A000108(n).
a(n) = Sum_{k=0..floor((n-1)/2)} (2k+1)*C(n,2k+1)*C(k).
a(n) = Sum_{k=0..n-1} ( Sum_{j=0..floor(k/2)} C(k,2j)*C(2j+1,j) ). (End)
a(n) = (A002426(n+1) - A002426(n))/2. - Paul Barry, May 22 2008
a(n) = n*A001006(n-1). - Paul Barry, Oct 05 2009
a(n) = Sum_{i=0..floor(n/2)} C(n+1,n-i) * C(n-i,i). - Shanzhen Gao, Apr 20 2010
D-finite with recurrence: (n+1)*a(n) - 3*n*a(n-1) - (n+3)*a(n-2) + 3*(n-2)*a(n-3) = 0. - R. J. Mathar, Nov 28 2011
a(n) ~ 3^(n+1/2)/(2*sqrt(Pi*n)). - Vaclav Kotesovec, Aug 09 2013
0 = a(n) * 3*(n+1)*(n+2) + a(n+1) * (n+2)*(2*n+3) - a(n+2) * (n+1)*(n+3) for all n in Z. - Michael Somos, Apr 03 2014
G.f.: z*M(z)/(1-z-2*z^2*M(z)), where M(z) is the g.f. of Motzkin paths. - José Luis Ramírez Ramírez, Apr 19 2015
Working with an offset of 0, a(n) = [x^n](1 + x + x^2)^(n+1); binomial transform is A076540. - Peter Bala, Jun 15 2015
a(n) = GegenbauerC(n,-n-1,-1/2). - Peter Luschny, May 07 2016
a(n) = (-1)^(n+1) * n * hypergeom([3/2, 1-n], [3], 4). - Vladimir Reshetnikov, Sep 28 2016
a(n) = Sum_{k=0..n-1} binomial(n,k)*binomial(n-k, k+1) [Krymski and Okhotin]. - Michel Marcus, Dec 04 2020
a(n) = (1/2)*(A005773(n+1) - A005043(n)). - Peter Bala, Feb 11 2022
a(n) = A002426(n) - A005043(n). - Amiram Eldar, May 17 2024

More terms from Erich Friedman, Jun 01 2001

A079523 Utterly odd numbers: numbers whose binary representation ends in an odd number of ones.

Original entry on oeis.org

1, 5, 7, 9, 13, 17, 21, 23, 25, 29, 31, 33, 37, 39, 41, 45, 49, 53, 55, 57, 61, 65, 69, 71, 73, 77, 81, 85, 87, 89, 93, 95, 97, 101, 103, 105, 109, 113, 117, 119, 121, 125, 127, 129, 133, 135, 137, 141, 145, 149, 151, 153, 157, 159, 161, 165, 167, 169, 173, 177, 181

Offset: 1

Benoit Cloitre, Jan 21 2003

Also, n such that A010060(n) = A010060(n+1) where A010060 is the Thue-Morse sequence.
Sequence of n such that a(n) = 3n begins 7, 23, 27, 29, 31, 39, 71, 87, 91, 93, 95, ...
Values of k such that the Motzkin number A001006(2k) is even. Values of k such that the number of restricted hexagonal polyominoes with 2k+1 cells is even (see A002212). Values of k such that the number of directed animals of size k+1 is even (see A005773). Values of k such that the Riordan number A005043(k) is even. - Emeric Deutsch and Bruce E. Sagan, Apr 02 2003
a(n) = A036554(n)-1 = A072939(n)-2. - Ralf Stephan, Jun 09 2003
Odious and evil terms alternate. - Vladimir Shevelev, Jun 22 2009
The sequence has the following fractal property: remove terms of the form 4k+1 from the sequence, and the remaining terms are of the form 4k+3: 7, 23, 31, 39, 55, 71, 87, ...; then subtract 3 from each of these terms and divide by 4 and you get the original sequence: 1, 5, 7, 9, 13, ... - Benoit Cloitre, Apr 06 2010
A035263(a(n)) = 0. - Reinhard Zumkeller, Mar 01 2012

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
J.-P. Allouche, Thue, Combinatorics on words, and conjectures inspired by the Thue-Morse sequence, arXiv preprint arXiv:1401.3727 [math.NT], 2014.
J.-P. Allouche, Thue, Combinatorics on words, and conjectures inspired by the Thue-Morse sequence, J. de Théorie des Nombres de Bordeaux, 27, no. 2 (2015), 375-388.
J.-P. Allouche, A. Arnold, J. Berstel, S. Brlek, W. Jockusch, Simon Plouffe, and B. E. Sagan, A relative of the Thue-Morse sequence, Discrete Math., 139, 1995, 455-461.
Narad Rampersad and Manon Stipulanti, The Formal Inverse of the Period-Doubling Sequence, arXiv:1807.11899 [math.CO], 2018.
Thomas Zaslavsky, Anti-Fibonacci Numbers: A Formula, Sep 26 2016 [Introduces the name "utterly odd". - _N. J. A. Sloane_, Sep 27 2016]
Index entries for 2-automatic sequences.

Cf. A003159, A003157, A003158, A075326, A131323.

import Data.List (elemIndices)
a079523 n = a079523_list !! (n-1)
a079523_list = elemIndices 0 a035263_list
-- Reinhard Zumkeller, Mar 01 2012

[n: n in [0..200] | Valuation(n+1, 2) mod 2 eq 0 + 1]; // Vincenzo Librandi, Apr 16 2015

Select[ Range[200], MatchQ[ IntegerDigits[#, 2], {b : (1) ..} | {_, 0, b : (1) ..} /; OddQ[ Length[{b}]]] & ] (* Jean-François Alcover, Jun 17 2013 *)

is(n)=valuation(n+1,2)%2 \\ Charles R Greathouse IV, Mar 07 2013

from itertools import count, islice
def A079523_gen(startvalue=1): return filter(lambda n:(~(n+1)&n).bit_length()&1,count(max(startvalue,1))) # generator of terms >= startvalue
A079523_list = list(islice(A079523_gen(),61)) # Chai Wah Wu, Jul 05 2022

def A079523(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        kmin = kmax >> 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x):
        c, s = n+x, bin(x)[2:]
        l = len(s)
        for i in range(l&1,l,2):
            c -= int(s[i])+int('0'+s[:i],2)
        return c
    return bisection(f,n,n)-1 # Chai Wah Wu, Jan 29 2025

a(n) is asymptotic to 3n.
a(n) = 2*A003159(n) - 1. a(1)=1, a(n) = a(n-1) + 2 if (a(n-1)+1)/2 does not belong to the sequence and a(n) = a(n-1) + 4 otherwise. - Emeric Deutsch and Bruce E. Sagan, Apr 02 2003
a(n) = (1/2)*A081706(2n-1).
a(n) = A003158(n) - n = A003157(n) - n - 1. - Philippe Deléham, Feb 22 2004
Values of k such that A091297(k) = 0. - Philippe Deléham, Feb 25 2004

A024718 a(n) = (1/2)(1 + Sum_{k=0..n} binomial(2k, k)).

Original entry on oeis.org

1, 2, 5, 15, 50, 176, 638, 2354, 8789, 33099, 125477, 478193, 1830271, 7030571, 27088871, 104647631, 405187826, 1571990936, 6109558586, 23782190486, 92705454896, 361834392116, 1413883873976, 5530599237776, 21654401079326, 84859704298202, 332818970772254

Offset: 0

Clark Kimberling

nonn

Total number of leaves in all rooted ordered trees with at most n edges. - Michael Somos, Feb 14 2006
Also: Number of UH-free Schroeder paths of semilength n with horizontal steps only at level less than two [see Yan]. - R. J. Mathar, May 24 2008
Hankel transform is A010892. - Paul Barry, Apr 28 2009
Binomial transform of A005773. - Philippe Deléham, Dec 13 2009
Number of vertices all of whose children are leaves in all ordered trees with n+1 edges. Example: a(3) = 15; for an explanation see David Callan's comment in A001519. - Emeric Deutsch, Feb 12 2015

			G.f. = 1 + 2*x + 5*x^2 + 15*x^3 + 50*x^4 + 176*x^5 + 638*x^6 + ...

Michael De Vlieger, Table of n, a(n) for n = 0..1664
Guo-Niu Han, Enumeration of Standard Puzzles, 2011. [Cached copy]
Guo-Niu Han, Enumeration of Standard Puzzles, arXiv:2006.14070 [math.CO], 2020.
Sherry H. F. Yan, Schröder Paths and Pattern Avoiding Partitions, arXiv:0805.2465 [math.CO], 2008-2009.

Partial sums of A088218.
Bisection of A086905.
Second column of triangle A102541.
Cf. A000108, A006134, A024494, A079309.

A024718 := n -> (binomial(2*n, n)*hypergeom([1, -n], [1/2 - n], 1/4) + 1)/2:
seq(simplify(A024718(n)), n = 0..26); # Peter Luschny, Dec 15 2024

Table[Sum[Binomial[2k-1,k-1],{k,0,n}],{n,0,100}] (* Emanuele Munarini, May 18 2018 *)

a(n) = (1 + sum(k=0, n, binomial(2*k, k)))/2; \\ Michel Marcus, May 18 2018

a(n) = A079309(n) + 1.
G.f.: 1/((1 - x)*(2 - C)), where C = g.f. for the Catalan numbers A000108. - N. J. A. Sloane, Aug 30 2002
Given g.f. A(x), then x * A(x - x^2) is the g.f. of A024494. - Michael Somos, Feb 14 2006
G.f.: (1 + 1 / sqrt(1 - 4*x)) / (2 - 2*x). - Michael Somos, Feb 14 2006
D-finite with recurrence: n*a(n) - (5*n-2)*a(n-1) + 2*(2*n-1)*a(n-2) = 0. - R. J. Mathar, Dec 02 2012
Remark: The above recurrence is true (it can be easily proved by differentiating the generating function). Notice that it is the same recurrence satisfied by the partial sums of the central binomial coefficients (A006134). - Emanuele Munarini, May 18 2018
0 = a(n)*(16*a(n+1) - 22*a(n+2) + 6*a(n+3)) + a(n+1)*(-18*a(n+1) + 27*a(n+2) - 7*a(n+3)) + a(n+2)*(-3*a(n+2) + a(n+3)) for all n in Z if a(n) = 1/2 for n < 0. - Michael Somos, Apr 23 2014
a(n) = ((1 - I/sqrt(3))/2 - binomial(2*n+1, n)*hypergeom([n+3/2, 1], [n+2], 4)). - Peter Luschny, May 18 2018
a(n) = [x^n] 1/((1-x+x^2) * (1-x)^n). - Seiichi Manyama, Apr 06 2024

Name edited by Petros Hadjicostas, Aug 04 2020

A038622 Triangular array that counts rooted polyominoes.

Original entry on oeis.org

1, 2, 1, 5, 3, 1, 13, 9, 4, 1, 35, 26, 14, 5, 1, 96, 75, 45, 20, 6, 1, 267, 216, 140, 71, 27, 7, 1, 750, 623, 427, 238, 105, 35, 8, 1, 2123, 1800, 1288, 770, 378, 148, 44, 9, 1, 6046, 5211, 3858, 2436, 1296, 570, 201, 54, 10, 1, 17303, 15115, 11505, 7590, 4302, 2067, 825, 265

Offset: 0

N. J. A. Sloane, torsten.sillke(AT)lhsystems.com

The PARI program gives any row k and any n-th term for this triangular array in square or right triangle array format. - Randall L Rathbun, Jan 20 2002
Triangle T(n,k), 0 <= k <= n, read by rows given by: T(0,0)=1, T(n,k)=0 if k < 0 or if k > n, T(n,0) = 2*T(n-1,0) + T(n-1,1), T(n,k) = T(n-1,k-1) + T(n-1,k) + T(n-1,k+1) for k >= 1. - Philippe Deléham, Mar 27 2007
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. - Philippe Deléham, Sep 25 2007
Triangle read by rows = partial sums of A064189 terms starting from the right. - Gary W. Adamson, Oct 25 2008
Column k has e.g.f. exp(x)*(Bessel_I(k,2x)+Bessel_I(k+1,2x)). - Paul Barry, Mar 08 2011

			From _Paul Barry_, Mar 08 2011: (Start)
Triangle begins
     1;
     2,    1;
     5,    3,    1;
    13,    9,    4,   1;
    35,   26,   14,   5,   1;
    96,   75,   45,  20,   6,   1;
   267,  216,  140,  71,  27,   7,  1;
   750,  623,  427, 238, 105,  35,  8, 1;
  2123, 1800, 1288, 770, 378, 148, 44, 9, 1;
Production matrix is
  2, 1,
  1, 1, 1,
  0, 1, 1, 1,
  0, 0, 1, 1, 1,
  0, 0, 0, 1, 1, 1,
  0, 0, 0, 0, 1, 1, 1,
  0, 0, 0, 0, 0, 1, 1, 1,
  0, 0, 0, 0, 0, 0, 1, 1, 1,
  0, 0, 0, 0, 0, 0, 0, 1, 1, 1
(End)

Reinhard Zumkeller, Rows n = 0..120 of triangle, flattened
D. Gouyou-Beauchamps and G. Viennot, Equivalence of the two-dimensional directed animal problem to a one-dimensional path problem, Adv. in Appl. Math. 9 (1988), no. 3, 334-357. See Table 1 on page 340.

Cf. A005773 (1st column), A005774 (2nd column), A005775, A066822, A000244 (row sums).

Cf. A064189, A007318, A061554, A092392.

import Data.List (transpose)
a038622 n k = a038622_tabl !! n !! k
a038622_row n = a038622_tabl !! n
a038622_tabl = iterate (\row -> map sum $
   transpose [tail row ++ [0,0], row ++ [0], [head row] ++ row]) [1]
-- Reinhard Zumkeller, Feb 26 2013

T := (n,k) -> simplify(GegenbauerC(n-k,-n+1,-1/2)+GegenbauerC(n-k-1,-n+1,-1/2)):
for n from 1 to 9 do seq(T(n,k),k=1..n) od; # Peter Luschny, May 12 2016

nmax = 10; t[n_ /; n > 0, k_ /; k >= 1] := t[n, k] = t[n-1, k-1] + t[n-1, k] + t[n-1, k+1]; t[0, 0] = 1; t[0, ] = 0; t[?Negative, ?Negative] = 0; t[n, 0] := 2 t[n-1, 0] + t[n-1, 1]; Flatten[ Table[ t[n, k], {n, 0, nmax}, {k, 0, n}]](* Jean-François Alcover, Nov 09 2011 *)

s=[0,1]; {A038622(n,k)=if(n==0,1,t=(2*(n+k)*(n+k-1)*s[2]+3*(n+k-1)*(n+k-2)*s[1])/((n+2*k-1)*n); s[1]=s[2]; s[2]=t; t)}

a(n, k) = a(n-1, k-1) + a(n-1, k) + a(n-1, k+1) for k>0, a(n, k) = 2*a(n-1, k) + a(n-1, k+1) for k=0.
Riordan array ((sqrt(1-2x-3x^2)+3x-1)/(2x(1-3x)),(1-x-sqrt(1-2x-3x^2))/(2x)). Inverse of Riordan array ((1-x)/(1+x+x^2),x/(1+x+x^2)). First column is A005773(n+1). Row sums are 3^n (A000244). If L=A038622, then L*L' is the Hankel matrix for A005773(n+1), where L' is the transpose of L. - Paul Barry, Sep 18 2006
T(n,k) = GegenbauerC(n-k,-n+1,-1/2) + GegenbauerC(n-k-1,-n+1,-1/2). In this form also the missing first column of the triangle 1,1,1,3,7,19,... (cf. A002426) can be computed. - Peter Luschny, May 12 2016
From Peter Bala, Jul 12 2021: (Start)
T(n,k) = Sum_{j = k..n} binomial(n,j)*binomial(j,floor((j-k)/2)).
Matrix product of Riordan arrays ( 1/(1 - x), x/(1 - x) ) * ( (1 - x*c(x^2))/(1 - 2*x), x*c(x^2) ) = A007318 * A061554 (triangle version), where c(x) = (1 - sqrt(1 - 4*x))/(2*x) is the g.f. of the Catalan numbers A000108.
Triangle equals A007318^(-1) * A092392 * A007318. (End)
The n-th row polynomial R(n,x) equals the n-th degree Taylor polynomial of the function (1 + x)*(1 + x + x^2)^n expanded about the point x = 0. - Peter Bala, Sep 06 2022

More terms from David W. Wilson

A091867 Triangle read by rows: T(n,k) = number of Dyck paths of semilength n having k peaks at odd height.

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 1, 3, 0, 1, 3, 4, 6, 0, 1, 6, 15, 10, 10, 0, 1, 15, 36, 45, 20, 15, 0, 1, 36, 105, 126, 105, 35, 21, 0, 1, 91, 288, 420, 336, 210, 56, 28, 0, 1, 232, 819, 1296, 1260, 756, 378, 84, 36, 0, 1, 603, 2320, 4095, 4320, 3150, 1512, 630, 120, 45, 0, 1, 1585, 6633, 12760, 15015, 11880, 6930, 2772, 990, 165, 55, 0, 1

Offset: 0

Emeric Deutsch, Mar 10 2004

Number of ordered trees with n edges having k leaves at odd height. Row sums are the Catalan numbers (A000108). T(n,0)=A005043(n). Sum_{k=0..n} k*T(n,k) = binomial(2n-2,n-1).
T(n,k)=number of Dyck paths of semilength n and having k ascents of length 1 (an ascent is a maximal string of consecutive up steps). Example: T(4,2)=6 because we have UdUduud, UduuddUd, uuddUdUd, uudUdUdd, UduudUdd and uudUddUd (the ascents of length 1 are indicated by U instead of u).
T(n,k) is the number of Łukasiewicz paths of length n having k level steps (i.e., (1,0)). A Łukasiewicz path of length n is a path in the first quadrant from (0,0) to (n,0) using rise steps (1,k) for any positive integer k, level steps (1,0) and fall steps (1,-1) (see R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge Univ. Press, Cambridge, 1999, p. 223, Exercise 6.19w; the integers are the slopes of the steps). Example: T(4,1)=4 because we have HU(2)DD, U(2)HDD, U(2)DHD and U(2)DDH, where H=(1,0), U(1,1), U(2)=(1,2) and D=(1,-1). - Emeric Deutsch, Jan 06 2005
T(n,k) = number of noncrossing partitions of [n] containing k singleton blocks. Also, T(n,k) = number of noncrossing partitions of [n] containing k adjacencies. An adjacency is an occurrence of 2 consecutive integers in the same block (here 1 and n are considered consecutive). In fact, the statistics # singletons and # adjacencies have a symmetric joint distribution.
Exponential Riordan array [e^x*(Bessel_I(0,2x)-Bessel_I(1,2x)),x]. - Paul Barry, Mar 03 2011
T(n,k) is the number of ordered trees having n edges and exactly k nodes with one child. - Geoffrey Critzer, Feb 25 2013
From Tom Copeland, Nov 04 2014: (Start)
Summing the coeff. of the partitions in A134264 for a Lagrange inversion formula (see also A249548) containing (h_1)^k = (1')^k gives this triangle, so this array's o.g.f. H(x,t) = x + t * x^2 + (1 + t^2) * x^3 ... is the inverse of the o.g.f. of A104597 with a sign change, i.e., H^(-1)(x,t) = (x-x^2) / [1 + (t-1)(x-x^2)] = Cinv(x)/[1 + (t-1)Cinv(x)] = P[Cinv(x),t-1] where Cinv(x)= x * (1-x) is the inverse of C(x) = [1-sqrt(1-4*x)]/2, an o.g.f. for the Catalan numbers A000108, and P(x,t) = x/(1+t*x) with inverse Pinv(x,t) = -P(-x,t) = x/(1-t*x). Therefore,
O.g.f.: H(x,t) = C[Pinv(x,t-1)] = C[P(x,1-t)] = C[x/(1-(t-1)x)] = {1-sqrt[1-4*x/(1-(t-1)x)]}/2 (for A091867). Reprising,
Inverse O.g.f.: H^(-1)(x,t) = x*(1-x) / [1 + (t-1)x(1-x)] = P[Cinv(x),t-1].
From general arguments in A134264, the row polynomials are an Appell sequence with lowering operator d/dt, having the umbral property (p(.,t)+a)^n=p(n,t+a) with e.g.f. = e^(x*t)/w(x), where 1/w(x)= e.g.f. of first column for the Motzkin numbers in A005043. (Mislabeled argument corrected on Jan 31 2016.)
Cf. A124644 (t-shifted polynomials), A026378 (t=-4), A001700 (t=-3), A005773 (t=-2), A126930 (t=-1) and A210736 (t=-1, a(0)=0, unsigned), A005043 (t=0), A000108 (t=1), A007317 (t=2), A064613 (t=3), A104455 (t=4), A030528 (for inverses).
(End)
The sequence of binomial transforms A126930, A005043, A000108, ... in the above comment appears in A126930 and the link therein to a paper by F. Fite et al. on page 42. - Tom Copeland, Jul 23 2016

			T(4,2)=6 because we have (ud)uu(ud)dd, uu(ud)dd(ud), uu(ud)(ud)dd, (ud)(ud)uudd, (ud)uudd(ud) and uudd(ud)(ud) (here u=(1,1), d=(1,-1) and the peaks at odd height are shown between parentheses).
Triangle begins:
   1;
   0,   1;
   1,   0,   1;
   1,   3,   0,   1;
   3,   4,   6,   0,  1;
   6,  15,  10,  10,  0,  1;
  15,  36,  45,  20, 15,  0, 1;
  36, 105, 126, 105, 35, 21, 0, 1;
  ...

R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison and Wesley, 1996, page 254 (first edition)

Alois P. Heinz, Rows n = 0..200, flattened
David Callan, On conjugates for set partitions and integer compositions , arXiv:math/0508052 [math.CO], 2005.
A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.
F. Yano and H. Yoshida, Some set partition statistics in non-crossing partitions and generating functions, Discr. Math., 307 (2007), 3147-3160.

Cf. A000108, A001700, A005043, A005773, A007317, A026378, A030528, A064613, A104455, A104597, A124644, A126930, A210736.

T := proc(n,k) if k>n then 0 elif k=n then 1 else (binomial(n+1,k)/(n+1))*sum(binomial(n+1-k,j)*binomial(n-k-j-1,j-1),j=1..floor((n-k)/2)) fi end: seq(seq(T(n,k),k=0..n),n=0..12);
T := (n,k) -> (-1)^(n+k)*binomial(n,k)*hypergeom([-n+k,1/2],[2],4): seq(seq(simplify(T(n, k)), k=0..n), n=0..10); # Peter Luschny, Jul 27 2016
# alternative Maple program:
b:= proc(x, y, t) option remember; expand(`if`(x=0, 1,
      `if`(y>0, b(x-1, y-1, 0)*z^irem(t*y, 2), 0)+
      `if`(y (p-> seq(coeff(p, z, i), i=0..n))(b(2*n, 0$2)):
seq(T(n), n=0..16);  # Alois P. Heinz, May 12 2017

nn=10;cy = ( 1 + x - x y - ( -4x(1+x-x y) + (-1 -x + x y)^2)^(1/2))/(2(1+x-x y)); Drop[CoefficientList[Series[cy,{x,0,nn}],{x,y}],1]//Grid  (* Geoffrey Critzer, Feb 25 2013 *)
Table[Which[k == n, 1, k > n, 0, True, (Binomial[n + 1, k]/(n + 1)) Sum[Binomial[n + 1 - k, j] Binomial[n - k - j - 1, j - 1], {j, Floor[(n - k)/2]}]], {n, 0, 11}, {k, 0, n}] // Flatten (* Michael De Vlieger, Jul 25 2016 *)

T(n, k) = [binomial(n+1, k)/(n+1)]*Sum_{j=1..floor((n-k)/2)} binomial(n+1-k, j)*binomial(n-k-j-1, j-1) for kn. G.f.=G=G(t, z) satisfies z(1+z-tz)G^2-(1+z-tz)G+1=0. T(n, k)=r(n-k)*binomial(n, k), where r(n)=A005043(n) are the Riordan numbers.
G.f.: 1/(1-xy-x^2/(1-x-xy-x^2/(1-x-xy-x^2/(1-x-xy-x^2/(1-... (continued fraction). - Paul Barry, Aug 03 2009
Sum_{k=0..n} T(n,k)*x^k = A126930(n), A005043(n), A000108(n), A007317(n), A064613(n), A104455(n) for x = -1,0,1,2,3,4 respectively. - Philippe Deléham, Dec 03 2009
Sum_{k=0..n} (-1)^(n-k)*T(n,k)*x^k = A168491(n), A099323(n+1), A001405(n), A005773(n+1), A001700(n), A026378(n+1), A005573(n), A122898(n) for x = -1, 0, 1, 2, 3, 4, 5, 6 respectively. - Philippe Deléham, Dec 03 2009
E.g.f.: e^(x+xy)*(Bessel_I(0,2x)-Bessel_I(1,2x)). - Paul Barry, Mar 10 2010
From Tom Copeland, Nov 06 2014: (Start)
O.g.f.: H(x,t) = {1-sqrt[1-4x/(1-(t-1)x)]}/2 (shifted index, as given in Copeland's comment, see comp. inverse there).
H(x,t)= x / [1-(C.+(t-1))x] = Sum_{n>=1} (C.+ (t-1))^(n-1)*x^n umbrally, e.g., (a.+b.)^2 = a_0*b_2 + 2 a_1*b1_+ a_0*b_2, where (C.)^n = C_n are the Catalan numbers (1,1,2,5,14,..) of A000108.
This shows directly that the lowering operator for the polynomials is D=d/dt, i.e., D p(n,t)= D(C. + (t-1))^n = n * (C. + (t-1))^(n-1) = n*p(n-1,t), so that the polynomials form an Appell sequence, and that p(n,0) gives a Motzkin sum, or Riordan, number A005043.
(End)
T(n,k) = (-1)^(n+k)*binomial(n,k)*hypergeom([k-n,1/2],[2],4). - Peter Luschny, Jul 27 2016

A027914 T(n,0) + T(n,1) + ... + T(n,n), T given by A027907.

Original entry on oeis.org

1, 2, 6, 17, 50, 147, 435, 1290, 3834, 11411, 34001, 101400, 302615, 903632, 2699598, 8068257, 24121674, 72137547, 215786649, 645629160, 1932081885, 5782851966, 17311097568, 51828203475, 155188936431, 464732722872

Offset: 0

Clark Kimberling

Let b(n)=a(n) mod 2; then b(n)=1/2+(-1)^n*(1/2-A010060(floor(n/2))). - Benoit Cloitre, Mar 23 2004
Binomial transform of A027306. Inverse binomial transform of = A032443. Hankel transform is {1, 2, 3, 4, ..., n, ...}. - Philippe Deléham, Jul 20 2005
Sums of rows of the triangle in A111808. - Reinhard Zumkeller, Aug 17 2005
Number of 3-ary words of length n in which the number of 1's does not exceed the number of 0's. - David Scambler, Aug 14 2012
The Gauss congruences a(n*p^k) == a(n^p^(k-1)) (mod p^k) hold for prime p and positive integers n and k. - Peter Bala, Jan 07 2022

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
Moa Apagodu and Ji-Cai Liu, Congruence properties for the trinomial coefficients, arXiv:1907.13547 [math.NT], 2019.
Yassine Otmani, The 2-Pascal Triangle and a Related Riordan Array, J. Int. Seq. (2025) Vol. 28, Issue 3, Art. No. 25.3.5. See p. 24.

Cf. A025191, A027915, A081673, A092255, A055217, A005773.

a027914 n = sum $ take (n + 1) $ a027907_row n
-- Reinhard Zumkeller, Jan 22 2013

a := n -> simplify((3^n + GegenbauerC(n,-n,-1/2))/2):
seq(a(n), n=0..25); # Peter Luschny, May 12 2016

CoefficientList[ Series[ (1 + x + Sqrt[1 - 2x - 3x^2])/(2 - 4x - 6x^2), {x, 0, 26}], x] (* Robert G. Wilson v, Jul 21 2015 *)
Table[(3^n + Hypergeometric2F1[1/2 - n/2, -n/2, 1, 4])/2, {n, 0, 20}] (* Vladimir Reshetnikov, May 07 2016 *)
f[n_] := Plus @@ Take[ CoefficientList[ Sum[x^k, {k, 0, 2}]^n, x], n +1]; Array[f, 26, 0] (* Robert G. Wilson v, Jan 30 2017 *)

a(n)=sum(i=0,n,polcoeff((1+x+x^2)^n,i,x))

a(n)=sum(i=0,n,sum(j=0,n,sum(k=0,j,if(i+j+k-n,0,(n!/i!/j!/k!)))))

x='x+O('x^99); Vec((1+x+(1-2*x-3*x^2)^(1/2))/(2*(1-2*x-3*x^2))) \\ Altug Alkan, May 12 2016

a(n) = ( 3^n + A002426(n) )/2; lim n -> infinity a(n+1)/a(n) = 3; 3^n < 2*a(n) < 3^(n+1). - Benoit Cloitre, Sep 28 2002
From Benoit Cloitre, Jan 26 2003: (Start)
a(n) = (1/2) *( Sum{k = 0..n} binomial(n,k)*binomial(n-k,k) + 3^n );
a(n) = Sum_{k = 0..n} Sum_{i = 0..k} binomial(n,i)*binomial(n-i,k);
a(n) = 3^n/2*(1+c/sqrt(n)+O(n^-1/2)) where c=0.5... (End)
c = sqrt(3/Pi)/2 = 0.4886025119... - Vaclav Kotesovec, May 07 2016
a(n) = n!*Sum(i+j+k=n, 1/(i!*j!*k!)) 0<=i<=n, 0<=k<=j<=n. - Benoit Cloitre, Mar 23 2004
G.f.: (1+x+sqrt(1-2x-3x^2))/(2(1-2x-3x^2)); a(n) = Sum_{k = 0..n} floor((k+2)/2)*Sum_{i = 0..floor((n-k)/2)} C(n,i)*C(n-i,i+k)* ((k+1)/(i+k+1)). - Paul Barry, Sep 23 2005; corrected Jan 20 2008
D-finite with recurrence: n*a(n) +(-5*n+4)*a(n-1) +3*(n-2)*a(n-2) +9*(n-2)*a(n-3)=0. - R. J. Mathar, Dec 02 2012
G.f.: (1+x+1/G(0))/(2*(1-2*x-3*x^2)), where G(k)= 1 + x*(2+3*x)*(4*k+1)/(4*k+2 - x*(2+3*x)*(4*k+2)*(4*k+3)/(x*(2+3*x)*(4*k+3) + 4*(k+1)/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jul 30 2013
From Peter Bala, Jul 21 2015: (Start)
a(n) = [x^n]( 3*x - 1/(1 - x) )^n.
1 + x*exp( Sum_{n >= 1} a(n)*x^n/n ) = 1 + x + 2*x^2 + 5*x^3 + 13*x^4 + 35*x^5 + ... is the o.g.f. for A005773. (End)
a(n) = (3^n + GegenbauerC(n,-n,-1/2))/2. - Peter Luschny, May 12 2016

A054391 Number of permutations with certain forbidden subsequences.

Original entry on oeis.org

1, 1, 2, 5, 14, 41, 123, 374, 1147, 3538, 10958, 34042, 105997, 330632, 1032781, 3229714, 10109310, 31667245, 99260192, 311294876, 976709394, 3065676758, 9625674442, 30231524869, 94972205349, 298419158008, 937861780439, 2947969125284, 9267666915326

Offset: 0

N. J. A. Sloane, Elisa Pergola (elisa(AT)dsi.unifi.it), May 21 2000

nonn

Hankel transform is [1,1,1,...] = A000012. - Paul Barry, Jan 19 2009
The inverse Motzkin transform apparently yields 1 followed by A000930, which implies a generating function g(x)=1+z/(1-z-z^3) where z=x*A001006(x). - R. J. Mathar, Jul 07 2009
It appears that the infinite set of interpolated sequences between the Motzkin and the Catalan can be generated with a succession of INVERT transforms, given each sequence has two leading 1's. Also, the N-th sequence in the set starting with (N=1, A001006) can be generated from a production matrix of the form "M" in the formula section, such that the main diagonal is (N leading 1's, 0, 0, 0, ...). M with a diagonal of (1, 0, 0, 0, ...) generates A001006, while M with a main diagonal of all 1's is the production matrix for A000108. - Gary W. Adamson, Jul 29 2011
From Gus Wiseman, Jun 22 2019: (Start)
Conjecture: Also the number of non-capturing set partitions of {1..n}. A set partition is capturing if it has two blocks of the form {...x...y...} and {...z...t...} where x < z and y > t or x > z and y < t. This is a weaker condition than nesting, so for example {{1,3,5},{2,4}} is capturing but not nesting. The a(0) = 1 through a(4) = 14 non-capturing set partitions are:
  {}  {{1}}  {{1,2}}    {{1,2,3}}      {{1,2,3,4}}
             {{1},{2}}  {{1},{2,3}}    {{1},{2,3,4}}
                        {{1,2},{3}}    {{1,2},{3,4}}
                        {{1,3},{2}}    {{1,2,3},{4}}
                        {{1},{2},{3}}  {{1,2,4},{3}}
                                       {{1,3},{2,4}}
                                       {{1,3,4},{2}}
                                       {{1},{2},{3,4}}
                                       {{1},{2,3},{4}}
                                       {{1,2},{3},{4}}
                                       {{1},{2,4},{3}}
                                       {{1,3},{2},{4}}
                                       {{1,4},{2},{3}}
                                       {{1},{2},{3},{4}}
Cf. A000108, A000110, A058681, A326212, A326237, A326243, A326244, A326249, A326255.
(End)
The above conjecture is true: A partition is non-capturing iff its representation in canonical sequential form avoids the patterns 1221 and 2112. In the context of these partition representations, the pattern 2112 is equivalent to the pattern 12112. Partitions whose canonical sequence form avoid 1221 and 12112 are one of the classes that are handled in the Mansour/Shattuck "Pattern Avoiding Partitions,..." paper. It shows that they are counted by this sequence. - Christian Sievers, Oct 29 2024

			a(4) = 14, a(5) = 41 since the top row of M^4 = (14, 14, 9, 3, 1), with 41 = (14 + 14 + 9 + 3 + 1).

G. C. Greubel, Table of n, a(n) for n = 0..1000
E. Barcucci et al., From Motzkin to Catalan Permutations, Discr. Math., 217 (2000), 33-49.
Jean-Luc Baril and Sergey Kirgizov, Bijections from Dyck and Motzkin meanders with catastrophes to pattern avoiding Dyck paths, arXiv:2104.01186 [math.CO], 2021.
Paul Barry, On sequences with {-1, 0, 1} Hankel transforms, arXiv preprint arXiv:1205.2565 [math.CO], 2012. - From _N. J. A. Sloane_, Oct 18 2012
Petr Gregor, Torsten Mütze, and Namrata, Combinatorial generation via permutation languages. VI. Binary trees, arXiv:2306.08420 [cs.DM], 2023.
Nickolas Hein and Jia Huang, Variations of the Catalan numbers from some nonassociative binary operations, arXiv:1807.04623 [math.CO], 2018.
J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5
Toufik Mansour and Mark Shattuck, Pattern Avoiding Partitions, Sequence A054391 and the Kernel Method, Applications and Applied Mathematics, Vol. 6, Issue 2 (December 2011), pp. 397-411.
T. Mansour and M. Shattuck, Restricted partitions and generalized Catalan numbers, PU. M. A., Vol. (2011), No. 2, pp. 239-251. - From _N. J. A. Sloane_, Oct 13 2012
Eric Marberg, Crossings and nestings in colored set partitions, arXiv preprint arXiv:1203.5738 [math.CO], 2012.

Interpolates between Motzkin numbers (A001006) and Catalan numbers (A000108). Cf. A005773, A054392, ...

Binomial transform of A224747.

c := x->(1-sqrt(1-4*x))/(2*x); a := (x,j)->(x)/((1-4*x)*(c(x))^2*(1-c(x))^(j))*(-x^2*(c(x))^2*(1-c(x))*(x^2*(c(x))^4)^(j)-(1-3*x-2*x^2)*(c(x))^2*(x*(c(x))^2)^(j)+x);
b := (x,j)->1+(1)/((1-4*x)*c(x)*(1-c(x))^(j))*(-2*x^3*(c(x))^2*(x^2*(c(x))^4)^(j)+(1-3*x-2*x^2)*c(x)*(x*(c(x))^2)^(j)-2*x^2);
co := (x,j)->(1)/((1-4*x)*(1-c(x))^(j))*(x^2*(x^2*(c(x))^4)^(j)-(1-3*x-2*x^2)*(x*(c(x))^2)^(j)+x^2);
s := (x,j)->(1-b(x,j)+(-1)^j*sqrt((1-b(x,j))^2-4*a(x,j)*co(x,j)))/(2*a(x,j)); j := 3; series(s(x,j),x=0..60); od; # j=1,2,3,... inf gives A001006, A005773, A054391, A054392, ..., A000108

CoefficientList[Series[1 - 2*x^2/(2*x^2 - 3*x + 1 - Sqrt[1 - 2*x - 3*x^2]), {x, 0, 50}], x] (* G. C. Greubel, Apr 27 2017 *)

a(n):=sum((sum((binomial(k,l)*l*sum(binomial(j,1-n-2*l+k+2*j)*binomial(n-1+l-k,j),j,0,n+l-k-1))/(n+l-k-1),l,1,k)),k,1,n-1)+1; /* Vladimir Kruchinin, Oct 31 2011 */

x='x+O('x^66); gf=1-2*x^2/(2*x^2-3*x+1-sqrt(1-2*x-3*x^2)); Vec(gf) \\ Joerg Arndt, Jun 29 2013

G.f.: 1 - 2*x^2 / (2*x^2 - 3*x + 1 - sqrt(1 - 2*x - 3*x^2)). - Mansour and Shattuck
G.f.: 1/(1-x-x^2/(1-2x-x^2/(1-x-x^2/(1-x-x^2/(1-x-x^2/(1-x-x^2/(1-... (continued fraction) (conjecture). - Paul Barry, Jan 19 2009
From Gary W. Adamson, Jul 29 2011: (Start)
a(n) = upper left term of M^n, a(n+1) = sum of top row terms of M^n; M = an infinite square production matrix as follows with a main diagonal of (1, 1, 1, 0, 0, 0, ...):
  1, 1, 0, 0, 0, 0, ...
  1, 1, 1, 0, 0, 0, ...
  1, 1, 1, 1, 0, 0, ...
  1, 1, 1, 0, 1, 0, ...
  1, 1, 1, 1, 0, 1, ...
  1, 1, 1, 1, 1, 0, ...
  ... (End)
a(n) = Sum_{k=1..n-1} (sum(l=1..k, (binomial(k,l)*l*sum(j=0..n+l-k-1, binomial(j,1-n-2*l+k+2*j)*binomial(n-1+l-k,j)))/(n+l-k-1))) + 1. - Vladimir Kruchinin, Oct 31 2011
D-finite with recurrence (-n+1)*a(n) + 3*(2*n-3)*a(n-1) + (-8*n+11)*a(n-2) + (-5*n+32)*a(n-3) + (7*n-31)*a(n-4) + 3*(-n+4)*a(n-5)= 0. - R. J. Mathar, Nov 26 2012
G.f.:  1 - x*(2*x^2-3*x+1 + 1/G(0))/(2*(x^3-3*x^2+4*x-1)), where G(k)= 1 + x*(2+3*x)*(4*k+1)/( 4*k+2 - x*(2+3*x)*(4*k+2)*(4*k+3)/(x*(2+3*x)*(4*k+3) + 4*(k+1)/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jun 29 2013

cp's OEIS Frontend

A035263 Trajectory of 1 under the morphism 0 -> 11, 1 -> 10; parity of 2-adic valuation of 2n: a(n) = A000035(A001511(n)).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

Python

Scheme

Formula

Extensions

A064189 Triangle T(n,k), 0 <= k <= n, read by rows, defined by: T(0,0)=1, T(n,k)=0 if n < k, T(n,k) = T(n-1,k-1) + T(n-1,k) + T(n-1,k+1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Formula

Extensions

A026300 Motzkin triangle, T, read by rows; T(0,0) = T(1,0) = T(1,1) = 1; for n >= 2, T(n,0) = 1, T(n,k) = T(n-1,k-2) + T(n-1,k-1) + T(n-1,k) for k = 1,2,...,n-1 and T(n,n) = T(n-1,n-2) + T(n-1,n-1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

A005717 Construct triangle in which n-th row is obtained by expanding (1 + x + x^2)^n and take the next-to-central column.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

PARI

PARI

Python

Formula

Extensions

A079523 Utterly odd numbers: numbers whose binary representation ends in an odd number of ones.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

A024718 a(n) = (1/2)(1 + Sum_{k=0..n} binomial(2k, k)).