A117641 -id:A117641 - cp's OEIS frontend

A126952 a(0)=1, a(n+1) = 5a(n)-4A117641(n) for n>=0.

1, 1, 5, 21, 93, 421, 1937, 9017, 42349, 200277, 952425, 4549953, 21818841, 104966889, 506372277, 2448641061, 11865563853, 57604036309, 280110716777, 1364092539041, 6651682319233, 32474171399649, 158714415664557

Offset: 0

Philippe Deléham, Mar 19 2007

nonn

Hankel transform is 4^n=A000302(n).

Michael De Vlieger, Table of n, a(n) for n = 0..1001
Isaac DeJager, Madeleine Naquin, Frank Seidl, Colored Motzkin Paths of Higher Order, VERUM 2019.

Cf. A000302, A117641.

Block[{$MaxExtraPrecision = 10^3, s = Rest@ CoefficientList[Series[(1 + 3 x - Sqrt[1 - 6 x + 5 x^2])/(2 x^2 + 6 x), {x, 0, 21}], x]}, Nest[Append[#, 5 #[[-1]] - 4 s[[Length@ # - 1]] ] &, {1, 1}, Length@ s]] (* Michael De Vlieger, Dec 15 2019, after Robert G. Wilson v at A117641 *)

a(n) = Sum_{k = 0..n} binomial(n,k)*b(k), where b(n) = Sum_{k = 0..n} binomial(n+k,k) * (-2)^(n-k). - Peter Bala, Jun 18 2025
From Vaclav Kotesovec, Jun 22 2025: (Start)
Recurrence: 5*(n-2)*a(n-3) + (9*n-26)*a(n-2) + (12-17*n)*a(n-1) + 3*n*a(n) = 0.
a(n) ~ 5^(n + 1/2) / (4*sqrt(Pi*n)). (End)

a(11) and a(22) corrected by Michael De Vlieger, Dec 15 2019

A171224 Riordan array (f(x),x*f(x)) where f(x) is the g.f. of A117641.

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 3, 2, 0, 1, 11, 6, 3, 0, 1, 42, 23, 9, 4, 0, 1, 167, 90, 36, 12, 5, 0, 1, 684, 365, 144, 50, 15, 6, 0, 1, 2867, 1518, 595, 204, 65, 18, 7, 0, 1, 12240, 6441, 2511, 858, 270, 81, 21, 8, 0, 1, 53043, 27774, 10782, 3672, 1155, 342, 98, 24, 9, 0, 1

Offset: 0

Philippe Deléham, Dec 05 2009

			Triangle begins
    1;
    0,  1;
    1,  0,  1;
    3,  2,  0,  1;
   11,  6,  3,  0,  1;
   42, 23,  9,  4,  0,  1;
  167, 90, 36, 12,  5,  0,  1;
  ...
Production array begins
    0,  1;
    1,  0,  1;
    3,  1,  0,  1;
    9,  3,  1,  0,  1;
   27,  9,  3,  1,  0,  1;
   81, 27,  9,  3,  1,  0,  1;
  243, 81, 27,  9,  3,  1,  0,  1;
  ... - _Philippe Deléham_, Mar 04 2013

G. C. Greubel, Rows n = 0..100 of triangle, flattened

Cf. A053121, A097609, A065600.

[[((k+1)/(n+1))*(&+[3^(n-k-2*j)*Binomial(n+1,j)*Binomial(n-k-j-1, n-k-2*j): j in [0..Floor((n-k)/2)]]): k in [0..n]]: n in [0..10]]; // G. C. Greubel, Apr 04 2019

T[n_, k_]:= (k+1)/(n+1)*Sum[3^(n-k-2*j)*Binomial[n+1,j]*Binomial[n-k-j-1, n-k-2*j], {j, 0, Floor[(n-k)/2]}]; Table[T[n, k], {n,0,10}, {k,0,n} ]//Flatten (* G. C. Greubel, Apr 04 2019 *)

T(n,k):=(k+1)/(n+1)*sum(3^(n-k-2*j)*binomial(n+1,j)*binomial(n-k-j-1,n-k-2*j),j,0,floor((n-k)/2)); /* Vladimir Kruchinin, Apr 04 2019 */

{T(n,k) = ((k+1)/(n+1))*sum(j=0, floor((n-k)/2), 3^(n-k-2*j) *binomial(n+1,j)*binomial(n-k-j-1, n-k-2*j))}; \\ G. C. Greubel, Apr 04 2019

[[((k+1)/(n+1))*sum(3^(n-k-2*j)*binomial(n+1,j)*binomial(n-k-j-1, n-k-2*j) for j in (0..floor((n-k)/2))) for k in (0..n)] for n in (0..10)] # G. C. Greubel, Apr 04 2019

Sum_{k=0..n} T(n,k)*x^k = A117641(n), A033321(n), A007317(n+1), A002212(n+1), A026378(n+1) for x = 0, 1, 2, 3, 4 respectively.
Triangle equals B*A065600*B^(-1) = B^2*A097609*B^(-2) = B^3*A053121*B^(-3), product considered as infinite lower triangular arrays and B = A007318. - Philippe Deléham, Dec 08 2009
T(n,k) = T(n-1,k-1) + Sum_{i>=0} T(n-1,k+1+i)*3^i, T(0,0) = 1. - Philippe Deléham, Feb 23 2012
T(n,k) = ((k+1)/(n+1))*Sum_{j=0..floor((n-k)/2)} 3^(n-k-2*j)*C(n+1,j)*C(n-k-j-1,n-k-2*j). - Vladimir Kruchinin, Apr 04 2019

Terms a(55) onward added by G. C. Greubel, Apr 04 2019

A171243 Riordan array (f(x), x*g(x)), f(x) is the g.f. of A126952, g(x) is the g.f. of A117641.

Original entry on oeis.org

1, 1, 1, 5, 1, 1, 21, 6, 1, 1, 93, 25, 7, 1, 1, 421, 112, 29, 8, 1, 1, 1937, 510, 132, 33, 9, 1, 1, 9017, 2357, 606, 153, 37, 10, 1, 1, 42349, 11009, 2819, 709, 175, 41, 11, 1, 1, 200277, 51840, 13233, 3324, 819, 198, 45, 12, 1, 1

Offset: 0

Philippe Deléham, Dec 06 2009

Expansion of row sums of T_(x,3), T_(x,y) defined in A039599.

Matrix product P^3 * Q * P^(-3), where P denotes Pascal's triangle A007318 and Q denotes A061554 (formed from P by sorting the rows into descending order). Cf. A158793 and A158815. - Peter Bala, Jul 13 2021

			Triangle begins:
    1;
    1,   1;
    5,   1,  1;
   21,   6,  1, 1;
   93,  25,  7, 1, 1;
  421, 112, 29, 8, 1, 1;
  ...

Cf. A061554, A158793, A158815, A171224.

Sum_{k=0..n} T(n,k)*x^k = A126952(n), A126568(n), A026375(n), A026378(n+1), A000351(n) for x = 0,1,2,3,4 respectively.

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

Original entry on oeis.org

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

A091965 Triangle read by rows: T(n,k) = number of lattice paths from (0,0) to (n,k) that do not go below the line y=0 and consist of steps U=(1,1), D=(1,-1) and three types of steps H=(1,0) (left factors of 3-Motzkin steps).

Original entry on oeis.org

1, 3, 1, 10, 6, 1, 36, 29, 9, 1, 137, 132, 57, 12, 1, 543, 590, 315, 94, 15, 1, 2219, 2628, 1629, 612, 140, 18, 1, 9285, 11732, 8127, 3605, 1050, 195, 21, 1, 39587, 52608, 39718, 19992, 6950, 1656, 259, 24, 1, 171369, 237129, 191754, 106644, 42498, 12177, 2457

Offset: 0

Emeric Deutsch, Mar 13 2004

T(n,0) = A002212(n+1), T(n,1) = A045445(n+1); row sums give A026378.
The inverse is A207815. - Gary W. Adamson, Dec 17 2006 [corrected by Philippe Deléham, Feb 22 2012]
Reversal of A084536. - Philippe Deléham, Mar 23 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) = 3*T(n-1,0) + T(n-1,1), T(n,k) = T(n-1,k-1) + 3*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
5^n = (n-th row terms) dot (first n+1 terms in (1,2,3,...)). Example for row 4: 5^4 = 625 = (137, 132, 57, 12, 1) dot (1, 2, 3, 4, 5) = (137 + 264 + 171 + 48 + 5) = 625. - Gary W. Adamson, Jun 15 2011
Riordan array ((1-3*x-sqrt(1-6*x+5*x^2))/(2*x^2), (1-3*x-sqrt(1-6*x+5*x^2))/(2*x)). - Philippe Deléham, Feb 19 2012

			Triangle begins:
     1;
     3,    1;
    10,    6,    1;
    36,   29,    9,    1;
   137,  132,   57,   12,    1;
   543,  590,  315,   94,   15,    1;
  2219, 2628, 1629,  612,  140,   18,    1;
T(3,1)=29 because we have UDU, UUD, 9 HHU paths, 9 HUH paths and 9 UHH paths.
Production matrix begins
  3, 1;
  1, 3, 1;
  0, 1, 3, 1;
  0, 0, 1, 3, 1;
  0, 0, 0, 1, 3, 1;
  0, 0, 0, 0, 1, 3, 1;
  0, 0, 0, 0, 0, 1, 3, 1;
  0, 0, 0, 0, 0, 0, 1, 3, 1;
  0, 0, 0, 0, 0, 0, 0, 1, 3, 1;
  0, 0, 0, 0, 0, 0, 0, 0, 1, 3, 1;
- _Philippe Deléham_, Nov 07 2011

A. Nkwanta, Lattice paths and RNA secondary structures, DIMACS Series in Discrete Math. and Theoretical Computer Science, 34, 1997, 137-147.

Vincenzo Librandi, Rows n = 0..100, flattened
Shu-Chiuan Chang and Robert Shrock, Structure of the Partition Function and Transfer Matrices for the Potts Model in a Magnetic Field on Lattice Strips, J. Stat. Physics 137 (2009) 667, table 5.
Helmut Prodinger, The amplitude of Motzkin paths, arXiv:2104.07596 [math.CO], 2021. Mentions this sequence.
Helmut Prodinger, Multi-edge trees and 3-coloured Motzkin paths: bijective issues, arXiv:2105.03350 [math.CO], 2021.
Helmut Prodinger, Weighted unary-binary trees, Hex-trees, marked ordered trees, and related structures, arXiv:2106.14782 [math.CO], 2021.

Cf. A002212, A045445, A026378.

Cf. A123965.

nmax = 9; t[n_, k_] := ((k+1)*n!*Hypergeometric2F1[k+3/2, k-n, 2k+3, -4]) / ((k+1)!*(n-k)!); Flatten[ Table[ t[n, k], {n, 0, nmax}, {k, 0, n}]] (* Jean-François Alcover, Nov 14 2011, after Vladimir Kruchinin *)
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, 3, 3], {n, 0, 10}, {k, 0, n}] // Flatten (* G. C. Greubel, May 22 2017 *)

T(n,k):=(k+1)*sum((binomial(2*(m+1),m-k)*binomial(n,m))/(m+1),m,k,n); /* Vladimir Kruchinin, Oct 08 2011 */

@CachedFunction
def A091965(n,k):
    if n==0 and k==0: return 1
    if k<0 or k>n: return 0
    if k==0: return 3*A091965(n-1,0)+A091965(n-1,1)
    return A091965(n-1,k-1)+3*A091965(n-1,k)+A091965(n-1,k+1)
for n in (0..7):
    [A091965(n,k) for k in (0..n)] # Peter Luschny, Nov 05 2012

G.f.: G = 2/(1 - 3*z - 2*t*z + sqrt(1-6*z+5*z^2)). Alternatively, G = M/(1 - t*z*M), where M = 1 + 3*z*M + z^2*M^2.
Sum_{k>=0} T(m, k)*T(n, k) = T(m+n, 0) = A002212(m+n+1). - Philippe Deléham, Sep 14 2005
The triangle may also be generated from M^n * [1,0,0,0,...], where M = an infinite tridiagonal matrix with 1's in the super and subdiagonals and [3,3,3,...] in the main diagonal. - Gary W. Adamson, Dec 17 2006
Sum_{k=0..n} T(n,k)*(k+1) = 5^n. - Philippe Deléham, Mar 27 2007
Sum_{k=0..n} T(n,k)*x^k = A117641(n), A033321(n), A007317(n), A002212(n+1), A026378(n+1) for x = -3, -2, -1, 0, 1 respectively. - Philippe Deléham, Nov 28 2009
T(n,k) = (k+1)*Sum_{m=k..n} binomial(2*(m+1),m-k)*binomial(n,m)/(m+1). - Vladimir Kruchinin, Oct 08 2011
The n-th row polynomial R(n,x) equals the n-th degree Taylor polynomial of the function (1 - x^2)*(1 + 3*x + x^2)^n expanded about the point x = 0. - Peter Bala, Sep 06 2022

A126970 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,1), T(n,k) = T(n-1,k-1) + 3*T(n-1,k) + T(n-1,k+1) for k >= 1.

Original entry on oeis.org

1, 0, 1, 1, 3, 1, 3, 11, 6, 1, 11, 42, 30, 9, 1, 42, 167, 141, 58, 12, 1, 167, 684, 648, 327, 95, 15, 1, 684, 2867, 2955, 1724, 627, 141, 18, 1, 2867, 12240, 13456, 8754, 3746, 1068, 196, 21, 1, 12240, 53043, 61362, 43464, 21060, 7146, 1677, 260, 24, 1

Offset: 0

Philippe Deléham, Mar 19 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

			Triangle begins:
    1;
    0,   1;
    1,   3,   1;
    3,  11,   6,   1;
   11,  42,  30,   9,  1;
   42, 167, 141,  58, 12,  1;
  167, 684, 648, 327, 95, 15, 1; ...
From _Philippe Deléham_, Nov 07 2011: (Start)
Production matrix begins:
  0, 1
  1, 3, 1
  0, 1, 3, 1
  0, 0, 1, 3, 1
  0, 0, 0, 1, 3, 1
  0, 0, 0, 0, 1, 3, 1
  0, 0, 0, 0, 0, 1, 3, 1
  0, 0, 0, 0, 0, 0, 1, 3, 1
  0, 0, 0, 0, 0, 0, 0, 1, 3, 1 (End)

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened

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, 0, 3], {n, 0, 49}, {k, 0, n}] // Flatten (* G. C. Greubel, Apr 21 2017 *)

Sum_{k=0..n} T(n,k) = A126952(n).
Sum_{k>=0} T(m,k)*T(n,k) = T(m+n,0) = A117641(m+n).
Sum_{k=0..n} T(n,k)*(4*k+1) = 5^n. - Philippe Deléham, Mar 22 2007

A128723 Number of skew Dyck paths of semilength n having no peaks at level 1.

Original entry on oeis.org

1, 0, 2, 6, 22, 84, 334, 1368, 5734, 24480, 106086, 465462, 2063658, 9231084, 41610162, 188820726, 861891478, 3954732384, 18230522422, 84390187986, 392120098258, 1828220666844, 8550445900442, 40103716079436

Offset: 0

Emeric Deutsch, Mar 31 2007

nonn

A skew Dyck path is a path in the first quadrant which begins at the origin, ends on the x-axis, consists of steps U=(1,1)(up), D=(1,-1)(down) and L=(-1,-1)(left) so that up and left steps do not overlap. The length of a path is defined to be the number of steps in it.

			a(3)=6 because we have UUDUDD, UUUDDD, UUUDLD, UUDUDL, UUUDDL and UUUDLL.

G. C. Greubel, Table of n, a(n) for n = 0..1000
E. Deutsch, E. Munarini and S. Rinaldi, Skew Dyck paths, J. Stat. Plann. Infer. 140 (8) (2010) 2191-2203.
Helmut Prodinger, Skew Dyck paths having no peaks at level 1, arXiv:2201.00640 [math.CO], 2022.

Cf. A117641, A128722.

G:=(3-3*z-sqrt(1-6*z+5*z^2))/(1+3*z+sqrt(1-6*z+5*z^2)): Gser:=series(G,z=0,30): seq(coeff(Gser,z,n),n=0..27);

CoefficientList[Series[(3-3*x-Sqrt[1-6*x+5*x^2])/(1+3*x+Sqrt[1-6*x+5*x^2]), {x, 0, 20}], x] (* Vaclav Kotesovec, Mar 20 2014 *)

my(z='x+O('z^50)); Vec((3-3*z-sqrt(1-6*z+5*z^2)) /(1+3*z +sqrt(1-6*z+5*z^2))) \\ G. C. Greubel, Mar 19 2017

a(n) = A128722(n,0).
a(n) = 2*A117641(n) for n>=1.
G.f.: (3-3*z-sqrt(1-6*z+5*z^2))/(1+3*z+sqrt(1-6*z+5*z^2)).
a(n) ~ 5^(n+3/2)/(16*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Mar 20 2014
Conjecture: +3*(n+1)*a(n) +(-17*n+10)*a(n-1) +9*(n-3)*a(n-2) +5*(n-2)*a(n-3)=0. - R. J. Mathar, Jun 17 2016

A171368 Another version of A126216.

Original entry on oeis.org

1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 2, 0, 1, 0, 0, 0, 5, 0, 1, 0, 0, 5, 0, 9, 0, 1, 0, 0, 0, 21, 0, 14, 0, 1, 0, 0, 14, 0, 56, 0, 20, 0, 1, 0, 0, 0, 84, 0, 120, 0, 27, 0, 1, 0, 0, 42, 0, 300, 0, 225, 0, 35, 0, 1, 0, 0, 0, 330, 0, 825, 0, 385, 0, 44, 0, 1, 0, 0

Offset: 0

Philippe Deléham, Dec 06 2009

Expansion of the first column of the triangle T_(0,x), T_(x,y) defined in A039599; T_(0,0)= A053121, T_(0,1)= A089942, T_(0,2)= A126093, T_(0,3)= A126970.

T(n,k) is the number of Riordan paths of length n with k horizontal steps. A Riordan path is a Motzkin path with no horizontal steps on the x-axis. - Emanuele Munarini, Oct 14 2023

			Triangle begins:
  1 ;
  0,0 ;
  1,0,0 ;
  0,1,0,0 ;
  2,0,1,0,0 ;
  0,5,0,1,0,0 ;
  5,0,9,0,1,0,0 ;
  ...

Cf. A000108, A001003,

Sum_{k, 0<=k<=n} T(n,k)*x^k = A099323(n+1), A126120(n), A005043(n), A000957(n+1), A117641(n) for x = -1, 0, 1, 2, 3 respectively.

A257363 Number of 3-Motzkin paths with no level steps at height 1.

Original entry on oeis.org

1, 3, 10, 33, 110, 369, 1247, 4248, 14603, 50724, 178314, 635526, 2300829, 8477382, 31842897, 122103276, 478372886, 1915188093, 7831613468, 32674683984, 138871668314, 600140517762, 2631926843602, 11690520554421, 52498671870181, 237966449687118, 1087246253873875, 5001141997115010, 23137102115963262

Offset: 0

José Luis Ramírez Ramírez, Apr 20 2015

nonn

For n=2 we have 10 paths: H(1)H(1), H(1)H(2), H(2)H(1), H(2)H(2), H(1)H(3), H(3)H(1), H(3)H(3), H(2)H(3), H(3)H(2), UD.

Robert Israel, Table of n, a(n) for n = 0..1000

Cf. A117641, A217312, A253831, A059231.

rec:= (95+95*n)*a(n)+(-180-9*n)*a(n+1)+(-329-197*n)*a(n+2)+(369+144*n)*a(n+3)+(-117-36*n)*a(4+n)+(12+3*n)*a(n+5):
f:= gfun:-rectoproc({rec,a(0)=1,a(1)=3,a(2)=10,a(3)=33,a(4)=110},a(n),remember):
seq(f(n),n=0..100); # Robert Israel, Apr 28 2015

CoefficientList[Series[2*(3+x)/(6-17*x-9*x^2+x*Sqrt[1-6*x+5*x^2]), {x, 0, 20}], x] (* Vaclav Kotesovec, Apr 21 2015 *)

G.f.: 1/(1-3*x-x*F(x)), where F(x) is the g.f. of the sequence A117641.
G.f.: 2*(3+x)/(6-17*x-9*x^2+x*sqrt(1-6*x+5*x^2)).
a(n) ~ 5^(n+3/2)/(98*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Apr 21 2015
From Robert Israel, Apr 28 2015 (Start):
G.f.: (6-x*sqrt(1-6*x+5*x^2)-17*x-9*x^2)/(6-36*x+42*x^2+38*x^3).
3*(-n+1)*a(n) +9*(4*n-7)*a(n-1) +9*(-16*n+39)*a(n-2) +(197*n-656)*a(n-3) +9*(n+15)*a(n-4) +95*(-n+4)*a(n-5)=0. (End)

A171486 Riordan array (f(x), x*f(x)) where f(x) is the g.f. of A033321.

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 6, 5, 3, 1, 21, 16, 9, 4, 1, 79, 58, 31, 14, 5, 1, 311, 224, 117, 52, 20, 6, 1, 1265, 900, 465, 205, 80, 27, 7, 1, 5275, 3720, 1910, 840, 330, 116, 35, 8, 1, 22431, 15713, 8034, 3532, 1396, 501, 161, 44, 9, 1, 96900, 67522, 34419, 15136, 6015, 2190

Offset: 0

Philippe Deléham, Dec 09 2009

Equal to B*A065600 = A171224*B where B = A007318 ; equal to B*A039598*B^(-2).

			Triangle begins :
1
1, 1
2, 2, 1
6, 5, 3, 1
21, 16, 9, 4, 1
79, 58, 31, 14, 5, 1
311, 224, 117, 52, 20, 6, 1

Cf. A171224, A104259, A091965

Sum_{k, 0<=k<=n} T(n,k)*x^k = A117641(n), A033321(n), A007317(n+1), A002212(n+1), A026378(n+1) for x = -1, 0, 1, 2, 3 respectively.

T(n,k) = T(n-1,k-1) + T(n-1,k) + sum_{i, i>=0} T(n-1,k+1+i)*2^i. - Philippe Deléham, Feb 23 2012

cp's OEIS Frontend

A126952 a(0)=1, a(n+1) = 5*a(n)-4*A117641(n) for n>=0.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A171224 Riordan array (f(x),x*f(x)) where f(x) is the g.f. of A117641.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Maxima

PARI

Sage

Formula

Extensions

A171243 Riordan array (f(x), x*g(x)), f(x) is the g.f. of A126952, g(x) is the g.f. of A117641.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

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

A091965 Triangle read by rows: T(n,k) = number of lattice paths from (0,0) to (n,k) that do not go below the line y=0 and consist of steps U=(1,1), D=(1,-1) and three types of steps H=(1,0) (left factors of 3-Motzkin steps).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Maxima

Sage

Formula

A126970 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,1), T(n,k) = T(n-1,k-1) + 3*T(n-1,k) + T(n-1,k+1) for k >= 1.

Views

Author

Keywords

Comments

Examples

Links

Programs

Mathematica

Formula

A128723 Number of skew Dyck paths of semilength n having no peaks at level 1.

Views

A126952 a(0)=1, a(n+1) = 5a(n)-4A117641(n) for n>=0.