A003242 -id:A003242 - cp's OEIS frontend

A000975 a(2n) = 2a(2n-1), a(2n+1) = 2a(2n)+1 (also a(n) is the n-th number without consecutive equal binary digits).

0, 1, 2, 5, 10, 21, 42, 85, 170, 341, 682, 1365, 2730, 5461, 10922, 21845, 43690, 87381, 174762, 349525, 699050, 1398101, 2796202, 5592405, 11184810, 22369621, 44739242, 89478485, 178956970, 357913941, 715827882, 1431655765, 2863311530, 5726623061, 11453246122

Offset: 0

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

Might be called the "Lichtenberg sequence" after Georg Christoph Lichtenberg, who discussed it in 1769 in connection with the Chinese Rings puzzle (baguenaudier). - Andreas M. Hinz, Feb 15 2017
Number of steps to change from a binary string of n 0's to n 1's using a Gray code. - Jon Stadler (jstadler(AT)coastal.edu)
Popular puzzles such as Spin-Out and The Brain Puzzler are based on the Gray binary system and require a(n) steps to complete for some number n.
Conjecture: {a(n)} also gives all j for which A048702(j) = A000217(j); i.e., if we take the a(n)-th triangular number (a(n)^2 + a(n))/2 and multiply it by 3, we get a(n)-th even-length binary palindrome A048701(a(n)) concatenated from a(n) and its reverse. E.g., a(4) = 10, which is 1010 in binary; the tenth triangular number is 55, and 55*3 = 165 = 10100101 in binary. - Antti Karttunen, circa 1999. (This has been now proved by Paul K. Stockmeyer in his arXiv:1608.08245 paper.) - Antti Karttunen, Aug 31 2016
Number of ways to tie a tie of n or fewer half turns, excluding mirror images. Also number of walks of length n or less on a triangular lattice with the following restrictions; given l, r and c as the lattice axes. 1. All steps are taken in the positive axis direction. 2. No two consecutive steps are taken on the same axis. 3. All walks begin with l. 4. All walks end with rlc or lrc. - Bill Blewett, Dec 21 2000
a(n) is the minimal number of vertices to be selected in a vertex-cover of the balanced tree B_n. - Sen-peng Eu, Jun 15 2002
A087117(a(n)) = A038374(a(n)) = 1 for n > 1; see also A090050. - Reinhard Zumkeller, Nov 20 2003
Intersection of A003754 and A003714; complement of A107907. - Reinhard Zumkeller, May 28 2005
Equivalently, numbers m whose binary representation is effectively, for some number k, both the lazy Fibonacci and the Zeckendorf representation of k (in which case k = A022290(m)). - Peter Munn, Oct 06 2022
a(n+1) gives row sums of Riordan array (1/(1-x), x(1+2x)). - Paul Barry, Jul 18 2005
Total number of initial 01's in all binary words of length n+1. Example: a(3) = 5 because the binary words of length 4 that start with 01 are (01)00, (01)(01), (01)10 and (01)11 and the total number of initial 01's is 5 (shown between parentheses). a(n) = Sum_{k >= 0} k*A119440(n+1, k). - Emeric Deutsch, May 19 2006
In Norway we call the 10-ring puzzle "strikketoy" or "knitwear" (see link). It takes 682 moves to free the two parts. - Hans Isdahl, Jan 07 2008
Equals A002450 and A020988 interlaced. - Zak Seidov, Feb 10 2008
For n > 1, let B_n = the complete binary tree with vertex set V where |V| = 2^n - 1. If VC is a minimum-size vertex cover of B_n, Sen-Peng Eu points out that a(n) = |VC|. It also follows that if IS = V\VC, a(n+1) = |IS|. - K.V.Iyer, Apr 13 2009
Starting with 1 and convolved with [1, 2, 2, 2, ...] = A000295. - Gary W. Adamson, Jun 02 2009
a(n) written in base 2 is sequence A056830(n). - Jaroslav Krizek, Aug 05 2009
This is the sequence A(0, 1; 1, 2; 1) of the family of sequences [a,b:c,d:k] considered by G. Detlefs, and treated as A(a,b;c,d;k) in the W. Lang link given below. - Wolfdieter Lang, Oct 18 2010
From Vladimir Shevelev, Jan 30 2012, Feb 13 2012: (Start)
1) Denote by {n, k} the number of permutations of 1, ..., n with the up-down index k (for definition, see comment in A203827). Then max_k{n, k} = {n, a(n)} = A000111(n).
2) a(n) is the minimal number > a(n-1) with the Hamming distance d_H(a(n-1), a(n)) = n. Thus this sequence is the Hamming analog of triangular numbers 0, 1, 3, 6, 10, ... (End)
From Hieronymus Fischer, Nov 22 2012: (Start)
Represented in binary form each term after the second one contains every previous term as a substring.
The terms a(2) = 2 and a(3) = 5 are the only primes. Proof: For even n we get a(n) = 2*(2^(2*n) - 1)/3, which shows that a(n) is even, too, and obviously a(n) > 2 for all even n > 2. For odd n we have a(n) = (2^(n+1) - 1)/3 = (2^((n+1)/2) - 1) * (2^((n+1)/2) + 1)/3. Evidently, at least one of these factors is divisible by 3, both are greater than 6, provided n > 3. Hence it follows that a(n) is composite for all odd n > 3.
Represented as a binary number, a(n+1) has exactly n prime substrings. Proof: Evidently, a(1) = 1_2 has zero and a(2) = 10_2 has 1 prime substring. Let n > 1. Written in binary, a(n+1) is 101010101...01 (if n + 1 is odd) and is 101010101...10 (if n + 1 is even) with n + 1 digits. Only the 2- and 3-digits substrings 10_2 (=2) and 101_2 (=5) are prime substrings. All the other substrings are nonprime since every substring is a previous term and all terms unequal to 2 and 5 are nonprime. For even n + 1, the number of prime substrings equal to 2 = 10_2 is (n+1)/2, and the number of prime substrings equal to 5 = 101_2 is (n-1)/2, makes a sum of n. For odd n + 1 we get n/2 for both, the number of 2's and 5's prime substrings, in any case, the sum is n. (End)
Number of different 3-colorings for the vertices of all triangulated planar polygons on a base with n+2 vertices if the colors of the two base vertices are fixed. - Patrick Labarque, Feb 09 2013
A090079(a(n)) = a(n) and A090079(m) <> a(n) for m < a(n). - Reinhard Zumkeller, Feb 16 2013
a(n) is the number of length n binary words containing at least one 1 and ending in an even number (possibly zero) of 0's. a(3) = 5 because we have: 001, 011, 100, 101, 111. - Geoffrey Critzer, Dec 15 2013
a(n) is the number of permutations of length n+1 having exactly one descent such that the first element of the permutation is an even number. - Ran Pan, Apr 18 2015
a(n) is the sequence of the last row of the Hadamard matrix H(2^n) obtained via Sylvester's construction: H(2) = [1,1;1,-1], H(2^n) = H(2^(n-1))*H(2), where * is the Kronecker product. - William P. Orrick, Jun 28 2015
Conjectured record values of A264784: a(n) = A264784(A155051(n-1)). - Reinhard Zumkeller, Dec 04 2015. (This is proved by Paul K. Stockmeyer in his arXiv:1608.08245 paper.) - Antti Karttunen, Aug 31 2016
Decimal representation of the x-axis, from the origin to the right edge, of the n-th stage of growth of the two-dimensional cellular automaton defined by "Rule 131", based on the 5-celled von Neumann neighborhood. See A279053 for references and links. - Robert Price, Dec 05 2016
For n > 4, a(n-2) is the second-largest number in row n of A127824. - Dmitry Kamenetsky, Feb 11 2017
Conjecture: a(n+1) is the number of compositions of n with two kinds of parts, n and n', where the order of the 1 and 1' does not matter. For n=2, a(3) = 5 compositions, enumerated as follows:  2; 2'; 1,1; 1',1 = 1',1; 1',1'. - Gregory L. Simay, Sep 02 2017
Conjecture proved by recognizing the appropriate g.f. is x/(1 - x)(1 - x)(1 - 2*x^2 - 2x^3 - ...) =  x/(1 - 2*x - x^2 + 2x^3). - Gregory L. Simay, Sep 10 2017
a(n) = 2^(n-1) + 2^(n-3) + 2^(n-5) + ... a(2*k -1) = A002450(k) is the sum of the powers of 4. a(2*k) = 2*A002450(k). - Gregory L. Simay, Sep 27 2017
a(2*n) = n times the string [10] in binary representation, a(2*n+1) = n times the string [10] followed with [1] in binary representation. Example: a(7) = 85 = (1010101) in binary, a(8) = 170 = (10101010) in binary. - Ctibor O. Zizka, Nov 06 2018
Except for 0, these are the positive integers whose binary expansion has cuts-resistance 1. For the operation of shortening all runs by 1, cuts-resistance is the number of applications required to reach an empty word. Cuts-resistance 2 is A329862. - Gus Wiseman, Nov 27 2019
From Markus Sigg, Sep 14 2020: (Start)
Let s(k) be the length of the Collatz orbit of k, e.g. s(1) = 1, s(2) = 2, s(3) = 5. Then s(a(n)) = n+3 for n >= 3. Proof by induction: s(a(3)) = s(5) = 6 = 3+3. For odd n >= 5 we have s(a(n)) = s(4*a(n-2)+1) = s(12*a(n-2)+4)+1 = s(3*a(n-2)+1)+3 = s(a(n-2))+2 = (n-2)+3+2 = n+3, and for even n >= 4 this gives s(a(n)) = s(2*a(n-1)) = s(a(n-1))+1 = (n-1)+3+1 = n+3.
Conjecture: For n >= 3, a(n) is the second largest natural number whose Collatz orbit has length n+3. (End)
From Gary W. Adamson, May 14 2021: (Start)
With offset 1 the sequence equals the numbers of 1's from n = 1 to 3, 3 to 7, 7 to 15, ...; of A035263; as shown below:
..1     3           7                      15...
..1  0  1  1  1  0  1  0  1  0  1  1  1  0  1...
..1.....2...........5......................10...; a(n) = Sum_(k=1..2n-1)A035263(k)
.....1...........2.......................5...; as to zeros.
..1's in the Tower of Hanoi game represent CW moves On disks in the pattern:
..0,  1,  2,  0,  1,  2, ... whereas even numbered disks move in the pattern:
..0,  2,  1,  0,  2,  1, ... (End)
Except for 0, numbers that are repunits in Gray-code representation (A014550). - Amiram Eldar, May 21 2021
From Gus Wiseman, Apr 20 2023: (Start)
Also the number of nonempty subsets of {1..n} with integer median, where the median of a multiset is the middle part in the odd-length case, and the average of the two middle parts in the even-length case. For example, the a(1) = 1 through a(4) = 10 subsets are:
  {1}  {1}  {1}      {1}
       {2}  {2}      {2}
            {3}      {3}
            {1,3}    {4}
            {1,2,3}  {1,3}
                     {2,4}
                     {1,2,3}
                     {1,2,4}
                     {1,3,4}
                     {2,3,4}
The complement is counted by A005578.
For mean instead of median we have A051293, counting empty sets A327475.
For normal multisets we have A056450, strongly normal A361202.
For partitions we have A325347, strict A359907, complement A307683.
(End)
In binary form, because the sequence 10101_2... keeps repeating, one can represent a(n) = floor(0.(10)2 * 2^n). Because 0.(10)_2 = 0.(10)_2 * 4 - 2, then 0.(10)_2 = 2/3. Substituting this value in the first expression, we obtain a(n) = floor(2^(n+1)/3). This also agrees with the formula of Paul Barry, Oct 08 2005. - _Giovanni Ciriani, Mar 31 2025

			a(4)=10 since 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101, 1111 are the 10 binary strings switching 0000 to 1111.
a(3) = 1 because "lrc" is the only way to tie a tie with 3 half turns, namely, pass the business end of the tie behind the standing part to the left, bring across the front to the right, then behind to the center. The final motion of tucking the loose end down the front behind the "lr" piece is not considered a "step".
a(4) = 2 because "lrlc" is the only way to tie a tie with 4 half turns. Note that since the number of moves is even, the first step is to go to the left in front of the tie, not behind it. This knot is the standard "four in hand", the most commonly known men's tie knot. By contrast, the second most well known tie knot, the Windsor, is represented by "lcrlcrlc".
a(n) = (2^0 - 1) XOR (2^1 - 1) XOR (2^2 - 1) XOR (2^3 - 1) XOR ... XOR (2^n - 1). - _Paul D. Hanna_, Nov 05 2011
G.f. = x + 2*x^2 + 5*x^3 + 10*x^4 + 21*x^5 + 42*x^6 + 85*x^7 + 170*x^8 + ...
a(9) = 341 = 2^8 + 2^6 + 2^4 + 2^2 + 2^0 = 4^4 + 4^3 + 4^2 + 4^1 + 4^0 = A002450(5). a(10) = 682 = 2*a(9) = 2*A002450(5). - _Gregory L. Simay_, Sep 27 2017

Thomas Fink and Yong Mao, The 85 Ways to Tie a Tie, Broadway Books, New York (1999), p. 138.
Clifford A. Pickover, The Math Book, From Pythagoras to the 57th Dimension, 250 Milestones in the History of Mathematics, Sterling Publ., NY, 2009.

G. C. Greubel, Table of n, a(n) for n = 0..3300 (terms 0..300 from T. D. Noe)
Paul Barry, Centered polygon numbers, heptagons and nonagons, and the Robbins numbers, arXiv:2104.01644 [math.CO], 2021.
Thomas Baruchel, Properties of the cumulated deficient binary digit sum, arXiv:1908.02250 [math.NT], 2019.
Sergei L. Bezrukov et al., The congestion of n-cube layout on a rectangular grid, Discrete Mathematics 213.1-3 (2000): 13-19. See Theorem 1.
F. Chapoton and S. Giraudo, Enveloping operads and bicoloured noncrossing configurations, arXiv:1310.4521 [math.CO], 2013. Is the sequence in Table 2 this sequence? - _N. J. A. Sloane_, Jan 04 2014. (Yes, it is. See Stockmeyer's arXiv:1608.08245 2016 paper for the proof.)
Ji Young Choi, Ternary Modified Collatz Sequences And Jacobsthal Numbers, Journal of Integer Sequences, Vol. 19 (2016), #16.7.5.
Ji Young Choi, A Generalization of Collatz Functions and Jacobsthal Numbers, J. Int. Seq., Vol. 21 (2018), Article 18.5.4.
Madeleine Goertz and Aaron Williams, The Quaternary Gray Code and How It Can Be Used to Solve Ziggurat and Other Ziggu Puzzles, arXiv:2411.19291 [math.CO], 2024. See pp. 1, 17, 42.
David Hayes, Kaveh Khodjasteh, Lorenza Viola and Michael J. Biercuk, Reducing sequencing complexity in dynamical quantum error suppression by Walsh modulation, arXiv:1109.6002 [quant-ph], 2011.
Clemens Heuberger and Daniel Krenn, Esthetic Numbers and Lifting Restrictions on the Analysis of Summatory Functions of Regular Sequences, arXiv:1808.00842 [math.CO], 2018. See p. 10.
Clemens Heuberger and Daniel Krenn, Asymptotic Analysis of Regular Sequences, arXiv:1810.13178 [math.CO], 2018. See p. 29.
Andreas M. Hinz, The Lichtenberg sequence, Fib. Quart., 55 (2017), 2-12.
Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović, and Ciril Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See page 56. Book's website
Andreas M. Hinz and Paul K. Stockmeyer, Precious Metal Sequences and Sierpinski-Type Graphs, J. Integer Seq., Vol 25 (2022), Article 22.4.8.
Jia Huang, Nonassociativity of the Norton Algebras of some distance regular graphs, arXiv:2001.05547 [math.CO], 2020.
Jia Huang, Norton algebras of the Hamming Graphs via linear characters, arXiv:2101.05711 [math.CO], 2021.
Jia Huang and Erkko Lehtonen, Associative-commutative spectra for some varieties of groupoids, arXiv:2401.15786 [math.CO], 2024. See p. 17.
Jia Huang, Madison Mickey, and Jianbai Xu, The Nonassociativity of the Double Minus Operation, Journal of Integer Sequences, Vol. 20 (2017), #17.10.3.
Ryota Inagaki, Tanya Khovanova, and Austin Luo, On Chip-Firing on Undirected Binary Trees, Ann. Comb. (2025). See p. 10.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 394
Hans Isdahl, "Knitwear" puzzle
D. E. Knuth and O. P. Lossers, Partitions of a circular set, Problem 11151 in Amer. Math. Monthly 114 (3) (2007) p 265, E_3.
S. Lafortune, A. Ramani, B. Grammaticos, Y. Ohta and K.M. Tamizhmani, Blending two discrete integrability criteria: singularity confinement and algebraic entropy, arXiv:nlin/0104020 [nlin.SI], 2001.
Robert L. Lamphere, A Recurrence Relation in the Spinout Puzzle, The College Mathematics Journal, Vol. 27, Nbr. 4, Page 289, Sep. 96.
Wolfdieter Lang, Notes on certain inhomogeneous three term recurrences.
Georg Christoph Lichtenberg, Vermischte Schriften, Band 6 (1805). See chapter 6, p. 257.
Saad Mneimneh, Simple Variations on the Tower of Hanoi to Guide the Study of Recurrences and Proofs by Induction, Department of Computer Science, Hunter College, CUNY, 2019.
Richard Moot, Partial Orders, Residuation, and First-Order Linear Logic, arXiv:2008.06351 [cs.LO], 2020.
Gregg Musiker and Son Nguyen, Labeled Chip-firing on Binary Trees, arXiv:2206.02007 [math.CO], 2022.
Kival Ngaokrajang, Illustration of initial terms
Ahmet Öteleş, On the sum of Pell and Jacobsthal numbers by the determinants of Hessenberg matrices, AIP Conference Proceedings 1863, 310003 (2017).
Vladimir Shevelev, On the Basis Polynomials in the Theory of Permutations with Prescribed Up-Down Structure, arXiv:0801.0072 [math.CO], 2007-2010. See Example 3.
Chloe E. Shiff and Noah A. Rosenberg, Enumeration of rooted binary perfect phylogenies, arXiv:2410.14915 [q-bio.PE], 2024. See pp. 15, 17.
A. V. Sills and H. Wang, On the maximal Wiener index and related questions, Discrete Applied Mathematics, Volume 160, Issues 10-11, July 2012, Pages 1615-1623 - _N. J. A. Sloane_, Sep 21 2012
N. J. A. Sloane, Transforms
Elen Viviani Pereira Spreafico, Francisco Regis Vieira Alves, Paula Maria Machado Cruz Catarino, and Eudes Antonio Costa, A brief study of the one parameter Lichtenberg numbers, VI Int'l Conf. Math. Appl. Sci. Eng. (ICMASE 2025).
Paul K. Stockmeyer, An Exploration of Sequence A000975, arXiv:1608.08245 [math.CO], 2016; Fib. Quart. 55 (2017) 174.
Eric Weisstein's World of Mathematics, Baguenaudier
A. K. Whitford, Binet's Formula Generalized, Fibonacci Quarterly, Vol. 15, No. 1, 1979, pp. 21, 24, 29.
Index entries for sequences related to binary expansion of n
Index entries for linear recurrences with constant coefficients, signature (2,1,-2).

Partial sums of A001045.
Row sums of triangle A013580.
Equals A026644/2.
Union of the bijections A002450 and A020988. - Robert G. Wilson v, Jun 09 2014
Column k=3 of A261139.
Cf. A000295, A005578, A015441, A043291, A053404, A059260, A077854, A119440, A127824, A130125, A135228, A155051, A179970, A264784.
Complement of A107907.
Row 3 of A300653.
Other sequences that relate to the binary representation of the terms: A003714, A003754, A007088, A022290, A056830, A104161, A107909.
Cf. A000120, A001511, A003242, A027383, A070939, A164707, A295235, A319416.
Cf. A005186, A033491, A153772.
Cf. A014550, A035263
Cf. A051293, A067659, A079309, A231147, A325347, A359893, A359907, A361801.

List([0..35],n->(2^(n+1)-2+(n mod 2))/3); # Muniru A Asiru, Nov 01 2018

a000975 n = a000975_list !! n
a000975_list = 0 : 1 : map (+ 1)
   (zipWith (+) (tail a000975_list) (map (* 2) a000975_list))
-- Reinhard Zumkeller, Mar 07 2012

[(2^(n+1) - 2 + (n mod 2))/3: n in [0..40]]; // Vincenzo Librandi, Mar 18 2015

A000975 := proc(n) option remember; if n <= 1 then n else if n mod 2 = 0 then 2*A000975(n-1) else 2*A000975(n-1)+1 fi; fi; end;
seq(iquo(2^n,3),n=1..33); # Zerinvary Lajos, Apr 20 2008
f:=n-> if n mod 2 = 0 then (2^n-1)/3 else (2^n-2)/3; fi; [seq(f(n),n=0..40)]; # N. J. A. Sloane, Mar 21 2017

Array[Ceiling[2(2^# - 1)/3] &, 41, 0]
RecurrenceTable[{a[0] == 0, a[1] == 1, a[n] == a[n - 1] + 2a[n - 2] + 1}, a, {n, 40}] (* or *)
LinearRecurrence[{2, 1, -2}, {0, 1, 2}, 40] (* Harvey P. Dale, Aug 10 2013 *)
f[n_] := Block[{exp = n - 2}, Sum[2^i, {i, exp, 0, -2}]]; Array[f, 33] (* Robert G. Wilson v, Oct 30 2015 *)
f[s_List] := Block[{a = s[[-1]]}, Append[s, If[OddQ@ Length@ s, 2a + 1, 2a]]]; Nest[f, {0}, 32] (* Robert G. Wilson v, Jul 20 2017 *)
NestList[2# + Boole[EvenQ[#]] &, 0, 39] (* Alonso del Arte, Sep 21 2018 *)

{a(n) = if( n<0, 0, 2 * 2^n \ 3)}; /* Michael Somos, Sep 04 2006 */

a(n)=if(n<=0,0,bitxor(a(n-1),2^n-1)) \\ Paul D. Hanna, Nov 05 2011

concat(0, Vec(x/(1-2*x-x^2+2*x^3) + O(x^100))) \\ Altug Alkan, Oct 30 2015

{a(n) = (4*2^n - 3 - (-1)^n) / 6}; /* Michael Somos, Jul 23 2017 */

def a(n): return (2**(n+1) - 2 + (n%2))//3
print([a(n) for n in range(35)]) # Michael S. Branicky, Dec 19 2021

a(n) = ceiling(2*(2^n-1)/3).
Alternating sum transform (PSumSIGN) of {2^n - 1} (A000225).
a(n) = a(n-1) + 2*a(n-2) + 1.
a(n) = 2*2^n/3 - 1/2 - (-1)^n/6.
a(n) = Sum_{i = 0..n} A001045(i), partial sums of A001045. - Bill Blewett
a(n) = n + 2*Sum_{k = 1..n-2} a(k).
G.f.: x/((1+x)*(1-x)*(1-2*x)) = x/(1-2*x-x^2+2*x^3). - Paul Barry, Feb 11 2003
a(n) = 2*a(n-1) + a(n-2) - 2*a(n-3). - Paul Barry, Feb 11 2003
a(n) = Sum_{k = 0..floor((n-1)/2)} 2^(n-2*k-1). - Paul Barry, Nov 11 2003
a(n+1) = Sum_{k=0..floor(n/2)} 2^(n-2*k); a(n+1) = Sum_{k = 0..n} Sum_{j = 0..k} (-1)^(j+k)*2^j. - Paul Barry, Nov 12 2003
(-1)^(n+1)*a(n) = Sum_{i = 0..n} Sum_{k = 1..i} k!*k* Stirling2(i, k)*(-1)^(k-1) = (1/3)*(-2)^(n+1)-(1/6)(3*(-1)^(n+1)-1). - Mario Catalani (mario.catalani(AT)unito.it), Dec 22 2003
a(n+1) = (n!/3)*Sum_{i - (-1)^i + j = n, i = 0..n, j = 0..n} 1/(i - (-1)^i)!/j!. - Benoit Cloitre, May 24 2004
a(n) = A001045(n+1) - A059841(n). - Paul Barry, Jul 22 2004
a(n) = Sum_{k = 0..n} 2^(n-k-1)*(1-(-1)^k), row sums of A130125. - Paul Barry, Jul 28 2004
a(n) = Sum_{k = 0..n} binomial(k, n-k+1)2^(n-k); a(n) = Sum_{k = 0..floor(n/2)} binomial(n-k, k+1)2^k. - Paul Barry, Oct 07 2004
a(n) = A107909(A104161(n)); A007088(a(n)) = A056830(n). - Reinhard Zumkeller, May 28 2005
a(n) = floor(2^(n+1)/3) = ceiling(2^(n+1)/3) - 1 = A005578(n+1) - 1. - Paul Barry, Oct 08 2005
Convolution of "Number of fixed points in all 231-avoiding involutions in S_n." (A059570) with "1-n" (A024000), treating the result as if offset was 0. - Graeme McRae, Jul 12 2006
a(n) = A081254(n) - 2^n. - Philippe Deléham, Oct 15 2006
Starting (1, 2, 5, 10, 21, 42, ...), these are the row sums of triangle A135228. - Gary W. Adamson, Nov 23 2007
Let T = the 3 X 3 matrix [1,1,0; 1,0,1; 0,1,1]. Then T^n * [1,0,0] = [A005578(n), A001045(n), a(n-1)]. - Gary W. Adamson, Dec 25 2007
2^n = 2*A005578(n-1) + 2*A001045(n) + 2*a(n-2). - Gary W. Adamson, Dec 25 2007
If we define f(m,j,x) = Sum_{k=j..m} binomial(m,k)*stirling2(k,j)*x^(m-k) then a(n-3) = (-1)^(n-1)*f(n,3,-2), (n >= 3). - Milan Janjic, Apr 26 2009
a(n) + A001045(n) = A166920(n). a(n) + A001045(n+2) = A051049(n+1). - Paul Curtz, Oct 29 2009
a(n) = floor(A051049(n+1)/3). - Gary Detlefs, Dec 19 2010
a(n) = round((2^(n+2)-3)/6) = floor((2^(n+1)-1)/3) = round((2^(n+1)-2)/3); a(n) = a(n-2) + 2^(n-1), n > 1. - Mircea Merca, Dec 27 2010
a(n) = binary XOR of 2^k-1 for k=0..n. - Paul D. Hanna, Nov 05 2011
E.g.f.: 2/3*exp(2*x) - 1/2*exp(x) - 1/6*exp(-x) = 2/3*U(0); U(k) = 1 - 3/(4*(2^k) - 4*(2^k)/(1+3*(-1)^k - 24*x*(2^k)/(8*x*(2^k)*(-1)^k - (k+1)/U(k+1)))); (continued fraction). - Sergei N. Gladkovskii, Nov 21 2011
Starting with "1" = triangle A059260 * [1, 2, 2, 2, ...] as a vector. - Gary W. Adamson, Mar 06 2012
a(n) = 2*(2^n - 1)/3, for even n; a(n) = (2^(n+1) - 1)/3 = (1/3)*(2^((n+1)/2) - 1)*(2^((n+1)/2) + 1), for odd n. - Hieronymus Fischer, Nov 22 2012
a(n) + a(n+1) = 2^(n+1) - 1. - Arie Bos, Apr 03 2013
G.f.: Q(0)/(3*(1-x)), where Q(k) = 1 - 1/(4^k - 2*x*16^k/(2*x*4^k - 1/(1 + 1/(2*4^k - 8*x*16^k/(4*x*4^k + 1/Q(k+1)))))); (continued fraction). - Sergei N. Gladkovskii, May 21 2013
floor(a(n+2)*3/5) = A077854(n), for n >= 0. - Armands Strazds, Sep 21 2014
a(n) = (2^(n+1) - 2 + (n mod 2))/3. - Paul Toms, Mar 18 2015
a(0) = 0, a(n) = 2*(a(n-1)) + (n mod 2). - Paul Toms, Mar 18 2015
Binary: a(n) = (a(n-1) shift left 1) + (a(n-1)) NOR (...11110). - Paul Toms, Mar 18 2015
Binary: for n > 1, a(n) = 2*a(n-1) OR a(n-2). - Stanislav Sykora, Nov 12 2015
a(n) = A266613(n) - 20*2^(n-5), for n > 2. - Andres Cicuttin, Mar 31 2016
From Michael Somos, Jul 23 2017: (Start)
a(n) = -(2^n)*a(-n) for even n; a(n) = -(2^(n+1))*a(-n) + 1 for odd n.
0 = +a(n)*(+2 +4*a(n) -4*a(n+1)) + a(n+1)*(-1 +a(n+1)) for all n in Z. (End)
G.f.: (x^1+x^3+x^5+x^7+...)/(1-2*x). - Gregory L. Simay, Sep 27 2017
a(n+1) = A051049(n) + A001045(n). - Yuchun Ji, Jul 12 2018
a(n) = A153772(n+3)/4. - Markus Sigg, Sep 14 2020
a(4*k+d) = 2^(d+1)*a(4*k-1) + a(d), a(n+4) = a(n) + 2^n*10, a(0..3) = [0,1,2,5]. So the last digit is always 0,1,2,5 repeated. - Yuchun Ji, May 22 2023

Additional comments from Barry E. Williams, Jan 10 2000

A333489 Numbers k such that the k-th composition in standard order is an anti-run (no adjacent equal parts).

Original entry on oeis.org

0, 1, 2, 4, 5, 6, 8, 9, 12, 13, 16, 17, 18, 20, 22, 24, 25, 32, 33, 34, 37, 38, 40, 41, 44, 45, 48, 49, 50, 52, 54, 64, 65, 66, 68, 69, 70, 72, 76, 77, 80, 81, 82, 88, 89, 96, 97, 98, 101, 102, 104, 105, 108, 109, 128, 129, 130, 132, 133, 134, 137, 140, 141

Offset: 1

Gus Wiseman, Mar 28 2020

nonn

A composition of n is a finite sequence of positive integers summing to n. The k-th composition in standard order (row k of A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again.

			The sequence together with the corresponding compositions begins:
    0: ()          33: (5,1)         70: (4,1,2)
    1: (1)         34: (4,2)         72: (3,4)
    2: (2)         37: (3,2,1)       76: (3,1,3)
    4: (3)         38: (3,1,2)       77: (3,1,2,1)
    5: (2,1)       40: (2,4)         80: (2,5)
    6: (1,2)       41: (2,3,1)       81: (2,4,1)
    8: (4)         44: (2,1,3)       82: (2,3,2)
    9: (3,1)       45: (2,1,2,1)     88: (2,1,4)
   12: (1,3)       48: (1,5)         89: (2,1,3,1)
   13: (1,2,1)     49: (1,4,1)       96: (1,6)
   16: (5)         50: (1,3,2)       97: (1,5,1)
   17: (4,1)       52: (1,2,3)       98: (1,4,2)
   18: (3,2)       54: (1,2,1,2)    101: (1,3,2,1)
   20: (2,3)       64: (7)          102: (1,3,1,2)
   22: (2,1,2)     65: (6,1)        104: (1,2,4)
   24: (1,4)       66: (5,2)        105: (1,2,3,1)
   25: (1,3,1)     68: (4,3)        108: (1,2,1,3)
   32: (6)         69: (4,2,1)      109: (1,2,1,2,1)

Vaclav Kotesovec, Table of n, a(n) for n = 1..10000

Anti-runs summing to n are counted by A003242(n).
A triangle counting maximal anti-runs of compositions is A106356.
A triangle counting maximal runs of compositions is A238279 or A238130.
Partitions whose first differences are an anti-run are A238424.
All of the following pertain to compositions in standard order (A066099):
- Adjacent equal pairs are counted by A124762.
- Weakly decreasing runs are counted by A124765.
- Weakly increasing runs are counted by A124766.
- Equal runs are counted by A124767.
- Strictly increasing runs are counted by A124768.
- Strictly decreasing runs are counted by A124769.
- Strict compositions are ranked by A233564.
- Constant compositions are ranked by A272919.
- Normal compositions are ranked by A333217.
- Anti-runs are counted by A333381.
- Adjacent unequal pairs are counted by A333382.
Cf. A000120, A029931, A048793, A066099, A070939, A228351.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Select[Range[0,100],!MatchQ[stc[#],{_,x_,x_,_}]&]

A032020 Number of compositions (ordered partitions) of n into distinct parts.

Original entry on oeis.org

1, 1, 1, 3, 3, 5, 11, 13, 19, 27, 57, 65, 101, 133, 193, 351, 435, 617, 851, 1177, 1555, 2751, 3297, 4757, 6293, 8761, 11305, 15603, 24315, 30461, 41867, 55741, 74875, 98043, 130809, 168425, 257405, 315973, 431065, 558327, 751491, 958265, 1277867, 1621273

Offset: 0

Christian G. Bower, Apr 01 1998

Compositions into distinct parts are equivalent to (1,1)-avoiding compositions. - Gus Wiseman, Jun 25 2020

All terms are odd. - Alois P. Heinz, Apr 09 2021

			a(6) = 11 because 6 = 5+1 = 4+2 = 3+2+1 = 3+1+2 = 2+4 = 2+3+1 = 2+1+3 = 1+5 = 1+3+2 = 1+2+3.
From _Gus Wiseman_, Jun 25 2020: (Start)
The a(0) = 1 through a(7) = 13 strict compositions:
  ()  (1)  (2)  (3)    (4)    (5)    (6)      (7)
                (1,2)  (1,3)  (1,4)  (1,5)    (1,6)
                (2,1)  (3,1)  (2,3)  (2,4)    (2,5)
                              (3,2)  (4,2)    (3,4)
                              (4,1)  (5,1)    (4,3)
                                     (1,2,3)  (5,2)
                                     (1,3,2)  (6,1)
                                     (2,1,3)  (1,2,4)
                                     (2,3,1)  (1,4,2)
                                     (3,1,2)  (2,1,4)
                                     (3,2,1)  (2,4,1)
                                              (4,1,2)
                                              (4,2,1)
(End)

Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem II, Missouri Journal of Mathematical Sciences, Vol. 16, No. 1, Winter 2004, pp. 12-17.

Alois P. Heinz, Table of n, a(n) for n = 0..10000 (first 1001 terms from T. D. Noe)
C. G. Bower, Transforms (2)
Martin Klazar, What is an answer? — remarks, results and problems on PIO formulas in combinatorial enumeration, part I, arXiv:1808.08449 [math.CO], 2018.
B. Richmond and A. Knopfmacher, Compositions with distinct parts, Aequationes Mathematicae 49 (1995), pp. 86-97.
B. Richmond and A. Knopfmacher, Compositions with distinct parts, Aequationes Mathematicae 49 (1995), pp. 86-97. (free access)
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

Cf. A008289, A032011.
Row sums of A241719.
Column k=1 of A243081, A242447, A261835, A261836, A327244, A327245.
Main diagonal of A261960.
Dominated by A003242 (anti-run compositions).
These compositions are ranked by A233564.
(1,1)-avoiding patterns are counted by A000142.
Numbers with strict prime signature are A130091.
(1,1,1)-avoiding compositions are counted by A232432.
(1,1)-matching compositions are counted by A261982.
Inseparable partitions are counted by A325535.
Patterns matched by compositions are counted by A335456.
Strict permutations of prime indices are counted by A335489.
Cf. A000009, A011782, A102726, A181796, A261962, A333489, A335457.

b:= proc(n, i) b(n, i):= `if`(n=0, [1], `if`(i<1, [], zip((x, y)
      -> x+y, b(n, i-1), `if`(i>n, [], [0, b(n-i, i-1)[]]), 0))) end:
a:= proc(n) local l; l:=b(n, n): add((i-1)! *l[i], i=1..nops(l)) end:
seq(a(n), n=0..50);  # Alois P. Heinz, Dec 12 2012
# second Maple program:
T:= proc(n, k) option remember; `if`(k<0 or n<0, 0,
      `if`(k=0, `if`(n=0, 1, 0), T(n-k, k) +k*T(n-k, k-1)))
    end:
a:= n-> add(T(n, k), k=0..floor((sqrt(8*n+1)-1)/2)):
seq(a(n), n=0..60);  # Alois P. Heinz, Sep 04 2015

f[list_]:=Length[list]!; Table[Total[Map[f, Select[IntegerPartitions[n], Sort[#] == Union[#] &]]], {n, 0,30}]
T[n_, k_] := T[n, k] = If[k<0 || n<0, 0, If[k==0, If[n==0, 1, 0], T[n-k, k] + k*T[n-k, k-1]]]; a[n_] := Sum[T[n, k], {k, 0, Floor[(Sqrt[8*n + 1] - 1) / 2]}]; Table[a[n], {n, 0, 60}] (* Jean-François Alcover, Sep 22 2015, after Alois P. Heinz *)

N=66;  q='q+O('q^N);
gf=sum(n=0,N, n!*q^(n*(n+1)/2) / prod(k=1,n, 1-q^k ) );
Vec(gf)
/* Joerg Arndt, Oct 20 2012 */

Q(N) = { \\ A008289
  my(q = vector(N)); q[1] = [1, 0, 0, 0];
  for (n = 2, N,
    my(m = (sqrtint(8*n+1) - 1)\2);
    q[n] = vector((1 + (m>>2)) << 2); q[n][1] = 1;
    for (k = 2, m, q[n][k] = q[n-k][k] + q[n-k][k-1]));
  return(q);
};
seq(N) = concat(1, apply(q -> sum(k = 1, #q, q[k] * k!), Q(N)));
seq(43) \\ Gheorghe Coserea, Sep 09 2018

"AGK" (ordered, elements, unlabeled) transform of 1, 1, 1, 1, ...
G.f.: Sum_{k>=0} k! * x^((k^2+k)/2) / Product_{j=1..k} (1-x^j). - David W. Wilson May 04 2000
a(n) = Sum_{m=1..n} A008289(n,m)*m!. - Geoffrey Critzer, Sep 07 2012

A088218 Total number of leaves in all rooted ordered trees with n edges.

Original entry on oeis.org

1, 1, 3, 10, 35, 126, 462, 1716, 6435, 24310, 92378, 352716, 1352078, 5200300, 20058300, 77558760, 300540195, 1166803110, 4537567650, 17672631900, 68923264410, 269128937220, 1052049481860, 4116715363800, 16123801841550, 63205303218876, 247959266474052

Offset: 0

Michael Somos, Sep 24 2003

Essentially the same as A001700, which has more information.
Note that the unique rooted tree with no edges has no leaves, so a(0)=1 is by convention. - Michael Somos, Jul 30 2011
Number of ordered partitions of n into n parts, allowing zeros (cf. A097070) is binomial(2*n-1,n) = a(n) = essentially A001700. - Vladeta Jovovic, Sep 15 2004
Hankel transform is A000027; example: Det([1,1,3,10;1,3,10,35;3,10,35,126; 10,35,126,462]) = 4. - Philippe Deléham, Apr 13 2007
a(n) is the number of functions f:[n]->[n] such that for all x,y in [n] if xA045992(n). - Geoffrey Critzer, Apr 02 2009
Hankel transform of the aeration of this sequence is A000027 doubled: 1,1,2,2,3,3,... - Paul Barry, Sep 26 2009
The Fi1 and Fi2 triangle sums of A039599 are given by the terms of this sequence. For the definitions of these triangle sums see A180662. - Johannes W. Meijer, Apr 20 2011
Alternating row sums of Riordan triangle A094527. See the Philippe Deléham formula. - Wolfdieter Lang, Nov 22 2012
(-2)*a(n) is the Z-sequence for the Riordan triangle A110162. For the notion of Z- and A-sequences for Riordan arrays see the W. Lang link under A006232 with details and references. - Wolfdieter Lang, Nov 22 2012
From Gus Wiseman, Jun 27 2021: (Start)
Also the number of integer compositions of 2n with alternating (or reverse-alternating) sum 0 (ranked by A344619). This is equivalent to Ran Pan's comment at A001700. For example, the a(0) = 1 through a(3) = 10 compositions are:
  ()  (11)  (22)    (33)
            (121)   (132)
            (1111)  (231)
                    (1122)
                    (1221)
                    (2112)
                    (2211)
                    (11121)
                    (12111)
                    (111111)
For n > 0, a(n) is also the number of integer compositions of 2n with alternating sum 2.
(End)
Number of terms in the expansion of (x_1+x_2+...+x_n)^n. - César Eliud Lozada, Jan 08 2022

			G.f. = 1 + x + 3*x^2 + 10*x^3 + 35*x^4 + 126*x^5 + 462*x^6 + 1716*x^7 + ...
The five rooted ordered trees with 3 edges have 10 leaves.
..x........................
..o..x.x..x......x.........
..o...o...o.x..x.o..x.x.x..
..r...r....r....r.....r....

L. W. Shapiro and C. J. Wang, Generating identities via 2 X 2 matrices, Congressus Numerantium, 205 (2010), 33-46.

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Anwar Al Ghabra, K. Gopala Krishna, Patrick Labelle, and Vasilisa Shramchenko, Enumeration of multi-rooted plane trees, arXiv:2301.09765 [math.CO], 2023.
Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.
B. Dasarathy and C. Yang, A transformation on ordered trees, Comput. J. 23 (1980) 161-164. - _Nachum Dershowitz_, Sep 01 2016
Toufik Mansour and Mark Shattuck, A statistic on n-color compositions and related sequences, Proc. Indian Acad. Sci. (Math. Sci.) Vol. 124, No. 2, May 2014, pp. 127-140.
Anthony Mansuy, Preordered forests, packed words and contraction algebras, J. Algebra 411 (2014) 259-311.
Mircea Merca, A Note on Cosine Power Sums, J. Integer Sequences, Vol. 15 (2012), Article 12.5.3.
A. Vogt, Resummation of small-x double logarithms in QCD: semi-inclusive electron-positron annihilation, arXiv preprint arXiv:1108.2993 [hep-ph], 2011.

Same as A001700 modulo initial term and offset.
First differences are A024718.
Main diagonal of A071919 and of A305161.
A signed version is A110556.
A000041 counts partitions of 2n with alternating sum 0, ranked by A000290.
A003242 counts anti-run compositions.
A025047 counts wiggly compositions (ascend: A025048, descend: A025049).
A103919 counts partitions by sum and alternating sum (reverse: A344612).
A106356 counts compositions by number of maximal anti-runs.
A124754 gives the alternating sum of standard compositions.
A345197 counts compositions by sum, length, and alternating sum.
Compositions of n, 2n, or 2n+1 with alternating/reverse-alternating sum k:
- k = 0:  counted by A088218 (this sequence), ranked by A344619/A344619.
- k = 1:  counted by A000984, ranked by A345909/A345911.
- k = -1: counted by A001791, ranked by A345910/A345912.
- k = 2:  counted by A088218 (this sequence), ranked by A345925/A345922.
- k = -2: counted by A002054, ranked by A345924/A345923.
- k >= 0: counted by A116406, ranked by A345913/A345914.
- k <= 0: counted by A058622(n-1), ranked by A345915/A345916.
- k > 0:  counted by A027306, ranked by A345917/A345918.
- k < 0:  counted by A294175, ranked by A345919/A345920.
- k != 0: counted by A058622, ranked by A345921/A345921.
- k even: counted by A081294, ranked by A053754/A053754.
- k odd:  counted by A000302, ranked by A053738/A053738.
Cf. A000027, A000070, A000097, A000108, A001622, A006232, A008965, A039599, A045992, A058696, A094527, A097070, A110162, A110555, A180662, A238279, A239830, A325534, A325535, A333213, A344607, A344611, A344617.

[Binomial(2*n-1, n): n in [0..30]]; // Vincenzo Librandi, Aug 07 2014

seq(binomial(2*n-1, n),n=0..24); # Peter Luschny, Sep 22 2014

a[ n_] := SeriesCoefficient[(1 - x)^-n, {x, 0, n}];
c = (1 - (1 - 4 x)^(1/2))/(2 x);CoefficientList[Series[1/(1-(c-1)),{x,0,20}],x] (* Geoffrey Critzer, Dec 02 2010 *)
Table[Binomial[2 n - 1, n], {n, 0, 20}] (* Vincenzo Librandi, Aug 07 2014 *)
a[ n_] := If[ n < 0, 0, With[ {m = 2 n}, m! SeriesCoefficient[ (1 + BesselI[0, 2 x]) / 2, {x, 0, m}]]]; (* Michael Somos, Nov 22 2014 *)

{a(n) = sum( i=0, n, binomial(n+i-2,i))};

{a(n) = if( n<0, 0, polcoeff( (1 + 1 / sqrt(1 - 4*x + x * O(x^n))) / 2, n))};

{a(n) = if( n<0, 0, polcoeff( 1 / (1 - x + x * O(x^n))^n, n))};

{a(n) = if( n<0, 0, binomial( 2*n - 1, n))};

{a(n) = if( n<1, n==0, polcoeff( subst((1 - x) / (1 - 2*x), x, serreverse( x - x^2 + x * O(x^n))), n))};

def A088218(n):
    return rising_factorial(n,n)/falling_factorial(n,n)
[A088218(n) for n in (0..24)]  # Peter Luschny, Nov 21 2012

G.f.: (1 + 1 / sqrt(1 - 4*x)) / 2.
a(n) = binomial(2*n - 1, n).
a(n) = (n+1)*A000108(n)/2, n>=1. - B. Dubalski (dubalski(AT)atr.bydgoszcz.pl), Feb 05 2002 (in A060150)
a(n) = (0^n + C(2n, n))/2. - Paul Barry, May 21 2004
a(n) is the coefficient of x^n in 1 / (1 - x)^n and also the sum of the first n coefficients of 1 / (1 - x)^n. Given B(x) with the property that the coefficient of x^n in B(x)^n equals the sum of the first n coefficients of B(x)^n, then B(x) = B(0) / (1 - x).
G.f.: 1 / (2 - C(x)) = (1 - x*C(x))/sqrt(1-4*x) where C(x) is g.f. for Catalan numbers A000108. Second equation added by Wolfdieter Lang, Nov 22 2012.
From Paul Barry, Nov 02 2004: (Start)
a(n) = Sum_{k=0..n} binomial(2*n, k)*cos((n-k)*Pi);
a(n) = Sum_{k=0..n} binomial(n, (n-k)/2)*(1+(-1)^(n-k))*cos(k*Pi/2)/2 (with interpolated zeros);
a(n) = Sum_{k=0..floor(n/2)} binomial(n, k)*cos((n-2*k)*Pi/2) (with interpolated zeros); (End)
a(n) = A110556(n)*(-1)^n, central terms in triangle A110555. - Reinhard Zumkeller, Jul 27 2005
a(n) = Sum_{0<=k<=n} A094527(n,k)*(-1)^k. - Philippe Deléham, Mar 14 2007
From Paul Barry, Mar 29 2010: (Start)
G.f.: 1/(1-x/(1-2x/(1-(1/2)x/(1-(3/2)x/(1-(2/3)x/(1-(4/3)x/(1-(3/4)x/(1-(5/4)x/(1-... (continued fraction);
E.g.f.: (of aerated sequence) (1 + Bessel_I(0, 2*x))/2. (End)
a(n + 1) = A001700(n). a(n) = A024718(n) - A024718(n - 1).
E.g.f.: E(x) = 1+x/(G(0)-2*x) ; G(k) = (k+1)^2+2*x*(2*k+1)-2*x*(2*k+3)*((k+1)^2)/G(k+1); (continued fraction). - Sergei N. Gladkovskii, Dec 21 2011
a(n) = Sum_{k=0..n}(-1)^k*binomial(2*n,n+k). - Mircea Merca, Jan 28 2012
a(n) = rf(n,n)/ff(n,n), where rf is the rising factorial and ff the falling factorial. - Peter Luschny, Nov 21 2012
D-finite with recurrence: n*a(n) +2*(-2*n+1)*a(n-1) = 0. - R. J. Mathar, Dec 04 2012
a(n) = hypergeom([1-n,-n],[1],1). - Peter Luschny, Sep 22 2014
G.f.: 1 + x/W(0), where W(k) = 4*k+1 - (4*k+3)*x/(1 - (4*k+1)*x/(4*k+3 - (4*k+5)*x/(1 - (4*k+3)*x/W(k+1)  ))) ; (continued fraction). - Sergei N. Gladkovskii, Nov 13 2014
a(n) = A000984(n) + A001791(n). - Gus Wiseman, Jun 28 2021
E.g.f.: (1 + exp(2*x) * BesselI(0,2*x)) / 2. - Ilya Gutkovskiy, Nov 03 2021
From Amiram Eldar, Mar 12 2023: (Start)
Sum_{n>=0} 1/a(n) = 5/3 + 4*Pi/(9*sqrt(3)).
Sum_{n>=0} (-1)^n/a(n) = 3/5 - 8*log(phi)/(5*sqrt(5)), where phi is the golden ratio (A001622). (End)
a(n) ~ 2^(2*n-1)/sqrt(n*Pi). - Stefano Spezia, Apr 17 2024

A106356 Triangle T(n,k) 0<=k

Original entry on oeis.org

1, 1, 1, 3, 0, 1, 4, 3, 0, 1, 7, 6, 2, 0, 1, 14, 7, 8, 2, 0, 1, 23, 20, 10, 8, 2, 0, 1, 39, 42, 22, 13, 9, 2, 0, 1, 71, 72, 58, 28, 14, 10, 2, 0, 1, 124, 141, 112, 72, 33, 16, 11, 2, 0, 1, 214, 280, 219, 150, 92, 36, 18, 12, 2, 0, 1, 378, 516, 466, 311, 189, 112, 40, 20, 13, 2, 0, 1

Offset: 1

Christian G. Bower, Apr 29 2005

For n > 0, also the number of compositions of n with k + 1 maximal anti-runs (sequences without adjacent equal terms). - Gus Wiseman, Mar 23 2020

			T(4,1) = 3 because the compositions of 4 with 1 adjacent equal part are 1+1+2, 2+1+1, 2+2.
Triangle begins:
   1;
   1,  1;
   3,  0,  1;
   4,  3,  0, 1;
   7,  6,  2, 0, 1;
  14,  7,  8, 2, 0, 1;
  23, 20, 10, 8, 2, 0, 1;
  ...
From _Gus Wiseman_, Mar 23 2020 (Start)
Row n = 6 counts the following compositions (empty column shown by dot):
  (6)     (33)    (222)    (11112)  .  (111111)
  (15)    (114)   (1113)   (21111)
  (24)    (411)   (1122)
  (42)    (1131)  (2211)
  (51)    (1221)  (3111)
  (123)   (1311)  (11121)
  (132)   (2112)  (11211)
  (141)           (12111)
  (213)
  (231)
  (312)
  (321)
  (1212)
  (2121)
(End)

Alois P. Heinz, Rows n = 1..141, flattened
A. Knopfmacher and H. Prodinger, On Carlitz compositions, European Journal of Combinatorics, Vol. 19, 1998, pp. 579-589.

Row sums: 2^(n-1)=A000079(n-1). Columns 0-4: A003242, A106357-A106360.
The version counting adjacent unequal parts is A238279.
The k-th composition in standard-order has A124762(k) adjacent equal parts and A333382(k) adjacent unequal parts.
The k-th composition in standard-order has A124767(k) maximal runs and A333381(k) maximal anti-runs.
The version for ascents/descents is A238343.
The version for weak ascents/descents is A333213.
Cf. A064113, A066099, A233564, A333214, A333216.

b:= proc(n, h, t) option remember;
      if n=0 then `if`(t=0, 1, 0)
    elif t<0 then 0
    else add(b(n-j, j, `if`(j=h, t-1, t)), j=1..n)
      fi
    end:
T:= (n, k)-> b(n, -1, k):
seq(seq(T(n, k), k=0..n-1), n=1..15); # Alois P. Heinz, Oct 23 2011

b[n_, h_, t_] := b[n, h, t] = If[n == 0, If[t == 0, 1, 0], If[t<0, 0, Sum[b[n-j, j, If [j == h, t-1, t]], {j, 1, n}]]]; T[n_, k_] := b[n, -1, k]; Table[Table[T[n, k], {k, 0, n-1}], {n, 1, 15}] // Flatten (* Jean-François Alcover, Feb 20 2015, after Alois P. Heinz *)
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],n==0||Length[Split[#,#1!=#2&]]==k+1&]],{n,0,12},{k,0,n}] (* Gus Wiseman, Mar 23 2020 *)

A005251 a(0) = 0, a(1) = a(2) = a(3) = 1; thereafter, a(n) = a(n-1) + a(n-2) + a(n-4).

Original entry on oeis.org

0, 1, 1, 1, 2, 4, 7, 12, 21, 37, 65, 114, 200, 351, 616, 1081, 1897, 3329, 5842, 10252, 17991, 31572, 55405, 97229, 170625, 299426, 525456, 922111, 1618192, 2839729, 4983377, 8745217, 15346786, 26931732, 47261895, 82938844, 145547525, 255418101, 448227521

Offset: 0

N. J. A. Sloane and R. K. Guy

a(n+3) is the number of n-bit sequences that avoid 010. Example: For n=4 the 12 sequences are all 4-bit sequences except 0100, 0101, 0010, 1010. - David Callan, Mar 25 2004
a(n+2) is the number of compositions (ordered partitions) of n where no two adjacent parts are != 1, see example. - Joerg Arndt, Jan 26 2013
a(n+1) is the number of compositions of n avoiding the part 2. - Joerg Arndt, Jul 13 2014
Number of different positive braids with n crossings of 3 strands.
This is a_2(n) in the Doroslovacki reference. Note that there is a typo in the paper in the formula for a_2(n): the upper bound in the inner sum should be "n-i" not "i-1". - Max Alekseyev, Jun 26 2007
a(n) is the number of peakless Motzkin paths of length n-1 with no UHH...HD's starting at level > 0 (here n > 0 and U=(1,1), H=(1,0), D=(1,-1)). Example: a(5)=7 because from all 8 peakless Motzkin paths of length 5 (see A004148) only UUHDD does not qualify. - Emeric Deutsch, Sep 13 2004
Equals the INVERT transform of (1, 0, 1, 1, 1, ...); equivalent to a(n) = a(n-1) + a(n-3) + a(n-4) + ... - Gary W. Adamson, Apr 27 2009
a(n) is the number of length n-1 words on {0,1} such that each string of 1's is followed by a string of at least two 0's. For example, a(5) = 4 because we have: 0000, 0100, 1000, and 1100. - Geoffrey Critzer, Aug 09 2013
a(n+1) is the top left entry of the n-th power of any of the 3 X 3 matrices [1, 1, 0; 0, 1, 1; 1, 0, 0] or [1, 0, 1; 1, 1, 0; 0, 1, 0] or [1, 1, 0; 0, 0, 1; 1, 0, 1] or [1, 0, 1; 1, 0, 0; 0, 1, 1]. - R. J. Mathar, Feb 03 2014
For n >= 2, a(n) is the number of (n-2)-length binary words with no isolated zeros. - Milan Janjic, Mar 07 2015
Apart from the first three terms, the total number of bargraphs of semiperimeter n of height at most two for n >= 2 starts 1, 2, 4, 7, 12, ... - Arnold Knopfmacher, Nov 02 2016
Number of DD-equivalence classes of Łukasiewicz paths. Łukasiewicz paths are DD-equivalent iff the positions of pattern DD are identical in these paths. - Sergey Kirgizov, Apr 08 2018
From Gus Wiseman, Nov 25 2019: (Start)
For n > 0, also the number of subsets of {1, ..., n - 3} such that if x and x + 2 are both in the subset, then so is x + 1. For example, the a(3) = 1 through a(7) = 12 subsets are:
  {}  {}   {}     {}       {}
      {1}  {1}    {1}      {1}
           {2}    {2}      {2}
           {1,2}  {3}      {3}
                  {1,2}    {4}
                  {2,3}    {1,2}
                  {1,2,3}  {1,4}
                           {2,3}
                           {3,4}
                           {1,2,3}
                           {2,3,4}
                           {1,2,3,4}
(End)
The two-dimensional version, which counts sets of pairs where, if two pairs are separated by graph-distance 2, then the intermediate pair or pairs are also in the set, is A329871. - Gus Wiseman, Nov 30 2019
a(n+1) is the number of ways to tile a strip of length n with squares, dominoes, and tetrominoes, where the first tile cannot be a domino. - Greg Dresden and Myanna Nash, Aug 18 2020

			From _Joerg Arndt_, Jan 26 2013: (Start)
The a(5+2) = 12 compositions of 5 where no two adjacent parts are != 1 are
  [ 1]  [ 1 1 1 1 1 ]
  [ 2]  [ 1 1 1 2 ]
  [ 3]  [ 1 1 2 1 ]
  [ 4]  [ 1 1 3 ]
  [ 5]  [ 1 2 1 1 ]
  [ 6]  [ 1 3 1 ]
  [ 7]  [ 1 4 ]
  [ 8]  [ 2 1 1 1 ]
  [ 9]  [ 2 1 2 ]
  [10]  [ 3 1 1 ]
  [11]  [ 4 1 ]
  [12]  [ 5 ]
(End)
G.f. = x + x^2 + x^3 + 2*x^4 + 4*x^5 + 7*x^6 + 12*x^7 + 21*x^8 + 37*x^9 + ...

S. Burckel, Efficient methods for three strand braids (submitted). [Apparently unpublished]
P. Chinn and S. Heubach, "Compositions of n with no occurrence of k", Congressus Numeratium, 2002, v. 162, pp. 33-51.
John H. Conway and R. K. Guy, The Book of Numbers, Copernicus Press, p. 205.
R. K. Guy, "Anyone for Twopins?" in D. A. Klarner, editor, The Mathematical Gardner. Prindle, Weber and Schmidt, Boston, 1981, pp. 2-15.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..500
Kassie Archer, Ethan Borsh, Jensen Bridges, Christina Graves, and Millie Jeske, Cyclic permutations avoiding patterns in both one-line and cycle forms, arXiv:2312.05145 [math.CO], 2023. See p. 2.
Andrei Asinowski and Cyril Banderier, On Lattice Paths with Marked Patterns: Generating Functions and Multivariate Gaussian Distribution, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020) Leibniz International Proceedings in Informatics (LIPIcs) Vol. 159, 1:1-1:16.
R. Austin and R. K. Guy, Binary sequences without isolated ones, Fib. Quart., 16 (1978), 84-86.
J.-L. Baril, Avoiding patterns in irreducible permutations, Discrete Mathematics and Theoretical Computer Science, Vol 17, No 3 (2016). See Table 4.
Jean-Luc Baril, Sergey Kirgizov and Armen Petrossian, Enumeration of Łukasiewicz paths modulo some patterns, arXiv:1804.01293 [math.CO], 2018.
N. Bergeron, S. Mykytiuk, F. Sottile and S. van Willigenburg, Shifted quasisymmetric functions and the Hopf algebra of peak functions, arXiv:math/9904105 [math.CO], 1999.
D. Birmajer, J. B. Gil, and M. D. Weiner, On the Enumeration of Restricted Words over a Finite Alphabet, J. Int. Seq. 19 (2016) # 16.1.3, Example 11.
A. Blecher, C. Brennan, A. Knopfmacher and H. Prodinger, The height and width of bargraphs, Discrete Applied Math. 180, (2015), 36-44.
A. Brousseau, Fibonacci and Related Number Theoretic Tables, Fibonacci Association, San Jose, CA, 1972, p. 112.
P. Chinn and S. Heubach, Integer Sequences Related to Compositions without 2's, J. Integer Seqs., Vol. 6, 2003.
James Currie, Pascal Ochem, Narad Rampersad, and Jeffrey Shallit, Properties of a Ternary Infinite Word, arXiv:2206.01776 [cs.DM], 2022.
James Currie, Pascal Ochem, Narad Rampersad, and Jeffrey Shallit, Complement Avoidance in Binary Words, arXiv:2209.09598 [math.CO], 2022.
J. Demetrovics et al., On the number of unions in a family of sets, in Combinatorial Math., Proc. 3rd Internat. Conf., Annals NY Acad. Sci., 555 (1989), 150-158.
R. Doroslovacki, Binary sequences without 011...110 (k-1 1's) for fixed k, Mat. Vesnik 46 (1994), no. 3-4, 93-98.
Nazim Fatès, Biswanath Sethi, and Sukanta Das, On the Reversibility of ECAs with Fully Asynchronous Updating: The Recurrence Point of View, in Reversibility and Universality, Andrew Adamatzky, editor, Emergence, Complexity and Computation Vol. 30. Springer, 2018.
Steven Finch, Cantor-solus and Cantor-multus distributions, arXiv:2003.09458 [math.CO], 2020.
R. L. Graham and N. J. A. Sloane, Anti-Hadamard matrices, Linear Alg. Applic., 62 (1984), 113-137.
R. K. Guy, Letter to N. J. A. Sloane, Feb 1986
R. K. Guy, Anyone for Twopins?, in D. A. Klarner, editor, The Mathematical Gardner. Prindle, Weber and Schmidt, Boston, 1981, pp. 2-15. [Annotated scanned copy, with permission]
V. C. Harris and C. C. Styles, A generalization of Fibonacci numbers, Fib. Quart. 2 (1964) 277-289, sequence u(n,1,2).
V. E. Hoggatt, Jr., 7-page typed letter to N. J. A. Sloane with suggestions for new sequences, circa 1977.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 98
Milan Janjic, Binomial Coefficients and Enumeration of Restricted Words, Journal of Integer Sequences, 2016, Vol 19, #16.7.3.
Vedran Krcadinac, A new generalization of the golden ratio, Fibonacci Quart. 44 (2006), no. 4, 335-340.
Erkko Lehtonen and Tamás Waldhauser, Associative spectra of graph algebras II. Satisfaction of bracketing identities, spectrum dichotomy, arXiv:2011.08522 [math.CO], 2020.
J. J. Madden, A generating function for the distribution of runs in binary words, arXiv:1707.04351 [math.CO], 2017, Theorem 1.1, r=2, k=0.
T. Mansour and M. Shattuck, Counting Peaks and Valleys in a Partition of a Set, J. Int. Seq. 13 (2010), 10.6.8, Lemma 2.1, k=2, 0 peaks.
Denis Neiter and Amsha Proag, Links Between Sums Over Paths in Bernoulli's Triangles and the Fibonacci Numbers, Journal of Integer Sequences, Vol. 19 (2016), Article 16.8.3.
Nicolas Ollinger and Jeffrey Shallit, The Repetition Threshold for Rote Sequences, arXiv:2406.17867 [math.CO], 2024.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
A. G. Shannon, Some recurrence relations for binary sequence matrices, NNTDM 17 (2011), 4, 913.
Bojan Vučković and Miodrag Živković, Row Space Cardinalities Above 2^(n - 2) + 2^(n - 3), ResearchGate, January 2017, p. 3.
Index entries for linear recurrences with constant coefficients, signature (2,-1,1).

Cf. A001608, A004148, A005314, A006498, A011973, A049864, A049853, A078065, A118891, A173022, A176971, A178470, A261041, A303696, A329871, A384153.
Bisection of Padovan sequence A000931.
Partial sums of A005314 shifted 3 times to the right, if we assume A005314(0) = 1.
Compositions without adjacent equal parts are A003242.
Compositions without isolated parts are A114901.
Row sums of A097230(n-2) for n>1.

a005251 n = a005251_list !! n
a005251_list = 0 : 1 : 1 : 1 : zipWith (+) a005251_list
   (drop 2 $ zipWith (+) a005251_list (tail a005251_list))
-- Reinhard Zumkeller, Dec 28 2011

I:=[0,1,1,1]; [n le 4 select I[n] else Self(n-1)+Self(n-2)+Self(n-4): n in [1..45]]; // Vincenzo Librandi, Nov 30 2018

R:=PowerSeriesRing(Integers(), 40); [0] cat Coefficients(R!( x*(1-x)/(1-2*x + x^2 - x^3) )); // Marius A. Burtea, Oct 24 2019

A005251 := proc(n) option remember; if n <= 2 then n elif n = 3 then 4 else 2*A005251(n - 1) - A005251(n - 2) + A005251(n - 3); fi; end;
A005251:=(-1+z)/(-1+2*z-z**2+z**3); # Simon Plouffe in his 1992 dissertation
a := n -> `if`(n<=1, n, hypergeom([(2-n)/3, 1-n/3, (1-n)/3], [1/2, -n+1], 27/4)):
seq(simplify(a(n)), n=0..36); # Peter Luschny, Apr 08 2018

LinearRecurrence[{2,-1,1},{0,1,1},40]  (* Harvey P. Dale, May 05 2011 *)
a[ n_]:= If[n<0, SeriesCoefficient[ -x(1-x)/(1 -x + 2x^2 -x^3), {x, 0, -n}], SeriesCoefficient[ x(1-x)/(1 -2x +x^2 -x^3), {x, 0, n}]] (* Michael Somos, Dec 13 2013 *)
a[0] = 1; a[1] = a[2] = 0; a[n_] := a[n] = a[n-2] + a[n-3]; Table[a[2 n-1], {n, 1, 20}] (* Rigoberto Florez, Oct 15 2019 *)
Table[If[n==0,0,Length[DeleteCases[Subsets[Range[n-3]],{_,x_,y_,_}/;x+2==y]]],{n,0,10}] (* Gus Wiseman, Nov 25 2019 *)

Vec((1-x)/(1-2*x+x^2-x^3)+O(x^99)) /* Charles R Greathouse IV, Nov 20 2012 */

{a(n) = if( n<0, polcoeff( -x*(1-x)/(1 -x +2*x^2 -x^3) + x*O(x^-n), -n), polcoeff( x*(1-x)/(1 -2*x +x^2 -x^3) + x*O(x^n), n))} /* Michael Somos, Dec 13 2013 */

[sum( binomial(n-j-1, 2*j) for j in (0..floor((n-1)/3)) ) for n in (0..50)] # G. C. Greubel, Apr 13 2022

a(n) = 2*a(n-1) - a(n-2) + a(n-3).
G.f.: z*(1-z)/(1 - 2*z + z^2 - z^3). - Emeric Deutsch, Sep 13 2004
23*a_n = 3*P_{2n+1} + 7*P_{2n} - 2*P_{2n-1}, where P_n are the Perrin numbers, A001608. - Don Knuth, Dec 09 2008
a(n+1) = Sum_{k=0..n} binomial(n-k, 2k). - Richard L. Ollerton, May 12 2004
From Henry Bottomley, Feb 21 2001: (Start)
a(n) = (Sum_{ja(n) = A005314(n) - A005314(n-1).
a(n) = A049853(n-1) - a(n-1).
a(n) = A005314(n) - a(n-2). (End)
Conjecture: a(n+1) + |A078065(n)| = 2*A005314(n+1). - Creighton Dement, Dec 21 2004
a(n+2) has g.f. (F_3(-x) + F_2(-x))/(F_4(-x) + F_3(-x)) = 1/(-x+1/(-x+1/(-x+1))) where F_n(x) is the n-th Fibonacci polynomial; see A011973. - Qiaochu Yuan (qchu(AT)mit.edu), Feb 19 2009
a(n) = A173022(2^(n-2) - 1) for n > 1. - Reinhard Zumkeller, Feb 07 2010
BINOMIAL transform of A176971 is a(n+1). - Michael Somos, Dec 13 2013
a(n) = hypergeom([(2-n)/3, 1-n/3, (1-n)/3], [1/2, -n+1], 27/4) for n > 1. - Peter Luschny, Apr 08 2018
G.f.: z/(1-z-z^3-z^4-z^5-...) for the compositions of n-1 avoiding 2. The g.f. for the number of compositions of n avoiding the part k is 1/(1-z-...-z^(k-1) - z^(k+1)-...). - Gregory L. Simay, Sep 09 2018
If p,q,r are the three solutions to x^3 = 2x^2 - x + 1, then a(n) = (p-1)*p^n/((p-q)*(p-r)) + (q-1)*q^n/((q-p)*(q-r)) + (r-1)*r^n/((r-p)*(r-q)). - Greg Dresden and AnXing Yang, Aug 12 2025

A025047 Number of alternating compositions, i.e., compositions with alternating increases and decreases, starting with either an increase or a decrease.

Original entry on oeis.org

1, 1, 1, 3, 4, 7, 12, 19, 29, 48, 75, 118, 186, 293, 460, 725, 1139, 1789, 2814, 4422, 6949, 10924, 17168, 26979, 42404, 66644, 104737, 164610, 258707, 406588, 639009, 1004287, 1578363, 2480606, 3898599, 6127152, 9629623, 15134213, 23785388, 37381849, 58750468

Offset: 0

David W. Wilson

nonn

Original name: Wiggly sums: number of sums adding to n in which terms alternately increase and decrease or vice versa.

			From _Joerg Arndt_, Dec 28 2012: (Start)
There are a(7)=19 such compositions of 7:
[ 1] +  [ 1 2 1 2 1 ]
[ 2] +  [ 1 2 1 3 ]
[ 3] +  [ 1 3 1 2 ]
[ 4] +  [ 1 4 2 ]
[ 5] +  [ 1 5 1 ]
[ 6] +  [ 1 6 ]
[ 7] -  [ 2 1 3 1 ]
[ 8] -  [ 2 1 4 ]
[ 9] +  [ 2 3 2 ]
[10] +  [ 2 4 1 ]
[11] +  [ 2 5 ]
[12] -  [ 3 1 2 1 ]
[13] -  [ 3 1 3 ]
[14] +  [ 3 4 ]
[15] -  [ 4 1 2 ]
[16] -  [ 4 3 ]
[17] -  [ 5 2 ]
[18] -  [ 6 1 ]
[19] 0  [ 7 ]
For A025048(7)-1=10 of these the first two parts are increasing (marked by '+'),
and for A025049(7)-1=8 the first two parts are decreasing (marked by '-').
The composition into one part is counted by both A025048 and A025049.
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..3333
Edward A. Bender and E. Rodney Canfield, Locally Restricted Compositions III. Adjacent-Part Periodic Inequalities, Electronic Journal of Combinatorics 17 (2010), #R145.

Dominated by A003242 (anti-run compositions), complement A261983.
The ascending case is A025048.
The descending case is A025049.
The version allowing pairs (x,x) is A344604.
These compositions are ranked by A345167, permutations A349051.
The complement is counted by A345192, ranked by A345168.
The version for patterns is A345194 (with twins: A344605).
A001250 counts alternating permutations, complement A348615.
A011782 counts compositions.
A032020 counts strict compositions.
A106356 counts compositions by number of maximal anti-runs.
A114901 counts compositions where each part is adjacent to an equal part.
A274174 counts compositions with equal parts contiguous.
A325534 counts separable partitions, ranked by A335433.
A325535 counts inseparable partitions, ranked by A335448.
A345164 counts alternating permutations of prime indices.
A345165 counts partitions w/o alternating permutation, ranked by A345171.
A345170 counts partitions w/ alternating permutation, ranked by A345172.
Cf. A000070, A008965, A238279, A333755, A344606, A344614, A344653, A344740, A345163, A345166, A345169.

b:= proc(n, l, t) option remember; `if`(n=0, 1, add(
      b(n-j, j, 1-t), j=`if`(t=1, 1..min(l-1, n), l+1..n)))
    end:
a:= n-> 1+add(add(b(n-j, j, i), i=0..1), j=1..n-1):
seq(a(n), n=0..40);  # Alois P. Heinz, Jan 31 2024

wigQ[y_]:=Or[Length[y]==0,Length[Split[y]]== Length[y]&&Length[Split[Sign[Differences[y]]]]==Length[y]-1];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],wigQ]],{n,0,15}] (* Gus Wiseman, Jun 17 2021 *)

D(n,f)={my(M=matrix(n,n,j,k,k>=j), s=M[,n]); for(b=1, n, f=!f; M=matrix(n,n,j,k,if(k1, M[j-k,k-1]), M[j-k,n]-M[j-k,k] ))); for(k=2, n, M[,k]+=M[,k-1]); s+=M[,n]); s~}
seq(n) = concat([1], D(n,0) + D(n,1) - vector(n,j,1)) \\ Andrew Howroyd, Jan 31 2024

a(n) = A025048(n) + A025049(n) - 1 = sum_k[A059881(n, k)] = sum_k[S(n, k) + T(n, k)] - 1 where if n>k>0 S(n, k) = sum_j[T(n - k, j)] over j>k and T(n, k) = sum_j[S(n - k, j)] over k>j (note reversal) and if n>0 S(n, n) = T(n, n) = 1; S(n, k) = A059882(n, k), T(n, k) = A059883(n, k). - Henry Bottomley, Feb 05 2001
a(n) ~ c * d^n, where d = 1.571630806607064114100138865739690782401305155950789062725..., c = 0.82222360450823867604750473815253345888526601460811483897... . - Vaclav Kotesovec, Sep 12 2014
a(n) = A344604(n) + 1 - n mod 2. - Gus Wiseman, Jun 17 2021

Better name using a comment of Franklin T. Adams-Watters by Peter Luschny, Oct 31 2021

A000213 Tribonacci numbers: a(n) = a(n-1) + a(n-2) + a(n-3) with a(0)=a(1)=a(2)=1.

Original entry on oeis.org

1, 1, 1, 3, 5, 9, 17, 31, 57, 105, 193, 355, 653, 1201, 2209, 4063, 7473, 13745, 25281, 46499, 85525, 157305, 289329, 532159, 978793, 1800281, 3311233, 6090307, 11201821, 20603361, 37895489, 69700671, 128199521, 235795681, 433695873, 797691075, 1467182629

Offset: 0

N. J. A. Sloane

The name "tribonacci number" is less well-defined than "Fibonacci number". The sequence A000073 (which begins 0, 0, 1) is probably the most important version, but the name has also been applied to A000213, A001590, and A081172. - N. J. A. Sloane, Jul 25 2024
Number of (n-1)-bit binary sequences with each one adjacent to a zero. - R. H. Hardin, Dec 24 2007
The binomial transform is A099216. The inverse binomial transform is (-1)^n*A124395(n). - R. J. Mathar, Aug 19 2008
Equals INVERT transform of (1, 0, 2, 0, 2, 0, 2, ...). a(6) = 17 = (1, 1, 1, 3, 5, 9) dot (0, 2, 0, 2, 0, 1) = (0 + 2 + 0 + 6 + 0 + 9) = 17. - Gary W. Adamson, Apr 27 2009
From John M. Campbell, May 16 2011: (Start)
Equals the number of tilings of a 2 X n grid using singletons and "S-shaped tetrominoes" (i.e., shapes of the form Polygon[{{0, 0}, {2, 0}, {2, 1}, {3, 1}, {3, 2}, {1, 2}, {1, 1}, {0, 1}}]).
Also equals the number of tilings of a 2 X n grid using singletons and "T-shaped tetrominoes" (i.e., shapes of the form Polygon[{{0, 0}, {3, 0}, {3, 1}, {2, 1}, {2, 2}, {1, 2}, {1, 1}, {0, 1}}]). (End)
Pisano period lengths: 1, 1, 13, 4, 31, 13, 48, 8, 39, 31, 110, 52, 168, 48, 403, 16, 96, 39, 360, 124, ... (differs from A106293). - R. J. Mathar, Aug 10 2012
a(n) is the number of compositions of n with no consecutive 1's. a(4) = 5 because we have: 4, 3+1, 1+3, 2+2, 1+2+1. Cf. A239791, A003242. - Geoffrey Critzer, Mar 27 2014
a(n+2) is the number of words of length n over alphabet {1,2,3} without having {11,12,22,23} as substrings. - Ran Pan, Sep 16 2015
Satisfies Benford's law [see A186190]. - N. J. A. Sloane, Feb 09 2017
a(n) is also the number of dominating sets on the (n-1)-path graph. - Eric W. Weisstein, Mar 31 2017
a(n) is also the number of maximal irredundant sets and minimal dominating sets in the (2n-3)-triangular snake graph. - Eric W. Weisstein, Jun 09 2019
a(n) is also the number of anti-palindromic compositions of n, where a composition (c(1), c(2),..., c(k)) is anti-palindromic if c(i) is not equal to c(k+1-i) whenever 1 <= i <= k/2. For instance, there are a(4) = 5 anti-palindromic compositions of 4: 4, 31, 13, 211, 112. - Jia Huang, Apr 08 2023

			G.f. = 1 + x + x^2 + 3*x^3 + 5*x^4 + 9*x^5+ 17*x^6 + 31*x^7 + 57*x^8 + ...

Kenneth Edwards, Michael A. Allen, A new combinatorial interpretation of the Fibonacci numbers squared, Part II, Fib. Q., 58:2 (2020), 169-177.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Indranil Ghosh, Table of n, a(n) for n = 0..3772 (terms 0..200 from T. D. Noe)
George E. Andrews, Matthew Just, and Greg Simay, Anti-palindromic compositions, arXiv:2102.01613 [math.CO], 2021. Also Fib. Q., 60:2 (2022), 164-176. See Table 1.
Joerg Arndt, Matters Computational (The Fxtbook), p.312
Jean-Luc Baril, Avoiding patterns in irreducible permutations, Discrete Mathematics and Theoretical Computer Science, Vol 17, No 3 (2016). See Table 4.
Jean-Luc Baril and Nathanaël Hassler, Intervals in a family of Fibonacci lattices, Univ. de Bourgogne (France, 2024). See p. 7.
B. G. Baumgart, Letter to the editor Part 1 Part 2 Part 3, Fib. Quart. 2 (1964), 260, 302.
Martin Burtscher, Igor Szczyrba and Rafał Szczyrba, Analytic Representations of the n-anacci Constants and Generalizations Thereof, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.
Kenneth Edwards and Michael A. Allen, A new combinatorial interpretation of the Fibonacci numbers squared, arXiv:1907.06517 [math.CO], 2019.
Mark Feinberg, Fibonacci-Tribonacci, Fib. Quart. 1(#3) (1963), 71-74.
Nick Hobson, Python program for this sequence
Joanna Jaszunska and Jan Okninski, Structure of Chinese algebras, Journal of Algebra, Volume 346, Issue 1, 15 November 2011, Pages 31-81.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
I. Tasoulas, K. Manes, A. Sapounakis, and P. Tsikouras, Chains with Small Intervals in the Lattice of Binary Paths, arXiv:1911.10883 [math.CO], 2019.
Eric Weisstein's World of Mathematics, Dominating Set
Eric Weisstein's World of Mathematics, Irredundant Set
Eric Weisstein's World of Mathematics, Minimal Dominating Set
Eric Weisstein's World of Mathematics, Path Graph
Eric Weisstein's World of Mathematics, Triangular Snake Graph
Eric Weisstein's World of Mathematics, Tribonacci Number
Index entries for linear recurrences with constant coefficients, signature (1,1,1).
Index entries for sequences related to Benford's law

Cf. A000073, A000288, A000322, A000383, A046735, A060455, A180735, A186190.

a:=[1,1,1];; for n in [4..45] do a[n]:=a[n-1]+a[n-2]+a[n-3]; od; a; # G. C. Greubel, Jun 09 2019

a000213 n = a000213_list !! n
a000213_list = 1 : 1 : 1 : zipWith (+) a000213_list
   (tail $ zipWith (+) a000213_list (tail a000213_list))
-- Reinhard Zumkeller, Apr 07 2012

I:=[1,1,1]; [n le 3 select I[n] else Self(n-1) + Self(n-2) + Self(n-3): n in [1..45]]; // G. C. Greubel, Jun 09 2019

K:=(1-z^2)/(1-z-z^2-z^3): Kser:=series(K, z=0, 45): seq((coeff(Kser, z, n)), n= 0..34); # Zerinvary Lajos, Nov 08 2007
A000213:=(z-1)*(1+z)/(-1+z+z**2+z**3); # Simon Plouffe in his 1992 dissertation

LinearRecurrence[{1, 1, 1}, {1, 1, 1}, 45] (* Harvey P. Dale, May 23 2011 *)
Table[RootSum[-1 - # - #^2 + #^3 &, 2 #^n - 4 #^(n + 1) + 3 #^(n + 2) &]/11, {n, 0, 45}] (* Eric W. Weisstein, Apr 10 2018 *)
CoefficientList[Series[(1-x)(1+x)/(1-x-x^2-x^3), {x, 0, 45}], x] (* Eric W. Weisstein, Apr 10 2018 *)

a(n):=sum(sum(binomial(n-2*m+1,m-i)*binomial(n-2*m+i,n-2*m), i,0,m),m,0,(n)/2); /* Vladimir Kruchinin, Dec 17 2011 */

a(n)=tn=[1,1,1;1,0,0;0,1,0]^n;tn[3,1]+tn[3,2]+tn[3,3] \\ Charles R Greathouse IV, Feb 18 2011

alst = [1, 1, 1]
[alst.append(alst[n-1] + alst[n-2] + alst[n-3]) for n in range(3, 37)]
print(alst) # Michael S. Branicky, Sep 21 2021

((1-x^2)/(1-x-x^2-x^3)).series(x, 45).coefficients(x, sparse=False) # G. C. Greubel, Jun 09 2019

G.f.: (1-x)*(1+x)/(1-x-x^2-x^3). - Ralf Stephan, Feb 11 2004
G.f.: 1 / (1 - x / (1 - 2*x^2 / (1 + x^2))). - Michael Somos, May 12 2012
a(n) = rightmost term of M^n * [1 1 1], where M is the 3 X 3 matrix [1 1 1 / 1 0 0 / 0 1 0]. M^n * [1 1 1] = [a(n+2) a(n+1) a(n)]. a(n)/a(n-1) tends to the tribonacci constant, 1.839286755...; an eigenvalue of M and a root of x^3 - x^2 - x - 1 = 0. - Gary W. Adamson, Dec 17 2004
a(n) = A001590(n+3) - A001590(n+2); a(n+1) - a(n) = 2*A000073(n); a(n) = A000073(n+3) - A000073(n+1). - Reinhard Zumkeller, May 22 2006
a(n) = A001590(n) + A001590(n+1). - Philippe Deléham, Sep 25 2006
a(n) ~ (F - 1) * T^n, where F = A086254 and T = A058265. - Charles R Greathouse IV, Nov 09 2008
a(n) = 2*a(n-1) - a(n-4), n > 3. - Gary Detlefs, Sep 13 2010
a(n) = Sum_{m=0..n/2} Sum_{i=0..m} binomial(n-2*m+1,m-i)*binomial(n-2*m+i, n-2*m). - Vladimir Kruchinin, Dec 17 2011
a(n) = 2*A008937(n-2) + 1 for n > 1. - Reinhard Zumkeller, Apr 07 2012
G.f.: 1+x/(U(0) - x) where U(k) = 1 - x^2/(1 - 1/(1 + 1/U(k+1))); (continued fraction, 3-step). - Sergei N. Gladkovskii, Nov 16 2012
G.f.: 1 + x + x^2/(G(0)-x) where G(k) = 1 - x*(2*k+1)/(1 - 1/(1 + (2*k+1)/G(k+1))); (continued fraction, 3-step). - Sergei N. Gladkovskii, Nov 17 2012
G.f.: (1+x)*(1-x)*(1 + x*(G(0)-1)/(x+1)) where G(k) = 1 + (1+x+x^2)/(1-x/(x+1/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jan 26 2013
G.f.: 1/(1+x-G(0)), where G(k) = 1 - 1/(1 - x/(x - 1/(1 + 1/(1 - x/(x + 1/G(k+1)))))); (continued fraction). - Sergei N. Gladkovskii, Jun 20 2013
a(n) = (-1)^n * A180735(-1-n) for all n in Z. - Michael Somos, Aug 15 2015
a(n) = Sum_{r root of x^3-x^2-x-1} r^n/(-r^2+2*r+2). - Fabian Pereyra, Nov 21 2024

Showing 1-10 of 507 results. Next

cp's OEIS Frontend

A241902 Decimal expansion of a constant related to Carlitz compositions (A003242).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A373420 Number of Carlitz compositions of n (see A003242) such that the first and last parts are equal.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Formula

A000975 a(2n) = 2*a(2n-1), a(2n+1) = 2*a(2n)+1 (also a(n) is the n-th number without consecutive equal binary digits).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

Python

Formula

Extensions

A333489 Numbers k such that the k-th composition in standard order is an anti-run (no adjacent equal parts).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A032020 Number of compositions (ordered partitions) of n into distinct parts.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A088218 Total number of leaves in all rooted ordered trees with n edges.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

A000975 a(2n) = 2a(2n-1), a(2n+1) = 2a(2n)+1 (also a(n) is the n-th number without consecutive equal binary digits).