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 27 results. Next

A000129 Pell numbers: a(0) = 0, a(1) = 1; for n > 1, a(n) = 2*a(n-1) + a(n-2).

Original entry on oeis.org

0, 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, 5741, 13860, 33461, 80782, 195025, 470832, 1136689, 2744210, 6625109, 15994428, 38613965, 93222358, 225058681, 543339720, 1311738121, 3166815962, 7645370045, 18457556052, 44560482149, 107578520350, 259717522849
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Sometimes also called lambda numbers.
Also denominators of continued fraction convergents to sqrt(2): 1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408, 1393/985, 3363/2378, 8119/5741, 19601/13860, 47321/33461, 114243/80782, ... = A001333/A000129.
Number of lattice paths from (0,0) to the line x=n-1 consisting of U=(1,1), D=(1,-1) and H=(2,0) steps (i.e., left factors of Grand Schroeder paths); for example, a(3)=5, counting the paths H, UD, UU, DU and DD. - Emeric Deutsch, Oct 27 2002
a(2*n) with b(2*n) := A001333(2*n), n >= 1, give all (positive integer) solutions to Pell equation b^2 - 2*a^2 = +1 (see Emerson reference). a(2*n+1) with b(2*n+1) := A001333(2*n+1), n >= 0, give all (positive integer) solutions to Pell equation b^2 - 2*a^2 = -1.
Bisection: a(2*n+1) = T(2*n+1, sqrt(2))/sqrt(2) = A001653(n), n >= 0 and a(2*n) = 2*S(n-1,6) = 2*A001109(n), n >= 0, with T(n,x), resp. S(n,x), Chebyshev's polynomials of the first, resp. second kind. S(-1,x)=0. See A053120, resp. A049310. - Wolfdieter Lang, Jan 10 2003
Consider the mapping f(a/b) = (a + 2b)/(a + b). Taking a = b = 1 to start with and carrying out this mapping repeatedly on each new (reduced) rational number gives the following sequence 1/1, 3/2, 7/5, 17/12, 41/29, ... converging to 2^(1/2). Sequence contains the denominators. - Amarnath Murthy, Mar 22 2003
This is also the Horadam sequence (0,1,1,2). Limit_{n->oo} a(n)/a(n-1) = sqrt(2) + 1 = A014176. - Ross La Haye, Aug 18 2003
Number of 132-avoiding two-stack sortable permutations.
From Herbert Kociemba, Jun 02 2004: (Start)
For n > 0, the number of (s(0), s(1), ..., s(n)) such that 0 < s(i) < 4 and |s(i) - s(i-1)| <= 1 for i = 1,2,...,n, s(0) = 2, s(n) = 3.
Number of (s(0), s(1), ..., s(n)) such that 0 < s(i) < 4 and |s(i) - s(i-1)| <= 1 for i = 1,2,...,n, s(0) = 1, s(n) = 2. (End)
Counts walks of length n from a vertex of a triangle to another vertex to which a loop has been added. - Mario Catalani (mario.catalani(AT)unito.it), Jul 23 2004
Apart from initial terms, Pisot sequence P(2,5). See A008776 for definition of Pisot sequences. - David W. Wilson
Sums of antidiagonals of A038207 [Pascal's triangle squared]. - Ross La Haye, Oct 28 2004
The Pell primality test is "If N is an odd prime, then P(N)-Kronecker(2,N) is divisible by N". "Most" composite numbers fail this test, so it makes a useful pseudoprimality test. The odd composite numbers which are Pell pseudoprimes (i.e., that pass the above test) are in A099011. - Jack Brennen, Nov 13 2004
a(n) = sum of n-th row of triangle in A008288 = A094706(n) + A000079(n). - Reinhard Zumkeller, Dec 03 2004
Pell trapezoids (cf. A084158); for n > 0, A001109(n) = (a(n-1) + a(n+1))*a(n)/2; e.g., 1189 = (12+70)*29/2. - Charlie Marion, Apr 01 2006
(0!a(1), 1!a(2), 2!a(3), 3!a(4), ...) and (1,-2,-2,0,0,0,...) form a reciprocal pair under the list partition transform and associated operations described in A133314. - Tom Copeland, Oct 29 2007
Let C = (sqrt(2)+1) = 2.414213562..., then for n > 1, C^n = a(n)*(1/C) + a(n+1). Example: C^3 = 14.0710678... = 5*(0.414213562...) + 12. Let X = the 2 X 2 matrix [0, 1; 1, 2]; then X^n * [1, 0] = [a(n-1), a(n); a(n), a(n+1)]. a(n) = numerator of n-th convergent to (sqrt(2)-1) = 0.414213562... = [2, 2, 2, ...], the convergents being [1/2, 2/5, 5/12, ...]. - Gary W. Adamson, Dec 21 2007
A = sqrt(2) = 2/2 + 2/5 + 2/(5*29) + 2/(29*169) + 2/(169*985) + ...; B = ((5/2) - sqrt(2)) = 2/2 + 2/(2*12) + 2/(12*70) + 2/(70*408) + 2/(408*2378) + ...; A+B = 5/2. C = 1/2 = 2/(1*5) + 2/(2*12) + 2/(5*29) + 2/(12*70) + 2/(29*169) + ... - Gary W. Adamson, Mar 16 2008
From Clark Kimberling, Aug 27 2008: (Start)
Related convergents (numerator/denominator):
lower principal convergents: A002315/A001653
upper principal convergents: A001541/A001542
intermediate convergents: A052542/A001333
lower intermediate convergents: A005319/A001541
upper intermediate convergents: A075870/A002315
principal and intermediate convergents: A143607/A002965
lower principal and intermediate convergents: A143608/A079496
upper principal and intermediate convergents: A143609/A084068. (End)
Equals row sums of triangle A143808 starting with offset 1. - Gary W. Adamson, Sep 01 2008
Binomial transform of the sequence:= 0,1,0,2,0,4,0,8,0,16,..., powers of 2 alternating with zeros. - Philippe Deléham, Oct 28 2008
a(n) is also the sum of the n-th row of the triangle formed by starting with the top two rows of Pascal's triangle and then each next row has a 1 at both ends and the interior values are the sum of the three numbers in the triangle above that position. - Patrick Costello (pat.costello(AT)eku.edu), Dec 07 2008
Starting with offset 1 = eigensequence of triangle A135387 (an infinite lower triangular matrix with (2,2,2,...) in the main diagonal and (1,1,1,...) in the subdiagonal). - Gary W. Adamson, Dec 29 2008
Starting with offset 1 = row sums of triangle A153345. - Gary W. Adamson, Dec 24 2008
From Charlie Marion, Jan 07 2009: (Start)
In general, denominators, a(k,n) and numerators, b(k,n), of continued fraction convergents to sqrt((k+1)/k) may be found as follows:
let a(k,0) = 1, a(k,1) = 2k; for n > 0, a(k,2n) = 2*a(k,2n-1) + a(k,2n-2)
and a(k,2n+1) = (2k)*a(k,2n) + a(k,2n-1);
let b(k,0) = 1, b(k,1) = 2k+1; for n > 0, b(k,2n) = 2*b(k,2n-1) + b(k,2n-2)
and b(k,2n+1) = (2k)*b(k,2n) + b(k,2n-1).
For example, the convergents to sqrt(2/1) start 1/1, 3/2, 7/5, 17/12, 41/29.
In general, if a(k,n) and b(k,n) are the denominators and numerators, respectively, of continued fraction convergents to sqrt((k+1)/k) as defined above, then
k*a(k,2n)^2 - a(k,2n-1)*a(k,2n+1) = k = k*a(k,2n-2)*a(k,2n) - a(k,2n-1)^2 and
b(k,2n-1)*b(k,2n+1) - k*b(k,2n)^2 = k+1 = b(k,2n-1)^2 - k*b(k,2n-2)*b(k,2n);
for example, if k=1 and n=3, then a(1,n) = a(n+1) and
1*a(1,6)^2 - a(1,5)*a(1,7) = 1*169^2 - 70*408 = 1;
1*a(1,4)*a(1,6) - a(1,5)^2 = 1*29*169 - 70^2 = 1;
b(1,5)*b(1,7) - 1*b(1,6)^2 = 99*577 - 1*239^2 = 2;
b(1,5)^2 - 1*b(1,4)*b(1,6) = 99^2 - 1*41*239 = 2.
Cf. A001333, A142238, A142239, A153313, A153314, A153315, A153316, A153317, A153318.
(End)
Starting with offset 1 = row sums of triangle A155002, equivalent to the statement that the Fibonacci sequence convolved with the Pell sequence prefaced with a "1": (1, 1, 2, 5, 12, 29, ...) = (1, 2, 5, 12, 29, ...). - Gary W. Adamson, Jan 18 2009
It appears that P(p) == 8^((p-1)/2) (mod p), p = prime; analogous to [Schroeder, p. 90]: Fp == 5^((p-1)/2) (mod p). Example: Given P(11) = 5741, == 8^5 (mod 11). Given P(17) = 11336689, == 8^8 (mod 17) since 17 divides (8^8 - P(17)). - Gary W. Adamson, Feb 21 2009
Equals eigensequence of triangle A154325. - Gary W. Adamson, Feb 12 2009
Another combinatorial interpretation of a(n-1) arises from a simple tiling scenario. Namely, a(n-1) gives the number of ways of tiling a 1 X n rectangle with indistinguishable 1 X 2 rectangles and 1 X 1 squares that come in two varieties, say, A and B. For example, with C representing the 1 X 2 rectangle, we obtain a(4)=12 from AAA, AAB, ABA, BAA, ABB, BAB, BBA, BBB, AC, BC, CA and CB. - Martin Griffiths, Apr 25 2009
a(n+1) = 2*a(n) + a(n-1), a(1)=1, a(2)=2 was used by Theon from Smyrna. - Sture Sjöstedt, May 29 2009
The n-th Pell number counts the perfect matchings of the edge-labeled graph C_2 x P_(n-1), or equivalently, the number of domino tilings of a 2 X (n-1) cylindrical grid. - Sarah-Marie Belcastro, Jul 04 2009
As a fraction: 1/79 = 0.0126582278481... or 1/9799 = 0.000102051229...(1/119 and 1/10199 for sequence in reverse). - Mark Dols, May 18 2010
Limit_{n->oo} (a(n)/a(n-1) - a(n-1)/a(n)) tends to 2.0. Example: a(7)/a(6) - a(6)/a(7) = 169/70 - 70/169 = 2.0000845... - Gary W. Adamson, Jul 16 2010
Numbers k such that 2*k^2 +- 1 is a square. - Vincenzo Librandi, Jul 18 2010
Starting (1, 2, 5, ...) = INVERTi transform of A006190: (1, 3, 10, 33, 109, ...). - Gary W. Adamson, Aug 06 2010
[u,v] = [a(n), a(n-1)] generates all Pythagorean triples [u^2-v^2, 2uv, u^2+v^2] whose legs differ by 1. - James R. Buddenhagen, Aug 14 2010
An elephant sequence, see A175654. For the corner squares six A[5] vectors, with decimal values between 21 and 336, lead to this sequence (without the leading 0). For the central square these vectors lead to the companion sequence A078057. - Johannes W. Meijer, Aug 15 2010
Let the 2 X 2 square matrix A=[2, 1; 1, 0] then a(n) = the (1,1) element of A^(n-1). - Carmine Suriano, Jan 14 2011
Define a t-circle to be a first-quadrant circle tangent to the x- and y-axes. Such a circle has coordinates equal to its radius. Let C(0) be the t-circle with radius 1. Then for n > 0, define C(n) to be the next larger t-circle which is tangent to C(n - 1). C(n) has radius A001333(2n) + a(2n)*sqrt(2) and each of the coordinates of its point of intersection with C(n + 1) is a(2n + 1) + (A001333(2n + 1)*sqrt(2))/2. See similar Comments for A001109 and A001653, Sep 14 2005. - Charlie Marion, Jan 18 2012
A001333 and A000129 give the diagonal numbers described by Theon from Smyrna. - Sture Sjöstedt, Oct 20 2012
Pell numbers could also be called "silver Fibonacci numbers", since, for n >= 1, F(n+1) = ceiling(phi*F(n)), if n is even and F(n+1) = floor(phi*F(n)), if n is odd, where phi is the golden ratio, while a(n+1) = ceiling(delta*a(n)), if n is even and a(n+1) = floor(delta*a(n)), if n is odd, where delta = delta_S = 1+sqrt(2) is the silver ratio. - Vladimir Shevelev, Feb 22 2013
a(n) is the number of compositions (ordered partitions) of n-1 into two sorts of 1's and one sort of 2's. Example: the a(3)=5 compositions of 3-1=2 are 1+1, 1+1', 1'+1, 1'+1', and 2. - Bob Selcoe, Jun 21 2013
Between every two consecutive squares of a 1 X n array there is a flap that can be folded over one of the two squares. Two flaps can be lowered over the same square in 2 ways, depending on which one is on top. The n-th Pell number counts the ways n-1 flaps can be lowered. For example, a sideway representation for the case n = 3 squares and 2 flaps is \\., .//, \./, ./., .\., where . is an empty square. - Jean M. Morales, Sep 18 2013
Define a(-n) to be a(n) for n odd and -a(n) for n even. Then a(n) = A005319(k)*(a(n-2k+1) - a(n-2k)) + a(n-4k) = A075870(k)*(a(n-2k+2) - a(n-2k+1)) - a(n-4k+2). - Charlie Marion, Nov 26 2013
An alternative formulation of the combinatorial tiling interpretation listed above: Except for n=0, a(n-1) is the number of ways of partial tiling a 1 X n board with 1 X 1 squares and 1 X 2 dominoes. - Matthew Lehman, Dec 25 2013
Define a(-n) to be a(n) for n odd and -a(n) for n even. Then a(n) = A077444(k)*a(n-2k+1) + a(n-4k+2). This formula generalizes the formula used to define this sequence. - Charlie Marion, Jan 30 2014
a(n-1) is the top left entry of the n-th power of any of the 3 X 3 matrices [0, 1, 1; 1, 1, 1; 0, 1, 1], [0, 1, 1; 0, 1, 1; 1, 1, 1], [0, 1, 0; 1, 1, 1; 1, 1, 1] or [0, 0, 1; 1, 1, 1; 1, 1, 1]. - R. J. Mathar, Feb 03 2014
a(n+1) counts closed walks on K2 containing two loops on the other vertex. Equivalently the (1,1) entry of A^(n+1) where the adjacency matrix of digraph is A=(0,1;1,2). - David Neil McGrath, Oct 28 2014
For n >= 1, a(n) equals the number of ternary words of length n-1 avoiding runs of zeros of odd lengths. - Milan Janjic, Jan 28 2015
This is a divisibility sequence (i.e., if n|m then a(n)|a(m)). - Tom Edgar, Jan 28 2015
A strong divisibility sequence, that is, gcd(a(n), a(m)) = a(gcd(n, m)) for all positive integers n and m. - Michael Somos, Jan 03 2017
a(n) is the number of compositions (ordered partitions) of n-1 into two kinds of parts, n and n', when the order of the 1 does not matter, or equivalently, when the order of the 1' does not matter. Example: When the order of the 1 does not matter, the a(3)=5 compositions of 3-1=2 are 1+1, 1+1'=1+1, 1'+1', 2 and 2'. (Contrast with entry from Bob Selcoe dated Jun 21 2013.) - Gregory L. Simay, Sep 07 2017
Number of weak orderings R on {1,...,n} that are weakly single-peaked w.r.t. the total ordering 1 < ... < n and for which {1,...,n} has exactly one minimal element for the weak ordering R. - J. Devillet, Sep 28 2017
Also the number of matchings in the (n-1)-centipede graph. - Eric W. Weisstein, Sep 30 2017
Let A(r,n) be the total number of ordered arrangements of an n+r tiling of r red squares and white tiles of total length n, where the individual tile lengths can range from 1 to n. A(r,0) corresponds to a tiling of r red squares only, and so A(r,0)=1. Let A_1(r,n) = Sum_{j=0..n} A(r,j) and let A_s(r,n) = Sum_{j=0..n} A_(s-1)(r,j). Then A_0(1,n) + A_2(3,n-4) + A_4(5,n-8) + ... + A_(2j) (2j+1, n-4j) = a(n) without the initial 0. - Gregory L. Simay, May 25 2018
(1, 2, 5, 12, 29, ...) is the fourth INVERT transform of (1, -2, 5, -12, 29, ...), as shown in A073133. - Gary W. Adamson, Jul 17 2019
Number of 2-compositions of n restricted to odd parts (and allowed zeros); see Hopkins & Ouvry reference. - Brian Hopkins, Aug 17 2020
Also called the 2-metallonacci sequence; the g.f. 1/(1-k*x-x^2) gives the k-metallonacci sequence. - Michael A. Allen, Jan 23 2023
Named by Lucas (1878) after the English mathematician John Pell (1611-1685). - Amiram Eldar, Oct 02 2023
a(n) is the number of compositions of n when there are F(i) parts of size i, with i,n >= 1, F(n) the Fibonacci numbers, A000045(n) (see example below). - Enrique Navarrete, Dec 15 2023

Examples

			G.f. = x + 2*x^2 + 5*x^3 + 12*x^4 + 29*x^5 + 70*x^6 + 169*x^7 + 408*x^8 + 985*x^9 + ...
From _Enrique Navarrete_, Dec 15 2023: (Start)
From the comment on compositions with Fibonacci number of parts, F(n), there are F(1)=1 type of 1, F(2)=1 type of 2, F(3)=2 types of 3, F(4)=3 types of 4, F(5)=5 types of 5 and F(6)=8 types of 6.
The following table gives the number of compositions of n=6 with Fibonacci number of parts:
Composition, number of such compositions, number of compositions of this type:
6,           1,     8;
5+1,         2,    10;
4+2,         2,     6;
3+3,         1,     4;
4+1+1,       3,     9;
3+2+1,       6,    12;
2+2+2,       1,     1;
3+1+1+1,     4,     8;
2+2+1+1,     6,     6;
2+1+1+1+1,   5,     5;
1+1+1+1+1+1, 1,     1;
for a total of a(6)=70 compositions of n=6. (End).

References

  • J. Austin and L. Schneider, Generalized Fibonacci sequences in Pythagorean triple preserving sequences, Fib. Q., 58:1 (2020), 340-350.
  • P. Bachmann, Niedere Zahlentheorie (1902, 1910), reprinted Chelsea, NY, 1968, vol. 2, p. 76.
  • A. H. Beiler, Recreations in the Theory of Numbers. New York: Dover, pp. 122-125, 1964.
  • Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 941.
  • J. M. Borwein, D. H. Bailey, and R. Girgensohn, Experimentation in Mathematics, A K Peters, Ltd., Natick, MA, 2004. x+357 pp. See p. 53.
  • John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See p. 204.
  • John Derbyshire, Prime Obsession, Joseph Henry Press, 2004, see p. 16.
  • S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 1.1.
  • Shaun Giberson and Thomas J. Osler, Extending Theon's Ladder to Any Square Root, Problem 3858, Elementa, No. 4 1996.
  • R. P. Grimaldi, Ternary strings with no consecutive 0's and no consecutive 1's, Congressus Numerantium, 205 (2011), 129-149.
  • Jan Gullberg, Mathematics from the Birth of Numbers, W. W. Norton & Co., NY & London, 1997, §8.5 The Fibonacci and Related Sequences, p. 288.
  • Thomas Koshy, Pell and Pell-Lucas Numbers with Applications, Springer, New York, 2014.
  • Serge Lang, Introduction to Diophantine Approximations, Addison-Wesley, New York, 1966.
  • Paulo Ribenboim, The Book of Prime Number Records. Springer-Verlag, NY, 2nd ed., 1989, p. 43.
  • Paulo Ribenboim, My Numbers, My Friends: Popular Lectures on Number Theory, Springer-Verlag, NY, 2000, p. 3.
  • Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See pp. 46, 61.
  • J. Roberts, Lure of the Integers, Math. Assoc. America, 1992, p. 224.
  • Manfred R. Schroeder, "Number Theory in Science and Communication", 5th ed., Springer-Verlag, 2009, p. 90.
  • 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).
  • David Wells, The Penguin Dictionary of Curious and Interesting Numbers. Penguin Books, NY, 1986, Revised edition 1987, p. 34.
  • D. B. West, Combinatorial Mathematics, Cambridge, 2021, p. 62.

Links

Crossrefs

Partial sums of A001333.
2nd row of A172236.
a(n) = A054456(n-1, 0), n>=1 (first column of triangle).
Cf. A002203, A096669, A096670, A097075, A097076, A051927, A005409.
Cf. A175181 (Pisano periods), A214028 (Entry points), A214027 (number of zeros in a fundamental period).
A077985 is a signed version.
INVERT transform of Fibonacci numbers (A000045).
Cf. A038207.
The following sequences (and others) belong to the same family: A001333, A000129, A026150, A002605, A046717, A015518, A084057, A063727, A002533, A002532, A083098, A083099, A083100, A015519.
Cf. A034867, A131980, A133156, A143808, A135387, A153346, A001622, A006497, A014176 (growth power), A098316, A154325, A021083, A243399, A008555.
Cf. A048739.
Cf. A073133.
Cf. A041085.
Cf. A157103, A352361.
Sequences with g.f. 1/(1-k*x-x^2) or x/(1-k*x-x^2): A000045 (k=1), this sequence (k=2), A006190 (k=3), A001076 (k=4), A052918 (k=5), A005668 (k=6), A054413 (k=7), A041025 (k=8), A099371 (k=9), A041041 (k=10), A049666 (k=11), A041061 (k=12), A140455 (k=13), A041085 (k=14), A154597 (k=15), A041113 (k=16), A178765 (k=17), A041145 (k=18), A243399 (k=19), A041181 (k=20).

Programs

  • GAP
    a := [0,1];; for n in [3..10^3] do a[n] := 2 * a[n-1] + a[n-2]; od; A000129 := a; # Muniru A Asiru, Oct 16 2017
  • Haskell
    a000129 n = a000129_list !! n
a000129_list = 0 : 1 : zipWith (+) a000129_list (map (2 *) $ tail a000129_list)
-- Reinhard Zumkeller, Jan 05 2012, Feb 05 2011
  • Magma
    [0] cat [n le 2 select n else 2*Self(n-1) + Self(n-2): n in [1..35]]; // Vincenzo Librandi, Aug 08 2015
  • Maple
    A000129 := proc(n) option remember; if n <=1 then n; else 2*procname(n-1)+procname(n-2); fi; end;
a:= n-> (<<2|1>, <1|0>>^n)[1, 2]: seq(a(n), n=0..40); # Alois P. Heinz, Aug 01 2008
A000129 := n -> `if`(n<2, n, 2^(n-1)*hypergeom([1-n/2, (1-n)/2], [1-n], -1)):
seq(simplify(A000129(n)), n=0..31); # Peter Luschny, Dec 17 2015
  • Mathematica
    CoefficientList[Series[x/(1 - 2*x - x^2), {x, 0, 60}], x] (* Stefan Steinerberger, Apr 08 2006 *)
Expand[Table[((1 + Sqrt[2])^n - (1 - Sqrt[2])^n)/(2Sqrt[2]), {n, 0, 30}]] (* Artur Jasinski, Dec 10 2006 *)
LinearRecurrence[{2, 1}, {0, 1}, 60] (* Harvey P. Dale, Jan 04 2012 *)
a[ n_] := With[ {s = Sqrt@2}, ((1 + s)^n - (1 - s)^n) / (2 s)] // Simplify; (* Michael Somos, Jun 01 2013 *)
Table[Fibonacci[n, 2], {n, 0, 20}] (* Vladimir Reshetnikov, May 08 2016 *)
Fibonacci[Range[0, 20], 2] (* Eric W. Weisstein, Sep 30 2017 *)
a[ n_] := ChebyshevU[n - 1, I] / I^(n - 1); (* Michael Somos, Oct 30 2021 *)
  • Maxima
    a[0]:0$
a[1]:1$
a[n]:=2*a[n-1]+a[n-2]$
A000129(n):=a[n]$
makelist(A000129(n),n,0,30); /* Martin Ettl, Nov 03 2012 */
  • Maxima
    makelist((%i)^(n-1)*ultraspherical(n-1,1,-%i),n,0,24),expand; /* Emanuele Munarini, Mar 07 2018 */
  • PARI
    for (n=0, 4000, a=contfracpnqn(vector(n, i, 1+(i>1)))[2, 1]; if (a > 10^(10^3 - 6), break); write("b000129.txt", n, " ", a)); \\ Harry J. Smith, Jun 12 2009
  • PARI
    {a(n) = imag( (1 + quadgen( 8))^n )}; /* Michael Somos, Jun 01 2013 */
  • PARI
    {a(n) = if( n<0, -(-1)^n, 1) * contfracpnqn( vector( abs(n), i, 1 + (i>1))) [2, 1]}; /* Michael Somos, Jun 01 2013 */
  • PARI
    a(n)=([2, 1; 1, 0]^n)[2,1] \\ Charles R Greathouse IV, Mar 04 2014
  • PARI
    {a(n) = polchebyshev(n-1, 2, I) / I^(n-1)}; /* Michael Somos, Oct 30 2021 */
  • Python
    from itertools import islice
def A000129_gen(): # generator of terms
    a, b = 0, 1
    yield from [a,b]
    while True:
        a, b = b, a+2*b
        yield b
A000129_list = list(islice(A000129_gen(),20)) # Chai Wah Wu, Jan 11 2022
  • Sage
    [lucas_number1(n, 2, -1) for n in range(30)]  # Zerinvary Lajos, Apr 22 2009

Formula

G.f.: x/(1 - 2*x - x^2). - Simon Plouffe in his 1992 dissertation.
a(2n+1)=A001653(n). a(2n)=A001542(n). - Ira Gessel, Sep 27 2002
G.f.: Sum_{n >= 0} x^(n+1) *( Product_{k = 1..n} (2*k + x)/(1 + 2*k*x) ) = Sum_{n >= 0} x^(n+1) *( Product_{k = 1..n} (x + 1 + k)/(1 + k*x) ) = Sum_{n >= 0} x^(n+1) *( Product_{k = 1..n} (x + 3 - k)/(1 - k*x) ) may all be proved using telescoping series. - Peter Bala, Jan 04 2015
a(n) = 2*a(n-1) + a(n-2), a(0)=0, a(1)=1.
a(n) = ((1 + sqrt(2))^n - (1 - sqrt(2))^n)/(2*sqrt(2)).
For initial values a(0) and a(1), a(n) = ((a(0)*sqrt(2)+a(1)-a(0))*(1+sqrt(2))^n + (a(0)*sqrt(2)-a(1)+a(0))*(1-sqrt(2))^n)/(2*sqrt(2)). - Shahreer Al Hossain, Aug 18 2019
a(n) = integer nearest a(n-1)/(sqrt(2) - 1), where a(0) = 1. - Clark Kimberling
a(n) = Sum_{i, j, k >= 0: i+j+2k = n} (i+j+k)!/(i!*j!*k!).
a(n)^2 + a(n+1)^2 = a(2n+1) (1999 Putnam examination).
a(2n) = 2*a(n)*A001333(n). - John McNamara, Oct 30 2002
a(n) = ((-i)^(n-1))*S(n-1, 2*i), with S(n, x) := U(n, x/2) Chebyshev's polynomials of the second kind. See A049310. S(-1, x)=0, S(-2, x)= -1.
Binomial transform of expansion of sinh(sqrt(2)x)/sqrt(2). E.g.f.: exp(x)sinh(sqrt(2)x)/sqrt(2). - Paul Barry, May 09 2003
a(n) = Sum_{k=0..floor(n/2)} binomial(n, 2k+1)*2^k. - Paul Barry, May 13 2003
a(n-2) + a(n) = (1 + sqrt(2))^(n-1) + (1 - sqrt(2))^(n-1) = A002203(n-1). (A002203(n))^2 - 8(a(n))^2 = 4(-1)^n. - Gary W. Adamson, Jun 15 2003
Unreduced g.f.: x(1+x)/(1 - x - 3x^2 - x^3); a(n) = a(n-1) + 3*a(n-2) + a(n-2). - Mario Catalani (mario.catalani(AT)unito.it), Jul 23 2004
a(n+1) = Sum_{k=0..floor(n/2)} binomial(n-k, k)*2^(n-2k). - Mario Catalani (mario.catalani(AT)unito.it), Jul 23 2004
Apart from initial terms, inverse binomial transform of A052955. - Paul Barry, May 23 2004
a(n)^2 + a(n+2k+1)^2 = A001653(k)*A001653(n+k); e.g., 5^2 + 70^2 = 5*985. - Charlie Marion Aug 03 2005
a(n+1) = Sum_{k=0..n} binomial((n+k)/2, (n-k)/2)*(1+(-1)^(n-k))*2^k/2. - Paul Barry, Aug 28 2005
a(n) = a(n-1) + A001333(n-1) = A001333(n) - a(n-1) = A001109(n)/A001333(n) = sqrt(A001110(n)/A001333(n)^2) = ceiling(sqrt(A001108(n)/2)). - Henry Bottomley, Apr 18 2000
a(n) = F(n, 2), the n-th Fibonacci polynomial evaluated at x=2. - T. D. Noe, Jan 19 2006
Define c(2n) = -A001108(n), c(2n+1) = -A001108(n+1) and d(2n) = d(2n+1) = A001652(n); then ((-1)^n)*(c(n) + d(n)) = a(n). [Proof given by Max Alekseyev.] - Creighton Dement, Jul 21 2005
a(r+s) = a(r)*a(s+1) + a(r-1)*a(s). - Lekraj Beedassy, Sep 03 2006
a(n) = (b(n+1) + b(n-1))/n where {b(n)} is the sequence A006645. - Sergio Falcon, Nov 22 2006
From Miklos Kristof, Mar 19 2007: (Start)
Let F(n) = a(n) = Pell numbers, L(n) = A002203 = companion Pell numbers (A002203):
For a >= b and odd b, F(a+b) + F(a-b) = L(a)*F(b).
For a >= b and even b, F(a+b) + F(a-b) = F(a)*L(b).
For a >= b and odd b, F(a+b) - F(a-b) = F(a)*L(b).
For a >= b and even b, F(a+b) - F(a-b) = L(a)*F(b).
F(n+m) + (-1)^m*F(n-m) = F(n)*L(m).
F(n+m) - (-1)^m*F(n-m) = L(n)*F(m).
F(n+m+k) + (-1)^k*F(n+m-k) + (-1)^m*(F(n-m+k) + (-1)^k*F(n-m-k)) = F(n)*L(m)*L(k).
F(n+m+k) - (-1)^k*F(n+m-k) + (-1)^m*(F(n-m+k) - (-1)^k*F(n-m-k)) = L(n)*L(m)*F(k).
F(n+m+k) + (-1)^k*F(n+m-k) - (-1)^m*(F(n-m+k) + (-1)^k*F(n-m-k)) = L(n)*F(m)*L(k).
F(n+m+k) - (-1)^k*F(n+m-k) - (-1)^m*(F(n-m+k) - (-1)^k*F(n-m-k)) = 8*F(n)*F(m)*F(k). (End)
a(n+1)*a(n) = 2*Sum_{k=0..n} a(k)^2 (a similar relation holds for A001333). - Creighton Dement, Aug 28 2007
a(n+1) = Sum_{k=0..n} binomial(n+1,2k+1) * 2^k = Sum_{k=0..n} A034867(n,k) * 2^k = (1/n!) * Sum_{k=0..n} A131980(n,k) * 2^k. - Tom Copeland, Nov 30 2007
Equals row sums of unsigned triangle A133156. - Gary W. Adamson, Apr 21 2008
a(n) (n >= 3) is the determinant of the (n-1) X (n-1) tridiagonal matrix with diagonal entries 2, superdiagonal entries 1 and subdiagonal entries -1. - Emeric Deutsch, Aug 29 2008
a(n) = A000045(n) + Sum_{k=1..n-1} A000045(k)*a(n-k). - Roger L. Bagula and Gary W. Adamson, Sep 07 2008
From Hieronymus Fischer, Jan 02 2009: (Start)
fract((1+sqrt(2))^n) = (1/2)*(1 + (-1)^n) - (-1)^n*(1+sqrt(2))^(-n) = (1/2)*(1 + (-1)^n) - (1-sqrt(2))^n.
See A001622 for a general formula concerning the fractional parts of powers of numbers x > 1, which satisfy x - x^(-1) = floor(x).
a(n) = round((1+sqrt(2))^n/(2*sqrt(2))) for n > 0. (End) [last formula corrected by Josh Inman, Mar 05 2024]
a(n) = ((4+sqrt(18))*(1+sqrt(2))^n + (4-sqrt(18))*(1-sqrt(2))^n)/4 offset 0. - Al Hakanson (hawkuu(AT)gmail.com), Aug 08 2009
If p[i] = Fibonacci(i) and if A is the Hessenberg matrix of order n defined by A[i,j] = p[j-i+1] when i<=j, A[i,j]=-1 when i=j+1, and A[i,j]=0 otherwise, then, for n >= 1, a(n) = det A. - Milan Janjic, May 08 2010
a(n) = 3*a(n-1) - a(n-2) - a(n-3), n > 2. - Gary Detlefs, Sep 09 2010
From Charlie Marion, Apr 13 2011: (Start)
a(n) = 2*(a(2k-1) + a(2k))*a(n-2k) - a(n-4k).
a(n) = 2*(a(2k) + a(2k+1))*a(n-2k-1) + a(n-4k-2). (End)
G.f.: x/(1 - 2*x - x^2) = sqrt(2)*G(0)/4; G(k) = ((-1)^k) - 1/(((sqrt(2) + 1)^(2*k)) - x*((sqrt(2) + 1)^(2*k))/(x + ((sqrt(2) - 1)^(2*k + 1))/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Dec 02 2011
In general, for n > k, a(n) = a(k+1)*a(n-k) + a(k)*a(n-k-1). See definition of Pell numbers and the formula for Sep 04 2008. - Charlie Marion, Jan 17 2012
Sum{n>=1} (-1)^(n-1)/(a(n)*a(n+1)) = sqrt(2) - 1. - Vladimir Shevelev, Feb 22 2013
From Vladimir Shevelev, Feb 24 2013: (Start)
(1) Expression a(n+1) via a(n): a(n+1) = a(n) + sqrt(2*a^2(n) + (-1)^n);
(2) a(n+1)^2 - a(n)*a(n+2) = (-1)^n;
(3) Sum_{k=1..n} (-1)^(k-1)/(a(k)*a(k+1)) = a(n)/a(n+1);
(4) a(n)/a(n+1) = sqrt(2) - 1 + r(n), where |r(n)| < 1/(a(n+1)*a(n+2)). (End)
a(-n) = -(-1)^n * a(n). - Michael Somos, Jun 01 2013
G.f.: G(0)/(2+2*x) - 1/(1+x), where G(k) = 1 + 1/(1 - x*(2*k-1)/(x*(2*k+1) - 1/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Aug 10 2013
G.f.: Q(0)*x/2, where Q(k) = 1 + 1/(1 - x*(4*k+2 + x)/( x*(4*k+4 + x) + 1/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 30 2013
a(n) = Sum_{r=0..n-1} Sum_{k=0..n-r-1} binomial(r+k,k)*binomial(k,n-k-r-1). - Peter Luschny, Nov 16 2013
a(n) = Sum_{k=1,3,5,...<=n} C(n,k)*2^((k-1)/2). - Vladimir Shevelev, Feb 06 2014
a(2n) = 2*a(n)*(a(n-1) + a(n)). - John Blythe Dobson, Mar 08 2014
a(k*n) = a(k)*a(k*n-k+1) + a(k-1)*a(k*n-k). - Charlie Marion, Mar 27 2014
a(k*n) = 2*a(k)*(a(k*n-k)+a(k*n-k-1)) + (-1)^k*a(k*n-2k). - Charlie Marion, Mar 30 2014
a(n+1) = (1+sqrt(2))*a(n) + (1-sqrt(2))^n. - Art DuPre, Apr 04 2014
a(n+1) = (1-sqrt(2))*a(n) + (1+sqrt(2))^n. - Art DuPre, Apr 04 2014
a(n) = F(n) + Sum_{k=1..n} F(k)*a(n-k), n >= 0 where F(n) the Fibonacci numbers A000045. - Ralf Stephan, May 23 2014
a(n) = round(sqrt(a(2n) + a(2n-1)))/2. - Richard R. Forberg, Jun 22 2014
a(n) = Product_{k divides n} A008555(k). - Tom Edgar, Jan 28 2015
a(n+k)^2 - A002203(k)*a(n)*a(n+k) + (-1)^k*a(n)^2 = (-1)^n*a(k)^2. - Alexander Samokrutov, Aug 06 2015
a(n) = 2^(n-1)*hypergeom([1-n/2, (1-n)/2], [1-n], -1) for n >= 2. - Peter Luschny, Dec 17 2015
a(n+1) = Sum_{k=0..n} binomial(n,k)*2^floor(k/2). - Tony Foster III, May 07 2017
a(n) = exp((i*Pi*n)/2)*sinh(n*arccosh(-i))/sqrt(2). - Peter Luschny, Mar 07 2018
From Rogério Serôdio, Mar 30 2018: (Start)
Some properties:
(1) a(n)^2 - a(n-2)^2 = 2*a(n-1)*(a(n) + a(n-2)) (see A005319);
(2) a(n-k)*a(n+k) = a(n)^2 + (-1)^(n+k+1)*a(k)^2;
(3) Sum_{k=2..n+1} a(k)*a(k-1) = a(n+1)^2 if n is odd, else a(n+1)^2 - 1 if n is even;
(4) a(n) - a(n-2*k+1) = (A077444(k) - 1)*a(n-2*k+1) + a(n-4*k+2);
(5) Sum_{k=n..n+9} a(k) = 41*A001333(n+5). (End)
From Kai Wang, Dec 30 2019: (Start)
a(m+r)*a(n+s) - a(m+s)*a(n+r) = -(-1)^(n+s)*a(m-n)*a(r-s).
a(m+r)*a(n+s) + a(m+s)*a(n+r) = (2*A002203(m+n+r+s) - (-1)^(n+s)*A002203(m-n)*A002203(r-s))/8.
A002203(m+r)*A002203(n+s) - A002203(m+s)*A002203(n+r) = (-1)^(n+s)*8*a(m-n)*a(r-s).
A002203(m+r)*A002203(n+s) - 8*a(m+s)*a(n+r) = (-1)^(n+s)*A002203(m-n)*A002203(r-s).
A002203(m+r)*A002203(n+s) + 8*a(m+s)*a(n+r) = 2*A002203(m+n+r+s)+ (-1)^(n+s)*8*a(m-n)*a(r-s). (End)
From Kai Wang, Jan 12 2020: (Start)
a(n)^2 - a(n+1)*a(n-1) = (-1)^(n-1).
a(n)^2 - a(n+r)*a(n-r) = (-1)^(n-r)*a(r)^2.
a(m)*a(n+1) - a(m+1)*a(n) = (-1)^n*a(m-n).
a(m-n) = (-1)^n (a(m)*A002203(n) - A002203(m)*a(n))/2.
a(m+n) = (a(m)*A002203(n) + A002203(m)*a(n))/2.
A002203(n)^2 - A002203(n+r)*A002203(n-r) = (-1)^(n-r-1)*8*a(r)^2.
A002203(m)*A002203(n+1) - A002203(m+1)*A002203(n) = (-1)^(n-1)*8*a(m-n).
A002203(m-n) = (-1)^(n)*(A002203(m)*A002203(n) - 8*a(m)*a(n) )/2.
A002203(m+n) = (A002203(m)*A002203(n) + 8*a(m)*a(n) )/2. (End)
From Kai Wang, Mar 03 2020: (Start)
Sum_{m>=1} arctan(2/a(2*m+1)) = arctan(1/2).
Sum_{m>=2} arctan(2/a(2*m+1)) = arctan(1/12).
In general, for n > 0,
Sum_{m>=n} arctan(2/a(2*m+1)) = arctan(1/a(2*n)). (End)
a(n) = (A001333(n+3*k) + (-1)^(k-1)*A001333(n-3*k)) / (20*A041085(k-1)) for any k>=1. - Paul Curtz, Jun 23 2021
Sum_{i=0..n} a(i)*J(n-i) = (a(n+1) + a(n) - J(n+2))/2 for J(n) = A001045(n). - Greg Dresden, Jan 05 2022
From Peter Bala, Aug 20 2022: (Start)
Sum_{n >= 1} 1/(a(2*n) + 1/a(2*n)) = 1/2.
Sum_{n >= 1} 1/(a(2*n+1) - 1/a(2*n+1)) = 1/4. Both series telescope - see A075870 and A005319.
Product_{n >= 1} ( 1 + 2/a(2*n) ) = 1 + sqrt(2).
Product_{n >= 2} ( 1 - 2/a(2*n) ) = (1/3)*(1 + sqrt(2)). (End)
G.f. = 1/(1 - Sum_{k>=1} Fibonacci(k)*x^k). - Enrique Navarrete, Dec 17 2023
Sum_{n >=1} 1/a(n) = 1.84220304982752858079237158327980838... - R. J. Mathar, Feb 05 2024
a(n) = ((3^(n+1) + 1)^(n-1) mod (9^(n+1) - 2)) mod (3^(n+1) - 1). - Joseph M. Shunia, Jun 06 2024

A001333 Pell-Lucas numbers: numerators of continued fraction convergents to sqrt(2).

Original entry on oeis.org

1, 1, 3, 7, 17, 41, 99, 239, 577, 1393, 3363, 8119, 19601, 47321, 114243, 275807, 665857, 1607521, 3880899, 9369319, 22619537, 54608393, 131836323, 318281039, 768398401, 1855077841, 4478554083, 10812186007, 26102926097, 63018038201, 152139002499, 367296043199
Offset: 0

Views

Author

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

Keywords

Comments

Number of n-step non-selfintersecting paths starting at (0,0) with steps of types (1,0), (-1,0) or (0,1) [Stanley].
Number of n steps one-sided prudent walks with east, west and north steps. - Shanzhen Gao, Apr 26 2011
Number of ternary strings of length n-1 with subwords (0,2) and (2,0) not allowed. - Olivier Gérard, Aug 28 2012
Number of symmetric 2n X 2 or (2n-1) X 2 crossword puzzle grids: all white squares are edge connected; at least 1 white square on every edge of grid; 180-degree rotational symmetry. - Erich Friedman
a(n+1) is the number of ways to put molecules on a 2 X n ladder lattice so that the molecules do not touch each other.
In other words, a(n+1) is the number of independent vertex sets and vertex covers in the n-ladder graph P_2 X P_n. - Eric W. Weisstein, Apr 04 2017
Number of (n-1) X 2 binary arrays with a path of adjacent 1's from top row to bottom row, see A359576. - R. H. Hardin, Mar 16 2002
a(2*n+1) with b(2*n+1) := A000129(2*n+1), n >= 0, give all (positive integer) solutions to Pell equation a^2 - 2*b^2 = -1.
a(2*n) with b(2*n) := A000129(2*n), n >= 1, give all (positive integer) solutions to Pell equation a^2 - 2*b^2 = +1 (see Emerson reference).
Bisection: a(2*n) = T(n,3) = A001541(n), n >= 0 and a(2*n+1) = S(2*n,2*sqrt(2)) = A002315(n), n >= 0, with T(n,x), resp. S(n,x), Chebyshev's polynomials of the first, resp. second kind. See A053120, resp. A049310.
Binomial transform of A077957. - Paul Barry, Feb 25 2003
For n > 0, the number of (s(0), s(1), ..., s(n)) such that 0 < s(i) < 4 and |s(i) - s(i-1)| <= 1 for i = 1,2,...,n, s(0) = 2, s(n) = 2. - Herbert Kociemba, Jun 02 2004
For n > 1, a(n) corresponds to the longer side of a near right-angled isosceles triangle, one of the equal sides being A000129(n). - Lekraj Beedassy, Aug 06 2004
Exponents of terms in the series F(x,1), where F is determined by the equation F(x,y) = xy + F(x^2*y,x). - Jonathan Sondow, Dec 18 2004
Number of n-words from the alphabet A={0,1,2} which two neighbors differ by at most 1. - Fung Cheok Yin (cheokyin_restart(AT)yahoo.com.hk), Aug 30 2006
Consider the mapping f(a/b) = (a + 2b)/(a + b). Taking a = b = 1 to start with and carrying out this mapping repeatedly on each new (reduced) rational number gives the following sequence 1/1, 3/2, 7/5, 17/12, 41/29, ... converging to 2^(1/2). Sequence contains the numerators. - Amarnath Murthy, Mar 22 2003 [Amended by Paul E. Black (paul.black(AT)nist.gov), Dec 18 2006]
Odd-indexed prime numerators are prime RMS numbers (A140480) and also NSW primes (A088165). - Ctibor O. Zizka, Aug 13 2008
The intermediate convergents to 2^(1/2) begin with 4/3, 10/7, 24/17, 58/41; essentially, numerators=A052542 and denominators here. - Clark Kimberling, Aug 26 2008
Equals right border of triangle A143966. Starting (1, 3, 7, ...) equals INVERT transform of (1, 2, 2, 2, ...) and row sums of triangle A143966. - Gary W. Adamson, Sep 06 2008
Inverse binomial transform of A006012; Hankel transform is := [1, 2, 0, 0, 0, 0, 0, 0, 0, ...]. - Philippe Deléham, Dec 04 2008
From Charlie Marion, Jan 07 2009: (Start)
In general, denominators, a(k,n) and numerators, b(k,n), of continued fraction convergents to sqrt((k+1)/k) may be found as follows:
let a(k,0) = 1, a(k,1) = 2k; for n>0, a(k,2n) = 2*a(k,2n-1) + a(k,2n-2) and a(k,2n+1) = (2k)*a(k,2n) + a(k,2n-1);
let b(k,0) = 1, b(k,1) = 2k+1; for n>0, b(k,2n) = 2*b(k,2n-1) + b(k,2n-2) and b(k,2n+1) = (2k)*b(k,2n) + b(k,2n-1).
For example, the convergents to sqrt(2/1) start 1/1, 3/2, 7/5, 17/12, 41/29.
In general, if a(k,n) and b(k,n) are the denominators and numerators, respectively, of continued fraction convergents to sqrt((k+1)/k) as defined above, then
k*a(k,2n)^2 - a(k,2n-1)*a(k,2n+1) = k = k*a(k,2n-2)*a(k,2n) - a(k,2n-1)^2 and
b(k,2n-1)*b(k,2n+1) - k*b(k,2n)^2 = k+1 = b(k,2n-1)^2 - k*b(k,2n-2)*b(k,2n);
for example, if k=1 and n=3, then b(1,n)=a(n+1) and
1*a(1,6)^2 - a(1,5)*a(1,7) = 1*169^2 - 70*408 = 1;
1*a(1,4)*a(1,6) - a(1,5)^2 = 1*29*169 - 70^2 = 1;
b(1,5)*b(1,7) - 1*b(1,6)^2 = 99*577 - 1*239^2 = 2;
b(1,5)^2 - 1*b(1,4)*b(1,6) = 99^2 - 1*41*239 = 2.
Cf. A000129, A142238-A142239, A153313-A153318.
(End)
This sequence occurs in the lower bound of the order of the set of equivalent resistances of n equal resistors combined in series and in parallel (A048211). - Sameen Ahmed Khan, Jun 28 2010
Let M = a triangle with the Fibonacci series in each column, but the leftmost column is shifted upwards one row. A001333 = lim_{n->infinity} M^n, the left-shifted vector considered as a sequence. - Gary W. Adamson, Jul 27 2010
a(n) is the number of compositions of n when there are 1 type of 1 and 2 types of other natural numbers. - Milan Janjic, Aug 13 2010
Equals the INVERTi transform of A055099. - Gary W. Adamson, Aug 14 2010
From L. Edson Jeffery, Apr 04 2011: (Start)
Let U be the unit-primitive matrix (see [Jeffery])
U = U_(8,2) = (0 0 1 0)
(0 1 0 1)
(1 0 2 0)
(0 2 0 1).
Then a(n) = (1/4)*Trace(U^n). (See also A084130, A006012.)
(End)
For n >= 1, row sums of triangle
m/k.|..0.....1.....2.....3.....4.....5.....6.....7
==================================================
.0..|..1
.1..|..1.....2
.2..|..1.....2.....4
.3..|..1.....4.....4.....8
.4..|..1.....4....12.....8....16
.5..|..1.....6....12....32....16....32
.6..|..1.....6....24....32....80....32....64
.7..|..1.....8....24....80....80...192....64...128
which is the triangle for numbers 2^k*C(m,k) with duplicated diagonals. - Vladimir Shevelev, Apr 12 2012
a(n) is also the number of ways to place k non-attacking wazirs on a 2 X n board, summed over all k >= 0 (a wazir is a leaper [0,1]). - Vaclav Kotesovec, May 08 2012
The sequences a(n) and b(n) := A000129(n) are entries of powers of the special case of the Brahmagupta Matrix - for details see Suryanarayan's paper. Further, as Suryanarayan remark, if we set A = 2*(a(n) + b(n))*b(n), B = a(n)*(a(n) + 2*b(n)), C = a(n)^2 + 2*a(n)*b(n) + 2*b(n)^2 we obtain integral solutions of the Pythagorean relation A^2 + B^2 = C^2, where A and B are consecutive integers. - Roman Witula, Jul 28 2012
Pisano period lengths: 1, 1, 8, 4, 12, 8, 6, 4, 24, 12, 24, 8, 28, 6, 24, 8, 16, 24, 40, 12, .... - R. J. Mathar, Aug 10 2012
This sequence and A000129 give the diagonal numbers described by Theon of Smyrna. - Sture Sjöstedt, Oct 20 2012
a(n) is the top left entry of the n-th power of any of the following six 3 X 3 binary matrices: [1, 1, 1; 1, 1, 1; 1, 0, 0] or [1, 1, 1; 1, 1, 0; 1, 1, 0] or [1, 1, 1; 1, 0, 1; 1, 1, 0] or [1, 1, 1; 1, 1, 0; 1, 0, 1] or [1, 1, 1; 1, 0, 1; 1, 0, 1] or [1, 1, 1; 1, 0, 0; 1, 1, 1]. - R. J. Mathar, Feb 03 2014
If p is prime, a(p) == 1 (mod p) (compare with similar comment for A000032). - Creighton Dement, Oct 11 2005, modified by Davide Colazingari, Jun 26 2016
a(n) = A000129(n) + A000129(n-1), where A000129(n) is the n-th Pell Number; e.g., a(6) = 99 = A000129(6) + A000129(5) = 70 + 29. Hence the sequence of fractions has the form 1 + A000129(n-1)/A000129(n), and the ratio A000129(n-1)/A000129(n)converges to sqrt(2) - 1. - Gregory L. Simay, Nov 30 2018
For n > 0, a(n+1) is the length of tau^n(1) where tau is the morphism: 1 -> 101, 0 -> 1. See Song and Wu. - Michel Marcus, Jul 21 2020
For n > 0, a(n) is the number of nonisomorphic quasitrivial semigroups with n elements, see Devillet, Marichal, Teheux. A292932 is the number of labeled quasitrivial semigroups. - Peter Jipsen, Mar 28 2021
a(n) is the permanent of the n X n tridiagonal matrix defined in A332602. - Stefano Spezia, Apr 12 2022
From Greg Dresden, May 08 2023: (Start)
For n >= 2, 4*a(n) is the number of ways to tile this T-shaped figure of length n-1 with two colors of squares and one color of domino; shown here is the figure of length 5 (corresponding to n=6), and it has 4*a(6) = 396 different tilings.
_
|| _
|||_|||
|_|
(End)
12*a(n) = number of walks of length n in the cyclic Kautz digraph CK(3,4). - Miquel A. Fiol, Feb 15 2024

Examples

			Convergents are 1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408, 1393/985, 3363/2378, 8119/5741, 19601/13860, 47321/33461, 114243/80782, ... = A001333/A000129.
The 15 3 X 2 crossword grids, with white squares represented by an o:
  ooo ooo ooo ooo ooo ooo ooo oo. o.o .oo o.. .o. ..o oo. .oo
  ooo oo. o.o .oo o.. .o. ..o ooo ooo ooo ooo ooo ooo .oo oo.
G.f. = 1 + x + 3*x^2 + 7*x^3 + 17*x^4 + 41*x^5 + 99*x^6 + 239*x^7 + 577*x^8 + ...

References

  • M. R. Bacon and C. K. Cook, Some properties of Oresme numbers and convolutions ..., Fib. Q., 62:3 (2024), 233-240.
  • A. H. Beiler, Recreations in the Theory of Numbers. New York: Dover, pp. 122-125, 1964.
  • John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See p. 204.
  • John Derbyshire, Prime Obsession, Joseph Henry Press, April 2004, see p. 16.
  • J. Devillet, J.-L. Marichal, and B. Teheux, Classifications of quasitrivial semigroups, Semigroup Forum, 100 (2020), 743-764.
  • Maribel Díaz Noguera [Maribel Del Carmen Díaz Noguera], Rigoberto Flores, Jose L. Ramirez, and Martha Romero Rojas, Catalan identities for generalized Fibonacci polynomials, Fib. Q., 62:2 (2024), 100-111.
  • Kenneth Edwards and Michael A. Allen, A new combinatorial interpretation of the Fibonacci numbers squared, Part II, Fib. Q., 58:2 (2020), 169-177.
  • R. P. Grimaldi, Ternary strings with no consecutive 0's and no consecutive 1's, Congressus Numerantium, 205 (2011), 129-149.
  • Jan Gullberg, Mathematics from the Birth of Numbers, W. W. Norton & Co., NY & London, 1997, §8.5 The Fibonacci and Related Sequences, p. 288.
  • A. F. Horadam, R. P. Loh, and A. G. Shannon, Divisibility properties of some Fibonacci-type sequences, pp. 55-64 of Combinatorial Mathematics VI (Armidale 1978), Lect. Notes Math. 748, 1979.
  • Thomas Koshy, Pell and Pell-Lucas Numbers with Applications, Springer, New York, 2014.
  • Kin Y. Li, Math Problem Book I, 2001, p. 24, Problem 159.
  • I. Niven and H. S. Zuckerman, An Introduction to the Theory of Numbers. 2nd ed., Wiley, NY, 1966, p. 102, Problem 10.
  • J. Roberts, Lure of the Integers, Math. Assoc. America, 1992, p. 224.
  • 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).
  • R. P. Stanley, Enumerative Combinatorics, Volume 1 (1986), p. 203, Example 4.1.2.
  • A. Tarn, Approximations to certain square roots and the series of numbers connected therewith, Mathematical Questions and Solutions from the Educational Times, 1 (1916), 8-12.
  • R. C. Tilley et al., The cell growth problem for filaments, Proc. Louisiana Conf. Combinatorics, ed. R. C. Mullin et al., Baton Rouge, 1970, 310-339.
  • David Wells, The Penguin Dictionary of Curious and Interesting Numbers. Penguin Books, NY, 1986, Revised edition 1987, p. 34.

Links

Crossrefs

For denominators see A000129.
See A040000 for the continued fraction expansion of sqrt(2).
See also A078057 which is the same sequence without the initial 1.
Cf. also A002203, A152113.
Row sums of unsigned Chebyshev T-triangle A053120. a(n)= A054458(n, 0) (first column of convolution triangle).
Row sums of A140750, A160756, A135837.
Equals A034182(n-1) + 2 and A084128(n)/2^n. First differences of A052937. Partial sums of A052542. Pairwise sums of A048624. Bisection of A002965.
The following sequences (and others) belong to the same family: A001333, A000129, A026150, A002605, A046717, A015518, A084057, A063727, A002533, A002532, A083098, A083099, A083100, A015519.
Second row of the array in A135597.
Cf. A048211, A153588, A174283, A174284, A174285, A174286, A176499, A176500, A176501, A176502.
Cf. A055099.
Cf. A028859, A001906 / A088305, A033303, A000225, A095263, A003945, A006356, A002478, A214260, A001911 and A000217 for other restricted ternary words.
Cf. Triangle A106513 (alternating row sums).
Equals A293004 + 1.
Cf. A033539, A332602, A086395 (subseq. of primes).

Programs

  • Haskell
    a001333 n = a001333_list !! n
a001333_list = 1 : 1 : zipWith (+)
                       a001333_list (map (* 2) $ tail a001333_list)
-- Reinhard Zumkeller, Jul 08 2012
  • Magma
    [n le 2 select 1 else 2*Self(n-1)+Self(n-2): n in [1..35]]; // Vincenzo Librandi, Nov 10 2018
  • Maple
    A001333 := proc(n) option remember; if n=0 then 1 elif n=1 then 1 else 2*procname(n-1)+procname(n-2) fi end;
Digits := 50; A001333 := n-> round((1/2)*(1+sqrt(2))^n);
with(numtheory): cf := cfrac (sqrt(2),1000): [seq(nthnumer(cf,i), i=0..50)];
a:= n-> (M-> M[2, 1]+M[2, 2])(<<2|1>, <1|0>>^n):
seq(a(n), n=0..33);  # Alois P. Heinz, Aug 01 2008
A001333List := proc(m) local A, P, n; A := [1,1]; P := [1,1];
for n from 1 to m - 2 do P := ListTools:-PartialSums([op(A), P[-2]]);
A := [op(A), P[-1]] od; A end: A001333List(32); # Peter Luschny, Mar 26 2022
  • Mathematica
    Insert[Table[Numerator[FromContinuedFraction[ContinuedFraction[Sqrt[2], n]]], {n, 1, 40}], 1, 1] (* Stefan Steinerberger, Apr 08 2006 *)
Table[((1 - Sqrt[2])^n + (1 + Sqrt[2])^n)/2, {n, 0, 29}] // Simplify (* Robert G. Wilson v, May 02 2006 *)
a[0] = 1; a[1] = 1; a[n_] := a[n] = 2a[n - 1] + a[n - 2]; Table[a@n, {n, 0, 29}] (* Robert G. Wilson v, May 02 2006 *)
Table[ MatrixPower[{{1, 2}, {1, 1}}, n][[1, 1]], {n, 0, 30}] (* Robert G. Wilson v, May 02 2006 *)
a=c=0;t={b=1}; Do[c=a+b+c; AppendTo[t,c]; a=b;b=c,{n,40}]; t (* Vladimir Joseph Stephan Orlovsky, Mar 23 2009 *)
LinearRecurrence[{2, 1}, {1, 1}, 40] (* Vladimir Joseph Stephan Orlovsky, Mar 23 2009 *)
Join[{1}, Numerator[Convergents[Sqrt[2], 30]]] (* Harvey P. Dale, Aug 22 2011 *)
Table[(-I)^n ChebyshevT[n, I], {n, 10}] (* Eric W. Weisstein, Apr 04 2017 *)
CoefficientList[Series[(-1 + x)/(-1 + 2 x + x^2), {x, 0, 20}], x] (* Eric W. Weisstein, Sep 21 2017 *)
Table[Sqrt[(ChebyshevT[n, 3] + (-1)^n)/2], {n, 0, 20}] (* Eric W. Weisstein, Apr 17 2018 *)
  • PARI
    {a(n) = if( n<0, (-1)^n, 1) * contfracpnqn( vector( abs(n), i, 1 + (i>1))) [1, 1]}; /* Michael Somos, Sep 02 2012 */
  • PARI
    {a(n) = polchebyshev(n, 1, I) / I^n}; /* Michael Somos, Sep 02 2012 */
  • PARI
    a(n) = real((1 + quadgen(8))^n); \\ Michel Marcus, Mar 16 2021
  • PARI
    { for (n=0, 4000, a=contfracpnqn(vector(n, i, 1+(i>1)))[1, 1]; if (a > 10^(10^3 - 6), break); write("b001333.txt", n, " ", a); ); } \\ Harry J. Smith, Jun 12 2009
  • Python
    from functools import cache
@cache
def a(n): return 1 if n < 2 else 2*a(n-1) + a(n-2)
print([a(n) for n in range(32)]) # Michael S. Branicky, Nov 13 2022
  • Sage
    from sage.combinat.sloane_functions import recur_gen2
it = recur_gen2(1,1,2,1)
[next(it) for i in range(30)] ## Zerinvary Lajos, Jun 24 2008
  • Sage
    [lucas_number2(n,2,-1)/2 for n in range(0, 30)] # Zerinvary Lajos, Apr 30 2009

Formula

a(n) = A055642(A125058(n)). - Reinhard Zumkeller, Feb 02 2007
a(n) = 2a(n-1) + a(n-2);
a(n) = ((1-sqrt(2))^n + (1+sqrt(2))^n)/2.
a(n)+a(n+1) = 2 A000129(n+1). 2*a(n) = A002203(n).
G.f.: (1 - x) / (1 - 2*x - x^2) = 1 / (1 - x / (1 - 2*x / (1 + x))). - Simon Plouffe in his 1992 dissertation.
A000129(2n) = 2*A000129(n)*a(n). - John McNamara, Oct 30 2002
a(n) = (-i)^n * T(n, i), with T(n, x) Chebyshev's polynomials of the first kind A053120 and i^2 = -1.
a(n) = a(n-1) + A052542(n-1), n>1. a(n)/A052542(n) converges to sqrt(1/2). - Mario Catalani (mario.catalani(AT)unito.it), Apr 29 2003
E.g.f.: exp(x)cosh(x*sqrt(2)). - Paul Barry, May 08 2003
a(n) = Sum_{k=0..floor(n/2)} binomial(n, 2k)2^k. - Paul Barry, May 13 2003
For n > 0, a(n)^2 - (1 + (-1)^(n))/2 = Sum_{k=0..n-1} ((2k+1)*A001653(n-1-k)); e.g., 17^2 - 1 = 288 = 1*169 + 3*29 + 5*5 + 7*1; 7^2 = 49 = 1*29 + 3*5 + 5*1. - Charlie Marion, Jul 18 2003
a(n+2) = A078343(n+1) + A048654(n). - Creighton Dement, Jan 19 2005
a(n) = A000129(n) + A000129(n-1) = A001109(n)/A000129(n) = sqrt(A001110(n)/A000129(n)^2) = ceiling(sqrt(A001108(n))). - Henry Bottomley, Apr 18 2000
Also the first differences of A000129 (the Pell numbers) because A052937(n) = A000129(n+1) + 1. - Graeme McRae, Aug 03 2006
a(n) = Sum_{k=0..n} A122542(n,k). - Philippe Deléham, Oct 08 2006
For another recurrence see A000129.
a(n) = Sum_{k=0..n} A098158(n,k)*2^(n-k). - Philippe Deléham, Dec 26 2007
a(n) = upper left and lower right terms of [1,1; 2,1]^n. - Gary W. Adamson, Mar 12 2008
If p[1]=1, and p[i]=2, (i>1), and if A is 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)=det A. - Milan Janjic, Apr 29 2010
For n>=2, a(n)=F_n(2)+F_(n+1)(2), where F_n(x) is Fibonacci polynomial (cf. A049310): F_n(x) = Sum_{i=0..floor((n-1)/2)} binomial(n-i-1,i)x^(n-2*i-1). - Vladimir Shevelev, Apr 13 2012
a(-n) = (-1)^n * a(n). - Michael Somos, Sep 02 2012
Dirichlet g.f.: (PolyLog(s,1-sqrt(2)) + PolyLog(s,1+sqrt(2)))/2. - Ilya Gutkovskiy, Jun 26 2016
a(n) = A000129(n) - A000129(n-1), where A000129(n) is the n-th Pell Number. Hence the continued fraction is of the form 1-(A000129(n-1)/A000129(n)). - Gregory L. Simay, Nov 09 2018
a(n) = (A000129(n+3) + A000129(n-3))/10, n>=3. - Paul Curtz, Jun 16 2021
a(n) = (A000129(n+6) - A000129(n-6))/140, n>=6. - Paul Curtz, Jun 20 2021
a(n) = round((1/2)*sqrt(Product_{k=1..n} 4*(1 + sin(k*Pi/n)^2))), for n>=1. - Greg Dresden, Dec 28 2021
a(n)^2 + a(n+1)^2 = A075870(n+1) = 2*(b(n)^2 + b(n+1)^2) for all n in Z where b(n) := A000129(n). - Michael Somos, Apr 02 2022
a(n) = 2*A048739(n-2)+1. - R. J. Mathar, Feb 01 2024
Sum_{n>=1} 1/a(n) = 1.5766479516393275911191017828913332473... - R. J. Mathar, Feb 05 2024
From Peter Bala, Jul 06 2025: (Start)
G.f.: Sum_{n >= 1} (-1)^(n+1) * x^(n-1) * Product_{k = 1..n} (1 - k*x)/(1 - 3*x + k*x^2).
The following series telescope:
Sum_{n >= 1} (-1)^(n+1)/(a(2*n) + 1/a(2*n)) = 1/4, since 1/(a(2*n) + 1/a(2*n)) = 1/A077445(n) + 1/A077445(n+1).
Sum_{n >= 1} (-1)^(n+1)/(a(2*n+1) - 1/a(2*n+1)) = 1/8, since. 1/(a(2*n+1) - 1/a(2*n+1)) = 1/(4*Pell(2*n)) + 1/(4*Pell(2*n+2)), where Pell(n) = A000129(n).
Sum_{n >= 1} (-1)^(n+1)/(a(2*n+1) + 9/a(2*n+1)) = 1/10, since 1/(a(2*n+1) + 9/a(2*n+1)) = b(n) + b(n+1), where b(n) = A001109(n)/(2*Pell(2*n-1)*Pell(2*n+1)).
Sum_{n >= 1} (-1)^(n+1)/(a(n)*a(n+1)) = 1 - sqrt(2)/2 = A268682, since (-1)^(n+1)/(a(n)*a(n+1)) = Pell(n)/a(n) - Pell(n+1)/a(n+1). (End)

Extensions

Chebyshev comments from Wolfdieter Lang, Jan 10 2003

A001792 a(n) = (n+2)*2^(n-1).

Original entry on oeis.org

1, 3, 8, 20, 48, 112, 256, 576, 1280, 2816, 6144, 13312, 28672, 61440, 131072, 278528, 589824, 1245184, 2621440, 5505024, 11534336, 24117248, 50331648, 104857600, 218103808, 452984832, 939524096, 1946157056, 4026531840, 8321499136, 17179869184, 35433480192
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Number of parts in all compositions (ordered partitions) of n + 1. For example, a(2) = 8 because in 3 = 2 + 1 = 1 + 2 = 1 + 1 + 1 we have 8 parts. Also number of compositions (ordered partitions) of 2n + 1 with exactly 1 odd part. For example, a(2) = 8 because the only compositions of 5 with exactly 1 odd part are 5 = 1 + 4 = 2 + 3 = 3 + 2 = 4 + 1 = 1 + 2 + 2 = 2 + 1 + 2 = 2 + 2 + 1. - Emeric Deutsch, May 10 2001
Binomial transform of natural numbers [1, 2, 3, 4, ...].
For n >= 1 a(n) is also the determinant of the n X n matrix with 3's on the diagonal and 1's elsewhere. - Ahmed Fares (ahmedfares(AT)my-deja.com), May 06 2001
The arithmetic mean of first n terms of the sequence is 2^(n-1). - Amarnath Murthy, Dec 25 2001, corrected by M. F. Hasler, Dec 17 2016
Also the number of "winning paths" of length n across an n X n Hex board. Satisfies the recursion a(n) = 2a(n-1) + 2^(n-2). - David Molnar (molnar(AT)stolaf.edu), Apr 10 2002
Diagonal in A053218. - Benoit Cloitre, May 08 2002
Let M_n be the n X n matrix m_(i, j) = 1 + abs(i-j) then det(M_n) = (-1)^(n-1)*a(n-1). - Benoit Cloitre, May 28 2002
Absolute value of determinant of n X n matrix of form: [1 2 3 4 5 / 2 1 2 3 4 / 3 2 1 2 3 / 4 3 2 1 2 / 5 4 3 2 1]. - Benoit Cloitre, Jun 20 2002
Number of ones in all (n+1)-bit integers (cf. A000120). - Ralf Stephan, Aug 02 2003
This sequence also emerges as a floretion force transform of powers of 2 (see program code). Define a(-1) = 0 (as the sequence is returned by FAMP). Then a(n-1) + A098156(n+1) = 2*a(n) (conjecture). - Creighton Dement, Mar 14 2005
This sequence gives the absolute value of the determinant of the Toeplitz matrix with first row containing the first n integers. - Paul Max Payton, May 23 2006
Equals sums of rows right of left edge of A102363 divided by three, + 2^K. - David G. Williams (davidwilliams(AT)paxway.com), Oct 08 2007
If X_1, X_2, ..., X_n are 2-blocks of a (2n+1)-set X then, for n >= 1, a(n) is the number of (n+1)-subsets of X intersecting each X_i, (i = 1, 2, ..., n). - Milan Janjic, Nov 18 2007
Also, a(n-1) is the determinant of the n X n matrix with A[i, j] = n - |i-j|. - M. F. Hasler, Dec 17 2008
1/2 the number of permutations of 1 .. (n+2) arranged in a circle with exactly one local maximum. - R. H. Hardin, Apr 19 2009
The first corrector line for transforming 2^n offset 0 with a leading 1 into the Fibonacci sequence. - Al Hakanson (hawkuu(AT)gmail.com), Jun 01 2009
a(n) is the number of runs of consecutive 1's in all binary sequences of length (n+1). - Geoffrey Critzer, Jul 02 2009
Let X_j (0 < j <= 2^n) all the subsets of N_n; m(i, j) := if {i} in X_j then 1 else 0. Let A = transpose(M).M; Then a(i, j) = (number of elements)|X_i intersect X_j|. Determinant(X*I-A) = (X-(n+1)*2^(n-2))*(X-2^(n-2))^(n-1)*X^(2^n-n).
Eigenvector for (n+1)*2^(n-2) is V_i=|X_i|.
Sum_{k=1..2^n} |X_i intersect X_k|*|X_k| = (n+1)*2^(n-2)*|X_i|.
Eigenvectors for 2^(n-2) are {line(M)[i] - line(M)[j], 1 <= i, j <= n}. - CLARISSE Philippe (clarissephilippe(AT)yahoo.fr), Mar 24 2010
The sequence b(n) = 2*A001792(n), for n >= 1 with b(0) = 1, is an elephant sequence, see A175655. For the central square four A[5] vectors, with decimal values 187, 190, 250 and 442, lead to the b(n) sequence. For the corner squares these vectors lead to the companion sequence A134401. - Johannes W. Meijer, Aug 15 2010
Equals partial sums of A045623: (1, 2, 5, 12, 28, ...); where A045623 = the convolution square of (1, 1, 2, 4, 8, 16, 32, ...). - Gary W. Adamson, Oct 26 2010
Equals (1, 2, 4, 8, 16, ...) convolved with (1, 1, 2, 4, 8, 16, ...); e.g., a(3) = 20 = (1, 1, 2, 4) dot (8, 4, 2, 1) = (8 + 4 + 4 + 4). - Gary W. Adamson, Oct 26 2010
This sequence seems to give the first x+1 nonzero terms in the sequence derived by subtracting the m-th term in the x_binacci sequence (where the first term is one and the y-th term is the sum of x terms immediately preceding it) from 2^(m-2). - Dylan Hamilton, Nov 03 2010
Recursive formulas for a(n) are in many cases derivable from its property wherein delta^k(a(n)) - a(n) = k*2^n where delta^k(a(n)) represents the k-th forward difference of a(n). Provable with a difference table and a little induction. - Ethan Beihl, May 02 2011
Let f(n,k) be the sum of numbers in the subsets of size k of {1, 2, ..., n}. Then a(n-1) is the average of the numbers f(n, 0), ... f(n, n). Example: (f(3, 1), f(3, 2), f(3, 3)) = (6, 12, 6), with average (6+12+6)/3. - Clark Kimberling, Feb 24 2012
a(n) is the number of length-2n binary sequences that contain a subsequence of ones with length n or more. To derive this result, note that there are 2^n sequences where the initial one of the subsequence occurs at entry one. If the initial one of the subsequence occurs at entry 2, 3, ..., or n + 1, there are 2^(n-1) sequences since a zero must precede the initial one. Hence a(n) = 2^n + n*2^(n-1)=(n+2)2^(n-1). An example is given in the example section below. - Dennis P. Walsh, Oct 25 2012
As the total number of parts in all compositions of n+1 (see the first line in Comments) the equivalent sequence for partitions is A006128. On the other hand, as the first differences of A001787 (see the first line in Crossrefs) the equivalent sequence for partitions is A138879. - Omar E. Pol, Aug 28 2013
a(n) is the number of spanning trees of the complete tripartite graph K_{n,1,1}. - James Mahoney, Oct 24 2013
a(n-1) = denominator of the mean (2n/(n+1), after reduction), of the compositions of n; numerator is given by A022998(n). - Clark Kimberling, Mar 11 2014
From Tom Copeland, Nov 09 2014: (Start)
The shifted array belongs to an interpolated family of arrays associated to the Catalan A000108 (t=1), and Riordan, or Motzkin sums A005043 (t=0), with the interpolating o.g.f. (1-sqrt(1-4x/(1+(1-t)x)))/2 and inverse x(1-x)/(1+(t-1)x(1-x)). See A091867 for more info on this family. Here the interpolation is t=-3 (mod signs in the results).
Let C(x) = (1 - sqrt(1-4x))/2, an o.g.f. for the Catalan numbers A000108, with inverse Cinv(x) = x*(1-x) and P(x,t) = x/(1+t*x) with inverse P(x,-t).
Shifted o.g.f: G(x) = x*(1-x)/(1 - 4x*(1-x)) = P[Cinv(x),-4].
Inverse o.g.f: Ginv(x) = [1 - sqrt(1 - 4*x/(1+4x))]/2 = C[P(x, 4)] (signed shifted A001700). Cf. A030528. (End)
For n > 0, element a(n) of the sequence is equal to the gradients of the (n-1)-th row of Pascal triangle multiplied with the square of the integers from n+1,...,1. I.e., row 3 of Pascal's triangle 1,3,3,1 has gradients 1,2,0,-2,-1, so a(4) = 1*(5^2) + 2*(4^2) + 0*(3^2) - 2*(2^2) - 1*(1^2) = 48. - Jens Martin Carlsson, May 18 2017
Number of self-avoiding paths connecting all the vertices of a convex (n+2)-gon. - Ivaylo Kortezov, Jan 19 2020
a(n-1) is the total number of elements of subsets of {1,2,..,n} that contain n. For example, for n = 3, a(2) = 8, and the subsets of {1,2,3} that contain 3 are {3}, {1,3}, {2,3}, {1,2,3}, with a total of 8 elements. - Enrique Navarrete, Aug 01 2020

Examples

			a(0) = 1, a(1) = 2*1 + 1 = 3, a(2) = 2*3 + 2 = 8, a(3) = 2*8 + 4 = 20, a(4) = 2*20 + 8 = 48, a(5) = 2*48 + 16 = 112, a(6) = 2*112 + 32 = 256, ... - _Philippe Deléham_, Apr 19 2009
a(2) = 8 since there are 8 length-4 binary sequences with a subsequence of ones of length 2 or more, namely, 1111, 1110, 1101, 1011, 0111, 1100, 0110, and 0011. - _Dennis P. Walsh_, Oct 25 2012
G.f. = 1 + 3*x + 8*x^2 + 20*x^3 + 48*x^4 + 112*x^5 + 256*x^6 + 576*x^7 + ...

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. 795.
  • 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).
  • A. M. Stepin and A. T. Tagi-Zade, Words with restrictions, pp. 67-74 of Kvant Selecta: Combinatorics I, Amer. Math. Soc., 2001 (G_n on p. 70).

Links

Crossrefs

First differences of A001787.
a(n) = A049600(n, 1), a(n) = A030523(n + 1, 1).
Cf. A053113.
Row sums of triangles A008949 and A055248.
a(n) = -A039991(n+2, 2).
Cf. A130584, A125092, A128064, A000079, A164910, A045623, A000120, A053120.
Cf. A000108, A005043, A091867, A001700, A030528.
If the exponent E in a(n) = Sum_{m=0..n} (Sum_{k=0..m} C(n,k))^E is 1, 2, 3, 4, 5 we get A001792, A003583, A007403, A294435, A294436 respectively.

Programs

  • GAP
    List([0..35],n->(n+2)*2^(n-1)); # Muniru A Asiru, Sep 25 2018
  • Haskell
    a001792 n = a001792_list !! n
a001792_list = scanl1 (+) a045623_list
-- Reinhard Zumkeller, Jul 21 2013
  • Magma
    [(n+2)*2^(n-1): n in [0..40]]; // Vincenzo Librandi, Nov 10 2014
  • Maple
    A001792 := n-> (n+2)*2^(n-1);
spec := [S, {B=Set(Z, 0 <= card), S=Prod(Z, B, B)}, labeled]: seq(combstruct[count](spec, size=n)/4, n=2..30); # Zerinvary Lajos, Oct 09 2006
A001792:=-(-3+4*z)/(2*z-1)^2; # Simon Plouffe in his 1992 dissertation, which gives the sequence without the initial 1
G(x):=1/exp(2*x)*(1-x): f[0]:=G(x): for n from 1 to 54 do f[n]:=diff(f[n-1],x) od: x:=0: seq(abs(f[n]),n=0..28 ); # Zerinvary Lajos, Apr 17 2009
a := n -> hypergeom([-n, 2], [1], -1);
seq(round(evalf(a(n),32)), n=0..31); # Peter Luschny, Aug 02 2014
  • Mathematica
    matrix[n_Integer /; n >= 1] := Table[Abs[p - q] + 1, {q, n}, {p, n}]; a[n_Integer /; n >= 1] := Abs[Det[matrix[n]]] (* Josh Locker (joshlocker(AT)macfora.com), Apr 29 2004 *)
g[n_,m_,r_] := Binomial[n - 1, r - 1] Binomial[m + 1, r] r; Table[1 + Sum[g[n, k - n, r], {r, 1, k}, {n, 1, k - 1}], {k, 1, 29}] (* Geoffrey Critzer, Jul 02 2009 *)
a[n_] := (n + 2)*2^(n - 1); a[Range[0, 40]] (* Vladimir Joseph Stephan Orlovsky, Feb 09 2011 *)
LinearRecurrence[{4, -4}, {1, 3}, 40] (* Harvey P. Dale, Aug 29 2011 *)
CoefficientList[Series[(1 - x) / (1 - 2 x)^2, {x, 0, 40}], x] (* Vincenzo Librandi, Nov 10 2014 *)
b[i_]:=i; a[n_]:=Abs[Det[ToeplitzMatrix[Array[b, n], Array[b, n]]]]; Array[a, 40] (* Stefano Spezia, Sep 25 2018 *)
a[n_]:=Hypergeometric2F1[2,-n+1,1,-1];Array[a,32] (* Giorgos Kalogeropoulos, Jan 04 2022 *)
  • PARI
    A001792(n)=(n+2)<<(n-1) \\ M. F. Hasler, Dec 17 2008
  • Python
    for n in range(0,40): print(int((n+2)*2**(n-1)), end=' ') # Stefano Spezia, Oct 16 2018

Formula

a(n) = (n+2)*2^(n-1).
G.f.: (1 - x)/(1 - 2*x)^2 = 2F1(1,3;2;2x).
a(n) = 4*a(n-1) - 4*a(n-2).
G.f. (-1 + (1-2*x)^(-2))/(x*2^2). - Wolfdieter Lang
a(n) = A018804(2^n). - Matthew Vandermast, Mar 01 2003
a(n) = Sum_{k=0..n+2} binomial(n+2, 2k)*k. - Paul Barry, Mar 06 2003
a(n) = (1/4)*A001787(n+2). - Emeric Deutsch, May 24 2003
With a leading 0, this is ((n+1)2^n - 0^n)/4 = Sum_{m=0..n} binomial(n - 1, m - 1)*m, the binomial transform of A004526(n+1). - Paul Barry, Jun 05 2003
a(n) = Sum_{k=0..n} binomial(n, k)*(k + 1). - Lekraj Beedassy, Jun 24 2004
a(n) = A000244(n) - A066810(n). - Ross La Haye, Apr 29 2006
Row sums of triangle A130585. - Gary W. Adamson, Jun 06 2007
Equals A125092 * [1/1, 1/2, 1/3, ...]. - Gary W. Adamson, Nov 16 2007
a(n) = (n+1)*2^n - n*2^(n-1). Equals A128064 * A000079. - Gary W. Adamson, Dec 28 2007
G.f.: F(3, 1; 2; 2x). - Paul Barry, Sep 03 2008
a(n) = 1 + Sum_{k=1..n} (n - k + 4)2^(n - k - 1). This follows from the result that the number of parts equal to k in all compositions of n is (n - k + 3)2^(n - k - 2) for 0 < k < n. - Geoffrey Critzer, Sep 21 2008
a(n) = 2^(n-1) + 2 a(n-1) ; a(n-1) = det(n - |i - j|){i, j = 1..n}. - _M. F. Hasler, Dec 17 2008
a(n) = 2*a(n-1) + 2^(n-1). - Philippe Deléham, Apr 19 2009
a(n) = A164910(2^n). - Gary W. Adamson, Aug 30 2009
a(n) = Sum_{i=1..2^n} gcd(i, 2^n) = A018804(2^n). So we have: 2^0 * phi(2^n) + ... + 2^n * phi(2^0) = (n + 2)*2^(n-1), where phi is the Euler totient function. - Jeffrey R. Goodwin, Nov 11 2011
a(n) = Sum_{j=0..n} Sum_{i=0..n} binomial(n, i + j). - Yalcin Aktar, Jan 17 2012
Eigensequence of an infinite lower triangular matrix with 2^n as the left border and the rest 1's. - Gary W. Adamson, Jan 30 2012
G.f.: 1 + 2*x*U(0) where U(k) = 1 + (k + 1)/(2 - 8*x/(4*x + (k + 1)/U(k + 1))); (continued fraction, 3 - step). - Sergei N. Gladkovskii, Oct 19 2012
a(n) = Sum_{k=0..n} Sum_{j=0..k} binomial(n,j). - Peter Luschny, Dec 03 2013
a(n) = Hyper2F1([-n, 2], [1], -1). - Peter Luschny, Aug 02 2014
G.f.: 1 / (1 - 3*x / (1 + x / (3 - 4*x))). - Michael Somos, Aug 26 2015
a(n) = -A053120(2+n, n), n >= 0, the negative of the third (sub)diagonal of the triangle of Chebyshev's T polynomials. - Wolfdieter Lang, Nov 26 2019
From Amiram Eldar, Jan 12 2021: (Start)
Sum_{n>=0} 1/a(n) = 8*log(2) - 4.
Sum_{n>=0} (-1)^n/a(n) = 4 - 8*log(3/2). (End)
E.g.f.: exp(2*x)*(1 + x). - Stefano Spezia, Jun 11 2021

A001788 a(n) = n*(n+1)*2^(n-2).

Original entry on oeis.org

0, 1, 6, 24, 80, 240, 672, 1792, 4608, 11520, 28160, 67584, 159744, 372736, 860160, 1966080, 4456448, 10027008, 22413312, 49807360, 110100480, 242221056, 530579456, 1157627904, 2516582400, 5452595200, 11777605632, 25367150592, 54492397568, 116769423360, 249644974080, 532575944704
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Number of 2-dimensional faces in (n+1)-dimensional hypercube; also number of 4-cycles in the (n+1)-dimensional hypercube. - Henry Bottomley, Apr 14 2000
Also the number of edges in the (n+1)-halved cube graph. - Eric W. Weisstein, Jun 21 2017
From Philippe Deléham, Apr 28 2004: a(n) is the sum, over all nonempty subsets E of {1, 2, ..., n}, of all elements of E. E.g., a(3) = 24: the nonempty subsets are {1, 2, 3}, {1, 2}, {1, 3}, {2, 3}, {1}, {2}, {3} and 1 + 2 + 3 + 1 + 2 + 1 + 3 + 2 + 3 + 1 + 2 + 3 = 24.
Equivalently, sum of all nodes (except the last one, equal to n+1) of all integer compositions of n+1. - Olivier Gérard, Oct 22 2011
The inverse binomial transform of a(n-k) for k=-1..4 gives A001844, A000290, A000217(n-1), A002620(n-1), A008805(n-4), A000217 interspersed with 0's. - Michael Somos, Jul 18 2003
Take n points on a finite line. They all move with the same constant speed; they instantaneously change direction when they collide with another; and they fall when they quit the line. a(n-1) is the total number of collisions before falling when the initials directions are the 2^n possible. The mean number of collisions is then n(n-1)/8. E.g., a(1)=0 before any collision is possible. a(2)=1 because there is a collision only if the initials directions are, say, right-left. - Emmanuel Moreau, Feb 11 2006
Also number of pericondensed hexagonal systems with n hexagons. For example, if n=5 then the number of pericondensed hexagonal systems with n hexagons is 24. - Parthasarathy Nambi, Sep 06 2006
If X_1,X_2,...,X_n is a partition of a 2n-set X into 2-blocks then, for n>1, a(n-1) is equal to the number of (n+2)-subsets of X intersecting each X_i (i=1,2,...,n). - Milan Janjic, Jul 21 2007
Number of n-permutations of 3 objects u,v,w, with repetition allowed, containing exactly two u's. Example: a(2)=6 because we have uuw, uuv, uwu, uvu, wuu and vuu. - Zerinvary Lajos, Dec 29 2007
For n>0 where [0]={}, the empty set, and [n]={1,2,...n} a(n) is the number of ways to separate [n-1] into three non-overlapping intervals (allowed to be empty) and then choose a subset from each interval. - Geoffrey Critzer, Feb 07 2009
Form an array with m(n,0) = m(0,n) = n^2 and m(i,j) = m(i-1,j-1) + m(i-1,j). Then m(1,n) = A001844(n) and m(n,n) = a(n). - J. M. Bergot, Nov 07 2012
The sum of the number of inversions of all sequences of zeros and ones with length n+1. - Evan M. Bailey, Dec 09 2020
a(n) is the number of strings of length n defined on {0,1,2,3} that contain at most one 2, exactly one 3, and have no restriction on the number of 0s and 1s. For example, a(3)=24 since the strings are 321 (6 of this type), 320 (6 of this type), 310 (6 of this type), 300 (3 of this type) and 311 (3 of this type). - Enrique Navarrete, May 04 2025

Examples

			The nodes of an integer composition are the partial sums of its elements, seen as relative distances between nodes of a 1-dimensional polygon. For a composition of 7 such as 1+2+1+3, the nodes are 0,1,3,4,7. Their sum (without the last node) is 8. The sum of all nodes of all 2^(7-1)=64 integer compositions of 7 is 672.

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. 796.
  • Clifford A. Pickover, The Math Book, From Pythagoras to the 57th Dimension, 250 Milestones in the History of Mathematics, Sterling Publ., NY, 2009, page 282.
  • A. P. Prudnikov, Yu. A. Brychkov and O.I. Marichev, "Integrals and Series", Volume 1: "Elementary Functions", Chapter 4: "Finite Sums", New York, Gordon and Breach Science Publishers, 1986-1992.
  • 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. A000079, A001787, A001789, A001793 (sum of all nodes of integer compositions, n included).
Cf. A001844, A038207, A290031 (6-cycles).
Row sums of triangle A094305.
Sequences similar to the form q^(n-2)*binomial(n, 2): A000217 (q=1), this sequence (q=2), A027472 (q=3), A038845 (q=4), A081135 (q=5), A081136 (q=6), A027474 (q=7), A081138 (q=8), A081139 (q=9), A081140 (q=10), A081141 (q=11), A081142 (q=12), A027476 (q=15).

Programs

  • GAP
    List([0..30], n-> n*(n+1)*2^(n-2)); # G. C. Greubel, Aug 27 2019
  • Haskell
    a001788 n = if n < 2 then n else n * (n + 1) * 2 ^ (n - 2)
a001788_list = zipWith (*) a000217_list $ 1 : a000079_list
-- Reinhard Zumkeller, Jul 11 2014
  • Magma
    [n*(n+1)*2^(n-2): n in [0..30]]; // G. C. Greubel, Aug 27 2019
  • Maple
    A001788 := n->n*(n+1)*2^(n-2);
A001788:=-1/(2*z-1)**3; # Simon Plouffe in his 1992 dissertation; gives sequence without initial zero
  • Mathematica
    CoefficientList[Series[x/(1-2x)^3, {x,0,30}], x]
Table[n*(n+1)*2^(n-2), {n,0,30}]
With[{n = 30}, Join[{0}, Times @@@ Thread[{Accumulate[Range[n]], 2^Range[0, n - 1]}]]] (* Harvey P. Dale, Jul 16 2013 *)
LinearRecurrence[{6, -12, 8}, {0, 1, 6}, 30] (* Harvey P. Dale, Jul 16 2013 *)
  • PARI
    a(n)=if(n<0,0,2^n*n*(n+1)/4)
  • PARI
    A001788_upto(n)=Vec(x/(1-2*x)^3+O(x^n),-n) \\ for illustration. - M. F. Hasler, Oct 05 2024
  • Sage
    [n if n < 2 else n * (n + 1) * 2**(n - 2) for n in range(28)] # Zerinvary Lajos, Mar 10 2009

Formula

G.f.: x/(1-2*x)^3.
E.g.f.: x*(1 + x)*exp(2*x).
a(n) = 2*a(n-1) + n*2^(n-1) = 2*a(n-1) + A001787(n).
a(n) = A038207(n+1,2).
a(n) = A055252(n, 2).
a(n) = Sum_{i=1..n} i^2 * binomial(n, i): binomial transform of A000290. - Yong Kong, Dec 26 2000
a(n) = Sum_{j=0..n} binomial(n+1,j)*(n+1-j)^2. - Zerinvary Lajos, Aug 22 2006
If the leading 0 is deleted, the binomial transform of A001844: (1, 5, 13, 25, 41, ...); = double binomial transform of [1, 4, 4, 0, 0, 0, ...]. - Gary W. Adamson, Sep 02 2007
a(n) = Sum_{1<=i<=k<=n} (-1)^(i+1)*i^2*binomial(n+1,k+i)*binomial(n+1,k-i). - Mircea Merca, Apr 09 2012
a(0)=0, a(1)=1, a(2)=6, a(n) = 6*a(n-1) - 12*a(n-2) + 8*a(n-3). - Harvey P. Dale, Jul 16 2013
a(n) = Sum_{k=0..n-1} Sum_{i=0..n-1} (k+1) * C(n-1,i). - Wesley Ivan Hurt, Sep 20 2017
From Amiram Eldar, Jan 05 2022: (Start)
Sum_{n>=1} 1/a(n) = 4*(1-log(2)).
Sum_{n>=1} (-1)^(n+1)/a(n) = 12*log(3/2) - 4. (End)

A000248 Expansion of e.g.f. exp(x*exp(x)).

Original entry on oeis.org

1, 1, 3, 10, 41, 196, 1057, 6322, 41393, 293608, 2237921, 18210094, 157329097, 1436630092, 13810863809, 139305550066, 1469959371233, 16184586405328, 185504221191745, 2208841954063318, 27272621155678841, 348586218389733556, 4605223387997411873
Offset: 0

Views

Author

N. J. A. Sloane, Simon Plouffe

Keywords

Comments

Number of forests with n nodes and height at most 1.
Equivalently, number of idempotent mappings f from a set of n elements into itself (i.e., satisfying f o f = f). - Robert FERREOL, Oct 11 2007
In other words, a(n) = number of idempotents in the full semigroup of maps from [1..n] to itself. [Tainiter]
a(n) is the number of ways to select a set partition of {1,2,...,n} and then designate one element in each block (cell) of the partition.
Let set B have cardinality n. Then a(n) is the number of functions f:D->C over all partitions {D,C} of B. See the example in the Example Section below. We note that f:empty set->B is designated as the null function, whereas f:B->empty set is undefined unless B itself is empty. - Dennis P. Walsh, Dec 05 2013
In physics, a(n) would be interpreted as the number of projection operators P on S_n, i.e., ones satisfying P^2 = P. Example: a particle with a half-integer spin s has a spin space with 2s+1 base states which admits a(2s+1) linear projection operators (including the identity). These are important because they satisfy the operator identity exp(zU) = 1+(exp(z)-1)*U, valid for any complex z. - Stanislav Sykora, Nov 03 2016

Examples

			a(3)=10 since, for B={1,2,3}, we have 10 functions: 1 function of the type f:empty set->B; 6 functions of the type f:{x}->B\{x}; and 3 functions of the type f:{x,y}->B\{x,y}. - _Dennis P. Walsh_, Dec 05 2013

References

  • L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 91.
  • 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).
  • R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.32(d).

Links

Crossrefs

First row of array A098697.
Row sums of A133399.
Column k=1 of A210725, A279636.
Column k=2 of A245501.
Cf. A005727, A048993.

Programs

  • Magma
    m:=25; R:=PowerSeriesRing(Rationals(), m); b:=Coefficients(R!(Exp(x*Exp(x)))); [Factorial(n-1)*b[n]: n in [1..m]]; // Vincenzo Librandi, Feb 01 2020
  • Maple
    A000248 := proc(n) local k; add(k^(n-k)*binomial(n, k), k=0..n); end; # Robert FERREOL, Oct 11 2007
a:= proc(n) option remember; if n=0 then 1 else add(binomial(n-1, j) *(j+1) *a(n-1-j), j=0..n-1) fi end: seq(a(n), n=0..20); # Zerinvary Lajos, Mar 28 2009
  • Mathematica
    CoefficientList[Series[Exp[x Exp[x]],{x,0,20}],x]*Table[n!,{n,0,20}]
a[0] = 1; a[1] = 1; a[n_] := a[n] = a[n - 1] + Sum[(Binomial[n - 1, j] + (n - 1) Binomial[n - 2, j]) a[j], {j, 0, n - 2}]; Table[a[n], {n, 0, 20}] (* David Callan, Oct 04 2013 *)
Flatten[{1,Table[Sum[Binomial[n,k]*(n-k)^k,{k,0,n}],{n,1,20}]}] (* Vaclav Kotesovec, Jul 13 2014 *)
Table[Sum[BellY[n, k, Range[n]], {k, 0, n}], {n, 0, 20}] (* Vladimir Reshetnikov, Nov 09 2016 *)
  • PARI
    a(n)=sum(k=0,n,binomial(n,k)*(n-k)^k); \\ Paul D. Hanna, Jun 26 2009
  • PARI
    x='x+O('x^66); Vec(serlaplace(exp(x*exp(x)))) \\ Joerg Arndt, Oct 06 2013
  • Sage
    # uses[bell_matrix from A264428]
B = bell_matrix(lambda k: k+1, 20)
print([sum(B.row(n)) for n in range(20)]) # Peter Luschny, Sep 03 2019

Formula

G.f.: Sum_{k>=0} x^k/(1-k*x)^(k+1). - Vladeta Jovovic, Oct 25 2003
a(n) = Sum_{k=0..n} C(n,k)*(n-k)^k. - Paul D. Hanna, Jun 26 2009
G.f.: G(0) where G(k) = 1 - x*(-1+2*k*x)^(2*k+1)/((x-1+2*k*x)^(2*k+2) - x*(x-1+2*k*x)^(4*k+4)/(x*(x-1+2*k*x)^(2*k+2) - (2*x-1+2*k*x)^(2*k+3)/G(k+1))) (continued fraction). - Sergei N. Gladkovskii, Jan 26 2013
E.g.f.: 1 + x/(1+x)*(G(0) - 1) where G(k) = 1 + exp(x)/(k+1)/(1-x/(x+(1)/G(k+1))) (continued fraction). - Sergei N. Gladkovskii, Feb 04 2013
Recurrence: a(0)=1, a(n) = Sum_{k=1..n} binomial(n-1,k-1)*k*a(n-k). - James East, Mar 30 2014
Asymptotics (Harris and Schoenfeld, 1968): a(n) ~ sqrt((r+1)/(2*Pi*(n+1)*(r^2+3*r+1))) * n! * exp((n+1)/(r+1)) / r^n, where r is the root of the equation r*(r+1)*exp(r) = n+1. - Vaclav Kotesovec, Jul 13 2014
a(n) = Sum_{k=0..n} A005727(k)*Stirling2(n, k). - Mélika Tebni, Jun 12 2022
More precise asymptotics: a(n) ~ n^(n + 1/2) / (sqrt(1 + 3*r + r^2) * exp(n - r*exp(r) + r/2) * r^(n + 1/2)), where r = 2*w - 1/(2*w) + 5/(8*w^2) - 19/(24*w^3) + 209/(192*w^4) - 763/(480*w^5) + 4657/(1920*w^6) - 6855/(1792*w^7) + 199613/(32256*w^8) + ... and w = LambertW(sqrt(n)/2). - Vaclav Kotesovec, Feb 20 2023

Extensions

In view of the multiple appearances of this sequence, I replaced the definition with the simple exponential generating function. - N. J. A. Sloane, Apr 16 2018

A001818 Squares of double factorials: (1*3*5*...*(2n-1))^2 = ((2*n-1)!!)^2.

Original entry on oeis.org

1, 1, 9, 225, 11025, 893025, 108056025, 18261468225, 4108830350625, 1187451971330625, 428670161650355625, 189043541287806830625, 100004033341249813400625, 62502520838281133375390625, 45564337691106946230659765625, 38319607998220941779984862890625
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Number of permutations in S_{2n} in which all cycles have even length (cf. A087137).
Also number of permutations in S_{2n} in which all cycles have odd length. - Vladeta Jovovic, Aug 10 2007
a(n) is the sum over all multinomials M2(2*n,k), k from {1..p(2*n)} restricted to partitions with only even parts. p(2*n)= A000041(2*n) (partition numbers) and for the M2-multinomial numbers in A-St order see A036039(2*n,k). - Wolfdieter Lang, Aug 07 2007
From Zhi-Wei Sun, Jun 26 2022: (Start)
Conjecture 1: For any primitive 2n-th root zeta of unity, the permanent of the 2n X 2n matrix [m(j,k)]_{j,k=1..2n} coincides with a(n) = ((2n-1)!!)^2, where m(j,k) is (1+zeta^(j-k))/(1-zeta^(j-k)) if j is not equal to k, and 1 otherwise.
The determinant of [m(j,k)]_{j,k=1..2n} was shown to be (-1)^(n-1)*((2n-1)!!)^2/(2n-1) by Han Wang and Zhi-Wei Sun in 2022.
Conjecture 2: Let p be an odd prime. Then the permanent of (p-1) X (p-1) matrix [f(j,k)]_{j,k=1..p-1} is congruent to a((p-1)/2) = ((p-2)!!)^2 modulo p^2, where f(j,k) is (j+k)/(j-k) if j is not equal to k, and f(j,k) = 1 otherwise. (End)

Examples

			Multinomial representation for a(2): partitions of 2*2=4 with even parts only: (4) with position k=1, (2^2) with k=3; M2(4,1)= 6 and M2(4,3)= 3, adding up to a(2)=9.
G.f. = 1 + x + 9*x^2 + 225*x^3 + 11025*x^4 + 893025*x^5 + 108056025*x^6 + ...

References

  • John Riordan, Combinatorial Identities, Wiley, 1968, p. 217.
  • 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).
  • Richard P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.34(c).

Links

Crossrefs

Cf. A001147, A002454, A111595, A197037.
Bisection of A012248.
Right-hand column 1 in triangle A008956.

Programs

  • Magma
    DoubleFactorial:=func< n | &*[n..2 by -2] >; [DoubleFactorial((2*n-1))^2: n in [0..20] ]; // Vincenzo Librandi, Jul 21 2017
  • Maple
    a := proc(m) local k; 4^m*mul((-1)^k*(k-m-1/2),k=1..2*m) end; # Peter Luschny, Jun 01 2009
  • Mathematica
    FoldList[Times,1,Range[1,25,2]]^2 (* or *) Join[{1},(Range[1,29,2]!!)^2] (* Harvey P. Dale, Jun 06 2011, Apr 10 2012 *)
Table[((2 n - 1)!!)^2, {n, 0, 30}] (* Vincenzo Librandi, Jul 21 2017 *)
  • PARI
    a(n)=((2*n)!/(n!*2^n))^2
  • PARI
    {a(n) = if( n<0, 1 / a(-n), sqr((2*n)! / (n! * 2^n)))}; /* Michael Somos, Jan 06 2017 */

Formula

a(n) = A001147(n)^2.
a(n) = A111595(2*n, 0).
a(n) = (2*n-1)!*Sum_{k=0..n-1} binomial(2*k,k)/4^k, n >= 1. - Wolfdieter Lang, Aug 23 2005
arcsinh(x) = Sum_{n>=1} (-1)^(n-1)*a(n)*x^(2*n-1)/(2*n-1)!. - James R. Buddenhagen, Mar 24 2009
From Karol A. Penson, Oct 21 2009: (Start)
G.f.: Sum_{n>=0} a(n)*x^n/(n!)^2 = 2*EllipticK(2*sqrt(x))/Pi.
Asymptotically: a(n) = (2/((exp(-1/2))^2*(exp(1/2))^2)-1/(6*(exp(-1/2))^2*(exp(1/2))^2*n)+1/(144*(exp(-1/2))^2*(exp(1/2))^2*n^2)+O(1/n^3))*(2^n)^2/(((1/n)^n)^2*(exp(n))^2), n->infinity.
Integral representation as n-th moment of a positive function on a positive halfaxis (solution of the Stieltjes moment problem), in Maple notation:
a(n) = Integral_{x>=0} x^n*BesselK(0,sqrt(x))/(Pi*sqrt(x)).
This solution is unique.
(End)
D-finite with recurrence: a(0) = 1, a(n) = (2*n-1)^2*a(n-1), n > 0.
a(n) ~ 2*2^(2*n)*e^(-2*n)*n^(2*n). - Joe Keane (jgk(AT)jgk.org), Jun 06 2002
E.g.f.: 1/sqrt(1-x^2) = Sum_{n >= 0} a(n)*x^(2*n)/(2*n)!. Also arcsin(x) = Sum_{n >= 0} a(n)*x^(2*n+1)/(2*n+1)!. - Michael Somos, Jul 03 2002
(-1)^n*a(n) is the coefficient of x^0 in prod(k=1, 2*n, x+2*k-2*n-1). - Benoit Cloitre and Michael Somos, Nov 22 2002
-arccos(x) + Pi/2 = x + x^3/3! + 9*x^5/5! + 225*x^7/7! + 11205*x^9/9! + ... - Tom Copeland, Oct 23 2008
G.f.: 1 + x*(G(0) - 1)/(x-1) where G(k) = 1 - (4*k^2+4*k+1)/(1-x/(x - 1/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jan 15 2013
a(n) = det(V(i+1,j), 1 <= i,j <= n), where V(n,k) are central factorial numbers of the second kind with odd indices. - Mircea Merca, Apr 04 2013
a(n) = (1+x^2)^(n+1/2) * (d/dx)^(2*n) (1+x^2)^(n-1/2). See Tao link. - Robert Israel, Jun 04 2015
a(n) = 4^n * gamma(n + 1/2)^2 / Pi. - Daniel Suteu, Jan 06 2017
0 = a(n)*(+384*a(n+2) - 60*a(n+3) + a(n+4)) + a(n+1)*(-36*a(n+2) - 4*a(n+3)) + a(n+2)*(+3*a(n+2)) and a(n) = 1/a(-n) for all n in Z. - Michael Somos, Jan 06 2017
From Robert FERREOL, Jul 30 2020: (Start)
a(n) = ((2*n)!/4^n)*binomial(2*n,n).
a(n) = (2*n-1)!*Sum_{k=0..n-1} a(k)/(2*k)!, n >= 1.
a(n) = A184877(2*n-1) for n>=1. (End)
From Amiram Eldar, Mar 18 2022: (Start)
Sum_{n>=0} 1/a(n) = 1 + L_0(1)*Pi/2, where L is the modified Struve function (see A197037).
Sum_{n>=0} (-1)^n/a(n) = 1 - H_0(1)*Pi/2, where H is the Struve function. (End)

Extensions

Incorrect formula deleted by N. J. A. Sloane, Jul 03 2009

A001858 Number of forests of trees on n labeled nodes.

Original entry on oeis.org

1, 1, 2, 7, 38, 291, 2932, 36961, 561948, 10026505, 205608536, 4767440679, 123373203208, 3525630110107, 110284283006640, 3748357699560961, 137557910094840848, 5421179050350334929, 228359487335194570528, 10239206473040881277575, 486909744862576654283616
Offset: 0

Views

Author

N. J. A. Sloane and Simon Plouffe

Keywords

Comments

The number of integer lattice points in the permutation polytope of {1,2,...,n}. - Max Alekseyev, Jan 26 2010
Equals the number of score sequences for a tournament on n vertices. See Prop. 7 of the article by Bartels et al., or Example 3.1 in the article by Stanley. - David Radcliffe, Aug 02 2022
Number of labeled acyclic graphs on n vertices. The unlabeled version is A005195. The covering case is A105784, connected A000272. - Gus Wiseman, Apr 29 2024

Examples

			From _Gus Wiseman_, Apr 29 2024: (Start)
Edge-sets of the a(4) = 38 forests:
  {}  {12}  {12,13}  {12,13,14}
      {13}  {12,14}  {12,13,24}
      {14}  {12,23}  {12,13,34}
      {23}  {12,24}  {12,14,23}
      {24}  {12,34}  {12,14,34}
      {34}  {13,14}  {12,23,24}
            {13,23}  {12,23,34}
            {13,24}  {12,24,34}
            {13,34}  {13,14,23}
            {14,23}  {13,14,24}
            {14,24}  {13,23,24}
            {14,34}  {13,23,34}
            {23,24}  {13,24,34}
            {23,34}  {14,23,24}
            {24,34}  {14,23,34}
                     {14,24,34}
(End)

References

  • B. Bollobas, Modern Graph Theory, Springer, 1998, p. 290.
  • 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

The connected case is A000272, rooted A000169.
The unlabeled version is A005195, connected A000055.
The covering case is A105784, unlabeled A144958.
Row sums of A138464.
For triangles instead of cycles we have A213434, covering A372168.
For a unique cycle we have A372193, covering A372195.
A002807 counts cycles in a complete graph.
A006125 counts simple graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
Cf. A006572, A006573, A088956.
Cf. A053530, A054548, A137916, A263340, A322661, A367863, A372176.

Programs

  • Maple
    exp(x+x^2+add(n^(n-2)*x^n/n!, n=3..50));
# second Maple program:
a:= proc(n) option remember; `if`(n=0, 1, add(
      binomial(n-1, j-1)*j^(j-2)*a(n-j), j=1..n))
    end:
seq(a(n), n=0..20);  # Alois P. Heinz, Sep 15 2008
# third Maple program:
F:= exp(-LambertW(-x)*(1+LambertW(-x)/2)):
S:= series(F,x,51):
seq(coeff(S,x,j)*j!, j=0..50); # Robert Israel, May 21 2015
  • Mathematica
    nn=20;t=Sum[n^(n-1)x^n/n!,{n,1,nn}];Range[0,nn]!CoefficientList[ Series[Exp[t-t^2/2],{x,0,nn}],x] (* Geoffrey Critzer, Sep 05 2012 *)
nmax = 20; CoefficientList[Series[-LambertW[-x]/(x*E^(LambertW[-x]^2/2)), {x, 0, nmax}], x] * Range[0, nmax]! (* Vaclav Kotesovec, Jul 19 2019 *)
  • PARI
    a(n)=if(n<0,0,sum(m=0,n,sum(j=0,m,binomial(m,j)*binomial(n-1,n-m-j)*n^(n-m-j)*(m+j)!/(-2)^j)/m!)) /* Michael Somos, Aug 22 2002 */

Formula

E.g.f.: exp( Sum_{n>=1} n^(n-2)*x^n/n! ). This implies (by a theorem of Wright) that a(n) ~ exp(1/2)*n^(n-2). - N. J. A. Sloane, May 12 2008 [Corrected by Philippe Flajolet, Aug 17 2008]
E.g.f.: exp(T - T^2/2), where T = T(x) = Sum_{n>=1} n^(n-1)*x^n/n! is Euler's tree function (see A000169). - Len Smiley, Dec 12 2001
Shifts 1 place left under the hyperbinomial transform (cf. A088956). - Paul D. Hanna, Nov 03 2003
a(0) = 1, a(n) = Sum_{j=0..n-1} C(n-1,j) (j+1)^(j-1) a(n-1-j) if n>0. - Alois P. Heinz, Sep 15 2008

Extensions

More terms from Michael Somos, Aug 22 2002

A007016 Number of permutations of length n with 1 fixed and 1 reflected point.

Original entry on oeis.org

0, 1, 0, 0, 8, 20, 96, 656, 5568, 48912, 494080, 5383552, 65097600, 840566080, 11833898496, 176621049600, 2838024476672, 48060623405312, 868000333234176, 16441638519762944, 329723762151352320, 6907027877807330304
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Number of distinct solutions to the order n checkerboard problem, including symmetrical solutions: place n pieces on an n X n board so there is exactly one piece in each row, column and main diagonal. Compare A064280.
Number of magic permutation matrices of order n. - Chai Wah Wu, Jan 15 2019
Upper bound for the number of diagonal transversals in a Latin square: A287647(n) <= A287648(n) <= a(n). - Eduard I. Vatutin, Jan 02 2020

References

  • Simpson, Todd; Permutations with unique fixed and reflected points. Ars Combin. 39 (1995), 97-108.
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Cf. A003471, A064280.

Programs

  • Mathematica
    x[n_] := x[n] = Integrate[If[EvenQ[n], (x^2 - 4*x + 2)^(n/2), (x - 1)*(x^2 - 4*x + 2)^((n - 1)/2)]/E^x, {x, 0, Infinity}];
a[n_ /; EvenQ[n]] := With[{m = n/2}, m*(x[2*m] - (2*m - 3)*x[2*m - 1])];
a[n_ /; OddQ[n]] := With[{m = (n - 1)/2}, (2*m + 1)*x[2*m] + 3*m*x[2*m - 1] - 2*m*(m - 1)*x[2*m - 2]];
Table[a[n], {n, 0, 21}] // Quiet (* Jean-François Alcover, Jun 29 2018 *)
  • PARI
    a(n) = {my(v = vector(n)); \\ v is A003471
for(n=4, length(v), v[n] = (n-1)*v[n-1] + 2*if(n%2==1, (n-1)*v[n-2], (n-2) * if(n==4,1,v[n-4])));
if(n<4, [1,0,0][n], if(n%2==0, n*(v[n] - (n-3)*v[n-1]), 2*n*v[n-1] + 3*(n-1)*v[n-2] - (n-1)*(n-3)*v[n-3])/2)} \\ Andrew Howroyd, Sep 12 2017

Formula

a(2*m) = m*(x(2*m) - (2*m-3)*x(2*m-1)), a(2*m+1) = (2*m+1)*x(2*m) + 3*m*x(2*m-1) - 2*m*(m-1)*x(2*m-2), where x(n) = A003471(n).
Conjecture D-finite with recurrence (365968635435167109808*n^2 -5566069866485493251505*n +20525522573033552369132)*a(n) +(-1215369044326430542311*n^2 +19103429957352794982854*n -73690801030090785944295)*a(n-1) +(-365968635435167109808*n^4 +6663975772790994580929*n^3 -35836353442786038818589*n^2 +34878550744402035813586*n +124043542472821007763204)*a(n-2) +(483431773456096322695*n^4 -10754417727097457203127*n^3 +85154149458907095778621*n^2 -277683967994722584206067*n +286254870342835757751852)*a(n-3) +2*(-393241909113483884738*n^4 +9142334951839265043383*n^3 -78427160779754271402777*n^2 +309283968160862567580813*n -465057422344277141977923)*a(n-4) +2*(-745044547502580209919*n^4 +21471238686323774026196*n^3 -222067832543690193789255*n^2 +944698954932049830084232*n -1372732531859619119793978)*a(n-5) +4*(365968635435167109808*n^4 -5227374504728642916627*n^3 +19793104565012302929789*n^2 +391834816007939927082*n -57365695502678698166146)*a(n-6) +4*(-483431773456096322695*n^4 +7592214312314395379733*n^3 -45284933032689911393913*n^2 +117535885088909103449165*n -84799883220517633629252)*a(n-7) +8*(n-7)*(393241909113483884738*n^3 -4789400677912625536335*n^2 +17834478528905815208536*n -23668675533486426523455)*a(n-8) +8*(n-7)*(n-8)*(745044547502580209919*n^2 -6086915962816073505121*n +12854159797389104313178)*a(n-9)=0. - R. J. Mathar, Feb 27 2025

A003472 a(n) = 2^(n-4)*C(n,4).

Original entry on oeis.org

1, 10, 60, 280, 1120, 4032, 13440, 42240, 126720, 366080, 1025024, 2795520, 7454720, 19496960, 50135040, 127008768, 317521920, 784465920, 1917583360, 4642570240, 11142168576, 26528972800, 62704844800, 147220070400
Offset: 4

Views

Author

N. J. A. Sloane

Keywords

Comments

Number of 4D hypercubes in n-dimensional hypercube. - Henry Bottomley, Apr 14 2000
With four leading zeros, binomial transform of C(n,4). - Paul Barry, Apr 10 2003
If X_1, X_2, ..., X_n is a partition of a 2n-set X into 2-blocks, then, for n>3, a(n) is equal to the number of (n+4)-subsets of X intersecting each X_i (i=1,2,...,n). - Milan Janjic, Jul 21 2007

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. 796.
  • Clifford A. Pickover, The Math Book, From Pythagoras to the 57th Dimension, 250 Milestones in the History of Mathematics, Sterling Publ., NY, 2009, page 282.
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Cf. A001787, A001788, A001789.
a(n) = A038207(n,4).

Programs

  • GAP
    List([4..30], n-> 2^(n-4)*Binomial(n,4)); # G. C. Greubel, Aug 27 2019
  • Magma
    [2^(n-4)*Binomial(n, 4): n in [4..30]]; // Vincenzo Librandi, Oct 16 2011
  • Maple
    A003472:=-1/(2*z-1)**5; # conjectured by Simon Plouffe in his 1992 dissertation
seq(binomial(n,4)*2^(n-4),n=4..24); # Zerinvary Lajos, Jun 12 2008
  • Mathematica
    Table[2^(n-4) Binomial[n,4],{n,4,50}] (* or *) LinearRecurrence[{10,-40,80,-80,32},{1,10,60,280,1120},50] (* Harvey P. Dale, May 27 2017 *)
  • PARI
    a(n)=binomial(n,4)<<(n-4) \\ Charles R Greathouse IV, May 18 2015
  • Sage
    [2^(n-4)*binomial(n,4) for n in (4..30)] # G. C. Greubel, Aug 27 2019

Formula

a(n) = 2*a(n-1) + A001789(n-1).
From Paul Barry, Apr 10 2003: (Start)
O.g.f.: x^4/(1-2*x)^5.
E.g.f.: exp(2*x)(x^4/4!) (with 4 leading zeros). (End)
a(n) = Sum_{i=4..n} binomial(i,4)*binomial(n,i). Example: for n=7, a(7) = 1*35 + 5*21 + 15*7 + 35*1 = 280. - Bruno Berselli, Mar 23 2018
From Amiram Eldar, Jan 06 2022: (Start)
Sum_{n>=4} 1/a(n) = 20/3 - 8*log(2).
Sum_{n>=4} (-1)^n/a(n) = 216*log(3/2) - 260/3. (End)

Extensions

More terms from James Sellers, Apr 15 2000

A002083 Narayana-Zidek-Capell numbers: a(n) = 1 for n <= 2. Otherwise a(2n) = 2a(2n-1), a(2n+1) = 2a(2n) - a(n).

Original entry on oeis.org

1, 1, 1, 2, 3, 6, 11, 22, 42, 84, 165, 330, 654, 1308, 2605, 5210, 10398, 20796, 41550, 83100, 166116, 332232, 664299, 1328598, 2656866, 5313732, 10626810, 21253620, 42505932, 85011864, 170021123, 340042246, 680079282, 1360158564
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

Comments

Number of compositions p(1) + p(2) + ... + p(k) = n of n into positive parts p(i) with p(1)=1 and p(k) <= Sum_{j=1..k-1} p(j), see example - Claude Lenormand (claude.lenormand(AT)free.fr), Jan 29 2001 (clarified by Joerg Arndt, Feb 01 2013)
a(n) is the number of sequences (b(1),b(2),...) of unspecified length satisfying b(1) = 1, 1 <= b(i) <= 1 + Sum[b(j),{j,i-1}] for i>=2, Sum[b(i)] = n-1. For example, a(5) = 3 counts (1, 1, 1, 1), (1, 2, 1), (1, 1, 2). These sequences are generated by the Mathematica code below. - David Callan, Nov 02 2005
a(n+1) is the number of padded compositions (d_1,d_2,...,d_n) of n satisfying d_i <= i for all i. A padded composition of n is obtained from an ordinary composition (c_1,c_2,...,c_r) of n (r >= 1, each c_i >= 1, Sum_{i=1..r} c_i = n) by inserting c_i - 1 zeros immediately after each c_i. Thus (3,1,2) -> (3,0,0,1,2,0) is a padded composition of 6 and a padded composition of n has length n. For example, with n=4, a(5) counts (1,1,1,1), (1,1,2,0), (1,2,0,1). - David Callan, Feb 04 2006
From David Callan, Sep 25 2006: (Start)
a(n) is the number of ordered trees on n edges in which (i) every node (= non-root non-leaf vertex) has at least 2 children and (ii) each leaf is either the leftmost or rightmost child of its parent.
For example, a(4)=2 counts
./\.../\
/\...../\,
and a(5)=3 counts
.|.......|....../|\
/ \...../ \...../ \
../\.../\.
(End)
Starting with offset 2 = eigensequence of triangle A101688 and row sums of triangle A167948. - Gary W. Adamson, Nov 15 2009
If we remove the condition that a(2) = 1, then the resulting sequence is A045690 minus the first term. - Chai Wah Wu, Nov 08 2022

Examples

			From _Joerg Arndt_, Feb 01 2013: (Start)
The a(7) = 11 compositions p(1) + p(2) + ... + p(k) = 7 of 7 into positive parts p(i) with p(1)=1 and p(k) <= Sum_{j=1..k-1} p(j) are
[ 1]  [ 1 1 1 1 1 1 1 ]
[ 2]  [ 1 1 1 1 1 2 ]
[ 3]  [ 1 1 1 1 2 1 ]
[ 4]  [ 1 1 1 1 3 ]
[ 5]  [ 1 1 1 2 1 1 ]
[ 6]  [ 1 1 1 2 2 ]
[ 7]  [ 1 1 1 3 1 ]
[ 8]  [ 1 1 2 1 1 1 ]
[ 9]  [ 1 1 2 1 2 ]
[10]  [ 1 1 2 2 1 ]
[11]  [ 1 1 2 3 ]
(End)

References

  • S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 2.28.
  • T. V. Narayana, Lattice Path Combinatorics with Statistical Applications. Univ. Toronto Press, 1979, pp. 100-101.
  • 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. A045690. A058222 gives sums of words.
Cf. A001045, A002487, A101688, A167948.
Cf. A242729.
Bisections: A245094, A259858.

Programs

  • Haskell
    a002083 n = a002083_list !! (n-1)
a002083_list = 1 : f [1] where
   f xs = x : f (x:xs) where x = sum $ take (div (1 + length xs) 2) xs
-- Reinhard Zumkeller, Dec 27 2011
  • Maple
    A002083 := proc(n) option remember; if n<=3 then 1 elif n mod 2 = 0 then 2*procname(n-1) else 2*procname(n-1)-procname((n-1)/2); end if; end proc:
a := proc(n::integer) # A002083 Narayana-Zidek-Capell numbers: a(2n)=2a(2n-1), a(2n+1)=2a(2n)-a(n). local k; option remember; if n = 0 then 1 else add(K(n-k+1, k)*procname(n - k), k = 1 .. n); #else add(K((n-k)!, k!)*procname(n - k), k = 1 .. n); end if end proc; K := proc(n::integer, k::integer) local KC; if 0 <= k and k <= n then KC := 1 else KC := 0 end if; end proc; # Thomas Wieder, Jan 13 2008
  • Mathematica
    a[1] = 1; a[n_] := a[n] = Sum[a[k], {k, n/2, n-1} ]; Table[ a[n], {n, 2, 70, 2} ] (* Robert G. Wilson v, Apr 22 2001 *)
bSequences[1]={ {1} }; bSequences[n_]/;n>=2 := bSequences[n] = Flatten[Table[Map[Join[ #, {i}]&, bSequences[n-i]], {i, Ceiling[n/2]}], 1] (* David Callan *)
a=ConstantArray[0,20]; a[[1]]=1; a[[2]]=1; Do[If[EvenQ[n],a[[n]]=2a[[n-1]],a[[n]]=2a[[n-1]]-a[[(n-1)/2]]];,{n,3,20}]; a (* Vaclav Kotesovec, Nov 19 2012 *)
  • PARI
    a(n)=if(n<3,n>0,2*a(n-1)-(n%2)*a(n\2))
  • PARI
    a(n)=local(A=1+x);for(i=1,n,A=(1-x-x^2*subst(A,x,x^2+O(x^n)))/(1-2*x));polcoeff(A,n) \\ Paul D. Hanna, Mar 17 2010
  • Python
    from functools import lru_cache
@lru_cache(maxsize=None)
def A002083(n): return 1 if n <=3 else (A002083(n-1)<<1)-(A002083(n>>1) if n&1 else 0) # Chai Wah Wu, Nov 07 2022

Formula

a(1)=1, else a(n) is sum of floor(n/2) previous terms.
Conjecture: lim_{n->oo} a(n)/2^(n-3) = a constant ~0.633368 (=2*A242729). - Gerald McGarvey, Jul 18 2004
First column of A155092. - Mats Granvik, Jan 20 2009
a(n+2) = A037254(n,1) = A037254(n,floor(n/2)+1). - Reinhard Zumkeller, Nov 18 2012
Limit is equal to 0.633368347305411640436713144616576659... = 2*Atkinson-Negro-Santoro constant = 2*A242729, see Finch's book, chapter 2.28 (Erdős' Sum-Distinct Set Constant), pp. 189, 552. - Vaclav Kotesovec, Nov 19 2012
a(n) is the permanent of the (n-1) X (n-1) matrix with (i, j) entry = 1 if i-1 <= j <= 2*i-1 and = 0 otherwise. - David Callan, Nov 02 2005
a(n) = Sum_{k=1..n} K(n-k+1, k)*a(n-k), where K(n,k) = 1 if 0 <= k AND k <= n and K(n,k)=0 else. (Several arguments to the K-coefficient K(n,k) can lead to the same sequence. For example, we get A002083 also from a(n) = Sum_{k=1..n} K((n-k)!,k!)*a(n-k), where K(n,k) = 1 if 0 <= k <= n and 0 else. See also the comment to a similar formula for A002487.) - Thomas Wieder, Jan 13 2008
G.f. satisfies: A(x) = (1-x - x^2*A(x^2))/(1-2x). - Paul D. Hanna, Mar 17 2010

Extensions

Definition clarified by Chai Wah Wu, Nov 08 2022
Showing 1-10 of 27 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.