cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-10 of 94 results. Next

A000079 Powers of 2: a(n) = 2^n.

Original entry on oeis.org

1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

2^0 = 1 is the only odd power of 2.
Number of subsets of an n-set.
There are 2^(n-1) compositions (ordered partitions) of n (see for example Riordan). This is the unlabeled analog of the preferential labelings sequence A000670.
This is also the number of weakly unimodal permutations of 1..n + 1, that is, permutations with exactly one local maximum. E.g., a(4) = 16: 12345, 12354, 12453, 12543, 13452, 13542, 14532 and 15432 and their reversals. - Jon Perry, Jul 27 2003 [Proof: see next line! See also A087783.]
Proof: n must appear somewhere and there are 2^(n-1) possible choices for the subset that precedes it. These must appear in increasing order and the rest must follow n in decreasing order. QED. - N. J. A. Sloane, Oct 26 2003
a(n+1) is the smallest number that is not the sum of any number of (distinct) earlier terms.
Same as Pisot sequences E(1, 2), L(1, 2), P(1, 2), T(1, 2). See A008776 for definitions of Pisot sequences.
With initial 1 omitted, same as Pisot sequences E(2, 4), L(2, 4), P(2, 4), T(2, 4). - David W. Wilson
Not the sum of two or more consecutive numbers. - Lekraj Beedassy, May 14 2004
Least deficient or near-perfect numbers (i.e., n such that sigma(n) = A000203(n) = 2n - 1). - Lekraj Beedassy, Jun 03 2004. [Comment from Max Alekseyev, Jan 26 2005: All the powers of 2 are least deficient numbers but it is not known if there exists a least deficient number that is not a power of 2.]
Almost-perfect numbers referred to as least deficient or slightly defective (Singh 1997) numbers. Does "near-perfect numbers" refer to both almost-perfect numbers (sigma(n) = 2n - 1) and quasi-perfect numbers (sigma(n) = 2n + 1)? There are no known quasi-perfect or least abundant or slightly excessive (Singh 1997) numbers.
The sum of the numbers in the n-th row of Pascal's triangle; the sum of the coefficients of x in the expansion of (x+1)^n.
The Collatz conjecture (the hailstone sequence will eventually reach the number 1, regardless of which positive integer is chosen initially) may be restated as (the hailstone sequence will eventually reach a power of 2, regardless of which positive integer is chosen initially).
The only hailstone sequence which doesn't rebound (except "on the ground"). - Alexandre Wajnberg, Jan 29 2005
With p(n) as the number of integer partitions of n, p(i) is the number of parts of the i-th partition of n, d(i) is the number of different parts of the i-th partition of n, m(i,j) is the multiplicity of the j-th part of the i-th partition of n, one has: a(n) = Sum_{i = 1..p(n)} (p(i)! / (Product_{j=1..d(i)} m(i,j)!)). - Thomas Wieder, May 18 2005
The number of binary relations on an n-element set that are both symmetric and antisymmetric. Also the number of binary relations on an n-element set that are symmetric, antisymmetric and transitive.
The first differences are the sequence itself. - Alexandre Wajnberg and Eric Angelini, Sep 07 2005
a(n) is the largest number with shortest addition chain involving n additions. - David W. Wilson, Apr 23 2006
Beginning with a(1) = 0, numbers not equal to the sum of previous distinct natural numbers. - Giovanni Teofilatto, Aug 06 2006
For n >= 1, a(n) is equal to the number of functions f:{1, 2, ..., n} -> {1, 2} such that for a fixed x in {1, 2, ..., n} and a fixed y in {1, 2} we have f(x) != y. - Aleksandar M. Janjic and Milan Janjic, Mar 27 2007
Let P(A) be the power set of an n-element set A. Then a(n) is the number of pairs of elements {x,y} of P(A) for which x = y. - Ross La Haye, Jan 09 2008
a(n) is the number of permutations on [n+1] such that every initial segment is an interval of integers. Example: a(3) counts 1234, 2134, 2314, 2341, 3214, 3241, 3421, 4321. The map "p -> ascents of p" is a bijection from these permutations to subsets of [n]. An ascent of a permutation p is a position i such that p(i) < p(i+1). The permutations shown map to 123, 23, 13, 12, 3, 2, 1 and the empty set respectively. - David Callan, Jul 25 2008
2^(n-1) is the largest number having n divisors (in the sense of A077569); A005179(n) is the smallest. - T. D. Noe, Sep 02 2008
a(n) appears to match the number of divisors of the modified primorials (excluding 2, 3 and 5). Very limited range examined, PARI example shown. - Bill McEachen, Oct 29 2008
Successive k such that phi(k)/k = 1/2, where phi is Euler's totient function. - Artur Jasinski, Nov 07 2008
A classical transform consists (for general a(n)) in swapping a(2n) and a(2n+1); examples for Jacobsthal A001045 and successive differences: A092808, A094359, A140505. a(n) = A000079 leads to 2, 1, 8, 4, 32, 16, ... = A135520. - Paul Curtz, Jan 05 2009
This is also the (L)-sieve transform of {2, 4, 6, 8, ..., 2n, ...} = A005843. (See A152009 for the definition of the (L)-sieve transform.) - John W. Layman, Jan 23 2009
a(n) = a(n-1)-th even natural number (A005843) for n > 1. - Jaroslav Krizek, Apr 25 2009
For n >= 0, a(n) is the number of leaves in a complete binary tree of height n. For n > 0, a(n) is the number of nodes in an n-cube. - K.V.Iyer, May 04 2009
Permutations of n+1 elements where no element is more than one position right of its original place. For example, there are 4 such permutations of three elements: 123, 132, 213, and 312. The 8 such permutations of four elements are 1234, 1243, 1324, 1423, 2134, 2143, 3124, and 4123. - Joerg Arndt, Jun 24 2009
Catalan transform of A099087. - R. J. Mathar, Jun 29 2009
a(n) written in base 2: 1,10,100,1000,10000,..., i.e., (n+1) times 1, n times 0 (A011557(n)). - Jaroslav Krizek, Aug 02 2009
Or, phi(n) is equal to the number of perfect partitions of n. - Juri-Stepan Gerasimov, Oct 10 2009
These are the 2-smooth numbers, positive integers with no prime factors greater than 2. - Michael B. Porter, Oct 04 2009
A064614(a(n)) = A000244(n) and A064614(m) < A000244(n) for m < a(n). - Reinhard Zumkeller, Feb 08 2010
a(n) is the largest number m such that the number of steps of iterations of {r - (largest divisor d < r)} needed to reach 1 starting at r = m is equal to n. Example (a(5) = 32): 32 - 16 = 16; 16 - 8 = 8; 8 - 4 = 4; 4 - 2 = 2; 2 - 1 = 1; number 32 has 5 steps and is the largest such number. See A105017, A064097, A175125. - Jaroslav Krizek, Feb 15 2010
a(n) is the smallest proper multiple of a(n-1). - Dominick Cancilla, Aug 09 2010
The powers-of-2 triangle T(n, k), n >= 0 and 0 <= k <= n, begins with: {1}; {2, 4}; {8, 16, 32}; {64, 128, 256, 512}; ... . The first left hand diagonal T(n, 0) = A006125(n + 1), the first right hand diagonal T(n, n) = A036442(n + 1) and the center diagonal T(2*n, n) = A053765(n + 1). Some triangle sums, see A180662, are: Row1(n) = A122743(n), Row2(n) = A181174(n), Fi1(n) = A181175(n), Fi2(2*n) = A181175(2*n) and Fi2(2*n + 1) = 2*A181175(2*n + 1). - Johannes W. Meijer, Oct 10 2010
Records in the number of prime factors. - Juri-Stepan Gerasimov, Mar 12 2011
Row sums of A152538. - Gary W. Adamson, Dec 10 2008
A078719(a(n)) = 1; A006667(a(n)) = 0. - Reinhard Zumkeller, Oct 08 2011
The compositions of n in which each natural number is colored by one of p different colors are called p-colored compositions of n. For n>=1, a(n) equals the number of 2-colored compositions of n such that no adjacent parts have the same color. - Milan Janjic, Nov 17 2011
Equals A001405 convolved with its right-shifted variant: (1 + 2x + 4x^2 + ...) = (1 + x + 2x^2 + 3x^3 + 6x^4 + 10x^5 + ...) * (1 + x + x^2 + 2x^3 + 3x^4 + 6x^5 + ...). - Gary W. Adamson, Nov 23 2011
The number of odd-sized subsets of an n+1-set. For example, there are 2^3 odd-sized subsets of {1, 2, 3, 4}, namely {1}, {2}, {3}, {4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, and {2, 3, 4}. Also, note that 2^n = Sum_{k=1..floor((n+1)/2)} C(n+1, 2k-1). - Dennis P. Walsh, Dec 15 2011
a(n) is the number of 1's in any row of Pascal's triangle (mod 2) whose row number has exactly n 1's in its binary expansion (see A007318 and A047999). (The result of putting together A001316 and A000120.) - Marcus Jaiclin, Jan 31 2012
A204455(k) = 1 if and only if k is in this sequence. - Wolfdieter Lang, Feb 04 2012
For n>=1 apparently the number of distinct finite languages over a unary alphabet, whose minimum regular expression has alphabetic width n (verified up to n=17), see the Gruber/Lee/Shallit link. - Hermann Gruber, May 09 2012
First differences of A000225. - Omar E. Pol, Feb 19 2013
This is the lexicographically earliest sequence which contains no arithmetic progression of length 3. - Daniel E. Frohardt, Apr 03 2013
a(n-2) is the number of bipartitions of {1..n} (i.e., set partitions into two parts) such that 1 and 2 are not in the same subset. - Jon Perry, May 19 2013
Numbers n such that the n-th cyclotomic polynomial has a root mod 2; numbers n such that the n-th cyclotomic polynomial has an even number of odd coefficients. - Eric M. Schmidt, Jul 31 2013
More is known now about non-power-of-2 "Almost Perfect Numbers" as described in Dagal. - Jonathan Vos Post, Sep 01 2013
Number of symmetric Ferrers diagrams that fit into an n X n box. - Graham H. Hawkes, Oct 18 2013
Numbers n such that sigma(2n) = 2n + sigma(n). - Jahangeer Kholdi, Nov 23 2013
a(1), ..., a(floor(n/2)) are all values of permanent on set of square (0,1)-matrices of order n>=2 with row and column sums 2. - Vladimir Shevelev, Nov 26 2013
Numbers whose base-2 expansion has exactly one bit set to 1, and thus has base-2 sum of digits equal to one. - Stanislav Sykora, Nov 29 2013
A072219(a(n)) = 1. - Reinhard Zumkeller, Feb 20 2014
a(n) is the largest number k such that (k^n-2)/(k-2) is an integer (for n > 1); (k^a(n)+1)/(k+1) is never an integer (for k > 1 and n > 0). - Derek Orr, May 22 2014
If x = A083420(n), y = a(n+1) and z = A087289(n), then x^2 + 2*y^2 = z^2. - Vincenzo Librandi, Jun 09 2014
The mini-sequence b(n) = least number k > 0 such that 2^k ends in n identical digits is given by {1, 18, 39}. The repeating digits are {2, 4, 8} respectively. Note that these are consecutive powers of 2 (2^1, 2^2, 2^3), and these are the only powers of 2 (2^k, k > 0) that are only one digit. Further, this sequence is finite. The number of n-digit endings for a power of 2 with n or more digits id 4*5^(n-1). Thus, for b(4) to exist, one only needs to check exponents up to 4*5^3 = 500. Since b(4) does not exist, it is clear that no other number will exist. - Derek Orr, Jun 14 2014
The least number k > 0 such that 2^k ends in n consecutive decreasing digits is a 3-number sequence given by {1, 5, 25}. The consecutive decreasing digits are {2, 32, 432}. There are 100 different 3-digit endings for 2^k. There are no k-values such that 2^k ends in '987', '876', '765', '654', '543', '321', or '210'. The k-values for which 2^k ends in '432' are given by 25 mod 100. For k = 25 + 100*x, the digit immediately before the run of '432' is {4, 6, 8, 0, 2, 4, 6, 8, 0, 2, ...} for x = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...}, respectively. Thus, we see the digit before '432' will never be a 5. So, this sequence is complete. - Derek Orr, Jul 03 2014
a(n) is the number of permutations of length n avoiding both 231 and 321 in the classical sense which are breadth-first search reading words of increasing unary-binary trees. For more details, see the entry for permutations avoiding 231 at A245898. - Manda Riehl, Aug 05 2014
Numbers n such that sigma(n) = sigma(2n) - phi(4n). - Farideh Firoozbakht, Aug 14 2014
This is a B_2 sequence: for i < j, differences a(j) - a(i) are all distinct. Here 2*a(n) < a(n+1) + 1, so a(n) - a(0) < a(n+1) - a(n). - Thomas Ordowski, Sep 23 2014
a(n) counts n-walks (closed) on the graph G(1-vertex; 1-loop, 1-loop). - David Neil McGrath, Dec 11 2014
a(n-1) counts walks (closed) on the graph G(1-vertex; 1-loop, 2-loop, 3-loop, 4-loop, ...). - David Neil McGrath, Jan 01 2015
b(0) = 4; b(n+1) is the smallest number not in the sequence such that b(n+1) - Prod_{i=0..n} b(i) divides b(n+1) - Sum_{i=0..n} b(i). Then b(n) = a(n) for n > 2. - Derek Orr, Jan 15 2015
a(n) counts the permutations of length n+2 whose first element is 2 such that the permutation has exactly one descent. - Ran Pan, Apr 17 2015
a(0)-a(30) appear, with a(26)-a(30) in error, in tablet M 08613 (see CDLI link) from the Old Babylonian period (c. 1900-1600 BC). - Charles R Greathouse IV, Sep 03 2015
Subsequence of A028982 (the squares or twice squares sequence). - Timothy L. Tiffin, Jul 18 2016
A000120(a(n)) = 1. A000265(a(n)) = 1. A000593(a(n)) = 1. - Juri-Stepan Gerasimov, Aug 16 2016
Number of monotone maps f : [0..n] -> [0..n] which are order-increasing (i <= f(i)) and idempotent (f(f(i)) = f(i)). In other words, monads on the n-th ordinal (seen as a posetal category). Any monad f determines a subset of [0..n] that contains n, by considering its set of monad algebras = fixed points { i | f(i) = i }. Conversely, any subset S of [0..n] containing n determines a monad on [0..n], by the function i |-> min { j | i <= j, j in S }. - Noam Zeilberger, Dec 11 2016
Consider n points lying on a circle. Then for n>=2 a(n-2) gives the number of ways to connect two adjacent points with nonintersecting chords. - Anton Zakharov, Dec 31 2016
Satisfies Benford's law [Diaconis, 1977; Berger-Hill, 2017] - N. J. A. Sloane, Feb 07 2017
Also the number of independent vertex sets and vertex covers in the n-empty graph. - Eric W. Weisstein, Sep 21 2017
Also the number of maximum cliques in the n-halved cube graph for n > 4. - Eric W. Weisstein, Dec 04 2017
Number of pairs of compositions of n corresponding to a seaweed algebra of index n-1. - Nick Mayers, Jun 25 2018
The multiplicative group of integers modulo a(n) is cyclic if and only if n = 0, 1, 2. For n >= 3, it is a product of two cyclic groups. - Jianing Song, Jun 27 2018
k^n is the determinant of n X n matrix M_(i, j) = binomial(k + i + j - 2, j) - binomial(i+j-2, j), in this case k=2. - Tony Foster III, May 12 2019
Solutions to the equation Phi(2n + 2*Phi(2n)) = 2n. - M. Farrokhi D. G., Jan 03 2020
a(n-1) is the number of subsets of {1,2,...,n} which have an element that is the size of the set. For example, for n = 4, a(3) = 8 and the subsets are {1}, {1,2}, {2,3}, {2,4}, {1,2,3}, {1,3,4}, {2,3,4}, {1,2,3,4}. - Enrique Navarrete, Nov 21 2020
a(n) is the number of self-inverse (n+1)-order permutations with 231-avoiding. E.g., a(3) = 8: [1234, 1243, 1324, 1432, 2134, 2143, 3214, 4321]. - Yuchun Ji, Feb 26 2021
For any fixed k > 0, a(n) is the number of ways to tile a strip of length n+1 with tiles of length 1, 2, ... k, where the tile of length k can be black or white, with the restriction that the first tile cannot be black. - Greg Dresden and Bora Bursalı, Aug 31 2023

Examples

			There are 2^3 = 8 subsets of a 3-element set {1,2,3}, namely { -, 1, 2, 3, 12, 13, 23, 123 }.

References

  • Milton Abramowitz and Irene A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 1016.
  • Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem, Mathematics and Computer Education Journal, Vol. 31, No. 1, pp. 24-28, Winter 1997.
  • John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See pp. 73, 84.
  • Jan Gullberg, Mathematics from the Birth of Numbers, W. W. Norton & Co., NY & London, 1997, §4.5 Logarithms and §8.1 Terminology, pp. 150, 264.
  • Paul J. Nahin, An Imaginary Tale: The Story of sqrt(-1), Princeton University Press, Princeton, NJ. 1998, pp. 69-70.
  • Alfred S. Posamentier, Math Charmers, Tantalizing Tidbits for the Mind, Prometheus Books, NY, 2003, page 273.
  • J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 124.
  • 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).
  • V. E. Tarakanov, Combinatorial problems on binary matrices, Combin. Analysis, MSU, 5 (1980), 4-15. (Russian)
  • James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, page 141.
  • S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 55.

Links

Crossrefs

Cf. A000225, A038754, A133464, A140730, A037124, A001787, A001788, A001789, A003472, A054849, A002409, A054851, A140325, A140354, A000041, A152537, A001405, A007318, A000120, A000265, A000593, A001227, A077020, A077021.
This is the Hankel transform (see A001906 for the definition) of A000984, A002426, A026375, A026387, A026569, A026585, A026671 and A032351. - John W. Layman, Jul 31 2000
Euler transform of A001037, A209406 (multisets), inverse binomial transform of A000244, binomial transform of A000012.
Complement of A057716.
Boustrophedon transforms: A000734, A000752.
Range of values of A006519, A007875, A011782, A030001, A034444, A037445, A053644, and A054243.
Cf. A018900, A014311, A014312, A014313, A023688, A023689, A023690, A023691 (sum of 2, ..., 9 distinct powers of 2).
Cf. A090129.
The following are parallel families: A000079 (2^n), A004094 (2^n reversed), A028909 (2^n sorted up), A028910 (2^n sorted down), A036447 (double and reverse), A057615 (double and sort up), A263451 (double and sort down); A000244 (3^n), A004167 (3^n reversed), A321540 (3^n sorted up), A321539 (3^n sorted down), A163632 (triple and reverse), A321542 (triple and sort up), A321541 (triple and sort down).

Programs

  • Haskell
    a000079 = (2 ^)
a000079_list = iterate (* 2) 1
-- Reinhard Zumkeller, Jan 22 2014, Mar 05 2012, Dec 29 2011
  • Magma
    [2^n: n in [0..40]]; // Vincenzo Librandi, Feb 17 2014
  • Magma
    [n le 2 select n else 5*Self(n-1)-6*Self(n-2): n in [1..40]]; // Vincenzo Librandi, Feb 17 2014
  • Maple
    A000079 := n->2^n; [ seq(2^n,n=0..50) ];
isA000079 := proc(n)
    local fs;
    fs := numtheory[factorset](n) ;
    if n = 1 then
        true ;
    elif nops(fs) <> 1 then
        false;
    elif op(1,fs) = 2 then
        true;
    else
        false ;
    end if;
end proc: # R. J. Mathar, Jan 09 2017
  • Mathematica
    Table[2^n, {n, 0, 50}]
2^Range[0, 50] (* Wesley Ivan Hurt, Jun 14 2014 *)
LinearRecurrence[{2}, {2}, {0, 20}] (* Eric W. Weisstein, Sep 21 2017 *)
CoefficientList[Series[1/(1 - 2 x), {x, 0, 20}], x] (* Eric W. Weisstein, Sep 21 2017 *)
NestList[2# &, 1, 40] (* Harvey P. Dale, Oct 07 2019 *)
  • Maxima
    A000079(n):=2^n$ makelist(A000079(n),n,0,30); /* Martin Ettl, Nov 05 2012 */
  • PARI
    A000079(n)=2^n \\ Edited by M. F. Hasler, Aug 27 2014
  • PARI
    unimodal(n)=local(x,d,um,umc); umc=0; for (c=0,n!-1, x=numtoperm(n,c); d=0; um=1; for (j=2,n,if (x[j]x[j-1] && d==1,um=0); if (um==0,break)); if (um==1,print(x)); umc+=um); umc
  • Python
    def a(n): return 1<Michael S. Branicky, Jul 28 2022
  • Python
    def is_powerof2(n) -> bool: return n and (n & (n - 1)) == 0  # Peter Luschny, Apr 10 2025
  • Scala
    (List.fill(20)(2: BigInt)).scanLeft(1: BigInt)( * ) // Alonso del Arte, Jan 16 2020
  • Scheme
    (define (A000079 n) (expt 2 n)) ;; Antti Karttunen, Mar 21 2017

Formula

a(n) = 2^n.
a(0) = 1; a(n) = 2*a(n-1).
G.f.: 1/(1 - 2*x).
E.g.f.: exp(2*x).
a(n)= Sum_{k = 0..n} binomial(n, k).
a(n) is the number of occurrences of n in A000523. a(n) = A001045(n) + A001045(n+1). a(n) = 1 + Sum_{k = 0..(n - 1)} a(k). The Hankel transform of this sequence gives A000007 = [1, 0, 0, 0, 0, 0, ...]. - Philippe Deléham, Feb 25 2004
n such that phi(n) = n/2, for n > 1, where phi is Euler's totient (A000010). - Lekraj Beedassy, Sep 07 2004
a(n + 1) = a(n) XOR 3*a(n) where XOR is the binary exclusive OR operator. - Philippe Deléham, Jun 19 2005
a(n) = StirlingS2(n + 1, 2) + 1. - Ross La Haye, Jan 09 2008
a(n+2) = 6a(n+1) - 8a(n), n = 1, 2, 3, ... with a(1) = 1, a(2) = 2. - Yosu Yurramendi, Aug 06 2008
a(n) = ka(n-1) + (4 - 2k)a(n-2) for any integer k and n > 1, with a(0) = 1, a(1) = 2. - Jaume Oliver Lafont, Dec 05 2008
a(n) = Sum_{l_1 = 0..n + 1} Sum_{l_2 = 0..n}...Sum_{l_i = 0..n - i}...Sum_{l_n = 0..1} delta(l_1, l_2, ..., l_i, ..., l_n) where delta(l_1, l_2, ..., l_i, ..., l_n) = 0 if any l_i <= l_(i+1) and l_(i+1) != 0 and delta(l_1, l_2, ..., l_i, ..., l_n) = 1 otherwise. - Thomas Wieder, Feb 25 2009
a(0) = 1, a(1) = 2; a(n) = a(n-1)^2/a(n-2), n >= 2. - Jaume Oliver Lafont, Sep 22 2009
a(n) = A173786(n, n)/2 = A173787(n + 1, n). - Reinhard Zumkeller, Feb 28 2010
If p[i] = i - 1 and if A is the Hessenberg matrix of order n defined by: A[i, j] = p[j - i + 1], (i <= j), A[i, j] = -1, (i = j + 1), and A[i, j] = 0 otherwise. Then, for n >= 1, a(n-1) = det A. - Milan Janjic, May 02 2010
If p[i] = Fibonacci(i-2) and if A is the Hessenberg matrix of order n defined by: A[i, j] = p[j - i + 1], (i <= j), A[i, j] = -1, (i = j + 1), and A[i, j] = 0 otherwise. Then, for n >= 2, a(n-2) = det A. - Milan Janjic, May 08 2010
The sum of reciprocals, 1/1 + 1/2 + 1/4 + 1/8 + ... + 1/(2^n) + ... = 2. - Mohammad K. Azarian, Dec 29 2010
a(n) = 2*A001045(n) + A078008(n) = 3*A001045(n) + (-1)^n. - Paul Barry, Feb 20 2003
a(n) = A118654(n, 2).
a(n) = A140740(n+1, 1).
a(n) = A131577(n) + A011782(n) = A024495(n) + A131708(n) + A024493(n) = A000749(n) + A038503(n) + A038504(n) + A038505(n) = A139761(n) + A139748(n) + A139714(n) + A133476(n) + A139398(n). - Paul Curtz, Jul 25 2011
a(n) = row sums of A007318. - Susanne Wienand, Oct 21 2011
a(n) = Hypergeometric([-n], [], -1). - Peter Luschny, Nov 01 2011
G.f.: A(x) = B(x)/x, B(x) satisfies B(B(x)) = x/(1 - x)^2. - Vladimir Kruchinin, Nov 10 2011
a(n) = Sum_{k = 0..n} A201730(n, k)*(-1)^k. - Philippe Deléham, Dec 06 2011
2^n = Sum_{k = 1..floor((n+1)/2)} C(n+1, 2k-1). - Dennis P. Walsh, Dec 15 2011
A209229(a(n)) = 1. - Reinhard Zumkeller, Mar 07 2012
A001227(a(n)) = 1. - Reinhard Zumkeller, May 01 2012
Sum_{n >= 1} mobius(n)/a(n) = 0.1020113348178103647430363939318... - R. J. Mathar, Aug 12 2012
E.g.f.: 1 + 2*x/(U(0) - x) where U(k) = 6*k + 1 + x^2/(6*k+3 + x^2/(6*k + 5 + x^2/U(k+1) )); (continued fraction, 3-step). - Sergei N. Gladkovskii, Dec 04 2012
a(n) = det(|s(i+2,j)|, 1 <= i,j <= n), where s(n,k) are Stirling numbers of the first kind. - Mircea Merca, Apr 04 2013
a(n) = det(|ps(i+1,j)|, 1 <= i,j <= n), where ps(n,k) are Legendre-Stirling numbers of the first kind (A129467). - Mircea Merca, Apr 06 2013
G.f.: W(0), where W(k) = 1 + 2*x*(k+1)/(1 - 2*x*(k+1)/( 2*x*(k+2) + 1/W(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 28 2013
a(n-1) = Sum_{t_1 + 2*t_2 + ... + n*t_n = n} multinomial(t_1 + t_2 + ... + t_n; t_1, t_2, ..., t_n). - Mircea Merca, Dec 06 2013
Construct the power matrix T(n,j) = [A^*j]*[S^*(j-1)] where A(n)=(1,1,1,...) and S(n)=(0,1,0,0,...) (where * is convolution operation). Then a(n-1) = Sum_{j=1..n} T(n,j). - David Neil McGrath, Jan 01 2015
a(n) = A000005(A002110(n)). - Ivan N. Ianakiev, May 23 2016
From Ilya Gutkovskiy, Jul 18 2016: (Start)
Exponential convolution of A000012 with themselves.
a(n) = Sum_{k=0..n} A011782(k).
Sum_{n>=0} a(n)/n! = exp(2) = A072334.
Sum_{n>=0} (-1)^n*a(n)/n! = exp(-2) = A092553. (End)
G.f.: (r(x) * r(x^2) * r(x^4) * r(x^8) * ...) where r(x) = A090129(x) = (1 + 2x + 2x^2 + 4x^3 + 8x^4 + ...). - Gary W. Adamson, Sep 13 2016
a(n) = A000045(n + 1) + A000045(n) + Sum_{k = 0..n - 2} A000045(k + 1)*2^(n - 2 - k). - Melvin Peralta, Dec 22 2017
a(n) = 7*A077020(n)^2 + A077021(n)^2, n>=3. - Ralf Steiner, Aug 08 2021
a(n)= n + 1 + Sum_{k=3..n+1} (2*k-5)*J(n+2-k), where Jacobsthal number J(n) = A001045(n). - Michael A. Allen, Jan 12 2022
Integral_{x=0..Pi} cos(x)^n*cos(n*x) dx = Pi/a(n) (see Nahin, pp. 69-70). - Stefano Spezia, May 17 2023

Extensions

Clarified a comment T. D. Noe, Aug 30 2009
Edited by Daniel Forgues, May 12 2010
Incorrect comment deleted by Matthew Vandermast, May 17 2014
Comment corrected to match offset by Geoffrey Critzer, Nov 28 2014

A000027 The positive integers. Also called the natural numbers, the whole numbers or the counting numbers, but these terms are ambiguous.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

Comments

For some authors, the terms "natural numbers" and "counting numbers" include 0, i.e., refer to the nonnegative integers A001477; the term "whole numbers" frequently also designates the whole set of (signed) integers A001057.
a(n) is smallest positive integer which is consistent with sequence being monotonically increasing and satisfying a(a(n)) = n (cf. A007378).
Inverse Euler transform of A000219.
The rectangular array having A000027 as antidiagonals is the dispersion of the complement of the triangular numbers, A000217 (which triangularly form column 1 of this array). The array is also the transpose of A038722. - Clark Kimberling, Apr 05 2003
For nonzero x, define f(n) = floor(nx) - floor(n/x). Then f=A000027 if and only if x=tau or x=-tau. - Clark Kimberling, Jan 09 2005
Numbers of form (2^i)*k for odd k (i.e., n = A006519(n)*A000265(n)); thus n corresponds uniquely to an ordered pair (i,k) where i=A007814, k=A000265 (with A007814(2n)=A001511(n), A007814(2n+1)=0). - Lekraj Beedassy, Apr 22 2006
If the offset were changed to 0, we would have the following pattern: a(n)=binomial(n,0) + binomial(n,1) for the present sequence (number of regions in 1-space defined by n points), A000124 (number of regions in 2-space defined by n straight lines), A000125 (number of regions in 3-space defined by n planes), A000127 (number of regions in 4-space defined by n hyperplanes), A006261, A008859, A008860, A008861, A008862 and A008863, where the last six sequences are interpreted analogously and in each "... by n ..." clause an offset of 0 has been assumed, resulting in a(0)=1 for all of them, which corresponds to the case of not cutting with a hyperplane at all and therefore having one region. - Peter C. Heinig (algorithms(AT)gmx.de), Oct 19 2006
Define a number of points on a straight line to be in general arrangement when no two points coincide. Then these are the numbers of regions defined by n points in general arrangement on a straight line, when an offset of 0 is assumed. For instance, a(0)=1, since using no point at all leaves one region. The sequence satisfies the recursion a(n) = a(n-1) + 1. This has the following geometrical interpretation: Suppose there are already n-1 points in general arrangement, thus defining the maximal number of regions on a straight line obtainable by n-1 points, and now one more point is added in general arrangement. Then it will coincide with no other point and act as a dividing wall thereby creating one new region in addition to the a(n-1)=(n-1)+1=n regions already there, hence a(n)=a(n-1)+1. Cf. the comments on A000124 for an analogous interpretation. - Peter C. Heinig (algorithms(AT)gmx.de), Oct 19 2006
The sequence a(n)=n (for n=1,2,3) and a(n)=n+1 (for n=4,5,...) gives to the rank (minimal cardinality of a generating set) for the semigroup I_n\S_n, where I_n and S_n denote the symmetric inverse semigroup and symmetric group on [n]. - James East, May 03 2007
The sequence a(n)=n (for n=1,2), a(n)=n+1 (for n=3) and a(n)=n+2 (for n=4,5,...) gives the rank (minimal cardinality of a generating set) for the semigroup PT_n\T_n, where PT_n and T_n denote the partial transformation semigroup and transformation semigroup on [n]. - James East, May 03 2007
"God made the integers; all else is the work of man." This famous quotation is a translation of "Die ganzen Zahlen hat der liebe Gott gemacht, alles andere ist Menschenwerk," spoken by Leopold Kronecker in a lecture at the Berliner Naturforscher-Versammlung in 1886. Possibly the first publication of the statement is in Heinrich Weber's "Leopold Kronecker," Jahresberichte D.M.V. 2 (1893) 5-31. - Clark Kimberling, Jul 07 2007
Binomial transform of A019590, inverse binomial transform of A001792. - Philippe Deléham, Oct 24 2007
Writing A000027 as N, perhaps the simplest one-to-one correspondence between N X N and N is this: f(m,n) = ((m+n)^2 - m - 3n + 2)/2. Its inverse is given by I(k)=(g,h), where g = k - J(J-1)/2, h = J + 1 - g, J = floor((1 + sqrt(8k - 7))/2). Thus I(1)=(1,1), I(2)=(1,2), I(3)=(2,1) and so on; the mapping I fills the first-quadrant lattice by successive antidiagonals. - Clark Kimberling, Sep 11 2008
a(n) is also the mean of the first n odd integers. - Ian Kent, Dec 23 2008
Equals INVERTi transform of A001906, the even-indexed Fibonacci numbers starting (1, 3, 8, 21, 55, ...). - Gary W. Adamson, Jun 05 2009
These are also the 2-rough numbers: positive integers that have no prime factors less than 2. - Michael B. Porter, Oct 08 2009
Totally multiplicative sequence with a(p) = p for prime p. Totally multiplicative sequence with a(p) = a(p-1) + 1 for prime p. - Jaroslav Krizek, Oct 18 2009
Triangle T(k,j) of natural numbers, read by rows, with T(k,j) = binomial(k,2) + j = (k^2-k)/2 + j where 1 <= j <= k. In other words, a(n) = n = binomial(k,2) + j where k is the largest integer such that binomial(k,2) < n and j = n - binomial(k,2). For example, T(4,1)=7, T(4,2)=8, T(4,3)=9, and T(4,4)=10. Note that T(n,n)=A000217(n), the n-th triangular number. - Dennis P. Walsh, Nov 19 2009
Hofstadter-Conway-like sequence (see A004001): a(n) = a(a(n-1)) + a(n-a(n-1)) with a(1) = 1, a(2) = 2. - Jaroslav Krizek, Dec 11 2009
a(n) is also the dimension of the irreducible representations of the Lie algebra sl(2). - Leonid Bedratyuk, Jan 04 2010
Floyd's triangle read by rows. - Paul Muljadi, Jan 25 2010
Number of numbers between k and 2k where k is an integer. - Giovanni Teofilatto, Mar 26 2010
Generated from a(2n) = r*a(n), a(2n+1) = a(n) + a(n+1), r = 2; in an infinite set, row 2 of the array shown in A178568. - Gary W. Adamson, May 29 2010
1/n = continued fraction [n]. Let barover[n] = [n,n,n,...] = 1/k. Then k - 1/k = n. Example: [2,2,2,...] = (sqrt(2) - 1) = 1/k, with k = (sqrt(2) + 1). Then 2 = k - 1/k. - Gary W. Adamson, Jul 15 2010
Number of n-digit numbers the binary expansion of which contains one run of 1's. - Vladimir Shevelev, Jul 30 2010
From Clark Kimberling, Jan 29 2011: (Start)
Let T denote the "natural number array A000027":
1 2 4 7 ...
3 5 8 12 ...
6 9 13 18 ...
10 14 19 25 ...
T(n,k) = n+(n+k-2)*(n+k-1)/2. See A185787 for a list of sequences based on T, such as rows, columns, diagonals, and sub-arrays. (End)
The Stern polynomial B(n,x) evaluated at x=2. See A125184. - T. D. Noe, Feb 28 2011
The denominator in the Maclaurin series of log(2), which is 1 - 1/2 + 1/3 - 1/4 + .... - Mohammad K. Azarian, Oct 13 2011
As a function of Bernoulli numbers B_n (cf. A027641: (1, -1/2, 1/6, 0, -1/30, 0, 1/42, ...)): let V = a variant of B_n changing the (-1/2) to (1/2). Then triangle A074909 (the beheaded Pascal's triangle) * [1, 1/2, 1/6, 0, -1/30, ...] = the vector [1, 2, 3, 4, 5, ...]. - Gary W. Adamson, Mar 05 2012
Number of partitions of 2n+1 into exactly two parts. - Wesley Ivan Hurt, Jul 15 2013
Integers n dividing u(n) = 2u(n-1) - u(n-2); u(0)=0, u(1)=1 (Lucas sequence A001477). - Thomas M. Bridge, Nov 03 2013
For this sequence, the generalized continued fraction a(1)+a(1)/(a(2)+a(2)/(a(3)+a(3)/(a(4)+...))), evaluates to 1/(e-2) = A194807. - Stanislav Sykora, Jan 20 2014
Engel expansion of e-1 (A091131 = 1.71828...). - Jaroslav Krizek, Jan 23 2014
a(n) is the number of permutations of length n simultaneously avoiding 213, 231 and 321 in the classical sense which are breadth-first search reading words of increasing unary-binary trees. For more details, see the entry for permutations avoiding 231 at A245898. - Manda Riehl, Aug 05 2014
a(n) is also the number of permutations simultaneously avoiding 213, 231 and 321 in the classical sense which can be realized as labels on an increasing strict binary tree with 2n-1 nodes. See A245904 for more information on increasing strict binary trees. - Manda Riehl, Aug 07 2014
a(n) = least k such that 2*Pi - Sum_{h=1..k} 1/(h^2 - h + 3/16) < 1/n. - Clark Kimberling, Sep 28 2014
a(n) = least k such that Pi^2/6 - Sum_{h=1..k} 1/h^2 < 1/n. - Clark Kimberling, Oct 02 2014
Determinants of the spiral knots S(2,k,(1)). a(k) = det(S(2,k,(1))). These knots are also the torus knots T(2,k). - Ryan Stees, Dec 15 2014
As a function, the restriction of the identity map on the nonnegative integers {0,1,2,3...}, A001477, to the positive integers {1,2,3,...}. - M. F. Hasler, Jan 18 2015
See also A131685(k) = smallest positive number m such that c(i) = m (i^1 + 1) (i^2 + 2) ... (i^k+ k) / k! takes integral values for all i>=0: For k=1, A131685(k)=1, which implies that this is a well defined integer sequence. - Alexander R. Povolotsky, Apr 24 2015
a(n) is the number of compositions of n+2 into n parts avoiding the part 2. - Milan Janjic, Jan 07 2016
Does not satisfy Benford's law [Berger-Hill, 2017] - N. J. A. Sloane, Feb 07 2017
Parametrization for the finite multisubsets of the positive integers, where, for p_j the j-th prime, n = Product_{j} p_j^(e_j) corresponds to the multiset containing e_j copies of j ('Heinz encoding' -- see A056239, A003963, A289506, A289507, A289508, A289509). - Christopher J. Smyth, Jul 31 2017
The arithmetic function v_1(n,1) as defined in A289197. - Robert Price, Aug 22 2017
For n >= 3, a(n)=n is the least area that can be obtained for an irregular octagon drawn in a square of n units side, whose sides are parallel to the axes, with 4 vertices that coincide with the 4 vertices of the square, and the 4 remaining vertices having integer coordinates. See Affaire de Logique link. - Michel Marcus, Apr 28 2018
a(n+1) is the order of rowmotion on a poset defined by a disjoint union of chains of length n. - Nick Mayers, Jun 08 2018
Number of 1's in n-th generation of 1-D Cellular Automata using Rules 50, 58, 114, 122, 178, 186, 206, 220, 238, 242, 250 or 252 in the Wolfram numbering scheme, started with a single 1. - Frank Hollstein, Mar 25 2019
(1, 2, 3, 4, 5, ...) is the fourth INVERT transform of (1, -2, 3, -4, 5, ...). - Gary W. Adamson, Jul 15 2019

References

  • T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 1.
  • T. M. Apostol, Modular Functions and Dirichlet Series in Number Theory, Springer-Verlag, 1990, page 25.
  • John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See p. 22.
  • W. Fulton and J. Harris, Representation theory: a first course, (1991), page 149. [From Leonid Bedratyuk, Jan 04 2010]
  • I. S. Gradstein and I. M. Ryshik, Tables of series, products, and integrals, Volume 1, Verlag Harri Deutsch, 1981.
  • R. E. Schwartz, You Can Count on Monsters: The First 100 numbers and Their Characters, A. K. Peters and MAA, 2010.
  • 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).

Links

Crossrefs

A001477 = nonnegative numbers.
Partial sums of A000012.
Cf. A001478, A001906, A007931, A007932, A027641, A074909, A089353 (multisets), A178568, A194807.
Cf. A026081 = integers in reverse alphabetical order in U.S. English, A107322 = English name for number and its reverse have the same number of letters, A119796 = zero through ten in alphabetical order of English reverse spelling, A005589, etc. Cf. A185787 (includes a list of sequences based on the natural number array A000027).
Cf. Boustrophedon transforms: A000737, A231179;
Cf. A038722 (mirrored when seen as triangle), A056011 (boustrophedon).
Cf. A048993, A048994, A000110 (see the Feb 03 2015 formula).
Cf. A289187, A000010, A008683, A000203, A049310.

Programs

Formula

a(2k+1) = A005408(k), k >= 0, a(2k) = A005843(k), k >= 1.
Multiplicative with a(p^e) = p^e. - David W. Wilson, Aug 01 2001
Another g.f.: Sum_{n>0} phi(n)*x^n/(1-x^n) (Apostol).
When seen as an array: T(k, n) = n+1 + (k+n)*(k+n+1)/2. Main diagonal is 2n*(n+1)+1 (A001844), antidiagonal sums are n*(n^2+1)/2 (A006003). - Ralf Stephan, Oct 17 2004
Dirichlet generating function: zeta(s-1). - Franklin T. Adams-Watters, Sep 11 2005
G.f.: x/(1-x)^2. E.g.f.: x*exp(x). a(n)=n. a(-n)=-a(n).
Series reversion of g.f. A(x) is x*C(-x)^2 where C(x) is the g.f. of A000108. - Michael Somos, Sep 04 2006
G.f. A(x) satisfies 0 = f(A(x), A(x^2)) where f(u, v) = u^2 - v - 4*u*v. - Michael Somos, Oct 03 2006
Convolution of A000012 (the all-ones sequence) with itself. - Tanya Khovanova, Jun 22 2007
a(n) = 2*a(n-1)-a(n-2); a(1)=1, a(2)=2. a(n) = 1+a(n-1). - Philippe Deléham, Nov 03 2008
a(n) = A000720(A000040(n)). - Juri-Stepan Gerasimov, Nov 29 2009
a(n+1) = Sum_{k=0..n} A101950(n,k). - Philippe Deléham, Feb 10 2012
a(n) = Sum_{d | n} phi(d) = Sum_{d | n} A000010(d). - Jaroslav Krizek, Apr 20 2012
G.f.: x * Product_{j>=0} (1+x^(2^j))^2 = x * (1+2*x+x^2) * (1+2*x^2+x^4) * (1+2*x^4+x^8) * ... = x + 2x^2 + 3x^3 + ... . - Gary W. Adamson, Jun 26 2012
a(n) = det(binomial(i+1,j), 1 <= i,j <= n). - Mircea Merca, Apr 06 2013
E.g.f.: x*E(0), where E(k) = 1 + 1/(x - x^3/(x^2 + (k+1)/E(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 03 2013
From Wolfdieter Lang, Oct 09 2013: (Start)
a(n) = Product_{k=1..n-1} 2*sin(Pi*k/n), n > 1.
a(n) = Product_{k=1..n-1} (2*sin(Pi*k/(2*n)))^2, n > 1.
These identities are used in the calculation of products of ratios of lengths of certain lines in a regular n-gon. For the first identity see the Gradstein-Ryshik reference, p. 62, 1.392 1., bringing the first factor there to the left hand side and taking the limit x -> 0 (L'Hôpital). The second line follows from the first one. Thanks to Seppo Mustonen who led me to consider n-gon lengths products. (End)
a(n) = Sum_{j=0..k} (-1)^(j-1)*j*binomial(n,j)*binomial(n-1+k-j,k-j), k>=0. - Mircea Merca, Jan 25 2014
a(n) = A052410(n)^A052409(n). - Reinhard Zumkeller, Apr 06 2014
a(n) = Sum_{k=1..n^2+2*n} 1/(sqrt(k)+sqrt(k+1)). - Pierre CAMI, Apr 25 2014
a(n) = floor(1/sin(1/n)) = floor(cot(1/(n+1))) = ceiling(cot(1/n)). - Clark Kimberling, Oct 08 2014
a(n) = floor(1/(log(n+1)-log(n))). - Thomas Ordowski, Oct 10 2014
a(k) = det(S(2,k,1)). - Ryan Stees, Dec 15 2014
a(n) = 1/(1/(n+1) + 1/(n+1)^2 + 1/(n+1)^3 + ...). - Pierre CAMI, Jan 22 2015
a(n) = Sum_{m=0..n-1} Stirling1(n-1,m)*Bell(m+1), for n >= 1. This corresponds to Bell(m+1) = Sum_{k=0..m} Stirling2(m, k)*(k+1), for m >= 0, from the fact that Stirling2*Stirling1 = identity matrix. See A048993, A048994 and A000110. - Wolfdieter Lang, Feb 03 2015
a(n) = Sum_{k=1..2n-1}(-1)^(k+1)*k*(2n-k). In addition, surprisingly, a(n) = Sum_{k=1..2n-1}(-1)^(k+1)*k^2*(2n-k)^2. - Charlie Marion, Jan 05 2016
G.f.: x/(1-x)^2 = (x * r(x) *r(x^3) * r(x^9) * r(x^27) * ...), where r(x) = (1 + x + x^2)^2 = (1 + 2x + 3x^2 + 2x^3 + x^4). - Gary W. Adamson, Jan 11 2017
a(n) = floor(1/(Pi/2-arctan(n))). - Clark Kimberling, Mar 11 2020
a(n) = Sum_{d|n} mu(n/d)*sigma(d). - Ridouane Oudra, Oct 03 2020
a(n) = Sum_{k=1..n} phi(gcd(n,k))/phi(n/gcd(n,k)). - Richard L. Ollerton, May 09 2021
a(n) = S(n-1, 2), with the Chebyshev S-polynomials A049310. - Wolfdieter Lang, Mar 09 2023
From Peter Bala, Nov 02 2024: (Start)
For positive integer m, a(n) = (1/m)* Sum_{k = 1..2*m*n-1} (-1)^(k+1) * k * (2*m*n - k) = (1/m) * Sum_{k = 1..2*m*n-1} (-1)^(k+1) * k^2 * (2*m*n - k)^2 (the case m = 1 is given above).
a(n) = Sum_{k = 0..3*n} (-1)^(n+k+1) * k * binomial(3*n+k, 2*k). (End)

Extensions

Links edited by Daniel Forgues, Oct 07 2009.

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

Original entry on oeis.org

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

Views

Author

N. J. A. Sloane

Keywords

Comments

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

Examples

			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

References

  • 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.

Links

Crossrefs

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).

Programs

  • Haskell
    a000225 = (subtract 1) . (2 ^)
a000225_list = iterate ((+ 1) . (* 2)) 0
-- Reinhard Zumkeller, Mar 20 2012
  • Maple
    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)
  • Mathematica
    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 *)
  • PARI
    A000225(n) = 2^n-1  \\ Michael B. Porter, Oct 27 2009
  • PARI
    concat(0, Vec(x/((1-2*x)*(1-x)) + O(x^100))) \\ Altug Alkan, Oct 28 2015
  • Python
    def A000225(n): return (1<Chai Wah Wu, Jul 06 2022
  • SageMath
    def isMersenne(n): return n == sum([(1 - b) << s for (s, b) in enumerate((n+1).bits())]) # Peter Luschny, Sep 01 2019

Formula

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)

Extensions

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

A000984 Central binomial coefficients: binomial(2*n,n) = (2*n)!/(n!)^2.

Original entry on oeis.org

1, 2, 6, 20, 70, 252, 924, 3432, 12870, 48620, 184756, 705432, 2704156, 10400600, 40116600, 155117520, 601080390, 2333606220, 9075135300, 35345263800, 137846528820, 538257874440, 2104098963720, 8233430727600, 32247603683100, 126410606437752, 495918532948104, 1946939425648112
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Devadoss refers to these numbers as type B Catalan numbers (cf. A000108).
Equal to the binomial coefficient sum Sum_{k=0..n} binomial(n,k)^2.
Number of possible interleavings of a program with n atomic instructions when executed by two processes. - Manuel Carro (mcarro(AT)fi.upm.es), Sep 22 2001
Convolving a(n) with itself yields A000302, the powers of 4. - T. D. Noe, Jun 11 2002
Number of ordered trees with 2n+1 edges, having root of odd degree and nonroot nodes of outdegree 0 or 2. - Emeric Deutsch, Aug 02 2002
Also number of directed, convex polyominoes having semiperimeter n+2.
Also number of diagonally symmetric, directed, convex polyominoes having semiperimeter 2n+2. - Emeric Deutsch, Aug 03 2002
The second inverse binomial transform of this sequence is this sequence with interpolated zeros. Its g.f. is (1 - 4*x^2)^(-1/2), with n-th term C(n,n/2)(1+(-1)^n)/2. - Paul Barry, Jul 01 2003
Number of possible values of a 2n-bit binary number for which half the bits are on and half are off. - Gavin Scott (gavin(AT)allegro.com), Aug 09 2003
Ordered partitions of n with zeros to n+1, e.g., for n=4 we consider the ordered partitions of 11110 (5), 11200 (30), 13000 (20), 40000 (5) and 22000 (10), total 70 and a(4)=70. See A001700 (esp. Mambetov Bektur's comment). - Jon Perry, Aug 10 2003
Number of nondecreasing sequences of n integers from 0 to n: a(n) = Sum_{i_1=0..n} Sum_{i_2=i_1..n}...Sum_{i_n=i_{n-1}..n}(1). - J. N. Bearden (jnb(AT)eller.arizona.edu), Sep 16 2003
Number of peaks at odd level in all Dyck paths of semilength n+1. Example: a(2)=6 because we have U*DU*DU*D, U*DUUDD, UUDDU*D, UUDUDD, UUU*DDD, where U=(1,1), D=(1,-1) and * indicates a peak at odd level. Number of ascents of length 1 in all Dyck paths of semilength n+1 (an ascent in a Dyck path is a maximal string of up steps). Example: a(2)=6 because we have uDuDuD, uDUUDD, UUDDuD, UUDuDD, UUUDDD, where an ascent of length 1 is indicated by a lower case letter. - Emeric Deutsch, Dec 05 2003
a(n-1) = number of subsets of 2n-1 distinct elements taken n at a time that contain a given element. E.g., n=4 -> a(3)=20 and if we consider the subsets of 7 taken 4 at a time with a 1 we get (1234, 1235, 1236, 1237, 1245, 1246, 1247, 1256, 1257, 1267, 1345, 1346, 1347, 1356, 1357, 1367, 1456, 1457, 1467, 1567) and there are 20 of them. - Jon Perry, Jan 20 2004
The dimension of a particular (necessarily existent) absolutely universal embedding of the unitary dual polar space DSU(2n,q^2) where q>2. - J. Taylor (jt_cpp(AT)yahoo.com), Apr 02 2004.
Number of standard tableaux of shape (n+1, 1^n). - Emeric Deutsch, May 13 2004
Erdős, Graham et al. conjectured that a(n) is never squarefree for sufficiently large n (cf. Graham, Knuth, Patashnik, Concrete Math., 2nd ed., Exercise 112). Sárközy showed that if s(n) is the square part of a(n), then s(n) is asymptotically (sqrt(2)-2) * (sqrt(n)) * zeta(1/2). Granville and Ramare proved that the only squarefree values are a(1)=2, a(2)=6 and a(4)=70. - Jonathan Vos Post, Dec 04 2004 [For more about this conjecture, see A261009. - N. J. A. Sloane, Oct 25 2015]
The MathOverflow link contains the following comment (slightly edited): The Erdős squarefree conjecture (that a(n) is never squarefree for n>4) was proved in 1980 by Sárközy, A. (On divisors of binomial coefficients. I. J. Number Theory 20 (1985), no. 1, 70-80.) who showed that the conjecture holds for all sufficiently large values of n, and by A. Granville and O. Ramaré (Explicit bounds on exponential sums and the scarcity of squarefree binomial coefficients. Mathematika 43 (1996), no. 1, 73-107) who showed that it holds for all n>4. - Fedor Petrov, Nov 13 2010. [From N. J. A. Sloane, Oct 29 2015]
p divides a((p-1)/2)-1=A030662(n) for prime p=5, 13, 17, 29, 37, 41, 53, 61, 73, 89, 97, ... = A002144(n) Pythagorean primes: primes of form 4n+1. - Alexander Adamchuk, Jul 04 2006
The number of direct routes from my home to Granny's when Granny lives n blocks south and n blocks east of my home in Grid City. To obtain a direct route, from the 2n blocks, choose n blocks on which one travels south. For example, a(2)=6 because there are 6 direct routes: SSEE, SESE, SEES, EESS, ESES and ESSE. - Dennis P. Walsh, Oct 27 2006
Inverse: With q = -log(log(16)/(pi a(n)^2)), ceiling((q + log(q))/log(16)) = n. - David W. Cantrell (DWCantrell(AT)sigmaxi.net), Feb 26 2007
Number of partitions with Ferrers diagrams that fit in an n X n box (including the empty partition of 0). Example: a(2) = 6 because we have: empty, 1, 2, 11, 21 and 22. - Emeric Deutsch, Oct 02 2007
So this is the 2-dimensional analog of A008793. - William Entriken, Aug 06 2013
The number of walks of length 2n on an infinite linear lattice that begins and ends at the origin. - Stefan Hollos (stefan(AT)exstrom.com), Dec 10 2007
The number of lattice paths from (0,0) to (n,n) using steps (1,0) and (0,1). - Joerg Arndt, Jul 01 2011
Integral representation: C(2n,n)=1/Pi Integral [(2x)^(2n)/sqrt(1 - x^2),{x,-1, 1}], i.e., C(2n,n)/4^n is the moment of order 2n of the arcsin distribution on the interval (-1,1). - N-E. Fahssi, Jan 02 2008
Also the Catalan transform of A000079. - R. J. Mathar, Nov 06 2008
Straub, Amdeberhan and Moll: "... it is conjectured that there are only finitely many indices n such that C_n is not divisible by any of 3, 5, 7 and 11." - Jonathan Vos Post, Nov 14 2008
Equals INVERT transform of A081696: (1, 1, 3, 9, 29, 97, 333, ...). - Gary W. Adamson, May 15 2009
Also, in sports, the number of ordered ways for a "Best of 2n-1 Series" to progress. For example, a(2) = 6 means there are six ordered ways for a "best of 3" series to progress. If we write A for a win by "team A" and B for a win by "team B" and if we list the played games chronologically from left to right then the six ways are AA, ABA, BAA, BB, BAB, and ABB. (Proof: To generate the a(n) ordered ways: Write down all a(n) ways to designate n of 2n games as won by team A. Remove the maximal suffix of identical letters from each of these.) - Lee A. Newberg, Jun 02 2009
Number of n X n binary arrays with rows, considered as binary numbers, in nondecreasing order, and columns, considered as binary numbers, in nonincreasing order. - R. H. Hardin, Jun 27 2009
Hankel transform is 2^n. - Paul Barry, Aug 05 2009
It appears that a(n) is also the number of quivers in the mutation class of twisted type BC_n for n>=2.
Central terms of Pascal's triangle: a(n) = A007318(2*n,n). - Reinhard Zumkeller, Nov 09 2011
Number of words on {a,b} of length 2n such that no prefix of the word contains more b's than a's. - Jonathan Nilsson, Apr 18 2012
From Pascal's triangle take row(n) with terms in order a1,a2,..a(n) and row(n+1) with terms b1,b2,..b(n), then 2*(a1*b1 + a2*b2 + ... + a(n)*b(n)) to get the terms in this sequence. - J. M. Bergot, Oct 07 2012. For example using rows 4 and 5: 2*(1*(1) + 4*(5) + 6*(10) + 4*(10) + 1*(5)) = 252, the sixth term in this sequence.
Take from Pascal's triangle row(n) with terms b1, b2, ..., b(n+1) and row(n+2) with terms c1, c2, ..., c(n+3) and find the sum b1*c2 + b2*c3 + ... + b(n+1)*c(n+2) to get A000984(n+1). Example using row(3) and row(5) gives sum 1*(5)+3*(10)+3*(10)+1*(5) = 70 = A000984(4). - J. M. Bergot, Oct 31 2012
a(n) == 2 mod n^3 iff n is a prime > 3. (See Mestrovic link, p. 4.) - Gary Detlefs, Feb 16 2013
Conjecture: For any positive integer n, the polynomial sum_{k=0}^n a(k)x^k is irreducible over the field of rational numbers. In general, for any integer m>1 and n>0, the polynomial f_{m,n}(x) = Sum_{k=0..n} (m*k)!/(k!)^m*x^k is irreducible over the field of rational numbers. - Zhi-Wei Sun, Mar 23 2013
This comment generalizes the comment dated Oct 31 2012 and the second of the sequence's original comments. For j = 1 to n, a(n) = Sum_{k=0..j} C(j,k)* C(2n-j, n-k) = 2*Sum_{k=0..j-1} C(j-1,k)*C(2n-j, n-k). - Charlie Marion, Jun 07 2013
The differences between consecutive terms of the sequence of the quotients between consecutive terms of this sequence form a sequence containing the reciprocals of the triangular numbers. In other words, a(n+1)/a(n)-a(n)/a(n-1) = 2/(n*(n+1)). - Christian Schulz, Jun 08 2013
Number of distinct strings of length 2n using n letters A and n letters B. - Hans Havermann, May 07 2014
From Fung Lam, May 19 2014: (Start)
Expansion of G.f. A(x) = 1/(1+q*x*c(x)), where parameter q is positive or negative (except q=-1), and c(x) is the g.f. of A000108 for Catalan numbers. The case of q=-1 recovers the g.f. of A000108 as xA^2-A+1=0. The present sequence A000984 refers to q=-2. Recurrence: (1+q)*(n+2)*a(n+2) + ((q*q-4*q-4)*n + 2*(q*q-q-1))*a(n+1) - 2*q*q*(2*n+1)*a(n) = 0, a(0)=1, a(1)=-q. Asymptotics: a(n) ~ ((q+2)/(q+1))*(q^2/(-q-1))^n, q<=-3, a(n) ~ (-1)^n*((q+2)/(q+1))*(q^2/(q+1))^n, q>=5, and a(n) ~ -Kq*2^(2*n)/sqrt(Pi*n^3), where the multiplicative constant Kq is given by K1=1/9 (q=1), K2=1/8 (q=2), K3=3/25 (q=3), K4=1/9 (q=4). These formulas apply to existing sequences A126983 (q=1), A126984 (q=2), A126982 (q=3), A126986 (q=4), A126987 (q=5), A127017 (q=6), A127016 (q=7), A126985 (q=8), A127053 (q=9), and to A007854 (q=-3), A076035 (q=-4), A076036 (q=-5), A127628 (q=-6), A126694 (q=-7), A115970 (q=-8). (End)
a(n)*(2^n)^(j-2) equals S(n), where S(n) is the n-th number in the self-convolved sequence which yields the powers of 2^j for all integers j, n>=0. For example, when n=5 and j=4, a(5)=252; 252*(2^5)^(4-2) = 252*1024 = 258048. The self-convolved sequence which yields powers of 16 is {1, 8, 96, 1280, 17920, 258048, ...}; i.e., S(5) = 258048. Note that the convolved sequences will be composed of numbers decreasing from 1 to 0, when j<2 (exception being j=1, where the first two numbers in the sequence are 1 and all others decreasing). - Bob Selcoe, Jul 16 2014
The variance of the n-th difference of a sequence of pairwise uncorrelated random variables each with variance 1. - Liam Patrick Roche, Jun 04 2015
Number of ordered trees with n edges where vertices at level 1 can be of 2 colors. Indeed, the standard decomposition of ordered trees leading to the equation C = 1 + zC^2 (C is the Catalan function), yields this time G = 1 + 2zCG, from where G = 1/sqrt(1-4z). - Emeric Deutsch, Jun 17 2015
Number of monomials of degree at most n in n variables. - Ran Pan, Sep 26 2015
Let V(n, r) denote the volume of an n-dimensional sphere with radius r, then V(n, 2^n) / Pi = V(n-1, 2^n) * a(n/2) for all even n. - Peter Luschny, Oct 12 2015
a(n) is the number of sets {i1,...,in} of length n such that n >= i1 >= i2 >= ... >= in >= 0. For instance, a(2) = 6 as there are only 6 such sets: (2,2) (2,1) (2,0) (1,1) (1,0) (0,0). - Anton Zakharov, Jul 04 2016
From Ralf Steiner, Apr 07 2017: (Start)
By analytic continuation to the entire complex plane there exist regularized values for divergent sums such as:
Sum_{k>=0} a(k)/(-2)^k = 1/sqrt(3).
Sum_{k>=0} a(k)/(-1)^k = 1/sqrt(5).
Sum_{k>=0} a(k)/(-1/2)^k = 1/3.
Sum_{k>=0} a(k)/(1/2)^k = -1/sqrt(7)i.
Sum_{k>=0} a(k)/(1)^k = -1/sqrt(3)i.
Sum_{k>=0} a(k)/2^k = -i. (End)
Number of sequences (e(1), ..., e(n+1)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) > e(j). [Martinez and Savage, 2.18] - Eric M. Schmidt, Jul 17 2017
The o.g.f. for the sequence equals the diagonal of any of the following the rational functions: 1/(1 - (x + y)), 1/(1 - (x + y*z)), 1/(1 - (x + x*y + y*z)) or 1/(1 - (x + y + y*z)). - Peter Bala, Jan 30 2018
From Colin Defant, Sep 16 2018: (Start)
Let s denote West's stack-sorting map. a(n) is the number of permutations pi of [n+1] such that s(pi) avoids the patterns 132, 231, and 321. a(n) is also the number of permutations pi of [n+1] such that s(pi) avoids the patterns 132, 312, and 321.
a(n) is the number of permutations of [n+1] that avoid the patterns 1342, 3142, 3412, and 3421. (End)
All binary self-dual codes of length 4n, for n>0, must contain at least a(n) codewords of weight 2n. More to the point, there will always be at least one, perhaps unique, binary self-dual code of length 4n that will contain exactly a(n) codewords that have a hamming weight equal to half the length of the code (2n). This code can be constructed by direct summing the unique binary self-dual code of length 2 (up to permutation equivalence) to itself an even number of times. A permutation equivalent code can be constructed by augmenting two identity matrices of length 2n together. - Nathan J. Russell, Nov 25 2018
From Isaac Saffold, Dec 28 2018: (Start)
Let [b/p] denote the Legendre symbol and 1/b denote the inverse of b mod p. Then, for m and n, where n is not divisible by p,
[(m+n)/p] == [n/p]*Sum_{k=0..(p-1)/2} (-m/(4*n))^k * a(k) (mod p).
Evaluating this identity for m = -1 and n = 1 demonstrates that, for all odd primes p, Sum_{k=0..(p-1)/2} (1/4)^k * a(k) is divisible by p. (End)
Number of vertices of the subgraph of the (2n-1)-dimensional hypercube induced by all bitstrings with n-1 or n many 1s. The middle levels conjecture asserts that this graph has a Hamilton cycle. - Torsten Muetze, Feb 11 2019
a(n) is the number of walks of length 2n from the origin with steps (1,1) and (1,-1) that stay on or above the x-axis. Equivalently, a(n) is the number of walks of length 2n from the origin with steps (1,0) and (0,1) that stay in the first octant. - Alexander Burstein, Dec 24 2019
Number of permutations of length n>0 avoiding the partially ordered pattern (POP) {3>1, 1>2} of length 4. That is, number of length n permutations having no subsequences of length 4 in which the first element is larger than the second element but smaller than the third elements. - Sergey Kitaev, Dec 08 2020
From Gus Wiseman, Jul 21 2021: (Start)
Also the number of integer compositions of 2n+1 with alternating sum 1, where the alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i. For example, the a(0) = 1 through a(2) = 6 compositions are:
(1) (2,1) (3,2)
(1,1,1) (1,2,2)
(2,2,1)
(1,1,2,1)
(2,1,1,1)
(1,1,1,1,1)
The following relate to these compositions:
- The unordered version is A000070.
- The alternating sum -1 version is counted by A001791, ranked by A345910/A345912.
- The alternating sum 0 version is counted by A088218, ranked by A344619.
- Including even indices gives A126869.
- The complement is counted by A202736.
- Ranked by A345909 (reverse: A345911).
Equivalently, a(n) counts binary numbers with 2n+1 digits and one more 1 than 0's. For example, the a(2) = 6 binary numbers are: 10011, 10101, 10110, 11001, 11010, 11100.
(End)
From Michael Wallner, Jan 25 2022: (Start)
a(n) is the number of nx2 Young tableaux with a single horizontal wall between the first and second column. If there is a wall between two cells, the entries may be decreasing; see [Banderier, Wallner 2021].
Example for a(2)=6:
3 4 2 4 3 4 3|4 4|3 2|4
1|2, 1|3, 2|1, 1 2, 1 2, 1 3
a(n) is also the number of nx2 Young tableaux with n "walls" between the first and second column.
Example for a(2)=6:
3|4 2|4 4|3 3|4 4|3 4|2
1|2, 1|3, 1|2, 2|1, 2|1, 3|1 (End)
From Shel Kaphan, Jan 12 2023: (Start)
a(n)/4^n is the probability that a fair coin tossed 2n times will come up heads exactly n times and tails exactly n times, or that a random walk with steps of +-1 will return to the starting point after 2n steps (not necessarily for the first time). As n becomes large, this number asymptotically approaches 1/sqrt(n*Pi), using Stirling's approximation for n!.
a(n)/(4^n*(2n-1)) is the probability that a random walk with steps of +-1 will return to the starting point for the first time after 2n steps. The absolute value of the n-th term of A144704 is denominator of this fraction.
Considering all possible random walks of exactly 2n steps with steps of +-1, a(n)/(2n-1) is the number of such walks that return to the starting point for the first time after 2n steps. See the absolute values of A002420 or A284016 for these numbers. For comparison, as mentioned by Stefan Hollos, Dec 10 2007, a(n) is the number of such walks that return to the starting point after 2n steps, but not necessarily for the first time. (End)
p divides a((p-1)/2) + 1 for primes p of the form 4*k+3 (A002145). - Jules Beauchamp, Feb 11 2023
Also the size of the shuffle product of two words of length n, such that the union of the two words consist of 2n distinct elements. - Robert C. Lyons, Mar 15 2023
a(n) is the number of vertices of the n-dimensional cyclohedron W_{n+1}. - Jose Bastidas, Mar 25 2025
Consider a stack of pancakes of height n, where the only allowed operation is reversing the top portion of the stack. First, perform a series of reversals of increasing sizes, followed by a series of reversals of decreasing sizes. The number of distinct permutations of the initial stack that can be reached through these operations is a(n). - Thomas Baruchel, May 12 2025

Examples

			G.f.: 1 + 2*x + 6*x^2 + 20*x^3 + 70*x^4 + 252*x^5 + 924*x^6 + ...
For n=2, a(2) = 4!/(2!)^2 = 24/4 = 6, and this is the middle coefficient of the binomial expansion (a + b)^4 = a^4 + 4a^3b + 6a^2b^2 + 4ab^3 + b^4. - _Michael B. Porter_, Jul 06 2016

References

  • M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 828.
  • Arthur T. Benjamin and Jennifer J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A., 2003, id. 160.
  • Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 575, line -3, with a=b=n.
  • John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See p. 101.
  • Emeric Deutsch and Louis W. Shapiro, Seventeen Catalan identities, Bulletin of the Institute of Combinatorics and its Applications, 31 (2001), 31-38.
  • Henry W. Gould, Combinatorial Identities, Morgantown, 1972, (3.66), page 30.
  • Ronald. L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics, Addison-Wesley, Reading, MA, Second Ed., see Exercise 112.
  • Martin Griffiths, The Backbone of Pascal's Triangle, United Kingdom Mathematics Trust (2008), 3-124.
  • Leonard Lipshitz and A. van der Poorten, "Rational functions, diagonals, automata and arithmetic", in Number Theory, Richard A. Mollin, ed., Walter de Gruyter, Berlin (1990), 339-358.
  • J. C. P. Miller, editor, Table of Binomial Coefficients. Royal Society Mathematical Tables, Vol. 3, Cambridge Univ. Press, 1954.
  • 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).

Links

Crossrefs

Cf. A000108, A002420, A002457, A030662, A002144, A135091, A081696, A182400. Differs from A071976 at 10th term.
Bisection of A001405 and of A226302. See also A025565, the same ordered partitions but without all in which are two successive zeros: 11110 (5), 11200 (18), 13000 (2), 40000 (0) and 22000 (1), total 26 and A025565(4)=26.
Cf. A226078, A051924 (first differences).
Row sums of A059481, A008459, A152229, A158815, A205946.
Cf. A258290 (arithmetic derivative). Cf. A098616, A214377.
See A261009 for a conjecture about this sequence.
Cf. A046521 (first column).
The Apéry-like numbers [or Apéry-like sequences, Apery-like numbers, Apery-like sequences] include A000172, A000984, A002893, A002895, A005258, A005259, A005260, A006077, A036917, A063007, A081085, A093388, A125143 (apart from signs), A143003, A143007, A143413, A143414, A143415, A143583, A183204, A214262, A219692,A226535, A227216, A227454, A229111 (apart from signs), A260667, A260832, A262177, A264541, A264542, A279619, A290575, A290576. (The term "Apery-like" is not well-defined.)
Sum_{k = 0..n} C(n,k)^m for m = 1..12: A000079, A000984, A000172, A005260, A005261, A069865, A182421, A182422, A182446, A182447, A342294, A342295.
Cf. A000346, A001700, A001791, A008549, A032443, A073016, A097805, A126869.
Cf. A003418, A056040, A001316, A261130, A356637.

Programs

  • GAP
    List([1..1000], n -> Binomial(2*n,n)); # Muniru A Asiru, Jan 30 2018
  • Haskell
    a000984 n = a007318_row (2*n) !! n  -- Reinhard Zumkeller, Nov 09 2011
  • Magma
    a:= func< n | Binomial(2*n,n) >; [ a(n) : n in [0..10]];
  • Maple
    A000984 := n-> binomial(2*n,n); seq(A000984(n), n=0..30);
with(combstruct); [seq(count([S,{S=Prod(Set(Z,card=i),Set(Z,card=i))}, labeled], size=(2*i)), i=0..20)];
with(combstruct); [seq(count([S,{S=Sequence(Union(Arch,Arch)), Arch=Prod(Epsilon, Sequence(Arch),Z)},unlabeled],size=i), i=0..25)];
with(combstruct):bin := {B=Union(Z,Prod(B,B))}: seq (count([B,bin,unlabeled],size=n)*n, n=1..25); # Zerinvary Lajos, Dec 05 2007
A000984List := proc(m) local A, P, n; A := [1,2]; P := [1];
for n from 1 to m - 2 do P := ListTools:-PartialSums([op(P), 2*P[-1]]);
A := [op(A), 2*P[-1]] od; A end: A000984List(28); # Peter Luschny, Mar 24 2022
  • Mathematica
    Table[Binomial[2n, n], {n, 0, 24}] (* Alonso del Arte, Nov 10 2005 *)
CoefficientList[Series[1/Sqrt[1-4x],{x,0,25}],x]  (* Harvey P. Dale, Mar 14 2011 *)
  • Maxima
    A000984(n):=(2*n)!/(n!)^2$ makelist(A000984(n),n,0,30); /* Martin Ettl, Oct 22 2012 */
  • PARI
    A000984(n)=binomial(2*n,n) \\ much more efficient than (2n)!/n!^2. \\ M. F. Hasler, Feb 26 2014
  • PARI
    fv(n,p)=my(s);while(n\=p,s+=n);s
a(n)=prodeuler(p=2,2*n,p^(fv(2*n,p)-2*fv(n,p))) \\ Charles R Greathouse IV, Aug 21 2013
  • PARI
    fv(n,p)=my(s);while(n\=p,s+=n);s
a(n)=my(s=1);forprime(p=2,2*n,s*=p^(fv(2*n,p)-2*fv(n,p)));s \\ Charles R Greathouse IV, Aug 21 2013
  • Python
    from _future_ import division
A000984_list, b = [1], 1
for n in range(10**3):
    b = b*(4*n+2)//(n+1)
    A000984_list.append(b) # Chai Wah Wu, Mar 04 2016

Formula

a(n)/(n+1) = A000108(n), the Catalan numbers.
G.f.: A(x) = (1 - 4*x)^(-1/2) = 1F0(1/2;;4x).
a(n+1) = 2*A001700(n) = A030662(n) + 1. a(2*n) = A001448(n), a(2*n+1) = 2*A002458(n) =A099976.
D-finite with recurrence: n*a(n) + 2*(1-2*n)*a(n-1)=0.
a(n) = 2^n/n! * Product_{k=0..n-1} (2*k+1).
a(n) = a(n-1)*(4-2/n) = Product_{k=1..n} (4-2/k) = 4*a(n-1) + A002420(n) = A000142(2*n)/(A000142(n)^2) = A001813(n)/A000142(n) = sqrt(A002894(n)) = A010050(n)/A001044(n) = (n+1)*A000108(n) = -A005408(n-1)*A002420(n). - Henry Bottomley, Nov 10 2000
Using Stirling's formula in A000142 it is easy to get the asymptotic expression a(n) ~ 4^n / sqrt(Pi * n). - Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Apr 07 2001
Integral representation as n-th moment of a positive function on the interval [0, 4]: a(n) = Integral_{x=0..4}(x^n*((x*(4-x))^(-1/2))/Pi), n=0, 1, ... This representation is unique. - Karol A. Penson, Sep 17 2001
Sum_{n>=1} 1/a(n) = (2*Pi*sqrt(3) + 9)/27. [Lehmer 1985, eq. (15)] - Benoit Cloitre, May 01 2002 (= A073016. - Bernard Schott, Jul 20 2022)
a(n) = Max_{ (i+j)!/(i!j!) | 0<=i,j<=n }. - Benoit Cloitre, May 30 2002
a(n) = Sum_{k=0..n} binomial(n+k-1,k), row sums of A059481. - Vladeta Jovovic, Aug 28 2002
E.g.f.: exp(2*x)*I_0(2x), where I_0 is Bessel function. - Michael Somos, Sep 08 2002
E.g.f.: I_0(2*x) = Sum a(n)*x^(2*n)/(2*n)!, where I_0 is Bessel function. - Michael Somos, Sep 09 2002
a(n) = Sum_{k=0..n} binomial(n, k)^2. - Benoit Cloitre, Jan 31 2003
Determinant of n X n matrix M(i, j) = binomial(n+i, j). - Benoit Cloitre, Aug 28 2003
Given m = C(2*n, n), let f be the inverse function, so that f(m) = n. Letting q denote -log(log(16)/(m^2*Pi)), we have f(m) = ceiling( (q + log(q)) / log(16) ). - David W. Cantrell (DWCantrell(AT)sigmaxi.net), Oct 30 2003
a(n) = 2*Sum_{k=0..(n-1)} a(k)*a(n-k+1)/(k+1). - Philippe Deléham, Jan 01 2004
a(n+1) = Sum_{j=n..n*2+1} binomial(j, n). E.g., a(4) = C(7,3) + C(6,3) + C(5,3) + C(4,3) + C(3,3) = 35 + 20 + 10 + 4 + 1 = 70. - Jon Perry, Jan 20 2004
a(n) = (-1)^(n)*Sum_{j=0..(2*n)} (-1)^j*binomial(2*n, j)^2. - Helena Verrill (verrill(AT)math.lsu.edu), Jul 12 2004
a(n) = Sum_{k=0..n} binomial(2n+1, k)*sin((2n-2k+1)*Pi/2). - Paul Barry, Nov 02 2004
a(n-1) = (1/2)*(-1)^n*Sum_{0<=i, j<=n}(-1)^(i+j)*binomial(2n, i+j). - Benoit Cloitre, Jun 18 2005
a(n) = C(2n, n-1) + C(n) = A001791(n) + A000108(n). - Lekraj Beedassy, Aug 02 2005
G.f.: c(x)^2/(2*c(x)-c(x)^2) where c(x) is the g.f. of A000108. - Paul Barry, Feb 03 2006
a(n) = A006480(n) / A005809(n). - Zerinvary Lajos, Jun 28 2007
a(n) = Sum_{k=0..n} A106566(n,k)*2^k. - Philippe Deléham, Aug 25 2007
a(n) = Sum_{k>=0} A039599(n, k). a(n) = Sum_{k>=0} A050165(n, k). a(n) = Sum_{k>=0} A059365(n, k)*2^k, n>0. a(n+1) = Sum_{k>=0} A009766(n, k)*2^(n-k+1). - Philippe Deléham, Jan 01 2004
a(n) = 4^n*Sum_{k=0..n} C(n,k)(-4)^(-k)*A000108(n+k). - Paul Barry, Oct 18 2007
a(n) = Sum_{k=0..n} A039598(n,k)*A059841(k). - Philippe Deléham, Nov 12 2008
A007814(a(n)) = A000120(n). - Vladimir Shevelev, Jul 20 2009
From Paul Barry, Aug 05 2009: (Start)
G.f.: 1/(1-2x-2x^2/(1-2x-x^2/(1-2x-x^2/(1-2x-x^2/(1-... (continued fraction);
G.f.: 1/(1-2x/(1-x/(1-x/(1-x/(1-... (continued fraction). (End)
If n>=3 is prime, then a(n) == 2 (mod 2*n). - Vladimir Shevelev, Sep 05 2010
Let A(x) be the g.f. and B(x) = A(-x), then B(x) = sqrt(1-4*x*B(x)^2). - Vladimir Kruchinin, Jan 16 2011
a(n) = (-4)^n*sqrt(Pi)/(gamma((1/2-n))*gamma(1+n)). - Gerry Martens, May 03 2011
a(n) = upper left term in M^n, M = the infinite square production matrix:
2, 2, 0, 0, 0, 0, ...
1, 1, 1, 0, 0, 0, ...
1, 1, 1, 1, 0, 0, ...
1, 1, 1, 1, 1, 0, ...
1, 1, 1, 1, 1, 1, .... - Gary W. Adamson, Jul 14 2011
a(n) = Hypergeometric([-n,-n],[1],1). - Peter Luschny, Nov 01 2011
E.g.f.: hypergeometric([1/2],[1],4*x). - Wolfdieter Lang, Jan 13 2012
a(n) = 2*Sum_{k=0..n-1} a(k)*A000108(n-k-1). - Alzhekeyev Ascar M, Mar 09 2012
G.f.: 1 + 2*x/(U(0)-2*x) where U(k) = 2*(2*k+1)*x + (k+1) - 2*(k+1)*(2*k+3)*x/U(k+1); (continued fraction, Euler's 1st kind, 1-step). - Sergei N. Gladkovskii, Jun 28 2012
a(n) = Sum_{k=0..n} binomial(n,k)^2*H(k)/(2*H(n)-H(2*n)), n>0, where H(n) is the n-th harmonic number. - Gary Detlefs, Mar 19 2013
G.f.: Q(0)*(1-4*x), where Q(k) = 1 + 4*(2*k+1)*x/( 1 - 1/(1 + 2*(k+1)/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 11 2013
G.f.: G(0)/2, where G(k) = 1 + 1/(1 - 2*x*(2*k+1)/(2*x*(2*k+1) + (k+1)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 24 2013
E.g.f.: E(0)/2, where E(k) = 1 + 1/(1 - 2*x/(2*x + (k+1)^2/(2*k+1)/E(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 01 2013
Special values of Jacobi polynomials, in Maple notation: a(n) = 4^n*JacobiP(n,0,-1/2-n,-1). - Karol A. Penson, Jul 27 2013
a(n) = 2^(4*n)/((2*n+1)*Sum_{k=0..n} (-1)^k*C(2*n+1,n-k)/(2*k+1)). - Mircea Merca, Nov 12 2013
a(n) = C(2*n-1,n-1)*C(4*n^2,2)/(3*n*C(2*n+1,3)), n>0. - Gary Detlefs, Jan 02 2014
Sum_{n>=0} a(n)/n! = A234846. - Richard R. Forberg, Feb 10 2014
0 = a(n)*(16*a(n+1) - 6*a(n+2)) + a(n+1)*(-2*a(n+1) + a(n+2)) for all n in Z. - Michael Somos, Sep 17 2014
a(n+1) = 4*a(n) - 2*A000108(n). Also a(n) = 4^n*Product_{k=1..n}(1-1/(2*k)). - Stanislav Sykora, Aug 09 2014
G.f.: Sum_{n>=0} x^n/(1-x)^(2*n+1) * Sum_{k=0..n} C(n,k)^2 * x^k. - Paul D. Hanna, Nov 08 2014
a(n) = (-4)^n*binomial(-1/2,n). - Jean-François Alcover, Feb 10 2015
a(n) = 4^n*hypergeom([-n,1/2],[1],1). - Peter Luschny, May 19 2015
a(n) = Sum_{k=0..floor(n/2)} C(n,k)*C(n-k,k)*2^(n-2*k). - Robert FERREOL, Aug 29 2015
a(n) ~ 4^n*(2-2/(8*n+2)^2+21/(8*n+2)^4-671/(8*n+2)^6+45081/(8*n+2)^8)/sqrt((4*n+1) *Pi). - Peter Luschny, Oct 14 2015
A(-x) = 1/x * series reversion( x*(2*x + sqrt(1 + 4*x^2)) ). Compare with the o.g.f. B(x) of A098616, which satisfies B(-x) = 1/x * series reversion( x*(2*x + sqrt(1 - 4*x^2)) ). See also A214377. - Peter Bala, Oct 19 2015
a(n) = GegenbauerC(n,-n,-1). - Peter Luschny, May 07 2016
a(n) = gamma(1+2*n)/gamma(1+n)^2. - Andres Cicuttin, May 30 2016
Sum_{n>=0} (-1)^n/a(n) = 4*(5 - sqrt(5)*log(phi))/25 = 0.6278364236143983844442267..., where phi is the golden ratio. - Ilya Gutkovskiy, Jul 04 2016
From Peter Bala, Jul 22 2016: (Start)
This sequence occurs as the closed-form expression for several binomial sums:
a(n) = Sum_{k = 0..2*n} (-1)^(n+k)*binomial(2*n,k)*binomial(2*n + 1,k).
a(n) = 2*Sum_{k = 0..2*n-1} (-1)^(n+k)*binomial(2*n - 1,k)*binomial(2*n,k) for n >= 1.
a(n) = 2*Sum_{k = 0..n-1} binomial(n - 1,k)*binomial(n,k) for n >= 1.
a(n) = Sum_{k = 0..2*n} (-1)^k*binomial(2*n,k)*binomial(x + k,n)*binomial(y + k,n) = Sum_{k = 0..2*n} (-1)^k*binomial(2*n,k)*binomial(x - k,n)*binomial(y - k,n) for arbitrary x and y.
For m = 3,4,5,... both Sum_{k = 0..m*n} (-1)^k*binomial(m*n,k)*binomial(x + k,n)*binomial(y + k,n) and Sum_{k = 0..m*n} (-1)^k*binomial(m*n,k)*binomial(x - k,n)*binomial(y - k,n) appear to equal Kronecker's delta(n,0).
a(n) = (-1)^n*Sum_{k = 0..2*n} (-1)^k*binomial(2*n,k)*binomial(x + k,n)*binomial(y - k,n) for arbitrary x and y.
For m = 3,4,5,... Sum_{k = 0..m*n} (-1)^k*binomial(m*n,k)*binomial(x + k,n)*binomial(y - k,n) appears to equal Kronecker's delta(n,0).
a(n) = Sum_{k = 0..2n} (-1)^k*binomial(2*n,k)*binomial(3*n - k,n)^2 = Sum_{k = 0..2*n} (-1)^k*binomial(2*n,k)* binomial(n + k,n)^2. (Gould, Vol. 7, 5.23).
a(n) = Sum_{k = 0..n} (-1)^(n+k)*binomial(2*n,n + k)*binomial(n + k,n)^2. (End)
From Ralf Steiner, Apr 07 2017: (Start)
Sum_{k>=0} a(k)/(p/q)^k = sqrt(p/(p-4q)) for q in N, p in Z/{-4q< (some p) <-2}.
...
Sum_{k>=0} a(k)/(-4)^k = 1/sqrt(2).
Sum_{k>=0} a(k)/(17/4)^k = sqrt(17).
Sum_{k>=0} a(k)/(18/4)^k = 3.
Sum_{k>=0} a(k)/5^k = sqrt(5).
Sum_{k>=0} a(k)/6^k = sqrt(3).
Sum_{k>=0} a(k)/8^k = sqrt(2).
...
Sum_{k>=0} a(k)/(p/q)^k = sqrt(p/(p-4q)) for p>4q.(End)
Boas-Buck recurrence: a(n) = (2/n)*Sum_{k=0..n-1} 4^(n-k-1)*a(k), n >= 1, a(0) = 1. Proof from a(n) = A046521(n, 0). See a comment there. - Wolfdieter Lang, Aug 10 2017
a(n) = Sum_{k = 0..n} (-1)^(n-k) * binomial(2*n+1, k) for n in N. - Rene Adad, Sep 30 2017
a(n) = A034870(n,n). - Franck Maminirina Ramaharo, Nov 26 2018
From Jianing Song, Apr 10 2022: (Start)
G.f. for {1/a(n)}: 4*(sqrt(4-x) + sqrt(x)*arcsin(sqrt(x)/2)) / (4-x)^(3/2).
E.g.f. for {1/a(n)}: 1 + exp(x/4)*sqrt(Pi*x)*erf(sqrt(x)/2)/2.
Sum_{n>=0} (-1)^n/a(n) = 4*(1/5 - arcsinh(1/2)/(5*sqrt(5))). (End)
From Peter Luschny, Sep 08 2022: (Start)
a(n) = 2^(2*n)*Product_{k=1..2*n} k^((-1)^(k+1)) = A056040(2*n).
a(n) = A001316(n) * A356637(n) * A261130(n) for n >= 2. (End)
a(n) = 4^n*binomial(n-1/2,-1/2) = 4^n*GegenbauerC(n,1/4,1). - Gerry Martens, Oct 19 2022
Occurs on the right-hand side of the binomial sum identities Sum_{k = -n..n} (-1)^k * (n + x - k) * binomial(2*n, n+k)^2 = (x + n)*a(n) and Sum_{k = -n..n} (-1)^k * (n + x - k)^2 * binomial(2*n, n+k)^3 = x*(x + 2*n)*a(n) (x arbitrary). Compare with the identity: Sum_{k = -n..n} (-1)^k * binomial(2*n, n+k)^2 = a(n). - Peter Bala, Jul 31 2023
From Peter Bala, Mar 31 2024: (Start)
4^n*a(n) = Sum_{k = 0..2*n} (-1)^k*a(k)*a(2*n-k).
16^n = Sum_{k = 0..2*n} a(k)*a(2*n-k). (End)
From Gary Detlefs, May 28 2024: (Start)
a(n) = Sum_{k=0..floor(n/2)} binomial(n,2k)*binomial(2*k,k)*2^(n-2*k). (H. W. Gould) - Gary Detlefs, May 28 2024
a(n) = Sum_{k=0..2*n} (-1)^k*binomial(2n,k)*binomial(2*n+2*k,n+k)*3^(2*n-k). (H. W. Gould) (End)
a(n) = Product_{k>=n+1} k^2/(k^2 - n^2). - Antonio Graciá Llorente, Sep 08 2024
a(n) = Product_{k=1..n} A003418(floor(2*n/k))^((-1)^(k+1)) (Golomb, 2003). - Amiram Eldar, Aug 08 2025

A000302 Powers of 4: a(n) = 4^n.

Original entry on oeis.org

1, 4, 16, 64, 256, 1024, 4096, 16384, 65536, 262144, 1048576, 4194304, 16777216, 67108864, 268435456, 1073741824, 4294967296, 17179869184, 68719476736, 274877906944, 1099511627776, 4398046511104, 17592186044416, 70368744177664, 281474976710656
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Same as Pisot sequences E(1, 4), L(1, 4), P(1, 4), T(1, 4). Essentially same as Pisot sequences E(4, 16), L(4, 16), P(4, 16), T(4, 16). See A008776 for definitions of Pisot sequences.
The convolution square root of this sequence is A000984, the central binomial coefficients: C(2n,n). - T. D. Noe, Jun 11 2002
With P(n) being the number of integer partitions of n, p(i) as the number of parts of the i-th partition of n, d(i) as the number of different parts of the i-th partition of n, m(i, j) the multiplicity of the j-th part of the i-th partition of n, one has a(n) = Sum_{i = 1..P(n)} p(i)!/(Product_{j = 1..d(i)} m(i, j)!) * 2^(n-1). - Thomas Wieder, May 18 2005
Sums of rows of the triangle in A122366. - Reinhard Zumkeller, Aug 30 2006
Hankel transform of A076035. - Philippe Deléham, Feb 28 2009
Equals the Catalan sequence: (1, 1, 2, 5, 14, ...), convolved with A032443: (1, 3, 11, 42, ...). - Gary W. Adamson, May 15 2009
Sum of coefficients of expansion of (1 + x + x^2 + x^3)^n.
a(n) is number of compositions of natural numbers into n parts less than 4. For example, a(2) = 16 since there are 16 compositions of natural numbers into 2 parts less than 4.
The compositions of n in which each natural number is colored by one of p different colors are called p-colored compositions of n. For n >= 1, a(n) equals the number of 4-colored compositions of n such that no adjacent parts have the same color. - Milan Janjic, Nov 17 2011
Squares in A002984. - Reinhard Zumkeller, Dec 28 2011
Row sums of Pascal's triangle using the rule that going left increases the value by a factor of k = 3. For example, the first three rows are {1}, {3, 1}, and {9, 6, 1}. Using this rule gives row sums as (k+1)^n. - Jon Perry, Oct 11 2012
First differences of A002450. - Omar E. Pol, Feb 20 2013
Sum of all peak heights in Dyck paths of semilength n+1. - David Scambler, Apr 22 2013
Powers of 4 exceed powers of 2 by A020522 which is the m-th oblong number A002378(m), m being the n-th Mersenne number A000225(n); hence, we may write, a(n) = A000079(n) + A002378(A000225(n)). - Lekraj Beedassy, Jan 17 2014
a(n) is equal to 1 plus the sum for 0 < k < 2^n of the numerators and denominators of the reduced fractions k/2^n. - J. M. Bergot, Jul 13 2015
Binomial transform of A000244. - Tony Foster III, Oct 01 2016
From Ilya Gutkovskiy, Oct 01 2016: (Start)
Number of nodes at level n regular 4-ary tree.
Partial sums of A002001. (End)
Satisfies Benford's law [Berger-Hill, 2011]. - N. J. A. Sloane, Feb 08 2017
Also the number of connected dominating sets in the (n+1)-barbell graph. - Eric W. Weisstein, Jun 29 2017
Side length of the cells at level n in a pyramid scheme where a square grid is decomposed into overlapping 2 X 2 blocks (cf. Kropatsch, 1985). - Felix Fröhlich, Jul 04 2019
a(n-1) is the number of 3-compositions of n; see Hopkins & Ouvry reference. - Brian Hopkins, Aug 15 2020

References

  • H. W. Gould, Combinatorial Identities, 1972, eq. (1.93), p. 12.
  • R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 2nd. ed., 1994, eq. (5.39), p. 187.
  • D. Phulara and L. W. Shapiro, Descendants in ordered trees with a marked vertex, Congressus Numerantium, 205 (2011), 121-128.
  • 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).
  • S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 55.

Links

Crossrefs

Cf. A024036, A052539, A032443, A000351 (Binomial transform).
Cf. A249307.
Cf. A083420.

Programs

Formula

a(n) = 4^n.
a(0) = 1; a(n) = 4*a(n-1).
G.f.: 1/(1-4*x).
E.g.f.: exp(4*x).
a(n) = Sum_{k = 0..n} binomial(2k, k) * binomial(2(n - k), n - k). - Benoit Cloitre, Jan 26 2003 [See Graham et al., eq. (5.39), p. 187. - Wolfdieter Lang, Aug 16 2019]
1 = Sum_{n >= 1} 3/a(n) = 3/4 + 3/16 + 3/64 + 3/256 + 3/1024, ...; with partial sums: 3/4, 15/16, 63/64, 255/256, 1023/1024, ... - Gary W. Adamson, Jun 16 2003
a(n) = A001045(2*n) + A001045(2*n+1). - Paul Barry, Apr 27 2004
A000005(a(n)) = A005408(n+1). - Reinhard Zumkeller, Mar 04 2007
a(n) = Sum_{j = 0..n} 2^(n - j)*binomial(n + j, j). - Peter C. Heinig (algorithms(AT)gmx.de), Apr 06 2007
Hankel transform of A115967. - Philippe Deléham, Jun 22 2007
a(n) = 6*Stirling2(n+1, 4) + 6*Stirling2(n+1, 3) + 3*Stirling2(n+1, 2) + 1 = 2*Stirling2(2^n, 2^n - 1) + Stirling2(n+1, 2) + 1. - Ross La Haye, Jun 26 2008
a(n) = A159991(n)/A001024(n) = A047653(n) + A181765(n). A160700(a(n)) = A010685(n). - Reinhard Zumkeller, May 02 2009
a(n) = A188915(A006127(n)). - Reinhard Zumkeller, Apr 14 2011
a(n) = Sum_{k = 0..n} binomial(2*n+1, k). - Mircea Merca, Jun 25 2011
Sum_{n >= 1} Mobius(n)/a(n) = 0.1710822479183... - R. J. Mathar, Aug 12 2012
a(n) = Sum_{k = 0..n} binomial(2*k + x, k)*binomial(2*(n - k) - x, n - k) for every real number x. - Rui Duarte and António Guedes de Oliveira, Feb 16 2013
a(n) = 5*a(n - 1) - 4*a(n - 2). - Jean-Bernard François, Sep 12 2013
a(n) = (2*n+1) * binomial(2*n,n) * Sum_{j=0..n} (-1)^j/(2*j+1)*binomial(n,j). - Vaclav Kotesovec, Sep 15 2013
a(n) = A000217(2^n - 1) + A000217(2^n). - J. M. Bergot, Dec 28 2014
a(n) = (2^n)^2 = A000079(n)^2. - Doug Bell, Jun 23 2015
a(n) = A002063(n)/3 - A004171(n). - Zhandos Mambetaliyev, Nov 19 2016
a(n) = (1/2) * Product_{k = 0..n} (1 + (2*n + 1)/(2*k + 1)). - Peter Bala, Mar 06 2018
a(n) = A001045(n+1)*A001045(n+2) + A001045(n)^2. - Ezhilarasu Velayutham, Aug 30 2019
a(n) = denominator(zeta_star({2}(n + 1))/zeta(2*n + 2)) where zeta_star is the multiple zeta star values and ({2}_n) represents (2, ..., 2) where the multiplicity of 2 is n. - _Roudy El Haddad, Feb 22 2022
a(n) = 1 + 3*Sum_{k=0..n} binomial(2*n, n+k)*(k|9), where (k|9) is the Jacobi symbol. - Greg Dresden, Oct 11 2022
a(n) = Sum_{k = 0..n} binomial(2*n+1, 2*k) = Sum_{k = 0..n} binomial(2*n+1, 2*k+1). - Sela Fried, Mar 23 2023

Extensions

Partially edited by Joerg Arndt, Mar 11 2010

A000124 Central polygonal numbers (the Lazy Caterer's sequence): n(n+1)/2 + 1; or, maximal number of pieces formed when slicing a pancake with n cuts.

Original entry on oeis.org

1, 2, 4, 7, 11, 16, 22, 29, 37, 46, 56, 67, 79, 92, 106, 121, 137, 154, 172, 191, 211, 232, 254, 277, 301, 326, 352, 379, 407, 436, 466, 497, 529, 562, 596, 631, 667, 704, 742, 781, 821, 862, 904, 947, 991, 1036, 1082, 1129, 1177, 1226, 1276, 1327, 1379
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

These are Hogben's central polygonal numbers with the (two-dimensional) symbol
2
.P
1 n
The first line cuts the pancake into 2 pieces. For n > 1, the n-th line crosses every earlier line (avoids parallelism) and also avoids every previous line intersection, thus increasing the number of pieces by n. For 16 lines, for example, the number of pieces is 2 + 2 + 3 + 4 + 5 + ... + 16 = 137. These are the triangular numbers plus 1 (cf. A000217).
m = (n-1)(n-2)/2 + 1 is also the smallest number of edges such that all graphs with n nodes and m edges are connected. - Keith Briggs, May 14 2004
Also maximal number of grandchildren of a binary vector of length n+2. E.g., a binary vector of length 6 can produce at most 11 different vectors when 2 bits are deleted.
This is also the order dimension of the (strong) Bruhat order on the finite Coxeter group B_{n+1}. - Nathan Reading (reading(AT)math.umn.edu), Mar 07 2002
Number of 132- and 321-avoiding permutations of {1,2,...,n+1}. - Emeric Deutsch, Mar 14 2002
For n >= 1 a(n) is the number of terms in the expansion of (x+y)*(x^2+y^2)*(x^3+y^3)*...*(x^n+y^n). - Yuval Dekel (dekelyuval(AT)hotmail.com), Jul 28 2003
Also the number of terms in (1)(x+1)(x^2+x+1)...(x^n+...+x+1); see A000140.
Narayana transform (analog of the binomial transform) of vector [1, 1, 0, 0, 0, ...] = A000124; using the infinite lower Narayana triangle of A001263 (as a matrix), N; then N * [1, 1, 0, 0, 0, ...] = A000124. - Gary W. Adamson, Apr 28 2005
Number of interval subsets of {1, 2, 3, ..., n} (cf. A002662). - Jose Luis Arregui (arregui(AT)unizar.es), Jun 27 2006
Define a number of straight lines in the plane to be in general arrangement when (1) no two lines are parallel, (2) there is no point common to three lines. Then these are the maximal numbers of regions defined by n straight lines in general arrangement in the plane. - Peter C. Heinig (algorithms(AT)gmx.de), Oct 19 2006
Note that a(n) = a(n-1) + A000027(n-1). This has the following geometrical interpretation: Suppose there are already n-1 lines in general arrangement, thus defining the maximal number of regions in the plane obtainable by n-1 lines and now one more line is added in general arrangement. Then it will cut each of the n-1 lines and acquire intersection points which are in general arrangement. (See the comments on A000027 for general arrangement with points.) These points on the new line define the maximal number of regions in 1-space definable by n-1 points, hence this is A000027(n-1), where for A000027 an offset of 0 is assumed, that is, A000027(n-1) = (n+1)-1 = n. Each of these regions acts as a dividing wall, thereby creating as many new regions in addition to the a(n-1) regions already there, hence a(n) = a(n-1) + A000027(n-1). Cf. the comments on A000125 for an analogous interpretation. - Peter C. Heinig (algorithms(AT)gmx.de), Oct 19 2006
When constructing a zonohedron, one zone at a time, out of (up to) 3-d non-intersecting parallelepipeds, the n-th element of this sequence is the number of edges in the n-th zone added with the n-th "layer" of parallelepipeds. (Verified up to 10-zone zonohedron, the enneacontahedron.) E.g., adding the 10th zone to the enneacontahedron requires 46 parallel edges (edges in the 10th zone) by looking directly at a 5-valence vertex and counting visible vertices. - Shel Kaphan, Feb 16 2006
Binomial transform of (1, 1, 1, 0, 0, 0, ...) and inverse binomial transform of A072863: (1, 3, 9, 26, 72, 192, ...). - Gary W. Adamson, Oct 15 2007
If Y is a 2-subset of an n-set X then, for n >= 3, a(n-3) is the number of (n-2)-subsets of X which do not have exactly one element in common with Y. - Milan Janjic, Dec 28 2007
Equals row sums of triangle A144328. - Gary W. Adamson, Sep 18 2008
It appears that a(n) is the number of distinct values among the fractions F(i+1)/F(j+1) as j ranges from 1 to n and, for each fixed j, i ranges from 1 to j, where F(i) denotes the i-th Fibonacci number. - John W. Layman, Dec 02 2008
a(n) is the number of subsets of {1,2,...,n} that contain at most two elements. - Geoffrey Critzer, Mar 10 2009
For n >= 2, a(n) gives the number of sets of subsets A_1, A_2, ..., A_n of n = {1, 2, ..., n} such that Meet_{i = 1..n} A_i is empty and Sum_{j in [n]} (|Meet{i = 1..n, i != j} A_i|) is a maximum. - Srikanth K S, Oct 22 2009
The numbers along the left edge of Floyd's triangle. - Paul Muljadi, Jan 25 2010
Let A be the Hessenberg matrix of order n, defined by: A[1,j] = A[i,i]:=1, A[i,i-1] = -1, and A[i,j] = 0 otherwise. Then, for n >= 1, a(n-1) = (-1)^(n-1)*coeff(charpoly(A,x),x). - Milan Janjic, Jan 24 2010
Also the number of deck entries of Euler's ship. See the Meijer-Nepveu link. - Johannes W. Meijer, Jun 21 2010
(1 + x^2 + x^3 + x^4 + x^5 + ...)*(1 + 2x + 3x^2 + 4x^3 + 5x^4 + ...) = (1 + 2x + 4x^2 + 7x^3 + 11x^4 + ...). - Gary W. Adamson, Jul 27 2010
The number of length n binary words that have no 0-digits between any pair of consecutive 1-digits. - Jeffrey Liese, Dec 23 2010
Let b(0) = b(1) = 1; b(n) = max(b(n-1)+n-1, b(n-2)+n-2) then a(n) = b(n+1). - Yalcin Aktar, Jul 28 2011
Also number of triangular numbers so far, for n > 0: a(n) = a(n-1) + Sum(A010054(a(k)): 0 <= k < n), see also A097602, A131073. - Reinhard Zumkeller, Nov 15 2012
Also number of distinct sums of 1 through n where each of those can be + or -. E.g., {1+2,1-2,-1+2,-1-2} = {3,-1,1,-3} and a(2) = 4. - Toby Gottfried, Nov 17 2011
This sequence is complete because the sum of the first n terms is always greater than or equal to a(n+1)-1. Consequently, any nonnegative number can be written as a sum of distinct terms of this sequence. See A204009, A072638. - Frank M Jackson, Jan 09 2012
The sequence is the number of distinct sums of subsets of the nonnegative integers, and its first differences are the positive integers. See A208531 for similar results for the squares. - John W. Layman, Feb 28 2012
Apparently the number of Dyck paths of semilength n+1 in which the sum of the first and second ascents add to n+1. - David Scambler, Apr 22 2013
Without 1 and 2, a(n) equals the terminus of the n-th partial sum of sequence 1, 1, 2. Explanation: 1st partial sums of 1, 1, 2 are 1, 2, 4; 2nd partial sums are 1, 3, 7; 3rd partial sums are 1, 4, 11; 4th partial sums are 1, 5, 16, etc. - Bob Selcoe, Jul 04 2013
Equivalently, numbers of the form 2*m^2+m+1, where m = 0, -1, 1, -2, 2, -3, 3, ... . - Bruno Berselli, Apr 08 2014
For n >= 2: quasi-triangular numbers; the almost-triangular numbers being A000096(n), n >= 2. Note that 2 is simultaneously almost-triangular and quasi-triangular. - Daniel Forgues, Apr 21 2015
n points in general position determine "n choose 2" lines, so A055503(n) <= a(n(n-1)/2). If n > 3, the lines are not in general position and so A055503(n) < a(n(n-1)/2). - Jonathan Sondow, Dec 01 2015
The digital root is period 9 (1, 2, 4, 7, 2, 7, 4, 2, 1), also the digital roots of centered 10-gonal numbers (A062786), for n > 0, A133292. - Peter M. Chema, Sep 15 2016
Partial sums of A028310. - J. Conrad, Oct 31 2016
For n >= 0, a(n) is the number of weakly unimodal sequences of length n over the alphabet {1, 2}. - Armend Shabani, Mar 10 2017
From Eric M. Schmidt, Jul 17 2017: (Start)
Number of sequences (e(1), ..., e(n+1)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) < e(j) != e(k). [Martinez and Savage, 2.4]
Number of sequences (e(1), ..., e(n+1)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) < e(j) and e(i) < e(k). [Martinez and Savage, 2.4]
Number of sequences (e(1), ..., e(n+1)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) >= e(j) != e(k). [Martinez and Savage, 2.4]
(End)
Numbers m such that 8m - 7 is a square. - Bruce J. Nicholson, Jul 24 2017
From Klaus Purath, Jan 29 2020: (Start)
The odd prime factors != 7 occur in an interval of p successive terms either never or exactly twice, while 7 always occurs only once. If a prime factor p appears in a(n) and a(m) within such an interval, then n + m == -1 (mod p). When 7 divides a(n), then 2*n == -1 (mod 7). a(n) is never divisible by the prime numbers given in A003625.
While all prime factors p != 7 can occur to any power, a(n) is never divisible by 7^2. The prime factors are given in A045373. The prime terms of this sequence are given in A055469.
(End)
From Roger Ford, May 10 2021: (Start)
a(n-1) is the greatest sum of arch lengths for the top arches of a semi-meander with n arches. An arch length is the number of arches covered + 1.
/\ The top arch has a length of 3. /\ The top arch has a length of 3.
/ \ Both bottom arches have a //\\ The middle arch has a length of 2.
//\/\\ length of 1. ///\\\ The bottom arch has a length of 1.
Example: for n = 4, a(4-1) = a(3) = 7 /\
//\\
/\ ///\\\ 1 + 3 + 2 + 1 = 7. (End)
a(n+1) is the a(n)-th smallest positive integer that has not yet appeared in the sequence. - Matthew Malone, Aug 26 2021
For n> 0, let the n-dimensional cube {0,1}^n be, provided with the Hamming distance, d. Given an element x in {0,1}^n, a(n) is the number of elements y in {0,1}^n such that d(x, y) <= 2. Example: n = 4. (0,0,0,0), (1,0,0,0), (0,1,0,0), (0,0,1,0), (0,0,0,1), (0,0,1,1), (0,1,0,1), (0,1,1,0), (1,0,0,1), (1,0,1,0), (1,1,0,0) are at distance <= 2 from (0,0,0,0), so a(4) = 11. - Yosu Yurramendi, Dec 10 2021
a(n) is the sum of the first three entries of row n of Pascal's triangle. - Daniel T. Martin, Apr 13 2022
a(n-1) is the number of Grassmannian permutations that avoid a pattern, sigma, where sigma is a pattern of size 3 with exactly one descent. For example, sigma is one of the patterns, {132, 213, 231, 312}. - Jessica A. Tomasko, Sep 14 2022
a(n+4) is the number of ways to tile an equilateral triangle of side length 2*n with smaller equilateral triangles of side length n and side length 1. For example, with n=2, there are 22 ways to tile an equilateral triangle of side length 4 with smaller ones of sides 2 and 1, including the one tiling with sixteen triangles of sides 1 and the one tiling with four triangles of sides 2. - Ahmed ElKhatib and Greg Dresden, Aug 19 2024
Define a "hatpin" to be the planar graph consisting of a distinguished point (called the "head") and a semi-infinite line from that point. The maximum number of regions than can be formed by drawing n hatpins is a(n-1). See link for the case n = 4. - N. J. A. Sloane, Jun 25 2025

Examples

			a(3) = 7 because the 132- and 321-avoiding permutations of {1, 2, 3, 4} are 1234, 2134, 3124, 2314, 4123, 3412, 2341.
G.f. = 1 + 2*x + 4*x^2 + 7*x^3 + 11*x^4 + 16*x^5 + 22*x^6 + 29*x^7 + ...

References

  • Robert B. Banks, Slicing Pizzas, Racing Turtles and Further Adventures in Applied Mathematics, Princeton Univ. Press, 1999. See p. 24.
  • Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 72, Problem 2.
  • John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See p. 80.
  • Henry Ernest Dudeney, Amusements in Mathematics, Nelson, London, 1917, page 177.
  • Derrick Niederman, Number Freak, From 1 to 200 The Hidden Language of Numbers Revealed, A Perigee Book, NY, 2009, p. 83.
  • Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.
  • Alain M. Robert, A Course in p-adic Analysis, Springer-Verlag, 2000; p. 213.
  • N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
  • N. J. A. Sloane, On single-deletion-correcting codes, in Codes and Designs (Columbus, OH, 2000), 273-291, Ohio State Univ. Math. Res. Inst. Publ., 10, de Gruyter, Berlin, 2002.
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
  • David Wells, The Penguin Dictionary of Curious and Interesting Numbers. Penguin Books, NY, 1986, Revised edition 1987. See p. 98.
  • William Allen Whitworth, DCC Exercises in Choice and Chance, Stechert, NY, 1945, p. 30.
  • Akiva M. Yaglom and Isaak M. Yaglom, Challenging Mathematical Problems with Elementary Solutions. Vol. I. Combinatorial Analysis and Probability Theory. New York: Dover Publications, Inc., 1987, p. 13, #44 (First published: San Francisco: Holden-Day, Inc., 1964).

Links

Crossrefs

Cf. A000096 (Maximal number of pieces that can be obtained by cutting an annulus with n cuts, for n >= 1).
Slicing a cake: A000125, a bagel: A003600.
Partial sums =(A033547)/2, (A014206)/2.
The first 20 terms are also found in A025732 and A025739.
Cf. A002061, A002522, A016028, A055503, A072863, A144328, A177862, A263883, A000127, A005408, A006261, A016813, A058331, A080856, A086514, A161701, A161702, A161703, A161704, A161706, A161707, A161708, A161710, A161711, A161712, A161713, A161715, A051601, A228918.
Cf. also A055469 Quasi-triangular primes, A002620, A000217.
A row of the array in A386478.

Programs

Formula

G.f.: (1 - x + x^2)/(1 - x)^3. - Simon Plouffe in his 1992 dissertation
a(n) = A108561(n+3, 2). - Reinhard Zumkeller, Jun 10 2005
G.f.: (1 - x^6)/((1 - x)^2*(1 - x^2)*(1 - x^3)). a(n) = a(-1 - n) for all n in Z. - Michael Somos, Sep 04 2006
Euler transform of length 6 sequence [ 2, 1, 1, 0, 0, -1]. - Michael Somos, Sep 04 2006
a(n+3) = 3*a(n+2) - 3*a(n+1) + a(n) and a(1) = 1, a(2) = 2, a(3) = 4. - Artur Jasinski, Oct 21 2008
a(n) = A000217(n) + 1.
a(n) = a(n-1) + n. E.g.f.:(1 + x + x^2/2)*exp(x). - Geoffrey Critzer, Mar 10 2009
a(n) = Sum_{k = 0..n + 1} binomial(n+1, 2(k - n)). - Paul Barry, Aug 29 2004
a(n) = binomial(n+2, 1) - 2*binomial(n+1, 1) + binomial(n+2, 2). - Zerinvary Lajos, May 12 2006
From Thomas Wieder, Feb 25 2009: (Start)
a(n) = Sum_{l_1 = 0..n + 1} Sum_{l_2 = 0..n}...Sum_{l_i = 0..n - i}...Sum_{l_n = 0..1} delta(l_1, l_2, ..., l_i, ..., l_n) where delta(l_1, l_2, ..., l_i, ..., l_n) = 0 if any l_i != l_(i+1) and l_(i+1) != 0 and delta(l_1, l_2, ..., l_i, ..., l_n) = 1 otherwise. (End)
a(n) = A034856(n+1) - A005843(n) = A000217(n) + A005408(n) - A005843(n). - Jaroslav Krizek, Sep 05 2009
a(n) = 2*a(n-1) - a(n-2) + 1. - Eric Werley, Jun 27 2011
E.g.f.: exp(x)*(1+x+(x^2)/2) = Q(0); Q(k) = 1+x/(1-x/(2+x-4/(2+x*(k+1)/Q(k+1)))); (continued fraction). - Sergei N. Gladkovskii, Nov 21 2011
a(n) = A014132(n, 1) for n > 0. - Reinhard Zumkeller, Dec 12 2012
a(n) = 1 + floor(n/2) + ceiling(n^2/2) = 1 + A004526(n) + A000982(n). - Wesley Ivan Hurt, Jun 14 2013
a(n) = A228074(n+1, n). - Reinhard Zumkeller, Aug 15 2013
For n > 0: A228446(a(n)) = 3. - Reinhard Zumkeller, Mar 12 2014
a(n) >= A263883(n) and a(n(n-1)/2) >= A055503(n). - Jonathan Sondow, Dec 01 2015
From Ilya Gutkovskiy, Jun 29 2016: (Start)
Dirichlet g.f.: (zeta(s-2) + zeta(s-1) + 2*zeta(s))/2.
Sum_{n >= 0} 1/a(n) = 2*Pi*tanh(sqrt(7)*Pi/2)/sqrt(7) = A226985. (End)
a(n) = (n+1)^2 - A000096(n). - Anton Zakharov, Jun 29 2016
a(n) = A101321(1, n). - R. J. Mathar, Jul 28 2016
a(n) = 2*a(n-1) - binomial(n-1, 2) and a(0) = 1. - Armend Shabani, Mar 10 2017
a(n) = A002620(n+2) + A002620(n-1). - Anton Zakharov, May 11 2017
From Klaus Purath, Jan 29 2020: (Start)
a(n) = (Sum_{i=n-2..n+2} A000217(i))/5.
a(n) = (Sum_{i=n-2..n+2} A002378(i))/10.
a(n) = (Sum_{i=n..n+2} A002061(i)+1)/6.
a(n) = (Sum_{i=n-1..n+2} A000290(i)+2)/8.
a(n) = A060533(n-1) + 10, n > 5.
a(n) = (A002378(n) + 2)/2.
a(n) = A152948(n+2) - 1.
a(n) = A152950(n+1) - 2.
a(n) = (A002061(n) + A002061(n+2))/4.
(End)
Sum_{n>=0} (-1)^n/a(n) = A228918. - Amiram Eldar, Nov 20 2020
From Amiram Eldar, Feb 17 2021: (Start)
Product_{n>=0} (1 + 1/a(n)) = cosh(sqrt(15)*Pi/2)*sech(sqrt(7)*Pi/2).
Product_{n>=1} (1 - 1/a(n)) = 2*Pi*sech(sqrt(7)*Pi/2). (End)
a((n^2-3n+6)/2) + a((n^2-n+4)/2) = a(n^2-2n+6)/2. - Charlie Marion, Feb 14 2023

A000295 Eulerian numbers (Euler's triangle: column k=2 of A008292, column k=1 of A173018).

Original entry on oeis.org

0, 0, 1, 4, 11, 26, 57, 120, 247, 502, 1013, 2036, 4083, 8178, 16369, 32752, 65519, 131054, 262125, 524268, 1048555, 2097130, 4194281, 8388584, 16777191, 33554406, 67108837, 134217700, 268435427, 536870882, 1073741793, 2147483616, 4294967263, 8589934558
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

There are 2 versions of Euler's triangle:
* A008292 Classic version of Euler's triangle used by Comtet (1974).
* A173018 Version of Euler's triangle used by Graham, Knuth and Patashnik in Concrete Math. (1990).
Euler's triangle rows and columns indexing conventions:
* A008292 The rows and columns of the Eulerian triangle are both indexed starting from 1. (Classic version: used in the classic books by Riordan and Comtet.)
* A173018 The rows and columns of the Eulerian triangle are both indexed starting from 0. (Graham et al.)
Number of Dyck paths of semilength n having exactly one long ascent (i.e., ascent of length at least two). Example: a(4)=11 because among the 14 Dyck paths of semilength 4, the paths that do not have exactly one long ascent are UDUDUDUD (no long ascent), UUDDUUDD and UUDUUDDD (two long ascents). Here U=(1,1) and D=(1,-1). Also number of ordered trees with n edges having exactly one branch node (i.e., vertex of outdegree at least two). - Emeric Deutsch, Feb 22 2004
Number of permutations of {1,2,...,n} with exactly one descent (i.e., permutations (p(1),p(2),...,p(n)) such that #{i: p(i)>p(i+1)}=1). E.g., a(3)=4 because the permutations of {1,2,3} with one descent are 132, 213, 231 and 312.
a(n+1) is the convolution of nonnegative integers (A001477) and powers of two (A000079). - Graeme McRae, Jun 07 2006
Partial sum of main diagonal of A125127. - Jonathan Vos Post, Nov 22 2006
Number of partitions of an n-set having exactly one block of size > 1. Example: a(4)=11 because, if the partitioned set is {1,2,3,4}, then we have 1234, 123|4, 124|3, 134|2, 1|234, 12|3|4, 13|2|4, 14|2|3, 1|23|4, 1|24|3 and 1|2|34. - Emeric Deutsch, Oct 28 2006
k divides a(k+1) for k in A014741. - Alexander Adamchuk, Nov 03 2006
(Number of permutations avoiding patterns 321, 2413, 3412, 21534) minus one. - Jean-Luc Baril, Nov 01 2007, Mar 21 2008
The chromatic invariant of the prism graph P_n for n >= 3. - Jonathan Vos Post, Aug 29 2008
Decimal integer corresponding to the result of XORing the binary representation of 2^n - 1 and the binary representation of n with leading zeros. This sequence and a few others are syntactically similar. For n > 0, let D(n) denote the decimal integer corresponding to the binary number having n consecutive 1's. Then D(n).OP.n represents the n-th term of a sequence when .OP. stands for a binary operator such as '+', '-', '*', 'quotentof', 'mod', 'choose'. We then get the various sequences A136556, A082495, A082482, A066524, A000295, A052944. Another syntactically similar sequence results when we take the n-th term as f(D(n)).OP.f(n). For example if f='factorial' and .OP.='/', we get (A136556)(A000295) ; if f='squaring' and .OP.='-', we get (A000295)(A052944). - K.V.Iyer, Mar 30 2009
Chromatic invariant of the prism graph Y_n.
Number of labelings of a full binary tree of height n-1, such that each path from root to any leaf contains each label from {1,2,...,n-1} exactly once. - Michael Vielhaber (vielhaber(AT)gmail.com), Nov 18 2009
Also number of nontrivial equivalence classes generated by the weak associative law X((YZ)T)=(X(YZ))T on words with n open and n closed parentheses. Also the number of join (resp. meet)-irreducible elements in the pruning-grafting lattice of binary trees with n leaves. - Jean Pallo, Jan 08 2010
Nonzero terms of this sequence can be found from the row sums of the third sub-triangle extracted from Pascal's triangle as indicated below by braces:
1;
1, 1;
{1}, 2, 1;
{1, 3}, 3, 1;
{1, 4, 6}, 4, 1;
{1, 5, 10, 10}, 5, 1;
{1, 6, 15, 20, 15}, 6, 1;
... - L. Edson Jeffery, Dec 28 2011
For integers a, b, denote by a<+>b the least c >= a, such that the Hamming distance D(a,c) = b (note that, generally speaking, a<+>b differs from b<+>a). Then for n >= 3, a(n) = n<+>n. This has a simple explanation: for n >= 3 in binary we have a(n) = (2^n-1)-n = "anti n". - Vladimir Shevelev, Feb 14 2012
a(n) is the number of binary sequences of length n having at least one pair 01. - Branko Curgus, May 23 2012
Nonzero terms are those integers k for which there exists a perfect (Hamming) error-correcting code. - L. Edson Jeffery, Nov 28 2012
a(n) is the number of length n binary words constructed in the following manner: Select two positions in which to place the first two 0's of the word. Fill in all (possibly none) of the positions before the second 0 with 1's and then complete the word with an arbitrary string of 0's or 1's. So a(n) = Sum_{k=2..n} (k-1)*2^(n-k). - Geoffrey Critzer, Dec 12 2013
Without first 0: a(n)/2^n equals Sum_{k=0..n} k/2^k. For example: a(5)=57, 57/32 = 0/1 + 1/2 + 2/4 + 3/8 + 4/16 + 5/32. - Bob Selcoe, Feb 25 2014
The first barycentric coordinate of the centroid of the first n rows of Pascal's triangle, assuming the numbers are weights, is A000295(n+1)/A000337(n). See attached figure. - César Eliud Lozada, Nov 14 2014
Starting (0, 1, 4, 11, ...), this is the binomial transform of (0, 1, 2, 2, 2, ...). - Gary W. Adamson, Jul 27 2015
Also the number of (non-null) connected induced subgraphs in the n-triangular honeycomb rook graph. - Eric W. Weisstein, Aug 27 2017
a(n) is the number of swaps needed in the worst case to transform a binary tree with n full levels into a heap, using (bottom-up) heapify. - Rudy van Vliet, Sep 19 2017
The utility of large networks, particularly social networks, with n participants is given by the terms a(n) of this sequence. This assertion is known as Reed's Law, see the Wikipedia link. - Johannes W. Meijer, Jun 03 2019
a(n-1) is the number of subsets of {1..n} in which the largest element of the set exceeds by at least 2 the next largest element. For example, for n = 5, a(4) = 11 and the 11 sets are {1,3}, {1,4}, {1,5}, {2,4}, {2,5}, {3,5}, {1,2,4}, {1,2,5}, {1,3,5}, {2,3,5}, {1,2,3,5}. - Enrique Navarrete, Apr 08 2020
a(n-1) is also the number of subsets of {1..n} in which the second smallest element of the set exceeds by at least 2 the smallest element. For example, for n = 5, a(4) = 11 and the 11 sets are {1,3}, {1,4}, {1,5}, {2,4}, {2,5}, {3,5}, {1,3,4}, {1,3,5}, {1,4,5}, {2,4,5}, {1,3,4,5}. - Enrique Navarrete, Apr 09 2020
a(n+1) is the sum of the smallest elements of all subsets of {1..n}. For example, for n=3, a(4)=11; the subsets of {1,2,3} are {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}, and the sum of smallest elements is 11. - Enrique Navarrete, Aug 20 2020
Number of subsets of an n-set that have more than one element. - Eric M. Schmidt, Mar 13 2021
Number of individual bets in a "full cover" bet on n-1 horses, dogs, etc. in different races. Each horse, etc. can be bet on or not, giving 2^n bets. But, by convention, singles (a bet on only one race) are not included, reducing the total number bets by n. It is also impossible to bet on no horses at all, reducing the number of bets by another 1. A full cover on 4 horses, dogs, etc. is therefore 6 doubles, 4 trebles and 1 four-horse etc. accumulator. In British betting, such a bet on 4 horses etc. is a Yankee; on 5, a super-Yankee. - Paul Duckett, Nov 17 2021
From Enrique Navarrete, May 25 2022: (Start)
Number of binary sequences of length n with at least two 1's.
a(n-1) is the number of ways to choose an odd number of elements greater than or equal to 3 out of n elements.
a(n+1) is the number of ways to split [n] = {1,2,...,n} into two (possibly empty) complementary intervals {1,2,...,i} and {i+1,i+2,...,n} and then select a subset from the first interval (2^i choices, 0 <= i <= n), and one block/cell (i.e., subinterval) from the second interval (n-i choices, 0 <= i <= n).
(End)
Number of possible conjunctions in a system of n planets; for example, there can be 0 conjunctions with one planet, one with two planets, four with three planets (three pairs of planets plus one with all three) and so on. - Wendy Appleby, Jan 02 2023
Largest exponent m such that 2^m divides (2^n-1)!. - Franz Vrabec, Aug 18 2023
It seems that a(n-1) is the number of odd r with 0 < r < 2^n for which there exist u,v,w in the x-independent beginning of the Collatz trajectory of 2^n x + r with u+v = w+1, as detailed in the link "Collatz iteration and Euler numbers?". A better understanding of this might also give a formula for A374527. - Markus Sigg, Aug 02 2024
This sequence has a connection to consecutively halved positional voting (CHPV); see Mendenhall and Switkay. - Hal M. Switkay, Feb 25 2025
a(n) is the number of subsets of size 2 and more of an n-element set. Equivalently, a(n) is the number of (hyper)edges of size 2 and more in a complete hypergraph of n vertices. - Yigit Oktar, Apr 05 2025

Examples

			G.f. = x^2 + 4*x^3 + 11*x^4 + 26*x^5 + 57*x^6 + 120*x^7 + 247*x^8 + 502*x^9 + ...

References

  • O. Bottema, Problem #562, Nieuw Archief voor Wiskunde, 28 (1980) 115.
  • L. Comtet, "Permutations by Number of Rises; Eulerian Numbers." Section 6.5 in Advanced Combinatorics: The Art of Finite and Infinite Expansions, rev. enl. ed. Dordrecht, Netherlands: Reidel, pp. 51 and 240-246, 1974.
  • F. N. David and D. E. Barton, Combinatorial Chance. Hafner, NY, 1962, p. 151.
  • R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990.
  • D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 3, p. 34.
  • J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 215.
  • 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).

Links

Crossrefs

Cf. A008292 (classic version of Euler's triangle used by Comtet (1974)).
Cf. A173018 (version of Euler's triangle used by Graham, Knuth and Patashnik in Concrete Math. (1990)).
Cf. A002662 (partial sums).
Partial sums of A000225.
Row sums of A014473 and of A143291.
Second column of triangles A112493 and A112500.
Sequences A125128 and A130103 are essentially the same.
Column k=1 of A124324.
Cf. A000079, A000108, A000217, A000325, A000975, A001511, A002663.
Cf. A002664, A007814, A008292, A008949, A014741, A016031, A028366.
Cf. A035039, A035040, A035041, A035042, A079583, A107907, A130321.
Cf. A130128, A130330, A131768, A131816.

Programs

  • Haskell
    a000295 n = 2^n - n - 1  -- Reinhard Zumkeller, Nov 25 2013
  • Magma
    [2^n-n-1: n in [0..40]]; // Vincenzo Librandi, Jul 29 2015
  • Magma
    [EulerianNumber(n, 1): n in [0..40]]; // G. C. Greubel, Oct 02 2024
  • Maple
    [ seq(2^n-n-1, n=1..50) ];
A000295 := -z/(2*z-1)/(z-1)**2; # Simon Plouffe in his 1992 dissertation
# Grammar specification:
spec := [S, { B = Set(Z, 1 <= card), C = Sequence(B, 2 <= card), S = Prod(B, C) }, unlabeled]:
struct := n -> combstruct[count](spec, size = n+1);
seq(struct(n), n = 0..33); # Peter Luschny, Jul 22 2014
  • Mathematica
    a[n_] = If[n==0, 0, n*(HypergeometricPFQ[{1, 1-n}, {2}, -1] - 1)];
Table[a[n], {n,0,40}] (* Olivier Gérard, Mar 29 2011 *)
LinearRecurrence[{4, -5, 2}, {0, 0, 1}, 40] (* Vincenzo Librandi, Jul 29 2015 *)
Table[2^n -n-1, {n,0,40}] (* Eric W. Weisstein, Nov 16 2017 *)
  • PARI
    a(n)=2^n-n-1 \\ Charles R Greathouse IV, Jun 10 2011
  • SageMath
    [2^n -(n+1) for n in range(41)] # G. C. Greubel, Oct 02 2024

Formula

a(n) = 2^n - n - 1.
G.f.: x^2/((1-2*x)*(1-x)^2).
A107907(a(n+2)) = A000079(n+2). - Reinhard Zumkeller, May 28 2005
E.g.f.: exp(x)*(exp(x)-1-x). - Emeric Deutsch, Oct 28 2006
a(0)=0, a(1)=0, a(n) = 3*a(n-1) - 2*a(n-2) + 1. - Miklos Kristof, Mar 09 2005
a(0)=0, a(n) = 2*a(n-1) + n - 1 for all n in Z.
a(n) = Sum_{k=2..n} binomial(n, k). - Paul Barry, Jun 05 2003
a(n+1) = Sum_{i=1..n} Sum_{j=1..i} C(i, j). - Benoit Cloitre, Sep 07 2003
a(n+1) = 2^n*Sum_{k=0..n} k/2^k. - Benoit Cloitre, Oct 26 2003
a(0)=0, a(1)=0, a(n) = Sum_{i=0..n-1} i+a(i) for i > 1. - Gerald McGarvey, Jun 12 2004
a(n+1) = Sum_{k=0..n} (n-k)*2^k. - Paul Barry, Jul 29 2004
a(n) = Sum_{k=0..n} binomial(n, k+2); a(n+2) = Sum_{k=0..n} binomial(n+2, k+2). - Paul Barry, Aug 23 2004
a(n) = Sum_{k=0..floor((n-1)/2)} binomial(n-k-1, k+1)*2^(n-k-2)*(-1/2)^k. - Paul Barry, Oct 25 2004
a(0) = 0; a(n) = Stirling2(n,2) + a(n-1) = A000225(n-1) + a(n-1). - Thomas Wieder, Feb 18 2007
a(n) = A000325(n) - 1. - Jonathan Vos Post, Aug 29 2008
a(0) = 0, a(n) = Sum_{k=0..n-1} 2^k - 1. - Doug Bell, Jan 19 2009
a(n) = A000217(n-1) + A002662(n) for n>0. - Geoffrey Critzer, Feb 11 2009
a(n) = A000225(n) - n. - Zerinvary Lajos, May 29 2009
a(n) = n*(2F1([1,1-n],[2],-1) - 1). - Olivier Gérard, Mar 29 2011
Column k=1 of A173018 starts a'(n) = 0, 1, 4, 11, ... and has the hypergeometric representation n*hypergeom([1, -n+1], [-n], 2). This can be seen as a formal argument to prefer Euler's A173018 over A008292. - Peter Luschny, Sep 19 2014
E.g.f.: exp(x)*(exp(x)-1-x); this is U(0) where U(k) = 1 - x/(2^k - 2^k/(x + 1 - x^2*2^(k+1)/(x*2^(k+1) - (k+1)/U(k+1)))); (continued fraction, 3rd kind, 4-step). - Sergei N. Gladkovskii, Dec 01 2012
a(n) = A079583(n) - A000225(n+1). - Miquel Cerda, Dec 25 2016
a(0) = 0; a(1) = 0; for n > 1: a(n) = Sum_{i=1..2^(n-1)-1} A001511(i). - David Siegers, Feb 26 2019
a(n) = A007814(A028366(n)). - Franz Vrabec, Aug 18 2023
a(n) = Sum_{k=1..floor((n+1)/2)} binomial(n+1, 2*k+1). - Taras Goy, Jan 02 2025

A097805 Number of compositions of n with k parts, T(n, k) = binomial(n-1, k-1) for n, k >= 1 and T(n, 0) = 0^n, triangle read by rows for n >= 0 and 0 <= k <= n.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 3, 1, 0, 1, 4, 6, 4, 1, 0, 1, 5, 10, 10, 5, 1, 0, 1, 6, 15, 20, 15, 6, 1, 0, 1, 7, 21, 35, 35, 21, 7, 1, 0, 1, 8, 28, 56, 70, 56, 28, 8, 1, 0, 1, 9, 36, 84, 126, 126, 84, 36, 9, 1, 0, 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1, 0, 1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1
Offset: 0

Views

Author

Paul Barry, Aug 25 2004

Keywords

Comments

Previous name was: Riordan array (1, 1/(1-x)) read by rows.
Note this Riordan array would be denoted (1, x/(1-x)) by some authors.
Columns have g.f. (x/(1-x))^k. Reverse of A071919. Row sums are A011782. Antidiagonal sums are Fibonacci(n-1). Inverse as Riordan array is (1, 1/(1+x)). A097805=B*A059260*B^(-1), where B is the binomial matrix.
(0,1)-Pascal triangle. - Philippe Deléham, Nov 21 2006
(n+1) * each term of row n generates triangle A127952: (1; 0, 2; 0, 3, 3; 0, 4, 8, 4; ...). - Gary W. Adamson, Feb 09 2007
Triangle T(n,k), 0<=k<=n, read by rows, given by [0,1,0,0,0,0,0,...] DELTA [1,0,0,0,0,0,0,...] where DELTA is the operator defined in A084938. - Philippe Deléham, Dec 12 2008
From Paul Weisenhorn, Feb 09 2011: (Start)
Triangle read by rows: T(r,c) is the number of unordered partitions of n=r*(r+1)/2+c into (r+1) parts < (r+1) and at most pairs of equal parts and parts in neighboring pairs have difference 2.
Triangle read by rows: T(r,c) is the number of unordered partitions of the number n=r*(r+1)/2+(c-1) into r parts < (r+1) and at most pairs of equal parts and parts in neighboring pairs have difference 2. (End)
Triangle read by rows: T(r,c) is the number of ordered partitions (compositions) of r into c parts. - Juergen Will, Jan 04 2016
From Tom Copeland, Oct 25 2012: (Start)
Given a basis composed of a sequence of polynomials p_n(x) characterized by ladder (creation / annihilation, or raising / lowering) operators defined by R p_n(x) = p_(n+1)(x) and L p_n(x) = n p_(n-1)(x) with p_0(x)=1, giving the number operator # p_n(x) = RL p_n(x) = n p_n(x), the lower triangular padded Pascal matrix Pd (A097805) serves as a matrix representation of the operator exp(R^2*L) = exp(R#) =
1) exp(x^2D) for the set x^n and
2) D^(-1) exp(t*x)D for the set x^n/n! (see A218234).
(End)
From James East, Apr 11 2014: (Start)
Square array a(m,n) with m,n=0,1,2,... read by off-diagonals.
a(m,n) gives the number of order-preserving functions f:{1,...,m}->{1,...,n}. Order-preserving means that x
a(n,n)=A088218(n) is the size of the semigroup O_n of all order-preserving transformations of {1,...,n}.
Read as a triangle, this sequence may be obtained by augmenting Pascal's triangle by appending the column 1,0,0,0,... on the left.
(End)
A formula based on the partitions of n with largest part k is given as a Sage program below. The 'conjugate' formula leads to A048004. - Peter Luschny, Jul 13 2015
From Wolfdieter Lang, Feb 17 2017: (Start)
The transposed of this lower triangular Riordan matrix of the associated type T provides the transition matrix between the monomial basis {x^n}, n >= 0, and the basis {y^n}, n >= 0, with y = x/(1-x): x^0 = 1 = y^0, x^n = Sum_{m >= n} Ttrans(n,m) y^m, for n >= 1, with Ttrans(n,m) = binomial(m-1,n-1).
Therefore, if a transformation with this Riordan matrix from a sequence {a} to the sequence {b} is given by b(n) = Sum_{m=0..n} T(n, m)*a(m), with T(n, m) = binomial(n-1, m-1), for n >= 1, then Sum_{n >= 0} a(n)*x^n = Sum_{n >= 0} b(n)*y^n, with y = x/(1-x) and vice versa. This is a modified binomial transformation; the usual one belongs to the Pascal Riordan matrix A007318. (End)
From Gus Wiseman, Jan 23 2022: (Start)
Also the number of compositions of n with alternating sum k, with k ranging from -n to n in steps of 2. For example, row n = 6 counts the following compositions (empty column indicated by dot):
. (15) (24) (33) (42) (51) (6)
(141) (132) (123) (114)
(1113) (231) (222) (213)
(1212) (1122) (321) (312)
(1311) (1221) (1131) (411)
(2112) (2121)
(2211) (3111)
(11121) (11112)
(12111) (11211)
(111111) (21111)
The reverse-alternating version is the same. Counting compositions by all three parameters (sum, length, alternating sum) gives A345197. Compositions of 2n with alternating sum 2k with k ranging from -n + 1 to n are A034871. (End)
Also the convolution triangle of A000012. - Peter Luschny, Oct 07 2022
From Sergey Kitaev, Nov 18 2023: (Start)
Number of permutations of length n avoiding simultaneously the patterns 123 and 132 with k right-to-left maxima. A right-to-left maximum in a permutation a(1)a(2)...a(n) is position i such that a(j) < a(i) for all i < j.
Number of permutations of length n avoiding simultaneously the patterns 231 and 312 with k right-to-left minima (resp., left-to-right maxima). A right-to-left minimum (resp., left-to-right maximum) in a permutation a(1)a(2)...a(n) is position i such that a(j) > a(i) for all j > i (resp., a(j) < a(i) for all j < i).
Number of permutations of length n avoiding simultaneously the patterns 213 and 312 with k right-to-left maxima (resp., left-to-right maxima).
Number of permutations of length n avoiding simultaneously the patterns 213 and 231 with k right-to-left maxima (resp., right-to-left minima). (End)

Examples

			G.f. = 1 + x * (x + x^3 * (1 + x) + x^6 * (1 + x)^2 + x^10 * (1 + x)^3 + ...). - _Michael Somos_, Aug 20 2006
The triangle T(n, k) begins:
n\k  0 1 2  3  4   5   6  7  8 9 10 ...
0:   1
1:   0 1
2:   0 1 1
3:   0 1 2  1
4:   0 1 3  3  1
5:   0 1 4  6  4   1
6:   0 1 5 10 10   5   1
7:   0 1 6 15 20  15   6  1
8:   0 1 7 21 35  35  21  7  1
9:   0 1 8 28 56  70  56 28  8 1
10:  0 1 9 36 84 126 126 84 36 9  1
... reformatted _Wolfdieter Lang_, Jul 31 2017
From _Paul Weisenhorn_, Feb 09 2011: (Start)
T(r=5,c=3) = binomial(4,2) = 6 unordered partitions of the number n = r*(r+1)/2+c = 18 with (r+1)=6 summands: (5+5+4+2+1+1), (5+5+3+3+1+1), (5+4+4+3+1+1), (5+5+3+2+2+1), (5+4+4+2+2+1), (5+4+3+3+2+1).
T(r=5,c=3) = binomial(4,2) = 6 unordered partitions of the number n = r*(r+1)/2+(c-1) = 17 with r=5 summands: (5+5+4+2+1), (5+5+3+3+1), (5+5+3+2+2), (5+4+4+3+1), (5+4+4+2+2), (5+4+3+3+2).  (End)
From _James East_, Apr 11 2014: (Start)
a(0,0)=1 since there is a unique (order-preserving) function {}->{}.
a(m,0)=0 for m>0 since there is no function from a nonempty set to the empty set.
a(3,2)=4 because there are four order-preserving functions {1,2,3}->{1,2}: these are [1,1,1], [2,2,2], [1,1,2], [1,2,2]. Here f=[a,b,c] denotes the function defined by f(1)=a, f(2)=b, f(3)=c.
a(2,3)=6 because there are six order-preserving functions {1,2}->{1,2,3}: these are [1,1], [1,2], [1,3], [2,2], [2,3], [3,3].
(End)

References

  • D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Part 1, Section 7.2.1.3, 2011.

Links

Crossrefs

Case m=0 of the polynomials defined in A278073.
Cf. A000012 (diagonal), A011782 (row sums), A088218 (central terms).
Cf. A007318, A048004, A127952, A118800, A200139, A130595, A167374.
The terms just left of center in odd-indexed rows are A001791, even A002054.
The odd-indexed rows are A034871.
Row sums without the center are A058622.
The unordered version is A072233, without zeros A008284.
Right half without center has row sums A027306(n-1).
Right half with center has row sums A116406(n).
Left half without center has row sums A294175(n-1).
Left half with center has row sums A058622(n-1).
A025047 counts alternating compositions.
A098124 counts balanced compositions, unordered A047993.
A106356 counts compositions by number of maximal anti-runs.
A344651 counts partitions by sum and alternating sum.
A345197 counts compositions by sum, length, and alternating sum.
Cf. A000346, A000984, A001700, A008549, A008965, A114121, A124754, A238279, A345907, A345908, A346632.

Programs

  • Maple
    b:= proc(n, i, p) option remember; `if`(n=0, p!, `if`(i<1, 0,
      expand(add(b(n-i*j, i-1, p+j)/j!*x^j, j=0..n/i))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n$2, 0)):
seq(T(n), n=0..20);  # Alois P. Heinz, May 25 2014
# Alternatively:
T := proc(k,n) option remember;
if k=n then 1 elif k=0 then 0 else
add(T(k-1,n-i), i=1..n-k+1) fi end:
A097805 := (n,k) -> T(k,n):
for n from 0 to 12 do seq(A097805(n,k), k=0..n) od; # Peter Luschny, Mar 12 2016
# Uses function PMatrix from A357368.
PMatrix(10, n -> 1);  # Peter Luschny, Oct 07 2022
  • Mathematica
    T[0, 0] = 1; T[n_, k_] := Binomial[n-1, k-1]; Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-François Alcover, Sep 03 2014, after Paul Weisenhorn *)
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Length[#]==k&]],{n,0,10},{k,0,n}] (* Gus Wiseman, Jan 23 2022 *)
  • PARI
    {a(n) = my(m); if( n<2, n==0, n--; m = (sqrtint(8*n + 1) - 1)\2; binomial(m-1, n - m*(m + 1)/2))}; /* Michael Somos, Aug 20 2006 */
  • PARI
    T(n,k) = if (k==0, 0^n, binomial(n-1, k-1)); \\ Michel Marcus, May 06 2022
  • PARI
    row(n) = vector(n+1, k, k--; if (k==0, 0^n, binomial(n-1, k-1))); \\ Michel Marcus, May 06 2022
  • Python
    from math import comb
def T(n, k): return comb(n-1, k-1) if k != 0 else k**n  # Peter Luschny, May 06 2022
  • Sage
    # Illustrates a basic partition formula, is not efficient as a program for large n.
def A097805_row(n):
    r = []
    for k in (0..n):
        s = 0
        for q in Partitions(n, max_part=k, inner=[k]):
            s += mul(binomial(q[j],q[j+1]) for j in range(len(q)-1))
        r.append(s)
    return r
[A097805_row(n) for n in (0..9)] # Peter Luschny, Jul 13 2015

Formula

Number triangle T(n, k) defined by T(n,k) = Sum_{j=0..n} binomial(n, j)*if(k<=j, (-1)^(j-k), 0).
T(r,c) = binomial(r-1,c-1), 0 <= c <= r. - Paul Weisenhorn, Feb 09 2011
G.f.: (-1+x)/(-1+x+x*y). - R. J. Mathar, Aug 11 2015
a(0,0) = 1, a(n,k) = binomial(n-1,n-k) = binomial(n-1,k-1) Juergen Will, Jan 04 2016
G.f.: (x^1 + x^2 + x^3 + ...)^k = (x/(1-x))^k. - Juergen Will, Jan 04 2016
From Tom Copeland, Nov 15 2016: (Start)
E.g.f.: 1 + x*[e^((x+1)t)-1]/(x+1).
This padded Pascal matrix with the odd columns negated is NpdP = M*S = S^(-1)*M^(-1) = S^(-1)*M, where M(n,k) = (-1)^n A130595(n,k), the inverse Pascal matrix with the odd rows negated, S is the summation matrix A000012, the lower triangular matrix with all elements unity, and S^(-1) = A167374, a finite difference matrix. NpdP is self-inverse, i.e., (M*S)^2 = the identity matrix, and has the e.g.f. 1 - x*[e^((1-x)t)-1]/(1-x).
M = NpdP*S^(-1) follows from the well-known recursion property of the Pascal matrix, implying NpdP = M*S.
The self-inverse property of -NpdP is implied by the self-inverse relation of its embedded signed Pascal submatrix M (cf. A130595). Also see A118800 for another proof.
Let P^(-1) be A130595, the inverse Pascal matrix. Then T = A200139*P^(-1) and T^(-1) = padded P^(-1) = P*A097808*P^(-1). (End)
The center (n>0) is T(2n+1,n+1) = A000984(n) = 2*A001700(n-1) = 2*A088218(n) = A126869(2n) = 2*A138364(2n-1). - Gus Wiseman, Jan 25 2022

Extensions

Corrected by Philippe Deléham, Oct 05 2005
New name using classical terminology by Peter Luschny, Feb 05 2019

A001791 a(n) = binomial coefficient C(2n, n-1).

Original entry on oeis.org

0, 1, 4, 15, 56, 210, 792, 3003, 11440, 43758, 167960, 646646, 2496144, 9657700, 37442160, 145422675, 565722720, 2203961430, 8597496600, 33578000610, 131282408400, 513791607420, 2012616400080, 7890371113950, 30957699535776, 121548660036300, 477551179875952
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Number of peaks at even level in all Dyck paths of semilength n+1. Example: a(2)=4 because UDUDUD, UDUU*DD, UU*DDUD, UU*DU*DD, UUUDDD, where U=(1,1), D=(1,-1) and the peaks at even level are shown by *. - Emeric Deutsch, Dec 05 2003
Also number of long ascents (i.e., ascents of length at least two) in all Dyck paths of semilength n+1. Example: a(2)=4 because in the five Dyck paths of semilength 3, namely UDUDUD, UD(UU)DD, (UU)DDUD, (UU)DUDD and (UUU)DDD, we have four long ascents (shown between parentheses). Here U=(1,1) and D=(1,-1). Also number of branch nodes (i.e., vertices of outdegree at least two) in all ordered trees with n+1 edges. - Emeric Deutsch, Feb 22 2004
Number of lattice paths from (0,0) to (n,n) with steps E=(1,0) and N=(0,1) which touch or cross the line x-y=1. Example: For n=2 these are the paths EENN, ENEN, ENNE and NEEN. - Herbert Kociemba, May 23 2004
Narayana transform (A001263) of [1, 3, 5, 7, 9, ...] = (1, 4, 15, 56, 210, ...). Row sums of triangles A136534 and A136536. - Gary W. Adamson, Jan 04 2008
Starting with offset 1 = the Catalan sequence starting (1, 2, 5, 14, ...) convolved with A000984: (1, 2, 6, 20, ...). - Gary W. Adamson, May 17 2009
Also number of peaks plus number of valleys in all Dyck n-paths. - David Scambler, Oct 08 2012
Apparently counts UDDUD in all Dyck paths of semilength n+2. - David Scambler, Apr 22 2013
Apparently the number of peaks strictly left of the midpoint in all Dyck paths of semilength n+1. - David Scambler, Apr 30 2013
For n>0, a(n) is the number of compositions of n into at most n parts if zeros are allowed as parts (so-called "weak" compositions). - L. Edson Jeffery, Jul 24 2014
Number of paths in the half-plane x >= 0, from (0,0) to (2n,2), and consisting of steps U=(1,1) and D=(1,-1). For example, for n=2, we have the 4 paths: UUUD, UUDU, UDUU, DUUU. - José Luis Ramírez Ramírez, Apr 19 2015
For n>1, 1/a(n) is the probability that when a stick is broken up at n points independently and uniformly chosen at random along its length any triple of pieces of the n+1 pieces can form a triangle. The corresponding probability for the existence of at least one triple is A339392(n)/A339393(n). - Amiram Eldar, Dec 04 2020
a(n) is the number of lattice paths of 2n steps taken from the step set {U=(1,1), D=(1,-1)} that start at the origin, never go below the x-axis, and end strictly above the x-axis; more succinctly, proper left factors of Dyck paths. For example, a(2)=4 counts UUUU, UUUD, UUDU, UDUU. - David Callan and Emeric Deutsch, Jan 25 2021
From Gus Wiseman, Jul 21 2021: (Start)
Also the number of integer compositions of 2n+1 with alternating sum -1, where the alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i. For example, the a(1) = 1 through a(3) = 15 compositions are:
(1,2) (2,3) (3,4)
(1,3,1) (1,4,2)
(1,1,1,2) (2,4,1)
(1,2,1,1) (1,1,2,3)
(1,2,2,2)
(1,3,2,1)
(2,1,1,3)
(2,2,1,2)
(2,3,1,1)
(1,1,1,3,1)
(1,2,1,2,1)
(1,3,1,1,1)
(1,1,1,1,1,2)
(1,1,1,2,1,1)
(1,2,1,1,1,1)
The following relate to these compositions.
- The unordered version is A000070.
- Allowing any negative alternating sum gives A000346.
- The opposite (positive 1) version is A000984.
- The version for reverse-alternating sum is also A001791 (this sequence).
- Taking alternating sum -2 instead of -1 gives A002054.
- The shifted version for alternating sum 0 is counted by A088218 and ranked by A344619.
- Ranked by A345910 (reverse: A345912).
Equivalently, a(n) counts binary numbers with 2n+1 digits and one more 0 than 1's. For example, the a(2) = 4 binary numbers are: 10001, 10010, 10100, 11000.
(End)
The diagonal of a square n X n matrix where cells of the first row are the nonnegative integers and cells of subsequent rows are sums of cells of the previous row up to and including n. - Torlach Rush, Apr 24 2024
For n>=1, a(n) is the independence number of the odd graph O_{n+1}. - Miquel A. Fiol, Jul 07 2024

References

  • M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 828.
  • Cornelius Lanczos, Applied Analysis, Prentice-Hall, Englewood Cliffs, NJ, 1956, p. 517.
  • R. C. Mullin, E. Nemeth and P. J. Schellenberg, The enumeration of almost cubic maps, pp. 281-295 in Proceedings of the Louisiana Conference on Combinatorics, Graph Theory and Computer Science. Vol. 1, edited R. C. Mullin et al., 1970.
  • 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).

Links

Crossrefs

Diagonal 3 of triangle A100257.
First differences are in A076540.
Cf. A000108, A000984, A002378, A002390, A025566, A132812.
A345197 counts compositions by length and alternating sum.
Cf. A000070, A000302, A000346, A002054, A008549, A032443, A088218, A097805, A163493, A202736, A345910.

Programs

  • GAP
    List([0..30],n->Binomial(2*n,n-1)); # Muniru A Asiru, Aug 09 2018
  • Magma
    [Binomial(2*n, n-1): n in [0..30]]; // Vincenzo Librandi, Apr 20 2015
  • Mathematica
    Table[Binomial[2n,n-1],{n,0,30}] (* Harvey P. Dale, Jul 12 2012 *)
CoefficientList[ Series[(1 - 2x - Sqrt[1 - 4x])/(2x*Sqrt[1 - 4x]), {x, 0, 26}], x] (* Robert G. Wilson v, Aug 10 2018 *)
  • Maxima
    A001791(n):=binomial(2*n,n-1)$
makelist(A001791(n),n,0,30); /* Martin Ettl, Nov 05 2012 */
  • PARI
    a(n)=if(n<1,0,(2*n)!/(n+1)!/(n-1)!)

Formula

a(n) = n*A000108(n).
G.f.: x*(d/dx)c(x) where c(x) = Catalan g.f. - Wolfdieter Lang
Convolution of A001700 (central binomial of odd order) and A000108 (Catalan): a(n+1) = Sum_{k=0..n} C(k)*binomial(2*(n-k)+1, n-k), C(k): Catalan. - Wolfdieter Lang
E.g.f.: exp(2x) * I_1(2x), where I_1 is Bessel function. - Michael Somos, Sep 08 2002
a(n) = Sum_{k=0..n} C(n, k)*C(n, k+1). - Paul Barry, May 15 2003
a(n) = Sum_{i=1..n} binomial(i+n-1, n).
G.f.: (1-2x-sqrt(1-4x))/(2x*sqrt(1-4x)). - Emeric Deutsch, Dec 05 2003
a(n) = A092956/(n!). - Amarnath Murthy, Jun 16 2004
a(n) = binomial(2n,n) - A000108(n). - Paul Barry, Apr 21 2005
a(n) = (1/(2*Pi))*Integral_{x=0..4} (x^n*(x-2)/sqrt(x(4-x))) is the moment sequence representation. - Paul Barry, Jan 11 2007
Row sums of triangle A132812 starting (1, 4, 15, 56, 210, ...). - Gary W. Adamson, Sep 01 2007
Starting (1, 4, 15, 56, 210, ...) gives the binomial transform of A025566 starting (1, 3, 8, 22, 61, 171, ...). - Gary W. Adamson, Sep 01 2007
For n >= 1, a(2^n) = 2^(n+1)*A001795(2^(n-1)). - Vladimir Shevelev, Sep 05 2010
D-finite with recurrence: (n-1)*(n+1)*a(n) = 2*n*(2n-1)*a(n-1). - R. J. Mathar, Dec 17 2011
From Sergei N. Gladkovskii, Jul 07 2012: (Start)
G.f.: -1/(2*x) - G(0) where G(k) = 1 - 1/(2*x - 8*x^3*(2*k+1)/(4*x^2*(2*k+1)- (k+1)/G(k+1))); (continued fraction, 3rd kind, 3-step);
E.g.f.: BesselI(1,2*x)*exp(2*x) = x*G(0) where G(k) = 1 + 2*x*(4*k+3)/((2*k+1)*(2*k+3) - x*(2*k+1)*(2*k+3)*(4*k+5)/(x*(4*k+5) + 2*(k+1)*(k+2)/G(k+1))); (continued fraction, 3rd kind, 3-step).
(End)
G.f.: c(x)^3/(2-c(x)) where c(x) is the g.f. for A000108. - Cheyne Homberger, May 05 2014
G.f.: z*C(z)^2/(1-2*z*C(z)), where C(z) is the g.f. of Catalan numbers. - José Luis Ramírez Ramírez, Apr 19 2015
G.f.: x*2F1(3/2,2;3;4x). - R. J. Mathar, Aug 09 2015
a(n) = Sum_{i=1..n} binomial(2*i-2,i-1)*binomial(2*(n-i+1),n-i+2)/(n-i+1). - Vladimir Kruchinin, Sep 07 2015
L.g.f.: 1/(1 - x/(1 - x/(1 - x/(1 - x/(1 - x/(1 - ...)))))) = Sum_{n>=1} a(n)*x^n/n. - Ilya Gutkovskiy, May 10 2017
Sum_{n>=1} 1/a(n) = 1/3 + 5*Pi/(9*sqrt(3)). - Amiram Eldar, Dec 04 2020
Sum_{n>=1} (-1)^(n+1)/a(n) = 1/5 + 14*sqrt(5)*log(phi)/25, where log(phi) = A002390. - Amiram Eldar, Feb 20 2021
a(n) = Product_{i=1..(n - 1)} (((4*i + 6)*i + 2)/((i + 2)*i)), for n>=1. - Neven Sajko, Oct 10 2021
a(n) = 2^(2*n)*gamma(n + 1/2)/(sqrt(Pi)*gamma(n)*(n+1)) for n > 0, and a(0) = lim_{n->0} a(n). - Karol A. Penson, Apr 24 2025

A027383 a(2*n) = 3*2^n - 2; a(2*n+1) = 2^(n+2) - 2.

Original entry on oeis.org

1, 2, 4, 6, 10, 14, 22, 30, 46, 62, 94, 126, 190, 254, 382, 510, 766, 1022, 1534, 2046, 3070, 4094, 6142, 8190, 12286, 16382, 24574, 32766, 49150, 65534, 98302, 131070, 196606, 262142, 393214, 524286, 786430, 1048574, 1572862, 2097150, 3145726, 4194302, 6291454
Offset: 0

Views

Author

R. K. Guy

Keywords

Comments

Number of balanced strings of length n: let d(S) = #(1's) - #(0's), # == count in S, then S is balanced if every substring T of S has -2 <= d(T) <= 2.
Number of "fold lines" seen when a rectangular piece of paper is folded n+1 times along alternate orthogonal directions and then unfolded. - Quim Castellsaguer (qcastell(AT)pie.xtec.es), Dec 30 1999
Also the number of binary strings with the property that, when scanning from left to right, once the first 1 is seen in position j, there must be a 1 in positions j+2, j+4, ... until the end of the string. (Positions j+1, j+3, ... can be occupied by 0 or 1.) - Jeffrey Shallit, Sep 02 2002
a(n-1) is also the Moore lower bound on the order of a (3,n)-cage. - Eric W. Weisstein, May 20 2003 and Jason Kimberley, Oct 30 2011
Partial sums of A016116. - Hieronymus Fischer, Sep 15 2007
Equals row sums of triangle A152201. - Gary W. Adamson, Nov 29 2008
From John P. McSorley, Sep 28 2010: (Start)
a(n) = DPE(n+1) is the total number of k-double-palindromes of n up to cyclic equivalence. See sequence A180918 for the definitions of a k-double-palindrome of n and of cyclic equivalence. Sequence A180918 is the 'DPE(n,k)' triangle read by rows where DPE(n,k) is the number of k-double-palindromes of n up to cyclic equivalence. For example, we have a(4) = DPE(5) = DPE(5,1) + DPE(5,2) + DPE(5,3) + DPE(5,4) + DPE(5,5) = 0 + 2 + 2 + 1 + 1 = 6.
The 6 double-palindromes of 5 up to cyclic equivalence are 14, 23, 113, 122, 1112, 11111. They come from cyclic equivalence classes {14,41}, {23,32}, {113,311,131}, {122,212,221}, {1112,2111,1211,1121}, and {11111}. Hence a(n)=DPE(n+1) is the total number of cyclic equivalence classes of n containing at least one double-palindrome.
(End)
From Herbert Eberle, Oct 02 2015: (Start)
For n > 0, there is a red-black tree of height n with a(n-1) internal nodes and none with less.
In order a red-black tree of given height has minimal number of nodes, it has exactly 1 path with strictly alternating red and black nodes. All nodes outside this height defining path are black.
Consider:
mrbt5 R
/ \
/ \
/ \
/ B
/ / \
mrbt4 B / B
/ \ B E E
/ B E E
mrbt3 R E E
/ \
/ B
mrbt2 B E E
/ E
mrbt1 R
E E
(Red nodes shown as R, blacks as B, externals as E.)
Red-black trees mrbt1, mrbt2, mrbt3, mrbt4, mrbt5 of respective heights h = 1, 2, 3, 4, 5; all minimal in the number of internal nodes, namely 1, 2, 4, 6, 10.
Recursion (let n = h-1): a(-1) = 0, a(n) = a(n-1) + 2^floor(n/2), n >= 0.
(End)
Also the number of strings of length n with the digits 1 and 2 with the property that the sum of the digits of all substrings of uneven length is not divisible by 3. An example with length 8 is 21221121. - Herbert Kociemba, Apr 29 2017
a(n-2) is the number of achiral n-bead necklaces or bracelets using exactly two colors. For n=4, the four arrangements are AAAB, AABB, ABAB, and ABBB. - Robert A. Russell, Sep 26 2018
Partial sums of powers of 2 repeated 2 times, like A200672 where is 3 times. - Yuchun Ji, Nov 16 2018
Also the number of binary words of length n with cuts-resistance <= 2, where, for the operation of shortening all runs by one, cuts-resistance is the number of applications required to reach an empty word. Explicitly, these are words whose sequence of run-lengths, all of which are 1 or 2, has no odd-length run of 1's sandwiched between two 2's. - Gus Wiseman, Nov 28 2019
Also the number of up-down paths with n steps such that the height difference between the highest and lowest points is at most 2. - Jeremy Dover, Jun 17 2020
Also the number of non-singleton integer compositions of n + 2 with no odd part other than the first or last. Including singletons gives A052955. This is an unsorted (or ordered) version of A351003. The version without even (instead of odd) interior parts is A001911, complement A232580. Note that A000045(n-1) counts compositions without odd parts, with non-singleton case A077896, and A052952/A074331 count non-singleton compositions without even parts. Also the number of compositions y of n + 1 such that y_i = y_{i+1} for all even i. - Gus Wiseman, Feb 19 2022

Examples

			After 3 folds one sees 4 fold lines.
Example: a(3) = 6 because the strings 001, 010, 100, 011, 101, 110 have the property.
Binary: 1, 10, 100, 110, 1010, 1110, 10110, 11110, 101110, 111110, 1011110, 1111110, 10111110, 11111110, 101111110, 111111110, 1011111110, 1111111110, 10111111110, ... - _Jason Kimberley_, Nov 02 2011
Example: Partial sums of powers of 2 repeated 2 times:
a(3) = 1+1+2 = 4;
a(4) = 1+1+2+2 = 6;
a(5) = 1+1+2+2+4 = 10.
_Yuchun Ji_, Nov 16 2018

References

  • John P. McSorley: Counting k-compositions of n with palindromic and related structures. Preprint, 2010. [John P. McSorley, Sep 28 2010]

Links

Crossrefs

Cf. A132666, A152201.
Moore lower bound on the order of a (k,g) cage: A198300 (square); rows: A000027 (k=2), this sequence (k=3), A062318 (k=4), A061547 (k=5), A198306 (k=6), A198307 (k=7), A198308 (k=8), A198309 (k=9), A198310 (k=10), A094626 (k=11); columns: A020725 (g=3), A005843 (g=4), A002522 (g=5), A051890 (g=6), A188377 (g=7). - Jason Kimberley, Oct 30 2011
Cf. A000066 (actual order of a (3,g)-cage).
Bisections are A033484 (even) and A000918 (odd).
a(n) = A305540(n+2,2), the second column of the triangle.
Numbers whose binary expansion is a balanced word are A330029.
Binary words counted by cuts-resistance are A319421 or A329860.
Cf. A000975, A062011, A329862, A329863.
The complementary compositions are counted by A274230(n-1) + 1, with bisections A060867 (even) and A134057 (odd).
Cf. A000346, A000984, A001405, A001700, A011782 (compositions).
The following sequences are all essentially the same, in the sense that they are simple transformations of each other, with A029744 = {s(n), n>=1}, the numbers 2^k and 3*2^k, as the parent: A029744 (s(n)); A052955 (s(n)-1), A027383 (s(n)-2), A354788 (s(n)-3), A347789 (s(n)-4), A209721 (s(n)+1), A209722 (s(n)+2), A343177 (s(n)+3), A209723 (s(n)+4); A060482, A136252 (minor differences from A354788 at the start); A354785 (3*s(n)), A354789 (3*s(n)-7). The first differences of A029744 are 1,1,1,2,2,4,4,8,8,... which essentially matches eight sequences: A016116, A060546, A117575, A131572, A152166, A158780, A163403, A320770. The bisections of A029744 are A000079 and A007283. - N. J. A. Sloane, Jul 14 2022

Programs

  • Haskell
    import Data.List (transpose)
a027383 n = a027383_list !! n
a027383_list = concat $ transpose [a033484_list, drop 2 a000918_list]
-- Reinhard Zumkeller, Jun 17 2015
  • Magma
    [2^Floor((n+2)/2)+2^Floor((n+1)/2)-2: n in [0..50]]; // Vincenzo Librandi, Aug 16 2011
  • Maple
    a[0]:=0:a[1]:=1:for n from 2 to 100 do a[n]:=2*a[n-2]+2 od: seq(a[n], n=1..41); # Zerinvary Lajos, Mar 16 2008
  • Mathematica
    a[n_?EvenQ] := 3*2^(n/2)-2; a[n_?OddQ] := 2^(2+(n-1)/2)-2; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Oct 21 2011, after Quim Castellsaguer *)
LinearRecurrence[{1, 2, -2}, {1, 2, 4}, 41] (* Robert G. Wilson v, Oct 06 2014 *)
Table[Length[Select[Tuples[{0,1},n],And[Max@@Length/@Split[#]<=2,!MatchQ[Length/@Split[#],{_,2,ins:1..,2,_}/;OddQ[Plus[ins]]]]&]],{n,0,15}] (* Gus Wiseman, Nov 28 2019 *)
  • PARI
    a(n)=2^(n\2+1)+2^((n+1)\2)-2 \\ Charles R Greathouse IV, Oct 21 2011
  • Python
    def a(n): return 2**((n+2)//2) + 2**((n+1)//2) - 2
print([a(n) for n in range(43)]) # Michael S. Branicky, Feb 19 2022

Formula

a(0)=1, a(1)=2; thereafter a(n+2) = 2*a(n) + 2.
a(2n) = 3*2^n - 2 = A033484(n);
a(2n-1) = 2^(n+1) - 2 = A000918(n+1).
G.f.: (1 + x)/((1 - x)*(1 - 2*x^2)). - David Callan, Jul 22 2008
a(n) = Sum_{k=0..n} 2^min(k, n-k).
a(n) = 2^floor((n+2)/2) + 2^floor((n+1)/2) - 2. - Quim Castellsaguer (qcastell(AT)pie.xtec.es)
a(n) = 2^(n/2)*(3 + 2*sqrt(2) + (3-2*sqrt(2))*(-1)^n)/2 - 2. - Paul Barry, Apr 23 2004
a(n) = A132340(A052955(n)). - Reinhard Zumkeller, Aug 20 2007
a(n) = A052955(n+1) - 1. - Hieronymus Fischer, Sep 15 2007
a(n) = A132666(a(n+1)) - 1. - Hieronymus Fischer, Sep 15 2007
a(n) = A132666(a(n-1)+1) for n > 0. - Hieronymus Fischer, Sep 15 2007
A132666(a(n)) = a(n-1) + 1 for n > 0. - Hieronymus Fischer, Sep 15 2007
G.f.: (1 + x)/((1 - x)*(1 - 2*x^2)). - David Callan, Jul 22 2008
a(n) = 2*( (a(n-2)+1) mod (a(n-1)+1) ), n > 1. - Pierre Charland, Dec 12 2010
a(n) = A136252(n-1) + 1, for n > 0. - Jason Kimberley, Nov 01 2011
G.f.: (1+x*R(0))/(1-x), where R(k) = 1 + 2*x/( 1 - x/(x + 1/R(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 16 2013
a(n) = 2^((2*n + 3*(1-(-1)^n))/4)*3^((1+(-1)^n)/2) - 2. - Luce ETIENNE, Sep 01 2014
a(n) = a(n-1) + 2^floor((n-1)/2) for n>0, a(0)=1. - Yuchun Ji, Nov 23 2018
E.g.f.: 3*cosh(sqrt(2)*x) - 2*cosh(x) + 2*sqrt(2)*sinh(sqrt(2)*x) - 2*sinh(x). - Stefano Spezia, Apr 06 2022

Extensions

More terms from Larry Reeves (larryr(AT)acm.org), Mar 24 2000
Replaced definition with a simpler one. - N. J. A. Sloane, Jul 09 2022
Showing 1-10 of 94 results. Next

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.