A002452 -id:A002452 - cp's OEIS frontend

A000225 a(n) = 2^n - 1. (Sometimes called Mersenne numbers, although that name is usually reserved for A001348.)

0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, 16777215, 33554431, 67108863, 134217727, 268435455, 536870911, 1073741823, 2147483647, 4294967295, 8589934591

Offset: 0

N. J. A. Sloane

This is the Gaussian binomial coefficient [n,1] for q=2.
Number of rank-1 matroids over S_n.
Numbers k such that the k-th central binomial coefficient is odd: A001405(k) mod 2 = 1. - Labos Elemer, Mar 12 2003
This gives the (zero-based) positions of odd terms in the following convolution sequences: A000108, A007460, A007461, A007463, A007464, A061922.
Also solutions (with minimum number of moves) for the problem of Benares Temple, i.e., three diamond needles with n discs ordered by decreasing size on the first needle to place in the same order on the third one, without ever moving more than one disc at a time and without ever placing one disc at the top of a smaller one. - Xavier Acloque, Oct 18 2003
a(0) = 0, a(1) = 1; a(n) = smallest number such that a(n)-a(m) == 0 (mod (n-m+1)), for all m. - Amarnath Murthy, Oct 23 2003
Binomial transform of [1, 1/2, 1/3, ...] = [1/1, 3/2, 7/3, ...]; (2^n - 1)/n, n=1,2,3, ... - Gary W. Adamson, Apr 28 2005
Numbers whose binary representation is 111...1. E.g., the 7th term is (2^7) - 1 = 127 = 1111111 (in base 2). - Alexandre Wajnberg, Jun 08 2005
Number of nonempty subsets of a set with n elements. - Michael Somos, Sep 03 2006
For n >= 2, a(n) is the least Fibonacci n-step number that is not a power of 2. - Rick L. Shepherd, Nov 19 2007
Let P(A) be the power set of an n-element set A. Then a(n+1) = the number of pairs of elements {x,y} of P(A) for which x and y are disjoint and for which either x is a subset of y or y is a subset of x. - Ross La Haye, Jan 10 2008
A simpler way to state this is that it is the number of pairs (x,y) where at least one of x and y is the empty set. - Franklin T. Adams-Watters, Oct 28 2011
2^n-1 is the sum of the elements in a Pascal triangle of depth n. - Brian Lewis (bsl04(AT)uark.edu), Feb 26 2008
Sequence generalized: a(n) = (A^n -1)/(A-1), n >= 1, A integer >= 2. This sequence has A=2; A003462 has A=3; A002450 has A=4; A003463 has A=5; A003464 has A=6; A023000 has A=7; A023001 has A=8; A002452 has A=9; A002275 has A=10; A016123 has A=11; A016125 has A=12; A091030 has A=13; A135519 has A=14; A135518 has A=15; A131865 has A=16; A091045 has A=17; A064108 has A=20. - Ctibor O. Zizka, Mar 03 2008
a(n) is also a Mersenne prime A000668 when n is a prime number in A000043. - Omar E. Pol, Aug 31 2008
a(n) is also a Mersenne number A001348 when n is prime. - Omar E. Pol, Sep 05 2008
With offset 1, = row sums of triangle A144081; and INVERT transform of A009545 starting with offset 1; where A009545 = expansion of sin(x)*exp(x). - Gary W. Adamson, Sep 10 2008
Numbers n such that A000120(n)/A070939(n) = 1. - Ctibor O. Zizka, Oct 15 2008
For n > 0, sequence is equal to partial sums of A000079; a(n) = A000203(A000079(n-1)). - Lekraj Beedassy, May 02 2009
Starting with offset 1 = the Jacobsthal sequence, A001045, (1, 1, 3, 5, 11, 21, ...) convolved with (1, 2, 2, 2, ...). - Gary W. Adamson, May 23 2009
Numbers n such that n=2*phi(n+1)-1. - Farideh Firoozbakht, Jul 23 2009
a(n) = (a(n-1)+1)-th odd numbers = A005408(a(n-1)) for n >= 1. - Jaroslav Krizek, Sep 11 2009
Partial sums of a(n) for n >= 0 are A000295(n+1). Partial sums of a(n) for n >= 1 are A000295(n+1) and A130103(n+1). a(n) = A006127(n) - (n+1). - Jaroslav Krizek, Oct 16 2009
If n is even a(n) mod 3 = 0. This follows from the congruences 2^(2k) - 1 ~ 2*2*...*2 - 1 ~ 4*4*...*4 - 1 ~ 1*1*...*1 - 1 ~ 0 (mod 3). (Note that 2*2*...*2 has an even number of terms.) - Washington Bomfim, Oct 31 2009
Let A be the Hessenberg matrix of order n, defined by: A[1,j]=1, A[i,i]:=2,(i>1), A[i,i-1]=-1, and A[i,j]=0 otherwise. Then, for n >= 1, a(n)=det(A). - Milan Janjic, Jan 26 2010
This is the sequence A(0,1;1,2;2) = A(0,1;3,-2;0) 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
a(n) = S(n+1,2), a Stirling number of the second kind. See the example below. - Dennis P. Walsh, Mar 29 2011
Entries of row a(n) in Pascal's triangle are all odd, while entries of row a(n)-1 have alternating parities of the form odd, even, odd, even, ..., odd.
Define the bar operation as an operation on signed permutations that flips the sign of each entry. Then a(n+1) is the number of signed permutations of length 2n that are equal to the bar of their reverse-complements and avoid the set of patterns {(-2,-1), (-1,+2), (+2,+1)}.  (See the Hardt and Troyka reference.) - Justin M. Troyka, Aug 13 2011
A159780(a(n)) = n and A159780(m) < n for m < a(n). - Reinhard Zumkeller, Oct 21 2011
This sequence is also the number of proper subsets of a set with n elements. - Mohammad K. Azarian, Oct 27 2011
a(n) is the number k such that the number of iterations of the map k -> (3k +1)/2 == 1 (mod 2) until reaching (3k +1)/2 == 0 (mod 2) equals n. (see the Collatz problem). - Michel Lagneau, Jan 18 2012
For integers a, b, denote by a<+>b the least c >= a such that Hd(a,c) = b (note that, generally speaking, a<+>b differs from b<+>a). Then a(n+1)=a(n)<+>1. Thus this sequence is the Hamming analog of nonnegative integers. - Vladimir Shevelev, Feb 13 2012
Pisano period lengths: 1, 1, 2, 1, 4, 2, 3, 1, 6, 4, 10, 2, 12, 3, 4, 1, 8, 6, 18, 4, ... apparently A007733. - R. J. Mathar, Aug 10 2012
Start with n. Each n generates a sublist {n-1,n-2,...,1}. Each element of each sublist also generates a sublist. Take the sum of all. E.g., 3->{2,1} and 2->{1}, so a(3)=3+2+1+1=7. - Jon Perry, Sep 02 2012
This is the Lucas U(P=3,Q=2) sequence. - R. J. Mathar, Oct 24 2012
The Mersenne numbers >= 7 are all Brazilian numbers, as repunits in base two. See Proposition 1 & 5.2 in Links: "Les nombres brésiliens". - Bernard Schott, Dec 26 2012
Number of line segments after n-th stage in the H tree. - Omar E. Pol, Feb 16 2013
Row sums of triangle in A162741. - Reinhard Zumkeller, Jul 16 2013
a(n) is the highest power of 2 such that 2^a(n) divides (2^n)!. - Ivan N. Ianakiev, Aug 17 2013
In computer programming, these are the only unsigned numbers such that k&(k+1)=0, where & is the bitwise AND operator and numbers are expressed in binary. - Stanislav Sykora, Nov 29 2013
Minimal number of moves needed to interchange n frogs in the frogs problem (see for example the NRICH 1246 link or the Britton link below). - N. J. A. Sloane, Jan 04 2014
a(n) !== 4 (mod 5); a(n) !== 10 (mod 11); a(n) !== 2, 4, 5, 6 (mod 7). - Carmine Suriano, Apr 06 2014
After 0, antidiagonal sums of the array formed by partial sums of integers (1, 2, 3, 4, ...). - Luciano Ancora, Apr 24 2015
a(n+1) equals the number of ternary words of length n avoiding 01,02. - Milan Janjic, Dec 16 2015
With offset 0 and another initial 0, the n-th term of 0, 0, 1, 3, 7, 15, ... is the number of commas required in the fully-expanded von Neumann definition of the ordinal number n. For example, 4 := {0, 1, 2, 3} := {{}, {{}}, {{}, {{}}}, {{}, {{}}, {{}, {{}}}}}, which uses seven commas. Also, for n>0, a(n) is the total number of symbols required in the fully-expanded von Neumann definition of ordinal n - 1, where a single symbol (as usual) is always used to represent the empty set and spaces are ignored. E.g., a(5) = 31, the total such symbols for the ordinal 4. - Rick L. Shepherd, May 07 2016
With the quantum integers defined by [n+1]A001045%20are%20given%20by%20q%20=%20i%20*%20sqrt(2)%20for%20i%5E2%20=%20-1.%20Cf.%20A239473.%20-%20_Tom%20Copeland">q = (q^(n+1) - q^(-n-1)) / (q - q^(-1)), the Mersenne numbers are a(n+1) = q^n [n+1]_q with q = sqrt(2), whereas the signed Jacobsthal numbers A001045 are given by q = i * sqrt(2) for i^2 = -1. Cf. A239473. - _Tom Copeland, Sep 05 2016
For n>1: numbers n such that n - 1 divides sigma(n + 1). - Juri-Stepan Gerasimov, Oct 08 2016
This is also the second column of the Stirling2 triangle A008277 (see also A048993). - Wolfdieter Lang, Feb 21 2017
Except for the initial terms, the decimal representation of the x-axis of the n-th stage of growth of the two-dimensional cellular automaton defined by "Rule 659", "Rule 721" and "Rule 734", based on the 5-celled von Neumann neighborhood initialized with a single on cell. - Robert Price, Mar 14 2017
a(n), n > 1, is the number of maximal subsemigroups of the monoid of order-preserving partial injective mappings on a set with n elements. - James Mitchell and Wilf A. Wilson, Jul 21 2017
Also the number of independent vertex sets and vertex covers in the complete bipartite graph K_{n-1,n-1}. - Eric W. Weisstein, Sep 21 2017
Sum_{k=0..n} p^k is the determinant of n X n matrix M_(i, j) = binomial(i + j - 1, j)*p + binomial(i+j-1, i), in this case p=2 (empirical observation). - Tony Foster III, May 11 2019
The rational numbers r(n) = a(n+1)/2^(n+1) = a(n+1)/A000079(n+1) appear also as root of the n-th iteration f^{[n]}(c; x) = 2^(n+1)*x - a(n+1)*c of f(c; x) = f^{[0]}(c; x) = 2*x - c as r(n)*c. This entry is motivated by a riddle of Johann Peter Hebel (1760 - 1826): Erstes Rechnungsexempel(Ein merkwürdiges Rechnungs-Exempel) from 1803, with c = 24 and n = 2, leading to the root r(2)*24 = 21 as solution. See the link and reference. For the second problem, also involving the present sequence, see a comment in A130330. - Wolfdieter Lang, Oct 28 2019
a(n) is the sum of the smallest elements of all subsets of {1,2,..,n} that contain n. For example, a(3)=7; the subsets of {1,2,3} that contain 3 are {3}, {1,3}, {2,3}, {1,2,3}, and the sum of smallest elements is 7. - Enrique Navarrete, Aug 21 2020
a(n-1) is the number of nonempty subsets of {1,2,..,n} which don't have an element that is the size of the set. For example, for n = 4, a(3) = 7 and the subsets are {2}, {3}, {4}, {1,3}, {1,4}, {3,4}, {1,2,4}. - Enrique Navarrete, Nov 21 2020
From Eric W. Weisstein, Sep 04 2021: (Start)
Also the number of dominating sets in the complete graph K_n.
Also the number of minimum dominating sets in the n-helm graph for n >= 3. (End)
Conjecture: except for a(2)=3, numbers m such that 2^(m+1) - 2^j - 2^k - 1 is composite for all 0 <= j < k <= m. - Chai Wah Wu, Sep 08 2021
a(n) is the number of three-in-a-rows passing through a corner cell in n-dimensional tic-tac-toe. - Ben Orlin, Mar 15 2022
From Vladimir Pletser, Jan 27 2023: (Start)
a(n) == 1 (mod 30) for n == 1 (mod 4);
a(n) == 7 (mod 120) for n == 3 (mod 4);
(a(n) - 1)/30 = (a(n+2) - 7)/120 for n odd;
(a(n) - 1)/30 = (a(n+2) - 7)/120 = A131865(m) for n == 1 (mod 4) and m >= 0 with A131865(0) = 0. (End)
a(n) is the number of n-digit numbers whose smallest decimal digit is 8. - Stefano Spezia, Nov 15 2023
Also, number of nodes in a perfect binary tree of height n-1, or: number of squares (or triangles) after the n-th step of the construction of a Pythagorean tree: Start with a segment. At each step, construct squares having the most recent segment(s) as base, and isosceles right triangles having the opposite side of the squares as hypotenuse ("on top" of each square). The legs of these triangles will serve as the segments which are the bases of the squares in the next step. - M. F. Hasler, Mar 11 2024
a(n) is the length of the longest path in the n-dimensional hypercube. - Christian Barrientos, Apr 13 2024
a(n) is the diameter of the n-Hanoi graph.  Equivalently, a(n) is the largest minimum number of moves between any two states of the Towers of Hanoi problem (aka problem of Benares Temple described above). - Allan Bickle, Aug 09 2024

			For n=3, a(3)=S(4,2)=7, a Stirling number of the second kind, since there are 7 ways to partition {a,b,c,d} into 2 nonempty subsets, namely,
  {a}U{b,c,d}, {b}U{a,c,d}, {c}U{a,b,d}, {d}U{a,b,c}, {a,b}U{c,d}, {a,c}U{b,d}, and {a,d}U{b,c}. - _Dennis P. Walsh_, Mar 29 2011
From _Justin M. Troyka_, Aug 13 2011: (Start)
Since a(3) = 7, there are 7 signed permutations of 4 that are equal to the bar of their reverse-complements and avoid {(-2,-1), (-1,+2), (+2,+1)}. These are:
  (+1,+2,-3,-4),
  (+1,+3,-2,-4),
  (+1,-3,+2,-4),
  (+2,+4,-1,-3),
  (+3,+4,-1,-2),
  (-3,+1,-4,+2),
  (-3,-4,+1,+2). (End)
G.f. = x + 3*x^2 + 7*x^3 + 15*x^4 + 31*x^5 + 63*x^6 + 127*x^7 + ...
For the Towers of Hanoi problem with 2 disks, the moves are as follows, so a(2) = 3.
12|_|_ -> 2|1|_ -> _|1|2 -> _|_|12  - _Allan Bickle_, Aug 07 2024

P. Bachmann, Niedere Zahlentheorie (1902, 1910), reprinted Chelsea, NY, 1968, vol. 2, p. 75.
Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, Fifth Edition, Addison-Wesley, 2004, p. 134.
Jan Gullberg, Mathematics from the Birth of Numbers, W. W. Norton & Co., NY & London, 1997, §3.2 Prime Numbers, p. 79.
Johann Peter Hebel, Gesammelte Werke in sechs Bänden, Herausgeber: Jan Knopf, Franz Littmann und Hansgeorg Schmidt-Bergmann unter Mitarbeit von Ester Stern, Wallstein Verlag, 2019. Band 3, S. 20-21, Loesung, S. 36-37. See also the link below.
Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See pp. 46, 60, 75-83.
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).
James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, page 141.
D. Wells, The Penguin Dictionary of Curious and Interesting Numbers, "Tower of Hanoi", Penguin Books, 1987, pp. 112-113.

Franklin T. Adams-Watters, Table of n, a(n) for n = 0..1000
Omran Ahmadi and Robert Granger, An efficient deterministic test for Kloosterman sum zeros, Math. Comp. 83 (2014), 347-363, arXiv:1104.3882 [math.NT], 2011-2012. See 1st and 2nd column of Table 1 p. 9.
Feryal Alayont and Evan Henning, Edge Covers of Caterpillars, Cycles with Pendants, and Spider Graphs, J. Int. Seq. (2023) Vol. 26, Art. 23.9.4.
Anonymous, The Tower of Hanoi
M. Baake, F. Gahler and U. Grimm, Examples of substitution systems and their factors, arXiv:1211.5466 [math.DS], 2012-2013.
Michael Baake, Franz Gähler, and Uwe Grimm, Examples of Substitution Systems and Their Factors, Journal of Integer Sequences, Vol. 16 (2013), #13.2.14.
J.-L. Baril, Classical sequences revisited with permutations avoiding dotted pattern, Electronic Journal of Combinatorics, 18 (2011), #P178.
Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.
Jonathan Beagley and Lara Pudwell, Colorful Tilings and Permutations, Journal of Integer Sequences, Vol. 24 (2021), Article 21.10.4.
J. Bernheiden, Mersennesche Zahlen, (Text in German) [Wayback Machine cached version].
Michael Boardman, The Egg-Drop Numbers, Mathematics Magazine, 77 (2004), 368-372.
R. P. Brent and H. J. J. te Riele, Factorizations of a^n +- 1, 13 <= a < 100, CWI Report 9212, 1992 [Wayback Machine cached version].
R. P. Brent, P. L. Montgomery and H. J. J. te Riele, Factorizations of a^n +- 1, 13 <= a < 100: Update 2
R. P. Brent, P. L. Montgomery and H. J. J. te Riele, Factorizations Of Cunningham Numbers With Bases 13 To 99. Millennium Edition [BROKEN LINK]
R. P. Brent, P. L. Montgomery and H. J. J. te Riele, Factorizations of Cunningham numbers with bases 13 to 99: Millennium edition
R. P. Brent and H. J. J. te Riele, Factorizations of a^n +- 1, 13 <= a < 100
John Brillhart et al., Cunningham Project [Factorizations of b^n +- 1, b = 2, 3, 5, 6, 7, 10, 11, 12 up to high powers] [Subscription required].
Jill Britton, The Tower of Hanoi [Video file, Wayback Machine cached version].
Jill Britton, The Frog Puzzle [Wayback Machine cached version].
C. K. Caldwell, The Prime Glossary, Mersenne number
Naiomi T. Cameron and Asamoah Nkwanta, On Some (Pseudo) Involutions in the Riordan Group, Journal of Integer Sequences, Vol. 8 (2005), Article 05.3.7.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
P. Catarino, H. Campos, and P. Vasco, On the Mersenne sequence, Annales Mathematicae et Informaticae, 46 (2016) pp. 37-53.
Robert George Cowell, A unifying framework for the modelling and analysis of STR DNA samples arising in forensic casework, arXiv:1802.09863 [stat.AP], 2018.
F. Javier de Vega, An extension of Furstenberg's theorem of the infinitude of primes, arXiv:2003.13378 [math.NT], 2020.
W. M. B. Dukes, On the number of matroids on a finite set, arXiv:math/0411557 [math.CO], 2004.
James East, Jitender Kumar, James D. Mitchell, and Wilf A. Wilson, Maximal subsemigroups of finite transformation and partition monoids, arXiv:1706.04967 [math.GR], 2017. [_James Mitchell_ and _Wilf A. Wilson_, Jul 21 2017]
W. Edgington, Mersenne Page [BROKEN LINK]
David Eppstein, Making Change in 2048, arXiv:1804.07396 [cs.DM], 2018.
T. Eveilleau, Animated solution to the Tower of Hanoi problem
G. Everest et al., Primes generated by recurrence sequences, Amer. Math. Monthly, 114 (No. 5, 2007), 417-431.
G. Everest, S. Stevens, D. Tamsett and T. Ward, Primitive divisors of quadratic polynomial sequences, arXiv:math/0412079 [math.NT], 2004-2006.
G. Everest, A. J. van der Poorten, Y. Puri and T. Ward, Integer Sequences and Periodic Points, Journal of Integer Sequences, Vol. 5 (2002), Article 02.2.3.
Bakir Farhi, Summation of Certain Infinite Lucas-Related Series, J. Int. Seq., Vol. 22 (2019), Article 19.1.6.
Emmanuel Ferrand, Deformations of the Taylor Formula, Journal of Integer Sequences, Vol. 10 (2007), Article 07.1.7.
Carrie E. Finch-Smith and R. Scottfield Groth, Arbitrarily Long Sequences of Sierpiński Numbers that are the Sum of a Sierpiński Number and a Mersenne Number, Journal of Integer Sequences, Vol. 28 (2025), Article 25.2.4. See p. 22.
Robert Frontczak and Taras Goy, Mersenne-Horadam identities using generating functions, Carpathian Mathematical Publications, Vol. 12, no. 1, (2020), 34-45.
Robert Granger, On the Enumeration of Irreducible Polynomials over GF(q) with Prescribed Coefficients, arXiv:1610.06878 [math.AG], 2016. See 1st and 2nd column of Table 1 p. 13.
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 p. 17.
Taras Goy, On new identities for Mersenne numbers, Applied Mathematics E-Notes, 18 (2018), 100-105.
R. K. Guy, Letter to N. J. A. Sloane
A. Hardt and J. M. Troyka, Restricted symmetric signed permutations, Pure Mathematics and Applications, Vol. 23 (No. 3, 2012), pp. 179--217.
A. Hardt and J. M. Troyka, Slides (associated with the Hardt and Troyka reference above).
Johann Peter Hebel, Erstes Rechnungsexempel, 1803; Solution: Auflösung des ersten Rechnungsexempels und ein zweites, 1804.
A. M. Hinz, S. Klavžar, U. Milutinović, and C. Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See page 11. Book's website
A. Hinz, S. Klavzar, and S. Zemljic, A survey and classification of Sierpinski-type graphs, Discrete Applied Mathematics 217 3 (2017), 565-600.
Andreas M. Hinz and Paul K. Stockmeyer, Precious Metal Sequences and Sierpinski-Type Graphs, J. Integer Seq., Vol 25 (2022), Article 22.4.8.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 138, 345, 371, and 880
Jiří Klaška, Jakóbczyk's Hypothesis on Mersenne Numbers and Generalizations of Skula's Theorem, J. Int. Seq., Vol. 26 (2023), Article 23.3.8.
Ross La Haye, Binary Relations on the Power Set of an n-Element Set, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.
Wolfdieter Lang, Notes on certain inhomogeneous three term recurrences.
J. Loy, The Tower of Hanoi
Edouard Lucas, The Theory of Simply Periodic Numerical Functions, Fibonacci Association, 1969. English translation of article "Théorie des Fonctions Numériques Simplement Périodiques, I", Amer. J. Math., 1 (1878), 184-240.
Mathforum, Tower of Hanoi
Mathforum, Problem of the Week, The Tower of Hanoi Puzzle
Donatella Merlini and Massimo Nocentini, Algebraic Generating Functions for Languages Avoiding Riordan Patterns, Journal of Integer Sequences, Vol. 21 (2018), Article 18.1.3.
R. Mestrovic, Euclid's theorem on the infinitude of primes: a historical survey of its proofs (300 BC--2012) and another new proof, arXiv preprint arXiv:1202.3670 [math.HO], 2012. - From _N. J. A. Sloane_, Jun 13 2012
N. Moreira and R. Reis, On the Density of Languages Representing Finite Set Partitions, Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.8.
N. Neumarker, Realizability of Integer Sequences as Differences of Fixed Point Count Sequences, JIS 12 (2009) 09.4.5, Example 11.
NRICH 1246, Frogs
Ahmet Öteleş, Bipartite Graphs Associated with Pell, Mersenne and Perrin Numbers, An. Şt. Univ. Ovidius Constantą, (2019) Vol. 27, Issue 2, 109-120.
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
Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
D. C. Santos, E. A. Costa, and P. M. M. C. Catarino, On Gersenne Sequence: A Study of One Family in the Horadam-Type Sequence, Axioms 14, 203, (2025). See pp. 1, 4.
Bernard Schott, Les nombres brésiliens, Reprinted from Quadrature, no. 76, avril-juin 2010, pages 30-38, included here with permission from the editors of Quadrature.
R. R. Snapp, The Tower of Hanoi.
Amelia Carolina Sparavigna, On the generalized sums of Mersenne, Fermat, Cullen and Woodall Numbers, Politecnico di Torino (Italy, 2019).
Amelia Carolina Sparavigna, Composition Operations of Generalized Entropies Applied to the Study of Numbers, International Journal of Sciences (2019) Vol. 8, No. 4, 87-92.
Amelia Carolina Sparavigna, The groupoids of Mersenne, Fermat, Cullen, Woodall and other Numbers and their representations by means of integer sequences, Politecnico di Torino, Italy (2019), [math.NT].
Amelia Carolina Sparavigna, Some Groupoids and their Representations by Means of Integer Sequences, International Journal of Sciences (2019) Vol. 8, No. 10.
Thesaurus.maths.org, Mersenne Number
Thinks.com, Tower of Hanoi, A classic puzzle game
A. Umar, Combinatorial Results for Semigroups of Orientation-Preserving Partial Transformations, Journal of Integer Sequences, 14 (2011), #11.7.5.
Eric Weisstein's World of Mathematics, Coin Tossing, Digit, Repunit, Rule 222, Run, and Tower of Hanoi
Eric Weisstein's World of Mathematics, Complete Bipartite Graph
Eric Weisstein's World of Mathematics, Complete Graph
Eric Weisstein's World of Mathematics, Dominating Set
Eric Weisstein's World of Mathematics, Helm Graph
Eric Weisstein's World of Mathematics, Independent Vertex Set
Eric Weisstein's World of Mathematics, Mersenne Number
Eric Weisstein's World of Mathematics, Minimum Dominating Set
Eric Weisstein's World of Mathematics, Vertex Cover
Wikipedia, H tree, Lucas sequence, and Tower of Hanoi
K. K. Wong, Tower Of Hanoi:Online Game
K. Zsigmondy, Zur Theorie der Potenzreste, Monatsh. Math., 3 (1892), 265-284.
Index entries for "core" sequences
Index to divisibility sequences
Index entries for linear recurrences with constant coefficients, signature (3,-2).

Cf. A000043 (Mersenne exponents).
Cf. A000668 (Mersenne primes).
Cf. A001348 (Mersenne numbers with n prime).
Cf. A000079, A001045, A009545, A016189, A052955, A083329, A085104, A144081.
Cf. a(n)=A112492(n, 2). Rightmost column of A008969.
a(n) = A118654(n, 1) = A118654(n-1, 3), for n > 0.
Subsequence of A132781.
Smallest number whose base b sum of digits is n: this sequence (b=2), A062318 (b=3), A180516 (b=4), A181287 (b=5), A181288 (b=6), A181303 (b=7), A165804 (b=8), A140576 (b=9), A051885 (b=10).
Cf. A000203, A239473, A279396.
Cf. A008277, A048993 (columns k=2), A000918, A130330.
Cf. A000225, A029858, A058809, A375256 (Hanoi graphs).

a000225 = (subtract 1) . (2 ^)
a000225_list = iterate ((+ 1) . (* 2)) 0
-- Reinhard Zumkeller, Mar 20 2012

A000225 := n->2^n-1; [ seq(2^n-1,n=0..50) ];
A000225:=1/(2*z-1)/(z-1); # Simon Plouffe in his 1992 dissertation, sequence starting at a(1)

a[n_] := 2^n - 1; Table[a[n], {n, 0, 30}] (* Stefan Steinerberger, Mar 30 2006 *)
Array[2^# - 1 &, 50, 0] (* Joseph Biberstine (jrbibers(AT)indiana.edu), Dec 26 2006 *)
NestList[2 # + 1 &, 0, 32] (* Robert G. Wilson v, Feb 28 2011 *)
2^Range[0, 20] - 1 (* Eric W. Weisstein, Jul 17 2017 *)
LinearRecurrence[{3, -2}, {1, 3}, 20] (* Eric W. Weisstein, Sep 21 2017 *)
CoefficientList[Series[1/(1 - 3 x + 2 x^2), {x, 0, 20}], x] (* Eric W. Weisstein, Sep 21 2017 *)

A000225(n) = 2^n-1  \\ Michael B. Porter, Oct 27 2009

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

def A000225(n): return (1<Chai Wah Wu, Jul 06 2022

def isMersenne(n): return n == sum([(1 - b) << s for (s, b) in enumerate((n+1).bits())]) # Peter Luschny, Sep 01 2019

G.f.: x/((1-2*x)*(1-x)).
E.g.f.: exp(2*x) - exp(x).
E.g.f. if offset 1: ((exp(x)-1)^2)/2.
a(n) = Sum_{k=0..n-1} 2^k. - Paul Barry, May 26 2003
a(n) = a(n-1) + 2*a(n-2) + 2, a(0)=0, a(1)=1. - Paul Barry, Jun 06 2003
Let b(n) = (-1)^(n-1)*a(n). Then b(n) = Sum_{i=1..n} i!*i*Stirling2(n,i)*(-1)^(i-1). E.g.f. of b(n): (exp(x)-1)/exp(2x). - Mario Catalani (mario.catalani(AT)unito.it), Dec 19 2003
a(n+1) = 2*a(n) + 1, a(0) = 0.
a(n) = Sum_{k=1..n} binomial(n, k).
a(n) = n + Sum_{i=0..n-1} a(i); a(0) = 0. - Rick L. Shepherd, Aug 04 2004
a(n+1) = (n+1)*Sum_{k=0..n} binomial(n, k)/(k+1). - Paul Barry, Aug 06 2004
a(n+1) = Sum_{k=0..n} binomial(n+1, k+1). - Paul Barry, Aug 23 2004
Inverse binomial transform of A001047. Also U sequence of Lucas sequence L(3, 2). - Ross La Haye, Feb 07 2005
a(n) = A099393(n-1) - A020522(n-1) for n > 0. - Reinhard Zumkeller, Feb 07 2006
a(n) = A119258(n,n-1) for n > 0. - Reinhard Zumkeller, May 11 2006
a(n) = 3*a(n-1) - 2*a(n-2); a(0)=0, a(1)=1. - Lekraj Beedassy, Jun 07 2006
Sum_{n>0} 1/a(n) = 1.606695152... = A065442, see A038631. - Philippe Deléham, Jun 27 2006
Stirling_2(n-k,2) starting from n=k+1. - Artur Jasinski, Nov 18 2006
a(n) = A125118(n,1) for n > 0. - Reinhard Zumkeller, Nov 21 2006
a(n) = StirlingS2(n+1,2). - Ross La Haye, Jan 10 2008
a(n) = A024036(n)/A000051(n). - Reinhard Zumkeller, Feb 14 2009
a(n) = A024088(n)/A001576(n). -Reinhard Zumkeller, Feb 15 2009
a(2*n) = a(n)*A000051(n); a(n) = A173787(n,0). - Reinhard Zumkeller, Feb 28 2010
For n > 0: A179857(a(n)) = A024036(n) and A179857(m) < A024036(n) for m < a(n). - Reinhard Zumkeller, Jul 31 2010
From Enrique Pérez Herrero, Aug 21 2010: (Start)
a(n) = J_n(2), where J_n is the n-th Jordan Totient function: (A007434, is J_2).
a(n) = Sum_{d|2} d^n*mu(2/d). (End)
A036987(a(n)) = 1. - Reinhard Zumkeller, Mar 06 2012
a(n+1) = A044432(n) + A182028(n). - Reinhard Zumkeller, Apr 07 2012
a(n) = A007283(n)/3 - 1. - Martin Ettl, Nov 11 2012
a(n+1) = A001317(n) + A219843(n); A219843(a(n)) = 0. - Reinhard Zumkeller, Nov 30 2012
a(n) = det(|s(i+2,j+1)|, 1 <= i,j <= n-1), where s(n,k) are Stirling numbers of the first kind. - Mircea Merca, Apr 06 2013
G.f.: Q(0), 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 22 2013
E.g.f.: Q(0), where Q(k) = 1 - 1/(2^k - 2*x*4^k/(2*x*2^k - (k+1)/Q(k+1))); (continued fraction).
G.f.: Q(0), where Q(k) = 1 - 1/(2^k - 2*x*4^k/(2*x*2^k - 1/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 23 2013
a(n) = A000203(2^(n-1)), n >= 1. - Ivan N. Ianakiev, Aug 17 2013
a(n) = Sum_{t_1+2*t_2+...+n*t_n=n} n*multinomial(t_1+t_2 +...+t_n,t_1,t_2,...,t_n)/(t_1+t_2 +...+t_n). - Mircea Merca, Dec 06 2013
a(0) = 0; a(n) = a(n-1) + 2^(n-1) for n >= 1. - Fred Daniel Kline, Feb 09 2014
a(n) = A125128(n) - A000325(n) + 1. - Miquel Cerda, Aug 07 2016
From Ilya Gutkovskiy, Aug 07 2016: (Start)
Binomial transform of A057427.
Sum_{n>=0} a(n)/n! = A090142. (End)
a(n) = A000918(n) + 1. - Miquel Cerda, Aug 09 2016
a(n+1) = (A095151(n+1) - A125128(n))/2. - Miquel Cerda, Aug 12 2016
a(n) = (A079583(n) - A000325(n+1))/2. - Miquel Cerda, Aug 15 2016
Convolution of binomial coefficient C(n,a(k)) with itself is C(n,a(k+1)) for all k >= 3. - Anton Zakharov, Sep 05 2016
a(n) = (A083706(n-1) + A000325(n))/2. - Miquel Cerda, Sep 30 2016
a(n) = A005803(n) + A005408(n-1). - Miquel Cerda, Nov 25 2016
a(n) = A279396(n+2,2). - Wolfdieter Lang, Jan 10 2017
a(n) = n + Sum_{j=1..n-1} (n-j)*2^(j-1). See a Jun 14 2017 formula for A000918(n+1) with an interpretation. - Wolfdieter Lang, Jun 14 2017
a(n) = Sum_{k=0..n-1} Sum_{i=0..n-1} C(k,i). - Wesley Ivan Hurt, Sep 21 2017
a(n+m) = a(n)*a(m) + a(n) + a(m). - Yuchun Ji, Jul 27 2018
a(n+m) = a(n+1)*a(m) - 2*a(n)*a(m-1). - Taras Goy, Dec 23 2018
a(n+1) is the determinant of n X n matrix M_(i, j) = binomial(i + j - 1, j)*2 + binomial(i+j-1, i) (empirical observation). - Tony Foster III, May 11 2019
From Peter Bala, Jun 27 2025: (Start)
For n >= 1, a(3*n)/a(n) = A001576(n), a(4*n)/a(n) = A034496(n), a(5*n)/a(n) = A020514(n) a(6*n)/a(n) = A034665(n), a(7*n)/a(n) = A020516(n) and a(8*n)/a(n) = A034674(n).
exp( Sum_{n >= 1} a(2*n)/a(n)*x^n/n ) = Sum_{n >= 0} a(n+1)*x^n.
Modulo differences in offsets, exp( Sum_{n >= 1} a(k*n)/a(n)*x^n/n ) is the o.g.f. of A006095 (k = 3), A006096 (k = 4), A006097 (k = 5), A006110 (k = 6), A022189 (k = 7), A022190 (k = 8), A022191 (k = 9) and A022192 (k = 10).
The following are all examples of telescoping series:
Sum_{n >= 1} 2^n/(a(n)*a(n+1)) = 1; Sum_{n >= 1} 2^n/(a(n)*a(n+1)*a(n+2)) = 1/9.
In general, for k >= 1, Sum_{n >= 1} 2^n/(a(n)*a(n+1)*...*a(n+k)) = 1/(a(1)*a(2)*...*a(k)*a(k)).
Sum_{n >= 1} 2^n/(a(n)*a(n+2)) = 4/9, since 2^n/(a(n)*a(n+2)) = b(n) - b(n+1), where b(n) = (2/3)*(3*2^(n-1) - 1)/((2^(n+1) - 1)*(2^n - 1)).
Sum_{n >= 1} (-2)^n/(a(n)*a(n+2)) = -2/9, since (-2)^n/(a(n)*a(n+2)) = c(n) - c(n+1), where c(n) = (1/3)*(-2)^n/((2^(n+1) - 1)*(2^n - 1)).
Sum_{n >= 1} 2^n/(a(n)*a(n+4)) = 18/175, since 2^n/(a(n)*a(n+4)) = d(n) - d(n+1), where d(n) = (120*8^n - 140*4^n + 45*2^n - 4)/(15*(2^n - 1)*(2^(n+1) - 1)*(2^(n+2) - 1)*(2^(n+3) - 1)).
Sum_{n >= 1} (-2)^n/(a(n)*a(n+4)) = -26/525, since (-2)^n/(a(n)*a(n+4)) = e(n) - e(n+1), where e(n) = (-1)^n*(40*8^n - 24*4^n + 5*2^n)/(15*(2^n - 1)*(2^(n+1) - 1)*(2^(n+2) - 1)*(2^(n+3) - 1)). (End)

Name partially edited by Eric W. Weisstein, Sep 04 2021

A003463 a(n) = (5^n - 1)/4.

Original entry on oeis.org

0, 1, 6, 31, 156, 781, 3906, 19531, 97656, 488281, 2441406, 12207031, 61035156, 305175781, 1525878906, 7629394531, 38146972656, 190734863281, 953674316406, 4768371582031, 23841857910156, 119209289550781, 596046447753906, 2980232238769531

Offset: 0

N. J. A. Sloane

5^a(n) is the highest power of 5 dividing (5^n)!. - Benoit Cloitre, Feb 04 2002
n such that A002294(n) is not divisible by 5. - Benoit Cloitre, Jan 14 2003
Without leading zero, i.e., sequence {a(n+1) = (5*5^n-1)/4}, this is the binomial transform of A003947. - Paul Barry, May 19 2003 [Edited by M. F. Hasler, Oct 31 2014]
Numbers n such that a(n) is prime are listed in A004061(n) = {3, 7, 11, 13, 47, 127, 149, 181, 619, 929, ...}. Corresponding primes a(n) are listed in A086122(n) = {31, 19531, 12207031, 305175781, 177635683940025046467781066894531, ...}. 3^(m+1) divides a(2*3^m*k). 31 divides a(3k). 13 divides a(4k). 11 divides a(5k). 71 divides a(5k). 7 divides a(6k). 19531 divides a(7k). 313 divides a(8k). 19 divides a(9k). 829 divides a(9k). 71 divides a(10k). 521 divides a(10k). 17 divides a(16k). p divides a(p-1) for all prime p except p = {2,5}. p^(m+1) divides a(p^m*(p-1)) for all prime p except p = {2,5}. p divides a((p-1)/2) for prime p = {11, 19, 29, 31, 41, 59, 61, 71, 79, 89, 101, 109, ...} = A045468, Primes congruent to {1, 4} mod 5. p divides a((p-1)/3) for prime p = {13, 67, 127, 163, 181, 199, 211, 241, 313, 337, 367, 379, 409, 457, ...}. p divides a((p-1)/4) for prime p = {101, 109, 149, 181, 269, 389, 401, 409, 449, 461, 521, 541, ...} = A107219, Primes of the form x^2+100y^2. p divides a((p-1)/5) for prime p = {31, 191, 251, 271, 601, 641, 761, 1091, 1861, ...}. p divides a((p-1)/6) for prime p = {181, 199, 211, 241, 379, 409, 631, 691, 739, 769, 1039, ...}. - Alexander Adamchuk, Jan 23 2007
Starting with 1 = convolution square of A026375: (1, 3, 11, 45, 195, 873, ...). - Gary W. Adamson, May 17 2009
Let A be the Hessenberg matrix of order n, defined by: A[1,j]=1, A[i,i]:=5, (i>1), A[i,i-1]=-1, and A[i,j]=0 otherwise. Then, for n>=1, a(n)=det(A). - Milan Janjic, Jan 27 2010
This is the sequence A(0,1;4,5;2) = A(0,1;6,-5;0) of the family of sequences [a,b:c,d:k] considered by Gary Detlefs, and treated as A(a,b;c,d;k) in the W. Lang link given below. - Wolfdieter Lang, Oct 18 2010
It is the Lucas sequence U(6,5). - Felix P. Muga II, Mar 21 2014
a(2*n+1) is the sum of the numerators and denominators of the reduced fractions 0 < b/5^n < 1 plus 1, with b < 5^n. - J. M. Bergot, Jul 24 2015
The sequence multiplied by 10 (0, 10, 60, 310, 1560, ...) is the maximum number of coins which can be decided by n weighings on 2 balances in the counterfeit coin problem with undecided under/overweight. [Halbeisen and Hungerbuhler, Disc. Math. 147 (1995) 139 Theorem 1]. - R. J. Mathar, Sep 10 2015
Order of the rank-n projective geometry PG(n-1,5) over the finite field GF(5). - Anthony Hernandez, Oct 05 2016
Number of zeros in the substitution system {0 -> 11100, 1 -> 11110} at step n from initial string "1" (1 -> 11110 -> 1111011110111101111011100 -> ...). - Ilya Gutkovskiy, Apr 10 2017
a(n) is the numerator of Sum_{k=1..n} 1/5^k, which approaches a limit of 1/4. The denominators are 5^n. In general, Sum_{k=1..n} 1/x^k approaches a limit of 1/(x-1). It is of interest to note that as x increases, so does the rate of convergence. See Crossrefs for numerators for other values of x which have the general form (x^n-1)/(x-1). - Gary Detlefs, Aug 31 2021

			Base 5...........decimal
0......................0
1......................1
11.....................6
111...................31
1111.................156
11111................781
111111..............3906
1111111............19531
11111111...........97656
111111111.........488281
1111111111.......2441406
etc. ...............etc.
- _Zerinvary Lajos_, Jan 14 2007

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, page 282.

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Joseph E. Bonin and Joseph P. S. Kung The Number of Points In A Combinatorial Geometry With No 8-Point-Line Minors, Mathematical Essays in Honor of Gian-Carlo Rota, B. Sagan and R. P. Stanley, eds., Birkhäuser, 1998, 271-284.
Carlos M. da Fonseca and Anthony G. Shannon, A formal operator involving Fermatian numbers, Notes Num. Theor. Disc. Math. (2024) Vol. 30, No. 3, 491-498.
Roger B. Eggleton, Maximal Midpoint-Free Subsets of Integers, International Journal of Combinatorics Volume 2015, Article ID 216475, 14 pages.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 374
Wolfdieter Lang, Notes on certain inhomogeneous three term recurrences.
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
Eric Weisstein's World of Mathematics, Repunit
Index entries for linear recurrences with constant coefficients, signature (6,-5).

Cf. A004061, A026375, A045468, A060458, A074479, A086122, A107219.

Cf. A003462, A002450, A003464, A023000, A023001, A002452, A002275.

[(5^n-1)/4 : n in [0..30]]; // Wesley Ivan Hurt, Sep 25 2014

a:=n->sum(5^(n-j),j=1..n): seq(a(n), n=0..23); # Zerinvary Lajos, Jan 04 2007
A003463:=1/(5*z-1)/(z-1); # Simon Plouffe in his 1992 dissertation
a[0]:=0:a[1]:=1:for n from 2 to 50 do a[n]:=6*a[n-1]-5*a[n-2]od: seq(a[n], n=0..23); # Zerinvary Lajos, Feb 21 2008

lst={}; Do[p=(5^n-1)/4; AppendTo[lst, p], {n, 0, 5!}]; lst (* Vladimir Joseph Stephan Orlovsky, Sep 29 2008 *)
Table[((5^n-1)/4),{n,0,25}] (* Vincenzo Librandi, Aug 20 2012 *)
NestList[5 # + 1 &, 0, 23] (* Bruno Berselli, Feb 06 2013 *)
LinearRecurrence[{6,-5},{0,1},30] (* Harvey P. Dale, Sep 20 2023 *)

A003463(n):=floor((5^n-1)/4)$ makelist(A003463(n),n,0,30); /* Martin Ettl, Nov 05 2012 */

a(n)=5^n\4; \\ Charles R Greathouse IV, Jul 15 2011

[lucas_number1(n,6,5) for n in range(0, 24)] # Zerinvary Lajos, Apr 22 2009

[gaussian_binomial(n,1,5) for n in range(0,24)] # Zerinvary Lajos, May 28 2009

Second binomial transform of A015518; binomial transform of A000302 (preceded by 0). - Paul Barry, Mar 28 2003
a(n) = Sum_{k=1..n} binomial(n,k)*4^(k-1). - Paul Barry, Mar 28 2003
a(n) = (-1)^n times the (i, j)-th element of M^n (for all i and j such that i is not equal to j), where M = ((1, -1, 1, -2), (-1, 1, -2, 1), (1, -2, 1, -1), (-2, 1, -1, 1)). - Simone Severini, Nov 25 2004
a(n) = A125118(n,4) for n>3. - Reinhard Zumkeller, Nov 21 2006
a(n) = ((3+sqrt(4))^n - (3-sqrt(4))^n)/4. - Al Hakanson (hawkuu(AT)gmail.com), Dec 31 2008
a(n) = 6*a(n-1) - 5*a(n-2) n>1, a(0)=0, a(1)=1. - Philippe Deléham, Jan 01 2009
From Wolfdieter Lang, Oct 18 2010: (Start)
O.g.f.: x/((1-5*x)*(1-x)).
a(n) = 4*a(n-1) + 5*a(n-2) + 2, a(0)=0, a(1)=1.
a(n) = 5*a(n-1) + a(n-2) - 5*a(n-3) = 7*a(n-1) - 11*a(n-2) + 5*a(n-3), a(0)=0, a(1)=1, a(2)=6. Observation by G. Detlefs. See the W. Lang comment and link. (End)
a(n) = 5*a(n-1) + 1 with n>0, a(0)=0. - Vincenzo Librandi, Nov 17 2010
a(n) = a(n-1) + A000351(n-1) n>0, a(0)=0. - Felix P. Muga II, Mar 19 2014
a(n) = a(n-1) + 20*a(n-2) + 5 for n > 1, a(0)=0, a(1)=1. - Felix P. Muga II, Mar 19 2014
a(n) = A060458(n)/2^(n+2), for n > 0. - R. J. Cano, Sep 25 2014
From Ilya Gutkovskiy, Oct 05 2016: (Start)
E.g.f.: (exp(4*x) - 1)*exp(x)/4.
Convolution of A000351 and A057427. (End)

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

Original entry on oeis.org

0, 1, 2, 7, 20, 61, 182, 547, 1640, 4921, 14762, 44287, 132860, 398581, 1195742, 3587227, 10761680, 32285041, 96855122, 290565367, 871696100, 2615088301, 7845264902, 23535794707, 70607384120, 211822152361, 635466457082

Offset: 0

Olivier Gérard

Number of walks of length n between any two distinct vertices of the complete graph K_4. - Paul Barry and Emeric Deutsch, Apr 01 2004
For n >= 1, a(n) is the number of integers k, 1 <= k <= 3^(n-1), whose ternary representation ends in an even number of zeros (see A007417). - Philippe Deléham, Mar 31 2004
Form the digraph with matrix A=[0,1,1,1;1,0,1,1;1,1,0,1;1,0,1,1]. A015518(n) corresponds to the (1,3) term of A^n. - Paul Barry, Oct 02 2004
The same sequence may be obtained by the following process. Starting a priori with the fraction 1/1, the denominators of fractions built according to the rule: add top and bottom to get the new bottom, add top and 4 times the bottom to get the new top. The limit of the sequence of fractions is 2. - Cino Hilliard, Sep 25 2005
(A046717(n))^2 + (2*a(n))^2 = A046717(2n). E.g., A046717(3) = 13, 2*a(3) = 14, A046717(6) = 365. 13^2 + 14^2 = 365. - Gary W. Adamson, Jun 17 2006
For n >= 2, number of ordered partitions of n-1 into parts of sizes 1 and 2 where there are two types of 1 (singletons) and three types of 2 (twins). For example, the number of possible configurations of families of n-1 male (M) and female (F) offspring considering only single births and twins, where the birth order of M/F/pair-of-twins is considered and there are three types of twins; namely, both F, both M, or one F and one M - where birth order within a pair of twins itself is disregarded. In particular, for a(3)=7, two children could be either: (1) F, then M; (2) M, then F; (3) F,F; (4) M,M; (5) F,F twins; (6) M,M twins; or (7) M,F twins (emphasizing that birth order is irrelevant here when both/all children are the same gender and when two children are within the same pair of twins). - Rick L. Shepherd, Sep 18 2004
a(n) is prime for n = {2, 3, 5, 7, 13, 23, 43, 281, 359, ...}, where only a(2) = 2 corresponds to a prime of the form (3^k - 1)/4. All prime terms, except a(2) = 2, are the primes of the form (3^k + 1)/4. Numbers k such that (3^k + 1)/4 is prime are listed in A007658. Note that all prime terms have prime indices. Prime terms are listed in A111010. - Alexander Adamchuk, Nov 19 2006
Let A be the Hessenberg matrix of order n, defined by: A[1,j]=1, A[i,i]:=-2, A[i,i-1]=-1, and A[i,j]=0 otherwise. Then, for n>=1, a(n)=charpoly(A,1). - Milan Janjic, Jan 26 2010
Select an odd size subset S from {1,2,...,n}, then select an even size subset from S. - Geoffrey Critzer, Mar 02 2010
a(n) is the number of ternary sequences of length n where the numbers of (0's, 1's) are (even, odd) respectively, and, by symmetry, the number of such sequences where those numbers are (odd, even) respectively. A122983 covers (even, even), and A081251 covers (odd, odd). - Toby Gottfried, Apr 18 2010
An elephant sequence, see A175654. For the corner squares just one A[5] vector, with decimal value 341, leads to this sequence (without the leading 0). For the central square this vector leads to the companion sequence A046717 (without the first leading 1). - Johannes W. Meijer, Aug 15 2010
Let R be the commutative algebra resulting from adjoining the elements of the Klein four-group to the integers (equivalently, K = Z[x,y,z]/{x*y - z, y*z - x, x*z - y, x^2 - 1, y^2 - 1, z^2 - 1}). Then a(n) is equal to the coefficients of x, y, and z in the expansion of (x + y + z)^n. - Joseph E. Cooper III (easonrevant(AT)gmail.com), Nov 06 2010
Pisano period lengths:  1, 2, 2, 4, 4, 2, 6, 8, 2, 4, 10, 4, 6, 6, 4, 16, 16, 2, 18, 4, ... - R. J. Mathar, Aug 10 2012
The ratio a(n+1)/a(n) converges to 3 as n approaches infinity. - Felix P. Muga II, Mar 09 2014
This is a divisibility sequence, also the values of Chebyshev polynomials, and also the number of ways of packing a 2 X n-1 rectangle with dominoes and unit squares. - R. K. Guy, Dec 16 2016
For n>0, gcd(a(n),a(n+1))=1. - Kengbo Lu, Jul 02 2020

John Derbyshire, Prime Obsession, Joseph Henry Press, April 2004, see p. 16.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
A. Abdurrahman, CM Method and Expansion of Numbers, arXiv:1909.10889 [math.NT], 2019.
Jean-Paul Allouche, Jeffrey Shallit, Zhixiong Wen, Wen Wu, and Jiemeng Zhang, Sum-free sets generated by the period-k-folding sequences and some Sturmian sequences, arXiv:1911.01687 [math.CO], 2019.
Katerina Böhmová, Cristina Dalfó, and Clemens Huemer, On cyclic Kautz digraphs, Research Report, 2015.
Garry Bowlin and Matthew G. Brin, Coloring Planar Graphs via Colored Paths in the Associahedra, arXiv preprint arXiv:1301.3984 [math.CO], 2013. - From _N. J. A. Sloane_, Feb 12 2013
AJ Bu and Doron Zeilberger, Using Symbolic Computation to Explore Generalized Dyck Paths and Their Areas, arXiv:2305.09030 [math.CO], 2023.
Ji Young Choi, A Generalization of Collatz Functions and Jacobsthal Numbers, J. Int. Seq., Vol. 21 (2018), Article 18.5.4.
Sergio Falcón, Binomial Transform of the Generalized k-Fibonacci Numbers, Communications in Mathematics and Applications (2019) Vol. 10, No. 3, 643-651.
Dale Gerdemann, Fractal generated from (2,3) recursion, YouTube Video, Dec 05 2014.
Toufik Mansour and Mark Shattuck, Pattern avoidance in flattened derangements, Disc. Math. Lett. (2025) Vol. 15, 67-74. See p. 74.
R. J. Mathar, Counting Walks on Finite Graphs, Nov 2020, Section 2.
Felix Pozon Muga II, Extending the Golden Ratio and the Binet-de Moivre Formula, March 2014.
Index entries for linear recurrences with constant coefficients, signature (2,3).
Index entries for sequences related to Chebyshev polynomials.

a(n) = A080926(n-1) + 1 = (1/3)*A054878(n+1) = (1/3)*abs(A084567(n+1)).
First differences of A033113 and A039300.
Partial sums of A046717.
The following sequences (and others) belong to the same family: A000129, A001333, A002532, A002533, A002605, A015518, A015519, A026150, A046717, A063727, A083098, A083099, A083100, A084057.
Cf. A046717.
Cf. A007658, A111010.
Cf. A001045, A078008, A097073, A115341. - Vladimir Joseph Stephan Orlovsky, Dec 11 2008
Cf. A007482, A059260.

[Round(3^n/4): n in [0..30]]; // Vincenzo Librandi, Jun 24 2011

Table[(3^n-(-1)^n)/4,{n,0,30}] (* Alexander Adamchuk, Nov 19 2006 *)

a(n):= round(3^n/4)$ /* Dimitri Papadopoulos, Nov 28 2023 */

PARI
```
a(n)=round(3^n/4)
```

for n in range(0, 20): print(int((3**n-(-1)**n)/4), end=', ') # Stefano Spezia, Nov 30 2018

Sage
```
[round(3^n/4) for n in range(0,27)]
```

G.f.: x/((1+x)*(1-3*x)).
a(n) = (3^n - (-1)^n)/4 = floor(3^n/4 + 1/2).
a(n) = 3^(n-1) - a(n-1). - Emeric Deutsch, Apr 01 2004
E.g.f.: (exp(3*x) - exp(-x))/4. Second inverse binomial transform of (5^n-1)/4, A003463. Inverse binomial transform for powers of 4, A000302 (when preceded by 0). - Paul Barry, Mar 28 2003
a(n) = Sum_{k=0..floor(n/2)} C(n, 2k+1)*2^(2k). - Paul Barry, May 14 2003
a(n) = Sum_{k=1..n} binomial(n, k)*(-1)^(n+k)*4^(k-1). - Paul Barry, Apr 02 2003
a(n+1) = Sum_{k=0..floor(n/2)} binomial(n-k, k)*2^(n-2*k)*3^k. - Paul Barry, Jul 13 2004
a(n) = U(n-1, i/sqrt(3))(-i*sqrt(3))^(n-1), i^2=-1. - Paul Barry, Nov 17 2003
G.f.: x*(1+x)^2/(1 - 6*x^2 - 8*x^3 - 3*x^4) = x(1+x)^2/characteristic polynomial(x^4*adj(K_4)(1/x)). - Paul Barry, Feb 03 2004
a(n) = sum_{k=0..3^(n-1)} A014578(k) = -(-1)^n*A014983(n) = A051068(3^(n-1)), for n > 0. - Philippe Deléham, Mar 31 2004
E.g.f.: exp(x)*sinh(2*x)/2. - Paul Barry, Oct 02 2004
a(2*n+1) = A054880(n) + 1. - M. F. Hasler, Mar 20 2008
2*a(n) + (-1)^n = A046717(n). - M. F. Hasler, Mar 20 2008
a(n) = ((1+sqrt(4))^n - (1-sqrt(4))^n)/4. - Al Hakanson (hawkuu(AT)gmail.com), Dec 31 2008
a(n) = abs(A014983(n)). - Zerinvary Lajos, May 28 2009
a(n) = round(3^n/4). - Mircea Merca, Dec 28 2010
a(n) = Sum_{k=1,3,5,...} binomial(n,k)*2^(k-1). - Geoffrey Critzer, Mar 02 2010
From Sergei N. Gladkovskii, Jul 19 2012: (Start)
G.f.: G(0)/4 where G(k)= 1 - 1/(9^k - 3*x*81^k/(3*x*9^k - 1/(1 + 1/(3*9^k - 27*x*81^k/(9*x*9^k + 1/G(k+1)))))); (continued fraction).
E.g.f.: G(0)/4 where G(k)= 1 - 1/(9^k - 3*x*81^k/(3*x*9^k - (2*k+1)/(1 + 1/(3*9^k - 27*x*81^k/(9*x*9^k + (2*k+2)/G(k+1)))))); (continued fraction).  (End)
G.f.: G(0)*x/(2*(1-x)), where G(k) = 1 + 1/(1 - x*(4*k-1)/(x*(4*k+3) - 1/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 26 2013
a(n+1) = Sum_{k = 0..n} A238801(n,k)*2^k. - Philippe Deléham, Mar 07 2014
a(n) = (-1)^(n-1)*Sum_{k=0..n-1} A135278(n-1,k)*(-4)^k = (-1)^(n-1)*Sum_{k=0..n-1} (-3)^k. Equals (-1)^(n-1)*Phi(n,-3), where Phi is the cyclotomic polynomial when n is an odd prime. (For n > 0.) - Tom Copeland, Apr 14 2014
a(n) = 2*A006342(n-1) - n mod 2 if n > 0, a(0)=0. - Yuchun Ji, Nov 30 2018
a(n) = 2*A033113(n-2) + n mod 2 if n > 0, a(0)=0. - Yuchun Ji, Aug 16 2019
a(2*k) = 2*A002452(k), a(2*k+1) = A066443(k). - Yuchun Ji, Aug 14 2019
a(n+1) = 2*Sum_{k=0..n} a(k) if n odd, and 1 + 2*Sum_{k=0..n} a(k) if n even. - Kengbo Lu, May 30 2020
a(n) = F(n) + Sum_{k=1..(n-1)} a(k)*L(n-k), for F(n) and L(n) the Fibonacci and Lucas numbers. - Kengbo Lu and Greg Dresden, Jun 05 2020
From Kengbo Lu, Jun 11 2020: (Start)
a(n) = A002605(n) + Sum_{k = 1..n-2} a(k)*A002605(n-k-1).
a(n) = A006130(n-1) + Sum_{k = 1..n-1} a(k)*A006130(n-k-1). (End)
a(2n) = Sum_{i>=0, j>=0} binomial(n-j-1,i)*binomial(n-i-1,j)* 2^(2n-2i-2j-1)* 3^(i+j). - Kengbo Lu, Jul 02 2020
a(n) = 3*a(n-1) - (-1)^n. - Dimitri Papadopoulos, Nov 28 2023
G.f.: x/((1 + x)*(1 - 3*x)) = Sum_{n >= 0} x^(n+1) * Product_{k = 1..n} (k + 3*x + 1)(1 + k*x) (a telescoping series). Cf. A007482. - Peter Bala, May 08 2024
From Peter Bala, Jun 29 2025: (Start)
For n >= 1, a(n+1) = 2^n * hypergeom([1/2 - (1/2)*n, -(1/2)*n], [-n], -3).
G.f. A(x) = x*exp(Sum_{n >= 1} a(2*n)/a(n)*x^n/n) =  x + 2*x^2 + 7*x^3 + 20*x^4 + ....
sqrt(A(x)/x) is the g.f. of A002426.
The following series telescope:
Sum_{n >= 1} (-3)^n/(a(n)*a(n+1)) = -1; Sum_{n >= 1} (-3)^n/(a(n)*a(n+1)*a(n+2)*a(n+3)) = -1/98.
In general, for k >= 0, Sum_{n >= 1} (-3)^n/(a(n)*a(n+1)*...*a(n+2*k+1)) = -1/((a(1)*a(2)*...*a(2*k+1))*a(2*k+1)).
Sum_{n >= 1} 3^n/(a(n)*a(n+1)*a(n+2)) = 1/4; Sum_{n >= 1} 3^n/(a(n)*a(n+1)*a(n+2)* a(n+3)*a(n+4)) = 1/5600.
In general, for k >= 1, Sum_{n >= 1} 3^n/(a(n)*a(n+1)*...*a(n+2*k)) = 1/((a(1)*a(2)*...*a(2*k))*a(2*k)). (End)

More terms from Emeric Deutsch, Apr 01 2004

Edited by Ralf Stephan, Aug 30 2004

A136630 Triangular array: T(n,k) counts the partitions of the set [n] into k odd sized blocks.

Original entry on oeis.org

1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 4, 0, 1, 0, 1, 0, 10, 0, 1, 0, 0, 16, 0, 20, 0, 1, 0, 1, 0, 91, 0, 35, 0, 1, 0, 0, 64, 0, 336, 0, 56, 0, 1, 0, 1, 0, 820, 0, 966, 0, 84, 0, 1, 0, 0, 256, 0, 5440, 0, 2352, 0, 120, 0, 1, 0, 1, 0, 7381, 0, 24970, 0, 5082, 0, 165, 0, 1, 0, 0, 1024, 0, 87296, 0

Offset: 0

Paul D. Hanna, Jan 14 2008

For partitions into blocks of even size see A156289.
Essentially the unsigned matrix inverse of triangle A121408.
From Peter Bala, Jul 28 2014: (Start)
Define a polynomial sequence x_(n) by setting x_(0) = 1 and for n = 1,2,... setting x_(n) = x*(x + n - 2)*(x + n - 4)*...*(x + n - 2*(n - 1)). Then this table is the triangle of connection constants for expressing the monomial polynomials x^n in terms of the basis x_(k), that is, x^n = sum {k = 0..n} T(n,k)*x_(k) for n = 0,1,2,.... An example is given below.
Let M denote the lower unit triangular array A119467 and for k = 0,1,2,... define M(k) to be the lower unit triangular block array
/I_k 0\
\ 0  M/ having the k x k identity matrix I_k as the upper left block; in particular, M(0) = M. Then the present triangle, omitting the first row and column, equals the infinite matrix product M(0)*M(1)*M(2)*.... (End)
Also the Bell transform of A000035(n+1). For the definition of the Bell transform see A264428. - Peter Luschny, Jan 27 2016

			Triangle begins:
  1;
  0, 1;
  0, 0,   1;
  0, 1,   0,    1;
  0, 0,   4,    0,    1;
  0, 1,   0,   10,    0,     1;
  0, 0,  16,    0,   20,     0,    1;
  0, 1,   0,   91,    0,    35,    0,    1;
  0, 0,  64,    0,  336,     0,   56,    0,   1;
  0, 1,   0,  820,    0,   966,    0,   84,   0,   1;
  0, 0, 256,    0, 5440,     0, 2352,    0, 120,   0, 1;
  0, 1,   0, 7381,    0, 24970,    0, 5082,   0, 165, 0, 1;
T(5,3) = 10. The ten partitions of the set [5] into 3 odd-sized blocks are
(1)(2)(345), (1)(3)(245), (1)(4)(235), (1)(5)(234), (2)(3)(145),
(2)(4)(135), (2)(5)(134), (3)(4)(125), (3)(5)(124), (4)(5)(123).
Connection constants: Row 5 = [0,1,0,10,0,1]. Hence, with the polynomial sequence x_(n) as defined in the Comments section we have x^5 = x_(1) + 10*x_(3) + x_(5) = x + 10*x*(x+1)*(x-1) + x*(x+3)*(x+1)*(x-1)*(x-3).

L. Comtet, Analyse Combinatoire, Presses Univ. de France, 1970, Vol. II, pages 61-62.
L. Comtet, Advanced Combinatorics, Reidel, 1974, pp. 225-226.

Ch. A. Charalambides, Central factorial numbers and related expansions, Fib. Quarterly, Vol. 19, No 5, Dec 1981, pp. 451-456.
Feng Qi and Peter Taylor, Series expansions for powers of sinc function and closed-form expressions for specific partial Bell polynomials, Appl. Anal. Disc. Math. (2024) Vol. 18, No. 1, 1-24. See p. 13.

Cf. A121408; A136631 (antidiagonal sums), A003724 (row sums), A136632; A002452 (column 3), A002453 (column 5); A008958 (central factorial triangle), A156289. A185690, A196776.

A136630 := proc (n, k) option remember; if k < 0 or n < k then 0 elif k = n then 1 else procname(n-2, k-2) + k^2*procname(n-2, k) end if end proc: seq(seq(A136630(n, k), k = 1 .. n), n = 1 .. 12); # Peter Bala, Jul 27 2014
# The function BellMatrix is defined in A264428.
BellMatrix(n -> (n+1) mod 2, 9); # Peter Luschny, Jan 27 2016

t[n_, k_] := Coefficient[ x^k/Product[ 1 - (2*j + k - 2*Quotient[k, 2])^2*x^2, {j, 0, k/2}] + x*O[x]^n, x, n]; Table[t[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-François Alcover, Nov 22 2013, after Pari *)
BellMatrix[f_Function, len_] := With[{t = Array[f, len, 0]}, Table[BellY[n, k, t], {n, 0, len-1}, {k, 0, len-1}]];
rows = 13;
M = BellMatrix[Mod[#+1, 2]&, rows];
Table[M[[n, k]], {n, 1, rows}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jun 23 2018, after Peter Luschny *)

{T(n,k)=polcoeff(x^k/prod(j=0,k\2,1-(2*j+k-2*(k\2))^2*x^2 +x*O(x^n)),n)}

G.f. for column k: x^k/Product_{j=0..floor(k/2)} (1 - (2*j + k-2*floor(k/2))^2 * x^2).
G.f. for column 2*k: x^(2*k)/Product_{j=0..k} (1 - (2*j)^2*x^2).
G.f. for column 2*k+1: x^(2*k+1)/Product_{j=0..k} (1 - (2*j+1)^2*x^2).
From Peter Bala, Feb 21 2011 (Start)
T(n,k) = 1/(2^k*k!)*Sum_{j = 0..k} (-1)^(k-j)*binomial(k,j)*(2*j-k)^n,
Recurrence relation T(n+2,k) = T(n,k-2) + k^2*T(n,k).
E.g.f.: F(x,z) = exp(x*sinh(z)) = Sum_{n>=0} R(n,x)*z^n/n! = 1 + x*z + x^2*z^2/2! + (x+x^3)*z^3/3! + ....
The row polynomials R(n,x) begin
R(1,x) = x
R(2,x) = x^2
R(3,x) = x+x^3.
The e.g.f. F(x,z) satisfies the partial differential equation d^2/dz^2(F) = x^2*F + x*F' + x^2*F'' where ' denotes differentiation w.r.t. x.
Hence the row polynomials satisfy the recurrence relation R(n+2,x) = x^2*R(n,x) + x*R'(n,x) + x^2*R''(n,x) with R(0,x) = 1.
The recurrence relation for T(n,k) given above follows from this.
(End)
For the corresponding triangle of ordered partitions into odd-sized blocks see A196776. Let P denote Pascal's triangle A070318 and put M = 1/2*(P-P^-1). M is A162590 (see also A131047). Then the first column of exp(t*M) lists the row polynomials for the present triangle. - Peter Bala, Oct 06 2011
Row generating polynomials equal D^n(exp(x*t)) evaluated at x = 0, where D is the operator sqrt(1+x^2)*d/dx. Cf. A196776. - Peter Bala, Dec 06 2011
From Peter Bala, Jul 28 2014: (Start)
E.g.f.: exp(t*sinh(x)) = 1 + t*x + t^2*x^2/2! + (t + t^3)*x^3/3! + ....
Hockey-stick recurrence: T(n+1,k+1) = Sum_{i = 0..floor((n-k)/2)} binomial(n,2*i)*T(n-2*i,k).
Recurrence equation for the row polynomials R(n,t):
R(n+1,t) = t*Sum_{k = 0..floor(n/2)} binomial(n,2*k)*R(n-2*k,t) with R(0,t) = 1. (End)

A006095 Gaussian binomial coefficient [n, 2] for q = 2.

Original entry on oeis.org

0, 0, 1, 7, 35, 155, 651, 2667, 10795, 43435, 174251, 698027, 2794155, 11180715, 44731051, 178940587, 715795115, 2863245995, 11453115051, 45812722347, 183251413675, 733006703275, 2932028910251, 11728119835307, 46912487729835

Offset: 0

N. J. A. Sloane

Number of 4-block coverings of an n-set where every element of the set is covered by exactly 3 blocks (if offset is 3), so a(n) = (1/4!)*(4^n-6*2^n+8). - Vladeta Jovovic, Feb 20 2001
Number of non-coprime pairs of polynomials (f,g) with binary coefficients where both f and g have degree n+1 and nonzero constant term. - Luca Mariot and Enrico Formenti, Sep 26 2016
Number of triplets found from the integers 1 to 2^n-1 by converting to binary and performing an XOR operation on the corresponding bits of each pair. Defining addition in this carryless way (0+0=1+1=0, 0+1=1+0=1), each triplet (A,B,C) has the property A+B=C, A+C=B and B+C=A. For example, n=3 gives the 7 triplets (1,2,3), (1,4,5), (1,6,7), (2,4,6), (2,5,7), (3,4,7) and (3,5,6). Each integer appears in the set of triplets 2^(n-1)-1 times, for example 3 for n=3. - Ian Duff, Oct 05 2019
Number of 2-dimensional vector subspaces of (Z_2)^n, so also number of Klein subgroups of the group (C_2)^n. - Robert FERREOL, Jul 28 2021

J. Goldman and G.-C. Rota, The number of subspaces of a vector space, pp. 75-83 of W. T. Tutte, editor, Recent Progress in Combinatorics. Academic Press, NY, 1969.
I. P. Goulden and D. M. Jackson, Combinatorial Enumeration. Wiley, NY, 1983, p. 99.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
M. Sved, Gaussians and binomials, Ars. Combinatoria, 17A (1984), 325-351.

T. D. Noe, Table of n, a(n) for n = 0..200
L. Mariot and E. Formenti, The number of coprime/non-coprime pairs of polynomials over F_2 with degree n and nonzero constant term.
Ronald Orozco López, Generating Functions of Generalized Simplicial Polytopic Numbers and (s,t)-Derivatives of Partial Theta Function, arXiv:2408.08943 [math.CO], 2024. See p. 11.
Ronald Orozco López, Simplicial d-Polytopic Numbers Defined on Generalized Fibonacci Polynomials, arXiv:2501.11490 [math.CO], 2025. See p. 6.
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. I. Solomon, C.-L. Ho and G. H. E. Duchamp, Degrees of entanglement for multipartite systems, arXiv preprint arXiv:1205.4958 [quant-ph], 2012. - _N. J. A. Sloane_, Oct 23 2012
M. Sved, Gaussians and binomials, Ars. Combinatoria, 17A (1984), 325-351. (Annotated scanned copy)
Index entries for linear recurrences with constant coefficients, signature (7,-14,8).

First differences: A006516.
Gaussian binomial coefficient [n, k] for q = 2: A000225 (k = 1), this sequence (k = 2), A006096 (k = 3), A006097 (k = 4), A006110 (k = 5), A022189 - A022195 (k = 6 thru 12).
Cf. A000392, A002275, A002452, A003462, A003463, A003464, A016123, A016125, A016208, A016256, A023000, A023001, A075113, A130324, A203235.

a:= n-> add((4^(n-1-j) - 2^(n-1-j))/2, j=0..n-1):
seq(a(n), n=0..24); # Zerinvary Lajos, Jan 04 2007
A006095 := -z^2/(z-1)/(2*z-1)/(4*z-1); # Simon Plouffe in his 1992 dissertation. [adapted to offset 0 by Peter Luschny, Jul 20 2021]
a := n -> (2^n - 2)*(2^n - 1)/6:
seq(a(n), n = 0..24); # Peter Luschny, Jul 20 2021

Join[{a=0,b=0},Table[c=6*b-8*a+1;a=b;b=c,{n,60}]] (* Vladimir Joseph Stephan Orlovsky, Feb 06 2011 *)
CoefficientList[Series[x^2/((1-x)(1-2x)(1-4x)),{x,0,30}],x] (* or *) LinearRecurrence[{7,-14,8},{0,0,1},30] (* Harvey P. Dale, Jul 22 2011 *)
(* Next, using elementary symmetric functions *)
f[k_] := 2^(k - 1); t[n_] := Table[f[k], {k, 1, n}]
a[n_] := SymmetricPolynomial[2, t[n]]
Table[a[n], {n, 2, 32}]    (* A203235 *)
Table[a[n]/2, {n, 2, 32}]  (* A006095 *)
(* Clark Kimberling, Dec 31 2011 *)
Table[QBinomial[n, 2, 2], {n, 0, 24}] (* Arkadiusz Wesolowski, Nov 12 2015 *)

a(n) = (2^n - 1)*(2^(n-1) - 1)/3 \\ Charles R Greathouse IV, Jul 25 2011

concat([0, 0], Vec(x^2/((1-x)*(1-2*x)*(1-4*x)) + O(x^50))) \\ Altug Alkan, Nov 12 2015

[gaussian_binomial(n,2,2) for n in range(0,25)] # Zerinvary Lajos, May 24 2009

G.f.: x^2/((1-x)(1-2x)(1-4x)).
a(n) = (2^n - 1)*(2^(n-1) - 1)/3 = 4^n/6 - 2^(n-1) + 1/3.
Row sums of triangle A130324. - Gary W. Adamson, May 24 2007
a(n) = Stirling2(n+1,3) + Stirling2(n+1,4). - Zerinvary Lajos, Oct 04 2007; corrected by R. J. Mathar, Mar 19 2011
a(n) = A139250(2^(n-1) - 1), n >= 1. - Omar E. Pol, Mar 03 2011
a(n) = 4*a(n-1) + 2^(n-1) - 1, n >= 2. - Vincenzo Librandi, Mar 19 2011
a(0) = 0, a(1) = 0, a(2) = 1, a(n) = 7*a(n-1) - 14*a(n-2) + 8*a(n-3). - Harvey P. Dale, Jul 22 2011
a(n) = Sum_{k=0..n-2} 2^k*C(2*n-k-2, k), n >= 2. - Johannes W. Meijer, Aug 19 2013
a(n) = Sum_{i=0..n-2, j=i..n-2} 2^{i+j} = 2^0 * (2^0 + 2^1 + ... + 2^(n-2)) + 2^1 * (2^1 + 2^2 + ... + 2^(n-2)) + ... + 2^(n-2) * 2^(n-2), n>1. - J. M. Bergot, May 08 2017
a(n) = a(n-1) + A000217(A000225(n-1)), n > 0. - Ivan N. Ianakiev, Dec 11 2017
E.g.f.: (2*exp(x)-3*exp(2*x)+exp(4*x))/6. - Paul Weisenhorn, Aug 22 2021
From Peter Bala, Jul 01 2025: (Start)
G.f. assuming an offset of 0: exp( Sum_{n >= 1} b(3*n)/b(n)*x^n/n ) = 1 + 7*x + 35*x^2 + ..., where b(n) = A000225(n) = 2^n - 1.
The following are examples of telescoping series:
Sum_{n >= 2} 2^n/a(n) = 6, follows from 1 - (1/6)*Sum_{k = 2..n} 2^k/a(k) = 1/(2^n - 1).
Sum_{n >= 2} 2^n/(a(n)*a(n+2)) = 6/49, follows from 1 - (49/6)*Sum_{k = 2..n} 2^k/(a(k)*a(k+2)) = 1/A006096(n+2);
Sum_{n >= 2} 4^n/(a(n)*a(n+2)) = 26/49, follows from 13 - (49/2)*Sum_{k = 2..n} 4^k/(a(k)*a(k+2)) = A086224(n)/A006096(n+2);
Sum_{n >= 2} 8^n/(a(n)*a(n+2)) = 129/49, follows from 43 - (49/3)*Sum_{k = 2..n} 8^k/(a(k)*a(k+2)) = A171479(n+1)/A006096(n+2). (End)

A000392 Stirling numbers of second kind S(n,3).

Original entry on oeis.org

0, 0, 0, 1, 6, 25, 90, 301, 966, 3025, 9330, 28501, 86526, 261625, 788970, 2375101, 7141686, 21457825, 64439010, 193448101, 580606446, 1742343625, 5228079450, 15686335501, 47063200806, 141197991025, 423610750290, 1270865805301

Offset: 0

N. J. A. Sloane

Number of palindromic structures using exactly three different symbols; Mobius transform: A056279. - Marks R. Nester
Number of ways of placing n labeled balls into k=3 indistinguishable boxes. - Thomas Wieder, Nov 30 2004
With two leading zeros, this is the second binomial transform of cosh(x)-1 and the binomial transform of A000225 (with extra leading zero). - Paul Barry, May 13 2003
Let [m] denote the first m positive integers. Then a(n) is the number of functions f from [n] to [n+1] that satisfy (i) f(x) > x for all x, (ii) f(x) = n+1 for exactly 3 elements and (iii) f(f(x)) = n+1 for the remaining n-3 elements of [n]. For example, a(4)=6 since there are exactly 6 functions from {1,2,3,4} to {1,2,3,4,5} such that f(x) > x, f(x) = 5 for 3 elements and f(f(x)) = 5 for the remaining element. The functions are f1 = {(1,5), (2,5), (3,4), (4,5)}, f2 = {(1,5), (2,3), (3,5), (4,5)}, f3 = {(1,5), (2,4), (3,5), (4,5)}, f4 = {(1,2), (2,5), (3,5), (4,5)}, f5 = {(1,3), (2,5), (3,5), (4,5)}, f6 = {(1,4), (2,5), (3,5), (4,5)}. - Dennis P. Walsh, Feb 20 2007
Conjecture. Let S(1)={1} and, for n > 1, let S(n) be the smallest set containing x, 2x and 3x for each element x in S(n-1). Then a(n+2) is the sum of the elements in S(n). (It is easy to prove that the number of elements in S(n) is the n-th triangular number given by A001952.) See A122554 for a sequence defined in this way. - John W. Layman, Nov 21 2007; corrected (a(n) to a(n+2) due to offset change) by Fred Daniel Kline, Oct 02 2014
Let P(A) be the power set of an n-element set A. Then a(n+1) = the number of pairs of elements {x,y} of P(A) for which x and y are disjoint and for which x is not a subset of y and y is not a subset of x. Wieder calls these "disjoint strict 2-combinations". - Ross La Haye, Jan 11 2008; corrected by Ross La Haye, Oct 29 2008
Also, let P(A) be the power set of an n-element set A. Then a(n+2) = the number of pairs of elements {x,y} of P(A) for which either 0) x and y are disjoint and for which either x is a subset of y or y is a subset of x, or 1) x and y are disjoint and for which x is not a subset of y and y is not a subset of x, or 2) x and y are intersecting and for which either x is a proper subset of y or y is a proper subset of x. - Ross La Haye, Jan 11 2008
3 * a(n+1) = p(n+1) where p(x) is the unique degree-n polynomial such that p(k) = a(k+1) for k = 0, 1, ..., n. - Michael Somos, Apr 29 2012
John W. Layman's conjecture that a(n+2) is the sum of elements in S(n) follows from the identification of S(n) with the first n rows of A036561, whose row sums are A001047. - Fred Daniel Kline, Oct 02 2014
From M. Sinan Kul, Sep 08 2016: (Start)
Let m be equal to the product of n-1 distinct primes. Then a(n) is equal to the number of distinct fractions >=1 that may be created by dividing a divisor of m by another divisor. For example for m = 2*3*5 = 30, we would have the following 6 fractions: 6/5, 3/2, 5/3, 5/2, 10/3, 15/2.
Here finding the number of fractions would be equivalent to distributing n-1 balls (distinct primes) to two bins (numerator and denominator) with no empty bins which can be found by Stirling numbers of the second kind. So another definition for a(n) is a(n) = Sum_{i=2..n-1} Stirling2(i,2)*binomial(n-1,i).
Also for n > 0, a(n) = (d(m^2)+1)/2 - d(m) where m is equal to the product of n-1 distinct primes. Example for a(5): m = 2*3*5*7 = 210 (product of four distinct primes) so a(5) = (d(210^2)+1)/2 - d(210) = 41 - 16 = 25. (End)
6*a(n) is the number of ternary strings of length n that contain at least one of each of the 3 symbols on which they are defined. For example, for n=4, the strings are the 12 permutations of 0012, the 12 permutations of 0112, and the 12 permutations of 0122. - Enrique Navarrete, Aug 23 2021
A simpler form of La Haye's first comment is: a(n+1) is the number of ways we can form disjoint unions of two nonempty subsets of [n] (see example below). Cf. A001047 for the requirement that the union contains n. - Enrique Navarrete, Aug 24 2021
As partial sums of the Nicomachus triangle's rows and the differences of the powers of 3 and 2 (A001047), each iteration corresponds to two figurate variations of the Sierpinski triangle (3^n) with cross-correlation to the Nicomachus triangle, see illustrations in links. The Sierpinski half-hexagons of (A001047) stack and conform to the footprint of 2^n - 1 triangular numbers. The 3^n Sierpinski triangle minus its 2^n bottom row, also correlates to the Nicomachus triangle according to each Sierpinski triangular sub-row. - John Elias, Oct 04 2021

			a(4) = 6. Let denote Z[i] the i-th labeled element = "ball". Then one has for n=4 six different ways to fill sets = "boxes" with the labeled elements:
Set(Set(Z[3], Z[4]), Set(Z[1]), Set(Z[2])), Set(Set(Z[3], Z[1]), Set(Z[4]), Set(Z[2])), Set(Set(Z[4], Z[1]), Set(Z[3]), Set(Z[2])), Set(Set(Z[4]), Set(Z[1]), Set(Z[3], Z[2])), Set(Set(Z[3]), Set(Z[1], Z[2]), Set(Z[4])), Set(Set(Z[3]), Set(Z[1]), Set(Z[4], Z[2])).
G.f. = x^3 + 6*x^4 + 25*x^5 + 90*x^6 + 301*x^7 + 966*x^8 + 3025*x^9 + ...
For example, for n=3, a(4)=6 since the disjoint unions are: {1}U{2}, {1}U{3}, {1}U{2,3}, {2}U{3}, {2}U{1,3}, and {1,2}U{3}. - _Enrique Navarrete_, Aug 24 2021

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 835.
F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 223.
M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]
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).

T. D. Noe, Table of n, a(n) for n = 0..200
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
Harry Crane, Left-right arrangements, set partitions, and pattern avoidance, Australasian Journal of Combinatorics, 61(1) (2015), 57-72.
John Elias, Illustration: Stirling-Sierpinski triangles, Nicomachus-Sierpinski towers
M. Griffiths and I. Mezo, A generalization of Stirling Numbers of the Second Kind via a special multiset, JIS 13 (2010) #10.2.5.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 346
Fred Kline and Peter Taylor, Partial sums of Nicomachus' Triangle rows produce Stirling numbers of the 2nd kind, Mathematics Stack Exchange. - _Fred Daniel Kline_, Sep 22 2014
Ross La Haye, Binary Relations on the Power Set of an n-Element Set, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.
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.
Anthony G. Shannon, Hakan Akkuş, Yeşim Aküzüm, Ömür Deveci, and Engin Özkan, A partial recurrence Fibonacci link, Notes Num. Theor. Disc. Math. (2024) Vol. 30, No. 3, 530-537. See Table 1, p. 531.
Kai Wang, Girard-Waring Type Formula For A Generalized Fibonacci Sequence, Fibonacci Quarterly (2020) Vol. 58, No. 5, 229-235.
Eric Weisstein's World of Mathematics, Minimal Cover.
Thomas Wieder, The number of certain k-combinations of an n-set, Applied Mathematics Electronic Notes, vol. 8 (2008).
Index entries for linear recurrences with constant coefficients, signature (6,-11,6).

Cf. A008277 (Stirling2 triangle), A007051, A056509, A000225.
Cf. A003462, A003463, A003464, A023000, A023001, A002452, A002275, A016123, A016125, A016256.
Cf. A028243, A122554.

List([0..400], n->Stirling2(n,3)); # Muniru A Asiru, Feb 04 2018

A000392 := n -> 9/2*3^n-4*2^n+1/2;  [ seq(9/2*3^n-4*2^n+1/2,n=0..30) ]; # Thomas Wieder
A000392:=-1/(z-1)/(3*z-1)/(2*z-1); # Simon Plouffe in his 1992 dissertation

StirlingS2[Range[0,30],3] (* Harvey P. Dale, Dec 29 2011 *)

PARI
```
{a(n) = 3^(n-1) / 2 - 2^(n-1) + 1/2};
```

[stirling_number2(i,3) for i in (0..40)] # Zerinvary Lajos, Jun 26 2008

G.f.: x^3/((1-x)*(1-2*x)*(1-3*x)).
E.g.f.: ((exp(x) - 1)^3) / 3!.
Recurrence: a(n+3) = 6*a(n+2) - 11*a(n+1) + 6*a(n), a(3) = 1, a(4) = 6, a(5) = 25. - Thomas Wieder, Nov 30 2004
With offset 0, this is 9*3^n/2 - 4*2^n + 1/2, the partial sums of 3*3^n - 2*2^n = A001047(n+1). - Paul Barry, Jun 26 2003
a(n) = (1 + 3^(n-1) - 2^n)/2, n > 0. - Dennis P. Walsh, Feb 20 2007
For n >= 3, a(n) = 3*a(n-1) + 2^(n-2) - 1. - Geoffrey Critzer, Mar 03 2009
a(n) = 5*a(n-1) - 6*a(n-2) + 1, for n > 3. - Vincenzo Librandi Nov 25 2010
a(n) = det(|s(i+3,j+2)|, 1 <= i,j <= n-3), where s(n,k) are Stirling numbers of the first kind. - Mircea Merca, Apr 06 2013
G.f.:  x^3 + 12*x^4/(G(0)-12*x), where G(k) = x + 1 + 9*(3*x+1)*3^k - 8*(2*x+1)*2^k - x*(9*3^k+1-8*2^k)*(81*3^k+1-32*2^k)/G(k+1); (continued fraction). - Sergei N. Gladkovskii, Feb 01 2014
a(n + 2) = (1 - 2^(2 + n) + 3^(1 + n))/2 for n > 0. - Fred Daniel Kline, Oct 02 2014
For n > 0, a(n) = (1/2) * Sum_{k=1..n-1} Sum_{i=1..n-1} C(n-k-1,i) * C(n-1,k). - Wesley Ivan Hurt, Sep 22 2017
a(n) = Sum_{k=0..n-3} 2^(k-1)*(3^(n-2-k) - 1).  - J. M. Bergot, Feb 05 2018

Offset changed by N. J. A. Sloane, Feb 08 2008

cp's OEIS Frontend

A141324 Sum of digits of A002452(n).

Views

Author

Keywords

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A000225 a(n) = 2^n - 1. (Sometimes called Mersenne numbers, although that name is usually reserved for A001348.)

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

SageMath

Formula

Extensions

A003463 a(n) = (5^n - 1)/4.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Maxima

PARI

Sage

Sage

Formula

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

Maxima

PARI

Python

Sage

Formula

Extensions

A136630 Triangular array: T(n,k) counts the partitions of the set [n] into k odd sized blocks.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A006095 Gaussian binomial coefficient [n, 2] for q = 2.

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