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-8 of 8 results.

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

Original entry on oeis.org

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

Views

Author

N. J. A. Sloane

Keywords

Comments

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

Examples

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

References

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

Links

Crossrefs

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

Programs

  • Haskell
    a000225 = (subtract 1) . (2 ^)
a000225_list = iterate ((+ 1) . (* 2)) 0
-- Reinhard Zumkeller, Mar 20 2012
  • Maple
    A000225 := n->2^n-1; [ seq(2^n-1,n=0..50) ];
A000225:=1/(2*z-1)/(z-1); # Simon Plouffe in his 1992 dissertation, sequence starting at a(1)
  • Mathematica
    a[n_] := 2^n - 1; Table[a[n], {n, 0, 30}] (* Stefan Steinerberger, Mar 30 2006 *)
Array[2^# - 1 &, 50, 0] (* Joseph Biberstine (jrbibers(AT)indiana.edu), Dec 26 2006 *)
NestList[2 # + 1 &, 0, 32] (* Robert G. Wilson v, Feb 28 2011 *)
2^Range[0, 20] - 1 (* Eric W. Weisstein, Jul 17 2017 *)
LinearRecurrence[{3, -2}, {1, 3}, 20] (* Eric W. Weisstein, Sep 21 2017 *)
CoefficientList[Series[1/(1 - 3 x + 2 x^2), {x, 0, 20}], x] (* Eric W. Weisstein, Sep 21 2017 *)
  • PARI
    A000225(n) = 2^n-1  \\ Michael B. Porter, Oct 27 2009
  • PARI
    concat(0, Vec(x/((1-2*x)*(1-x)) + O(x^100))) \\ Altug Alkan, Oct 28 2015
  • Python
    def A000225(n): return (1<Chai Wah Wu, Jul 06 2022
  • SageMath
    def isMersenne(n): return n == sum([(1 - b) << s for (s, b) in enumerate((n+1).bits())]) # Peter Luschny, Sep 01 2019

Formula

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

Extensions

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

A001045 Jacobsthal sequence (or Jacobsthal numbers): a(n) = a(n-1) + 2*a(n-2), with a(0) = 0, a(1) = 1; also a(n) = nearest integer to 2^n/3.

Original entry on oeis.org

0, 1, 1, 3, 5, 11, 21, 43, 85, 171, 341, 683, 1365, 2731, 5461, 10923, 21845, 43691, 87381, 174763, 349525, 699051, 1398101, 2796203, 5592405, 11184811, 22369621, 44739243, 89478485, 178956971, 357913941, 715827883, 1431655765, 2863311531, 5726623061, 11453246123
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Don Knuth points out (personal communication) that Jacobsthal may never have seen the actual values of this sequence. However, Horadam uses the name "Jacobsthal sequence", such an important sequence needs a name, and there is a law that says the name for something should never be that of its discoverer. - N. J. A. Sloane, Dec 26 2020
Number of ways to tile a 3 X (n-1) rectangle with 1 X 1 and 2 X 2 square tiles.
Also, number of ways to tile a 2 X (n-1) rectangle with 1 X 2 dominoes and 2 X 2 squares. - Toby Gottfried, Nov 02 2008
Also a(n) counts each of the following four things: n-ary quasigroups of order 3 with automorphism group of order 3, n-ary quasigroups of order 3 with automorphism group of order 6, (n-1)-ary quasigroups of order 3 with automorphism group of order 2 and (n-2)-ary quasigroups of order 3. See the McKay-Wanless (2008) paper. - Ian Wanless, Apr 28 2008
Also the number of ways to tie a necktie using n + 2 turns. So three turns make an "oriental", four make a "four in hand" and for 5 turns there are 3 methods: "Kelvin", "Nicky" and "Pratt". The formula also arises from a special random walk on a triangular grid with side conditions (see Fink and Mao, 1999). - arne.ring(AT)epost.de, Mar 18 2001
Also the number of compositions of n + 1 ending with an odd part (a(2) = 3 because 3, 21, 111 are the only compositions of 3 ending with an odd part). Also the number of compositions of n + 2 ending with an even part (a(2) = 3 because 4, 22, 112 are the only compositions of 4 ending with an even part). - Emeric Deutsch, May 08 2001
Arises in study of sorting by merge insertions and in analysis of a method for computing GCDs - see Knuth reference.
Number of perfect matchings of a 2 X n grid upon replacing unit squares with tetrahedra (C_4 to K_4):
o----o----o----o...
| \/ | \/ | \/ |
| /\ | /\ | /\ |
o----o----o----o... - Roberto E. Martinez II, Jan 07 2002
Also the numerators of the reduced fractions in the alternating sum 1/2 - 1/4 + 1/8 - 1/16 + 1/32 - 1/64 + ... - Joshua Zucker, Feb 07 2002
Also, if A(n), B(n), C(n) are the angles of the n-orthic triangle of ABC then A(1) = Pi - 2*A, A(n) = s(n)*Pi + (-2)^n*A where s(n) = (-1)^(n-1) * a(n) [1-orthic triangle = the orthic triangle of ABC, n-orthic triangle = the orthic triangle of the (n-1)-orthic triangle]. - Antreas P. Hatzipolakis (xpolakis(AT)otenet.gr), Jun 05 2002
Also the number of words of length n+1 in the two letters s and t that reduce to the identity 1 by using the relations sss = 1, tt = 1 and stst = 1. The generators s and t and the three stated relations generate the group S3. - John W. Layman, Jun 14 2002
Sums of pairs of consecutive terms give all powers of 2 in increasing order. - Amarnath Murthy, Aug 15 2002
Excess clockwise moves (over counterclockwise) needed to move a tower of size n to the clockwise peg is -(-1)^n*(2^n - (-1)^n)/3; a(n) is its unsigned version. - Wouter Meeussen, Sep 01 2002
Also the absolute value of the number represented in base -2 by the string of n 1's, the negabinary repunit. The Mersenne numbers (A000225 and its subsequences) are the binary repunits. - Rick L. Shepherd, Sep 16 2002
Note that 3*a(n) + (-1)^n = 2^n is significant for Pascal's triangle A007318. It arises from a Jacobsthal decomposition of Pascal's triangle illustrated by 1 + 7 + 21 + 35 + 35 + 21 + 7 + 1 = (7 + 35 + 1) + (1 + 35 + 7) + (21 + 21) = 43 + 43 + 42 = 3a(7) - 1; 1 + 8 + 28 + 56 + 70 + 56 + 28 + 8 + 1 = (1 + 56 + 28) + (28 + 56 + 1) + (8 + 70 + 8) = 85 + 85 + 86 = 3a(8)+1. - Paul Barry, Feb 20 2003
Number of positive integers requiring exactly n signed bits in the nonadjacent form representation.
Equivalently, number of length-(n-1) words with letters {0, 1, 2} where no two consecutive letters are nonzero, see example and fxtbook link. - Joerg Arndt, Nov 10 2012
Counts walks between adjacent vertices of a triangle. - Paul Barry, Nov 17 2003
Every amphichiral rational knot written in Conway notation is a palindromic sequence of numbers, not beginning or ending with 1. For example, for 4 <= n <= 12, the amphichiral rational knots are: 2 2, 2 1 1 2, 4 4, 3 1 1 3, 2 2 2 2, 4 1 1 4, 3 1 1 1 1 3, 2 3 3 2, 2 1 2 2 1 2, 2 1 1 1 1 1 1 2, 6 6, 5 1 1 5, 4 2 2 4, 3 3 3 3, 2 4 4 2, 3 2 1 1 2 3, 3 1 2 2 1 3, 2 2 2 2 2 2, 2 2 1 1 1 1 2 2, 2 1 2 1 1 2 1 2, 2 1 1 1 1 1 1 1 1 2. For the number of amphichiral rational knots for n=2*k (k=1, 2, 3, ...), we obtain the sequence 0, 1, 1, 3, 5, 11, 21, 43, 85, 171, 341, 683, ... - Slavik Jablan, Dec 26 2003
a(n+2) counts the binary sequences of total length n made up of codewords from C = {0, 10, 11}. - Paul Barry, Jan 23 2004
Number of permutations with no fixed points avoiding 231 and 132.
The n-th entry (n > 1) of the sequence is equal to the 2,2-entry of the n-th power of the unnormalized 4 X 4 Haar matrix: [1 1 1 0 / 1 1 -1 0 / 1 1 0 1 / 1 1 0 -1]. - Simone Severini, Oct 27 2004
a(n) is the number of Motzkin (n+1)-sequences whose flatsteps all occur at level 1 and whose height is less than or equal to 2. For example, a(4) = 5 counts UDUFD, UFDUD, UFFFD, UFUDD, UUDFD. - David Callan, Dec 09 2004
a(n+1) gives row sums of A059260. - Paul Barry, Jan 26 2005
If (m + n) is odd, then 3*(a(m) + a(n)) is always of the form a^2 + 2*b^2, where a and b both equal powers of 2; consequently every factor of (a(m) + a(n)) is always of the form a^2 + 2*b^2. - Matthew Vandermast, Jul 12 2003
Number of "0,0" in f_{n+1}, where f_0 = "1" and f_{n+1} = a sequence formed by changing all "1"s in f_n to "1,0" and all "0"s in f_n to "0,1". - Fung Cheok Yin (cheokyin_restart(AT)yahoo.com.hk), Sep 22 2006
All prime Jacobsthal numbers A049883[n] = {3, 5, 11, 43, 683, 2731, 43691, ...} have prime indices except for a(4) = 5. All prime Jacobsthal numbers with prime indices (all but a(4) = 5) are of the form (2^p + 1)/3 - the Wagstaff primes A000979[n]. Indices of prime Jacobsthal numbers are listed in A107036[n] = {3, 4, 5, 7, 11, 13, 17, 19, 23, 31, 43, 61, ...}. For n>1 A107036[n] = A000978[n] Numbers n such that (2^n + 1)/3 is prime. - Alexander Adamchuk, Oct 03 2006
Correspondence: a(n) = b(n)*2^(n-1), where b(n) is the sequence of the arithmetic means of previous two terms defined by b(n) = 1/2*(b(n-1) + b(n-2)) with initial values b(0) = 0, b(1) = 1; the g.f. for b(n) is B(x) := x/(1-(x^1+x^2)/2), so the g.f. A(x) for a(n) satisfies A(x) = B(2*x)/2. Because b(n) converges to the limit lim (1-x)*B(x) = 1/3*(b(0) + 2*b(1)) = 2/3 (for x --> 1), it follows that a(n)/2^(n-1) also converges to 2/3 (see also A103770). - Hieronymus Fischer, Feb 04 2006
Inverse: floor(log_2(a(n))) = n - 2 for n >= 2. Also: log_2(a(n) + a(n-1)) = n - 1 for n >= 1 (see also A130249). Characterization: x is a Jacobsthal number if and only if there is a power of 4 (= c) such that x is a root of p(x) = 9*x*(x-c) + (c-1)*(2*c+1) (see also the indicator sequence A105348). - Hieronymus Fischer, May 17 2007
This sequence counts the odd coefficients in the expansion of (1 + x + x^2)^(2^n - 1), n >= 0. - Tewodros Amdeberhan (tewodros(AT)math.mit.edu), Oct 18 2007, Jan 08 2008
2^(n+1) = 2*A005578(n) + 2*a(n) + 2*A000975(n-1). Let A005578(n), a(n), A000975(n-1) = triangle (a, b, c). Then ((S-c), (S-b), (S-a)) = (A005578(n-1), a(n-1), A000975(n-2)). Example: (a, b, c) = (11, 11, 10) = (A005578(5), a(5), A000975(4)). Then ((S-c), (S-b), (S-a)) = (6, 5, 5) = (A005578(4), a(4), A000975(3)). - Gary W. Adamson, Dec 24 2007
Sequence is identical to the absolute values of its inverse binomial transform. A similar result holds for [0,A001045*2^n]. - Paul Curtz, Jan 17 2008
From a(2) on (i.e., 1, 3, 5, 11, 21, ...) also: least odd number such that the subsets of {a(2), ..., a(n)} sum to 2^(n-1) different values, cf. A138000 and A064934. It is interesting to note the pattern of numbers occurring (or not occurring) as such a sum (A003158). - M. F. Hasler, Apr 09 2008
a(n) is the term (5, 1) of n-th power of the 5 X 5 matrix shown in A121231. - Gary W. Adamson, Oct 03 2008
A147612(a(n)) = 1. - Reinhard Zumkeller, Nov 08 2008
a(n+1) = Sum(A153778(i): 2^n <= i < 2^(n+1)). - Reinhard Zumkeller, Jan 01 2009
It appears that a(n) is also the number of integers between 2^n and 2^(n+1) that are divisible by 3 with no remainder. - John Fossaceca (john(AT)fossaceca.net), Jan 31 2009
Number of pairs of consecutive odious (or evil) numbers between 2^(n+1) and 2^(n+2), inclusive. - T. D. Noe, Feb 05 2009
Equals eigensequence of triangle A156319. - Gary W. Adamson, Feb 07 2009
A three-dimensional interpretation of a(n+1) is that it gives the number of ways of filling a 2 X 2 X n hole with 1 X 2 X 2 bricks. - Martin Griffiths, Mar 28 2009
Starting with offset 1 = INVERTi transform of A002605: (1, 2, 6, 16, 44, ...). - Gary W. Adamson, May 12 2009
Convolved with (1, 2, 2, 2, ...) = A000225: (1, 3, 7, 15, 31, ...). - Gary W. Adamson, May 23 2009
The product of a pair of successive terms is always a triangular number. - Giuseppe Ottonello, Jun 14 2009
Let A be the Hessenberg matrix of order n, defined by: A[1, j] = 1, A[i, i] := -2, A[i, i - 1] = -1, and A[i, j] = 0 otherwise. Then, for n >= 1, a(n) = (-1)^(n-1)*det(A). - Milan Janjic, Jan 26 2010
Let R denote the irreducible representation of the symmetric group S_3 of dimension 2, and let s and t denote respectively the sign and trivial irreducible representations of dimension 1. The decomposition of R^n into irreducible representations consists of a(n) copies of R and a(n-1) copies of each of s and t. - Andrew Rupinski, Mar 12 2010
As a fraction: 1/88 = 0.0113636363... or 1/9898 = 0.00010103051121... - Mark Dols, May 18 2010
Starting with "1" = the INVERT transform of (1, 0, 2, 0, 4, 0, 8, ...); e.g., a(7) = 43 = (1, 1, 1, 3, 5, 11, 21) dot (8, 0, 4, 0, 2, 0, 1) = (8 + 4 + 10 + 21) = 43. - Gary W. Adamson, Oct 28 2010
Rule 28 elementary cellular automaton (A266508) generates this sequence. - Paul Muljadi, Jan 27 2011
This is a divisibility sequence. - Michael Somos, Feb 06 2011
From L. Edson Jeffery, Apr 04 2011: (Start)
Let U be the unit-primitive matrix (see [Jeffery])
U = U_(6,2) =
(0 0 1)
(0 2 0)
(2 0 1).
Then a(n+1) = (Trace(U^n))/3, a(n+1) = ((U^n){3, 3})/3, a(n) = ((U^n){1, 3})/3 and a(n) = ((U^(n+1))_{1, 1})/2. (End)
The sequence emerges in using iterated deletion of strictly dominated strategies to establish the best-response solution to the Cournot duopoly problem as a strictly dominant strategy. The best response of firm 1 to firm 2's chosen quantity is given by q*1 = 1/2*(a - c - q_2), where a is reservation price, c is marginal cost, and q_2 is firm two's chosen quantity. Given that q_2 is in [o, a - c], q*_1 must be in [o, 1/2*(a - c)]. Since costs are symmetric, we know q_2 is in [0, 1/2*(a - c)]. Then we know q*_1 is in [1/4*(a - c), 1/2*(a - c)]. Continuing in this way, the sequence of bounds we get (factoring out a - c) is {1/2, 1/4, 3/8, 5/16, ...}; the numerators are the Jacobsthal numbers. - _Michael Chirico, Sep 10 2011
The compositions of n in which each natural number is colored by one of p different colors are called p-colored compositions of n. For n >= 2, 3*a(n-1) equals the number of 3-colored compositions of n with all parts greater than or equal to 2, such that no adjacent parts have the same color. - Milan Janjic, Nov 26 2011
This sequence is connected with the Collatz problem. We consider the array T(i, j) where the i-th row gives the parity trajectory of i, for example for i = 6, the infinite trajectory is 6 -> 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 -> 4 -> 2 -> 1 -> 4 -> 2 -> 1... and T(6, j) = [0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, ..., 1, 0, 0, 1, ...]. Now, we consider the sum of the digits "1" of each column. We obtain the sequence a(n) = Sum_{k = 1..2^n} T(k, n) = Sum {k = 1..2^n} digits "1" of the n-th column. Because a(n) + a(n+1) = 2^n, then a(n+1) = Number of digits "0" among the 2^n elements of the n-th column. - _Michel Lagneau, Jan 11 2012
3!*a(n-1) is apparently the trace of the n-th power of the adjacency matrix of the complete 3-graph, a 3 X 3 matrix with diagonal elements all zero and off-diagonal all ones. The off-diagonal elements for the n-th power are all equal to a(n) while each diagonal element seems to be a(n) + 1 for an even power and a(n) - 1 for an odd. These are related to the lengths of closed paths on the graph (see Delfino and Viti's paper). - Tom Copeland, Nov 06 2012
From Paul Curtz, Dec 11 2012: (Start)
2^n * a(-n) = (-1)^(n-1) * a(n), which extends the sequence to negative indices: ..., -5/16, 3/8, -1/4, 1/2, 0, 1, 1, 3, 5, ...
The "autosequence" property with respect to the binomial transform mentioned in my comment of Jan 17 2008 is still valid if the term a(-1) is added to the array of the sequence and its iterated higher-order differences in subsequent rows:
0 1/2 1/2 3/2 5/2 11/2 ...
1/2 0 1 1 3 5 ...
-1/2 1 0 2 2 6 ...
3/2 -1 2 0 4 4 ...
-5/2 3 -2 4 0 8 ...
11/2 -5 6 -4 8 0 ...
The main diagonal in this array contains 0's. (End)
Assign to a triangle T(n, 0) = 1 and T(n+1, 1) = n; T(r, c) = T(r-1, c-1) + T(r-1, c-2) + T(r-2, c-2). Then T(n+1, n) - T(n, n) = a(n). - J. M. Bergot, May 02 2013
a(n+1) counts clockwise walks on n points on a circle that take steps of length 1 and 2, return to the starting point after two full circuits, and do not duplicate any steps (USAMO 2013, problem 5). - Kiran S. Kedlaya, May 11 2013
Define an infinite square array m by m(n, 0) = m(0, n) = a(n) in top row and left column and m(i, j) = m(i, j-1) + m(i-1, j-1) otherwise, then m(n+1, n+1) = 3^(n-1). - J. M. Bergot, May 10 2013
a(n) is the number of compositions (ordered partitions) of n - 1 into one sort of 1's and two sorts of 2's. Example: the a(4) = 5 compositions of 3 are 1 + 1 + 1, 1 + 2, 1 + 2', 2 + 1 and 2' + 1. - Bob Selcoe, Jun 24 2013
Without 0, a(n)/2^n equals the probability that n will occur as a partial sum in a randomly-generated infinite sequence of 1's and 2's. The limiting ratio is 2/3. - Bob Selcoe, Jul 04 2013
Number of conjugacy classes of Z/2Z X Z/2Z in GL(2,2^(n+1)). - Jared Warner, Aug 18 2013
a(n) is the top left entry of the (n-1)-st power of the 3 X 3 matrix [1, 1, 1, 1, 0, 0, 1, 0, 0]. a(n) is the top left entry of the (n+1)-st power of any of the six 3 X 3 matrices [0, 1, 0; 1, 1, 1; 0, 1, 0], [0, 1, 1; 0, 1, 1; 1, 1, 0], [0, 0, 1; 1, 1, 1; 1, 1, 0], [0, 1, 1; 1, 0, 1; 0, 1, 1], [0, 0, 1; 0, 0, 1; 1, 1, 1] or [0, 1, 0; 1, 0, 1; 1, 1, 1]. - R. J. Mathar, Feb 03 2014
This is the only integer sequence from the family of homogeneous linear recurrence of order 2 given by a(n) = k*a(n-1) + t*a(n-2) with positive integer coefficients k and t and initial values a(0) = 0 and a(1) = 1 whose ratio a(n+1)/a(n) converges to 2 as n approaches infinity. - Felix P. Muga II, Mar 14 2014
This is the Lucas sequence U(1, -2). - Felix P. Muga II, Mar 21 2014
sqrt(a(n+1) * a(n-1)) -> a(n) + 3/4 if n is even, and -> a(n) - 3/4 if n is odd, for n >= 2. - Richard R. Forberg, Jun 24 2014
a(n+1) counts closed walks on the end vertices of P_3 containing one loop at the middle vertex. a(n-1) counts closed walks on the middle vertex of P_3 containing one loop at that vertex. - David Neil McGrath, Nov 07 2014
From César Eliud Lozada, Jan 21 2015: (Start)
Let P be a point in the plane of a triangle ABC (with sides a, b, c) and barycentric coordinates P = [x:y:z]. The Complement of P with respect to ABC is defined to be Complement(P) = [b*y + c*z : c*z + a*x : a*x + b*y].
Then, for n >= 1, Complement(Complement(...(Complement(P))..)) = (n times) =
[2*a(n-1)*a*x + (2*a(n-1) - (-1)^n)*(b*y + c*z):
2*a(n-1)*b*y + (2*a(n-1) - (-1)^n)*(c*z + a*x):
2*a(n-1)*c*z + (2*a(n-1) - (-1)^n)*(a*x + b*y)]. (End)
a(n) (n >= 2) is the number of induced hypercubes of the Fibonacci cube Gamma(n-2). See p. 513 of the Klavzar reference. Example: a(5) = 11. Indeed, the Fibonacci cube Gamma(3) is <>- (cycle C(4) with a pendant edge) and the hypercubes are: 5 vertices, 5 edges, and 1 square. - Emeric Deutsch, Apr 07 2016
If the sequence of points {P_i(x_i, y_i)} on the cubic y = a*x^3 + b*x^2 + c*x + d has the property that the segment P_i(x_i, y_i) P_i+1(x_i+1, y_i+1) is always tangent to the cubic at P_i+1(x_i+1, y_i+1) then a(n) = -2^n*a/b*(x_(n+1)-(-1/2)^n*x_1). - Michael Brozinsky, Aug 01 2016
With the quantum integers defined by [n+1]A000225%20are%20given%20by%20q%20=%20sqrt(2).%20Cf.%20A239473.%20-%20_Tom%20Copeland">q = (q^(n+1) - q^(-n-1)) / (q - q^(-1)), the Jacobsthal numbers are a(n+1) = (-1)^n*q^n [n+1]_q with q = i * sqrt(2) for i^2 = -1, whereas the signed Mersenne numbers A000225 are given by q = sqrt(2). Cf. A239473. - _Tom Copeland, Sep 05 2016
Every positive integer has a unique expression as a sum of Jacobsthal numbers in which the index of the smallest summand is odd, with a(1) and a(2) both allowed. See the L. Carlitz, R. Scoville, and V. E. Hoggatt, Jr. reference. - Ira M. Gessel, Dec 31 2016. See A280049 for these expansions. - N. J. A. Sloane, Dec 31 2016
For n > 0, a(n) equals the number of ternary words of length n-1 in which 0 and 1 avoid runs of odd lengths. - Milan Janjic, Jan 08 2017
For n > 0, a(n) equals the number of orbits of the finite group PSL(2,2^n) acting on subsets of size 4 for the 2^n+1 points of the projective line. - Paul M. Bradley, Jan 31 2017
For n > 1, number of words of length n-2 over alphabet {1,2,3} such that no odd letter is followed by an odd letter. - Armend Shabani, Feb 17 2017
Also, the decimal representation of the x-axis, from the origin to the right edge, of the n-th stage of growth of the two-dimensional cellular automaton defined by "Rule 678", based on the 5-celled von Neumann neighborhood, initialized with a single black (ON) cell at stage zero. See A283641. - Robert Price, Mar 12 2017
Also the number of independent vertex sets and vertex covers in the 2 X (n-2) king graph. - Eric W. Weisstein, Sep 21 2017
From César Eliud Lozada, Dec 14 2017: (Start)
Let T(0) be a triangle and let T(1) be the medial triangle of T(0), T(2) the medial triangle of T(1) and, in general, T(n) the medial triangle of T(n-1). The barycentric coordinates of the first vertex of T(n) are [2*a(n-1)/a(n), 1, 1], for n > 0.
Let S(0) be a triangle and let S(1) be the antimedial triangle of S(0), S(2) the antimedial triangle of S(1) and, in general, S(n) the antimedial triangle of S(n-1). The barycentric coordinates of the first vertex of S(n) are [-a(n+1)/a(n), 1, 1], for n > 0. (End)
a(n) is also the number of derangements in S_{n+1} with empty peak set. - Isabella Huang, Apr 01 2018
For n > 0, gcd(a(n), a(n+1)) = 1. - Kengbo Lu, Jul 27 2020
Number of 2-compositions of n+1 with 1 not allowed as a part; see Hopkins & Ouvry reference. - Brian Hopkins, Aug 17 2020
The number of Hamiltonian paths of the flower snark graph of even order 2n > 2 is 12*a(n-1). - Don Knuth, Dec 25 2020
When set S = {1, 2, ..., 2^n}, n>=0, then the largest subset T of S with the property that if x is in T, then 2*x is not in T, has a(n+1) elements. For example, for n = 4, #S = 16, a(5) = 11 with T = {1, 3, 4, 5, 7, 9, 11, 12, 13, 15, 16} (see Hassan Tarfaoui link, Concours Général 1991). - Bernard Schott, Feb 14 2022
a(n) is the number of words of length n over a binary alphabet whose position in the lexicographic order is one more than a multiple of three. a(3) = 3: aaa, abb, bba. - Alois P. Heinz, Apr 13 2022
Named by Horadam (1988) after the German mathematician Ernst Jacobsthal (1882-1965). - Amiram Eldar, Oct 02 2023
Define the sequence u(n) = (u(n-1) + u(n-2))/u(n-3) with u(0) = 0, u(1) = 1, u(2) = u(3) = -1. Then u(4*n) = -1 + (-1)^n/a(n+1), u(4*n+1) = 2 - (-1)^n/a(n+1), u(4*n+2) = u(4*n+3) = -1. For example, a(3) = 3 and u(8) = -2/3, u(9) = 5/3, u(10) = u(11) = -1. - Michael Somos, Oct 24 2023
From Miquel A. Fiol, May 25 2024: (Start)
Also, a(n) is the number of (3-color) states of a cycle (n+1)-pole C_{n+1} with n+1 terminals (or semiedges).
For instance, for n=3, the a(3)=3 states (3-coloring of the terminals) of C_4 are
a a a a a b
a a b b a b (End)
Also, with offset 1, the cogrowth sequence of the 6-element dihedral group D3. - Sean A. Irvine, Nov 04 2024

Examples

			a(2) = 3 because the tiling of the 3 X 2 rectangle has either only 1 X 1 tiles, or one 2 X 2 tile in one of two positions (together with two 1 X 1 tiles).
From _Joerg Arndt_, Nov 10 2012: (Start)
The a(6)=21 length-5 ternary words with no two consecutive letters nonzero are (dots for 0's)
[ 1]   [ . . . . ]
[ 2]   [ . . . 1 ]
[ 3]   [ . . . 2 ]
[ 4]   [ . . 1 . ]
[ 5]   [ . . 2 . ]
[ 6]   [ . 1 . . ]
[ 7]   [ . 1 . 1 ]
[ 8]   [ . 1 . 2 ]
[ 9]   [ . 2 . . ]
[10]   [ . 2 . 1 ]
[11]   [ . 2 . 2 ]
[12]   [ 1 . . . ]
[13]   [ 1 . . 1 ]
[14]   [ 1 . . 2 ]
[15]   [ 1 . 1 . ]
[16]   [ 1 . 2 . ]
[17]   [ 2 . . . ]
[18]   [ 2 . . 1 ]
[19]   [ 2 . . 2 ]
[20]   [ 2 . 1 . ]
[21]   [ 2 . 2 . ]
(End)
G.f. = x + x^2 + 3*x^3 + 5*x^4 + 11*x^5 + 21*x^6 + 43*x^7 + 85*x^8 + 171*x^9 + ...

References

  • Jathan Austin and Lisa Schneider, Generalized Fibonacci sequences in Pythagorean triple preserving sequences, Fib. Q., 58:1 (2020), 340-350.
  • Thomas Fink and Yong Mao, The 85 ways to tie a tie, Fourth Estate, London, 1999; Die 85 Methoden eine Krawatte zu binden. Hoffmann und Kampe, Hamburg, 1999.
  • International Mathematical Olympiad 2001, Hong Kong Preliminary Selection Contest Problem #16.
  • Jablan S. and Sazdanovic R., LinKnot: Knot Theory by Computer, World Scientific Press, 2007. See p. 80.
  • Ernst Erich Jacobsthal, Fibonaccische Polynome und Kreisteilungsgleichungen, Sitzungsber. Berliner Math. Gesell. 17 (1919-1920), 43-57.
  • Tanya Khovanova, "Coins and Logic", Chapter 6, The Mathematics of Various Entertaining Subjects: Volume 3 (2019), Jennifer Beineke & Jason Rosenhouse, eds. Princeton University Press, Princeton and Oxford, p. 73. ISBN: 0691182582, 978-0691182582.
  • Donald E. Knuth, Art of Computer Programming, Vol. 3, Sect. 5.3.1, Eq. 13.
  • Thomas Koshy, Fibonacci and Lucas numbers with applications, Wiley, 2001, p. 98.
  • Steven Roman, Introduction to Coding and Information Theory, Springer Verlag, 1996, 41-42.
  • P. D. Seymour and D. J. A. Welsh, Combinatorial applications of an inequality form statistical mechanics, Math. Proc. Camb. Phil. Soc. 77 (1975), 485-495. [Although Daykin et al. (1979) claim that the present sequence is studied in this article, it does not seem to be explicitly mentioned. Note that definition of log-convex in (3.1) is wrong. - N. J. A. Sloane, Dec 26 2020]
  • 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).
  • Robert M. Young, Excursions in Calculus, MAA, 1992, p. 239

Links

Crossrefs

Partial sums of this sequence give A000975, where there are additional comments from B. E. Williams and Bill Blewett on the tie problem.
A002487(a(n)) = A000045(n).
Row sums of A059260, A156667 and A134317. Equals A026644(n-2)+1 for n > 1.
a(n) = A073370(n-1, 0), n >= 1 (first column of triangle).
Cf. A266508 (binary), A081857 (base 4), A147612 (characteristic function).
Cf. A000978, A000979, A019322, A066845, A105348, A130249, A130250, A130253, A005578, A002083, A113405, A138000, A064934, A003158, A175286 (Pisano periods), A147613, A156319, A002605, A000225, A052129, A014551 (companion "autosequence"), A015266, A015287, A015305, A015323, A015338, A015356, A015371, A084175, A245489, A283641.
Cf. A049883 = primes in this sequence, A107036 = indices of primes, A129738.
Cf. A091084 (mod 10), A239473, A280049.
Bisections: A002450, A007583.
Cf. A077925 (signed version).

Programs

  • Haskell
    a001045 = (`div` 3) . (+ 1) . a000079
a001045_list = 0 : 1 :
   zipWith (+) (map (2 *) a001045_list) (tail a001045_list)
-- Reinhard Zumkeller, Mar 24 2013, Jan 05 2012, Feb 05 2011
  • Magma
    [n le 2 select n-1 else Self(n-1)+2*Self(n-2): n in [1..40]]; // Vincenzo Librandi, Jun 27 2016
  • Maple
    A001045 := proc(n)
  (2^n-(-1)^n)/3 ;
end proc: # R. J. Mathar, Dec 18 2012
  • Mathematica
    Jacob0[n_] := (2^n - (-1)^n)/3; Table[Jacob0[n], {n, 0, 33}] (* Robert G. Wilson v, Dec 05 2005 *)
Array[(2^# - (-1)^#)/3 &, 33, 0] (* Joseph Biberstine (jrbibers(AT)indiana.edu), Dec 26 2006 *)
LinearRecurrence[{1, 2}, {0, 1}, 40] (* Harvey P. Dale, Nov 30 2011 *)
CoefficientList[Series[x/(1 - x - 2 x^2), {x, 0, 34}], x] (* Robert G. Wilson v, Jul 21 2015 *)
Table[(2^n - (-1)^n)/3, {n, 0, 20}] (* Eric W. Weisstein, Sep 21 2017 *)
Table[Abs[QBinomial[n, 1, -2]], {n, 0, 35}] (* John Keith, Jan 29 2022 *)
  • Maxima
    a[0]:0$
a[n]:=2^(n-1)-a[n-1]$
A001045(n):=a[n]$
makelist(A001045(n),n,0,30); /* Martin Ettl, Nov 05 2012 */
  • PARI
    a(n) = (2^n - (-1)^n) / 3
  • PARI
    M=[1,1,0;1,0,1;0,1,1];for(i=0,34,print1((M^i)[2,1],",")) \\ Lambert Klasen (lambert.klasen(AT)gmx.net), Jan 28 2005
  • PARI
    a=0; for(n=0,34,print1(a,", "); a=2*(a-n%2)+1) \\ K. Spage, Aug 22 2014
  • Python
    # A001045.py
def A001045():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, b+2*a
sequence = A001045()
[next(sequence) for i in range(20)] # David Radcliffe, Jun 26 2016
  • Python
    [(2**n-(-1)**n)//3 for n in range(40)] # Gennady Eremin, Mar 03 2022
  • Sage
    [lucas_number1(n, 1, -2) for n in range(34)]  # Zerinvary Lajos, Apr 22 2009
# Alternatively:
a = BinaryRecurrenceSequence(1,2)
[a(n) for n in (0..34)] # Peter Luschny, Aug 29 2016

Formula

a(n) = 2^(n-1) - a(n-1). a(n) = 2*a(n-1) - (-1)^n = (2^n - (-1)^n)/3.
G.f.: x/(1 - x - 2*x^2) = x/((x+1)*(1-2*x)). Simon Plouffe in his 1992 dissertation
E.g.f.: (exp(2*x) - exp(-x))/3.
a(2*n) = 2*a(2*n-1)-1 for n >= 1, a(2*n+1) = 2*a(2*n)+1 for n >= 0. - Lee Hae-hwang, Oct 11 2002; corrected by Mario Catalani (mario.catalani(AT)unito.it), Dec 04 2002
Also a(n) is the coefficient of x^(n-1) in the bivariate Fibonacci polynomials F(n)(x, y) = x*F(n-1)(x, y) + y*F(n-2)(x, y), with y=2*x^2. - Mario Catalani (mario.catalani(AT)unito.it), Dec 04 2002
a(n) = Sum_{k=1..n} binomial(n, k)*(-1)^(n+k)*3^(k-1). - Paul Barry, Apr 02 2003
The ratios a(n)/2^(n-1) converge to 2/3 and every fraction after 1/2 is the arithmetic mean of the two preceding fractions. - Gary W. Adamson, Jul 05 2003
a(n) = U(n-1, i/(2*sqrt(2)))*(-i*sqrt(2))^(n-1) with i^2=-1. - Paul Barry, Nov 17 2003
a(n+1) = Sum_{k=0..ceiling(n/2)} 2^k*binomial(n-k, k). - Benoit Cloitre, Mar 06 2004
a(2*n) = A002450(n) = (4^n - 1)/3; a(2*n+1) = A007583(n) = (2^(2*n+1) + 1)/3. - Philippe Deléham, Mar 27 2004
a(n) = round(2^n/3) = (2^n + (-1)^(n-1))/3 so lim_{n->infinity} 2^n/a(n) = 3. - Gerald McGarvey, Jul 21 2004
a(n) = Sum_{k=0..n-1} (-1)^k*2^(n-k-1) = Sum_{k=0..n-1}, 2^k*(-1)^(n-k-1). - Paul Barry, Jul 30 2004
a(n+1) = Sum_{k=0..n} binomial(k, n-k)*2^(n-k). - Paul Barry, Oct 07 2004
a(n) = Sum_{k=0..n-1} W(n-k, k)*(-1)^(n-k)*binomial(2*k,k), W(n, k) as in A004070. - Paul Barry, Dec 17 2004
From Paul Barry, Jan 17 2005: (Start)
a(n) = Sum_{k=0..n} k*binomial(n-1, (n-k)/2)*(1+(-1)^(n+k))*floor((2*k+1)/3).
a(n+1) = Sum_{k=0..n} k*binomial(n-1, (n-k)/2)*(1+(-1)^(n+k))*(A042965(k)+0^k). (End)
From Paul Barry, Jan 17 2005: (Start)
a(n+1) = ceiling(2^n/3) + floor(2^n/3) = (ceiling(2^n/3))^2 - (floor(2^n/3))^2.
a(n+1) = A005578(n) + A000975(n-1) = A005578(n)^2 - A000975(n-1)^2. (End)
a(n+1) = Sum_{k=0..n} Sum_{j=0..n} (-1)^(n-j)*binomial(j, k). - Paul Barry, Jan 26 2005
Let M = [1, 1, 0; 1, 0, 1; 0, 1, 1], then a(n) = (M^n)[2, 1], also matrix characteristic polynomial x^3 - 2*x^2 - x + 2 defines the three-step recursion a(0)=0, a(1)=1, a(2)=1, a(n) = 2*a(n-1) + a(n-2) - 2*a(n-3) for n > 2. - Lambert Klasen (lambert.klasen(AT)gmx.net), Jan 28 2005
a(n) = ceiling(2^(n+1)/3) - ceiling(2^n/3) = A005578(n+1) - A005578(n). - Paul Barry, Oct 08 2005
a(n) = floor(2^(n+1)/3) - floor(2^n/3) = A000975(n) - A000975(n-1). - Paul Barry, Oct 08 2005
From Paul Barry, Feb 20 2003: (Start)
a(n) = Sum_{k=0..floor(n/3)} binomial(n, f(n-1)+3*k);
a(n) = Sum_{k=0..floor(n/3)} binomial(n, f(n-2)+3*k), where f(n)=A080425(n). (End)
From Miklos Kristof, Mar 07 2007: (Start)
a(2*n) = (1/3)*Product_{d|n} cyclotomic(d,4).
a(2*n+1) = (1/3)*Product_{d|2*n+1} cyclotomic(2*d,2). (End)
From Hieronymus Fischer, Apr 23 2007: (Start)
The a(n) are closely related to nested square roots; this is 2*sin(2^(-n)*Pi/2*a(n)) = sqrt(2-sqrt(2-sqrt(2-sqrt(...sqrt(2)))...) {with the '2' n times, n >= 0}.
Also 2*cos(2^(-n)*Pi*a(n)) = sqrt(2-sqrt(2-sqrt(2-sqrt(...sqrt(2)))...) {with the '2' n-1 times, n >= 1} as well as
2*sin(2^(-n)*3/2*Pi*a(n)) = sqrt(2+sqrt(2+sqrt(2+sqrt(...sqrt(2)))...) {with the '2' n times, n >= 0} and
2*cos(2^(-n)*3*Pi*a(n)) = -sqrt(2+sqrt(2+sqrt(2+sqrt(...sqrt(2)))...) {with the '2' n-1 times, n >= 1}.
a(n) = 2^(n+1)/Pi*arcsin(b(n+1)/2) where b(n) is defined recursively by b(0)=2, b(n)=sqrt(2-b(n-1)).
There is a similar formula regarding the arccos function, this is a(n) = 2^n/Pi*arccos(b(n)/2).
With respect to the sequence c(n) defined recursively by c(0)=-2, c(n)=sqrt(2+c(n-1)), the following formulas hold true: a(n) = 2^n/3*(1-(-1)^n*(1-2/Pi*arcsin(c(n+1)/2))); a(n) = 2^n/3*(1-(-1)^n*(1-1/Pi*arccos(-c(n)/2))).
(End)
Sum_{k=0..n} A039599(n,k)*a(k) = A049027(n), for n >= 1. - Philippe Deléham, Jun 10 2007
Sum_{k=0..n} A039599(n,k)*a(k+1) = A067336(n). - Philippe Deléham, Jun 10 2007
Let T = the 3 X 3 matrix [1,1,0; 1,0,1; 0,1,1]. Then T^n * [1,0,0,] = [A005578(n), a(n), A000975(n-1)]. - Gary W. Adamson, Dec 24 2007
a(n) + a(n+5) = 11*2^n. - Paul Curtz, Jan 17 2008
a(n) = Sum_{k=1..n} K(2, k)*a(n - k), where K(n,k) = k if 0 <= k <= n and K(n,k)=0 otherwise. (When using such a K-coefficient, several different arguments to K or several different definitions of K may lead to the same integer sequence. For example, the Fibonacci sequence can be generated in several ways using the K-coefficient.) - Thomas Wieder, Jan 13 2008
a(n) + a(n+2*k+1) = a(2*k+1)*2^n. - Paul Curtz, Feb 12 2008
a(n) = lower left term in the 2 X 2 matrix [0,2; 1,1]^n. - Gary W. Adamson, Mar 02 2008
a(n+1) = Sum_{k=0..n} A109466(n,k)*(-2)^(n-k). -Philippe Deléham, Oct 26 2008
a(n) = sqrt(8*a(n-1)*a(n-2) + 1). E.g., sqrt(3*5*8+1) = 11, sqrt(5*11*8+1) = 21. - Giuseppe Ottonello, Jun 14 2009
Let p[i] = Fibonacci(i-1) and let A be the Hessenberg matrix of order n defined by: A[i,j] = p[j-i+1], (i <= j), A[i,j] = -1, (i = j+1), and A[i,j] = 0 otherwise. Then, for n >= 1, a(n-1) = det(A). - Milan Janjic, May 08 2010
a(p-1) = p*A007663(n)/3 if n > 1, and a(p-1) = p*A096060(n) if n > 2, with p=prime(n). - Jonathan Sondow, Jul 19 2010
Algebraically equivalent to replacing the 5's with 9's in the explicit (Binet) formula for the n-th term in the Fibonacci sequence: The formula for the n-th term in the Fibonacci sequence is F(n) = ((1+sqrt(5))^n - (1-sqrt(5))^n)/(2^n*sqrt(5)). Replacing the 5's with 9's gives ((1+sqrt(9))^n - (1-sqrt(9))^n)/(2^n*sqrt(9)) = (2^n+(-1)^(n+1))/3 = (2^n-(-1)^(n))/3 = a(n). - Jeffrey R. Goodwin, May 27 2011
For n > 1, a(n) = A000975(n-1) + (1 + (-1)^(n-1))/2. - Vladimir Shevelev, Feb 27 2012
From Sergei N. Gladkovskii, Jun 12 2012: (Start)
G.f.: x/(1-x-2*x^2) = G(0)/3; G(k) = 1 - ((-1)^k)/(2^k - 2*x*4^k/(2*x*2^k - ((-1)^k)/G(k+1))); (continued fraction 3 kind, 3-step).
E.g.f.: G(0)/3; G(k) = 1 - ((-1)^k)/(2^k - 2*x*4^k/(2*x*2^k - ((-1)^k)*(k+1)/G(k+1))); (continued fraction 3rd kind, 3-step). (End)
a(n) = 2^k * a(n-k) + (-1)^(n+k)*a(k). - Paul Curtz, Jean-François Alcover, Dec 11 2012
a(n) = sqrt((A014551(n))^2 + (-1)^(n-1)*2^(n+2))/3. - Vladimir Shevelev, Mar 13 2013
G.f.: Q(0)/3, where Q(k) = 1 - 1/(4^k - 2*x*16^k/(2*x*4^k - 1/(1 + 1/(2*4^k - 8*x*16^k/(4*x*4^k + 1/Q(k+1)))))); (continued fraction). - Sergei N. Gladkovskii, May 21 2013
G.f.: Q(0)*x/2, where Q(k) = 1 + 1/(1 - x*(2*k+1 + 2*x)/( x*(2*k+2 + 2*x) + 1/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 29 2013
G.f.: Q(0) -1, where Q(k) = 1 + 2*x^2 + (k+2)*x - x*(k+1 + 2*x)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Oct 06 2013
a(n+2) = Sum_{k=0..n} A108561(n,k)*(-2)^k. - Philippe Deléham, Nov 17 2013
a(n) = (Sum_{k=1..n, k odd} C(n,k)*3^(k-1))/2^(n-1). - Vladimir Shevelev, Feb 05 2014
a(-n) = -(-1)^n * a(n) / 2^n for all n in Z. - Michael Somos, Mar 18 2014
a(n) = (-1)^(n-1)*Sum_{k=0..n-1} A135278(n-1,k)*(-3)^k = (2^n - (-1)^n)/3 = (-1)^(n-1)*Sum_{k=0..n-1} (-2)^k. Equals (-1)^(n-1)*Phi(n,-2), where Phi is the cyclotomic polynomial when n is an odd prime. (For n > 0.) - Tom Copeland, Apr 14 2014
From Peter Bala, Apr 06 2015: (Start)
a(2*n)/a(n) = A014551(n) for n >= 1; a(3*n)/a(n) = 3*A245489(n) for n >= 1.
exp( Sum_{n >= 1} a(2*n)/a(n)*x^n/n ) = Sum_{n >= 0} a(n+1)*x^n.
exp( Sum_{n >= 1} a(3*n)/a(n)*x^n/n ) = Sum_{n >= 0} A084175(n+1)*x^n.
exp( Sum_{n >= 1} a(4*n)/a(n)*x^n/n ) = Sum_{n >= 0} A015266(n+3)*(-x)^n.
exp( Sum_{n >= 1} a(5*n)/a(n)*x^n/n ) = Sum_{n >= 0} A015287(n+4)*x^n.
exp( Sum_{n >= 1} a(6*n)/a(n)*x^n/n ) = Sum_{n >= 0} A015305(n+5)*(-x)^n.
exp( Sum_{n >= 1} a(7*n)/a(n)*x^n/n ) = Sum_{n >= 0} A015323(n+6)*x^n.
exp( Sum_{n >= 1} a(8*n)/a(n)*x^n/n ) = Sum_{n >= 0} A015338(n+7)*(-x)^n.
exp( Sum_{n >= 1} a(9*n)/a(n)*x^n/n ) = Sum_{n >= 0} A015356(n+8)*x^n.
exp( Sum_{n >= 1} a(10*n)/a(n)*x^n/n ) = Sum_{n >= 0} A015371(n+9)*(-x)^n. (End)
a(n) = (1-(-1)^n)/2 + floor((2^n)/3). - Reiner Moewald, Jun 05 2015
a(n+k)^2 - A014551(k)*a(n)*a(n+k) + (-2)^k*a(n)^2 = (-2)^n*a(k)^2, for n >= 0 and k >= 0. - Alexander Samokrutov, Jul 21 2015
Dirichlet g.f.: (PolyLog(s,2) + (1 - 2^(1-s))*zeta(s))/3. - Ilya Gutkovskiy, Jun 27 2016
From Yuchun Ji, Apr 08 2018: (Start)
a(m)*a(n) + a(m-1)*a(n-1) - 2*a(m-2)*a(n-2) = 2^(m+n-3).
a(m+n-1) = a(m)*a(n) + 2*a(m-1)*a(n-1); a(m+n) = a(m+1)*a(n+1) - 4*a(m-1)*a(n-1).
a(2*n-1) = a(n)^2 + 2*a(n-1)^2; a(2*n) = a(n+1)^2 - 4*a(n-1)^2. (End)
a(n+4) = a(n) + 5*2^n, a(0) = 0, a(1..4) = [1,1,3,5]. That is to say, for n > 0, the ones digits of Jacobsthal numbers follow the pattern 1,1,3,5,1,1,3,5,1,1,3,5,.... - Yuchun Ji, Apr 25 2019
a(n) mod 10 = A091084(n). - Alois P. Heinz, Apr 25 2019
The sequence starting with "1" is the second INVERT transform of (1, -1, 3, -5, 11, -21, 43, ...). - Gary W. Adamson, Jul 08 2019
From Kai Wang, Jan 14 2020: (Start)
a(n)^2 - a(n+1)*a(n-1) = (-2)^(n-1).
a(n)^2 - a(n+r)*a(n-r) = (-2)^(n-r)*a(r)^2.
a(m)*a(n+1) - a(m+1)*a(n) = (-2)^n*a(m-n).
a(m-n) = (-1)^n*(a(m)*A014551(n) - A014551(m)*a(n))/(2^(n+1)).
a(m+n) = (a(m)*A014551(n) + A014551(m)*a(n))/2.
A014551(n)^2 - A014551(n+r)*A014551(n-r) = 9*(-1)^(n-r-1)*2^(n-r)*a(r)^2 .
A014551(m)*A014551(n+1) - A014551(m+1)*A014551(n) = 9*(-1)^(n-1)*2^(n)*a(m-n).
A014551(m-n) = (-1)^(n)*(A014551(m)*A014551(n) - 9*a(m)*a(n))/2^(n+1).
A014551(m+n) = (A014551(m)*A014551(n) + 9*a(m)*a(n))/2.
a(n) = Sum_{i=0..n-1; j=0..n-1; i+2*j=n-1} 2^j*((i+j)!/(i!*j!)). (End)
For n > 0, 1/(2*a(n+1)) = Sum_{m>=n} a(m)/(a(m+1)*a(m+2)). - Kai Wang, Mar 03 2020
For 4 > h >= 0, k >= 0, a(4*k+h) mod 5 = a(h) mod 5. - Kai Wang, May 07 2020
From Kengbo Lu, Jul 27 2020: (Start)
a(n) = 1 + Sum_{k=0..n-1} a(k) if n odd; a(n) = Sum_{k=0..n-1} a(k) if n even.
a(n) = F(n) + Sum_{k=0..n-2} a(k)*F(n-k-1), where F denotes the Fibonacci numbers.
a(n) = b(n) + Sum_{k=0..n-1} a(k)*b(n-k), where b(n) is defined through b(0) = 0, b(1) = 1, b(n) = 2*b(n-2).
a(n) = 1 + 2*Sum_{k=0..n-2} a(k).
a(m+n) = a(m)*a(n+1) + 2*a(m-1)*a(n).
a(2*n) = Sum_{i>=0, j>=0} binomial(n-j-1,i)*binomial(n-i-1,j)*2^(i+j). (End)
G.f.: x/(1 - x - 2*x^2) = Sum_{n >= 0} x^(n+1) * Product_{k = 1..n} (k + 2*x)/(1 + k*x) (a telescoping series). - Peter Bala, May 08 2024
a(n) = Sum_{r>=0} F(n-2r, r), where F(n, 0) is the n-th Fibonacci number and F(n,r) = Sum_{j=1..n} F(n+1-j, r-1) F(j, r-1). - Gregory L. Simay, Aug 31 2024
From Peter Bala, Jun 27 2025: (Start)
The following are all examples of telescoping infinite products:
Product_{n >= 1} (1 + 2^n/a(2*n+2)) = 2, since 1 + 2^n/a(2*n+2) = b(n+1)/b(n), where b(n) = 2 - 3/(2^n + 1).
Product_{n >= 1} (1 - 2^n/a(2*n+2)) = 2/5, since 1 - 2^n/a(2*n+2) = c(n+1)/c(n), where c(n) = 2 + 3/(2^n - 1).
Product_{n >= 1} (1 + (-2)^n/a(2*n+2)) = 2/3, since 1 + (-2)^n/a(2*n+2) = d(n+1)/d(n), where d(n) = 2 - 1/(1 + (-2)^n).
Product_{n >= 1} (1 - (-2)^n/a(2*n+2)) = 6/5, since 1 - (-2)^n/a(2*n+2) = e(n+1)/e(n), where e(n) = 2 - 1/(1 - (-2)^n). (End)

Extensions

Thanks to Don Knuth, who pointed out several missing references, including Brocard (1880), which although it was mentioned in the 1973 Handbook of Integer Sequences, was omitted from the 1995 "Encyclopedia". - N. J. A. Sloane, Dec 26 2020

A059260 Triangle read by rows giving coefficient T(i,j) of x^i y^j in 1/(1-y-x*y-x^2) = 1/((1+x)(1-x-y)) for (i,j) = (0,0), (1,0), (0,1), (2,0), (1,1), (0,2), ...

Original entry on oeis.org

1, 0, 1, 1, 1, 1, 0, 2, 2, 1, 1, 2, 4, 3, 1, 0, 3, 6, 7, 4, 1, 1, 3, 9, 13, 11, 5, 1, 0, 4, 12, 22, 24, 16, 6, 1, 1, 4, 16, 34, 46, 40, 22, 7, 1, 0, 5, 20, 50, 80, 86, 62, 29, 8, 1, 1, 5, 25, 70, 130, 166, 148, 91, 37, 9, 1, 0, 6, 30, 95, 200, 296, 314, 239, 128, 46, 10, 1
Offset: 0

Views

Author

N. J. A. Sloane, Jan 23 2001

Keywords

Comments

Coefficients of the (left, normalized) shifted cyclotomic polynomial. Or, coefficients of the basic n-th q-series for q=-2. Indeed, let Y_n(x) = Sum_{k=0..n} x^k, having as roots all the n-th roots of unity except for 0; then coefficients in x of (-1)^n Y_n(-x-1) give exactly the n-th row of A059260 and a practical way to compute it. - Olivier Gérard, Jul 30 2002
The maximum in the (2n)-th row is T(n,n), which is A026641; also T(n,n) ~ (2/3)*binomial(2n,n). The maximum in the (2n-1)-th row is T(n-1,n), which is A014300 (but T does not have the same definition as in A026637); also T(n-1,n) ~ (1/3)*binomial(2n,n). Here is a generalization of the formula given in A026641: T(i,j) = Sum_{k=0..j} binomial(i+k-x,j-k)*binomial(j-k+x,k) for all x real (the proof is easy by induction on i+j using T(i,j) = T(i-1,j) + T(i,j-1)). - Claude Morin, May 21 2002
The second greatest term in the (2n)-th row is T(n-1,n+1), which is A014301; the second greatest term in the (2n+1)-th row is T(n+1,n) = 2*T(n-1,n+1), which is 2*A014301. - Claude Morin
Diagonal sums give A008346. - Paul Barry, Sep 23 2004
Riordan array (1/(1-x^2), x/(1-x)). As a product of Riordan arrays, factors into the product of (1/(1+x),x) and (1/(1-x),1/(1-x)) (binomial matrix). - Paul Barry, Oct 25 2004
Signed version is A239473 with relations to partial sums of sequences. - Tom Copeland, Mar 24 2014
From Robert Coquereaux, Oct 01 2014: (Start)
Columns of the triangle (cf. Example below) give alternate partial sums along nw-se diagonals of the Pascal triangle, i.e., sequences A000035, A004526, A002620 (or A087811), A002623 (or A173196), A001752, A001753, A001769, A001779, A001780, A001781, A001786, A001808, etc.
The dimension of the space of closed currents (distributional forms) of degree p on Gr(n), the Grassmann algebra with n generators, equivalently, the dimension of the space of Gr(n)-valued symmetric multilinear forms with vanishing graded divergence, is V(n,p) = 2^n T(p,n-1) - (-1)^p.
If p is odd V(n,p) is also the dimension of the cyclic cohomology group of order p of the Z2 graded algebra Gr(n).
If p is even the dimension of this cohomology group is V(n,p)+1.
Cf. A193844. (End)
From Peter Bala, Feb 07 2024: (Start)
The following remarks assume the row indexing starts at n = 1.
The sequence of row polynomials R(n,x), beginning R(1,x) = 1, R(2,x) = x, R(3,x) = 1 + x + x^2 , ..., is a strong divisibility sequence of polynomials in the ring Z[x]; that is, for all positive integers n and m, poly_gcd( R(n,x), R(m,x)) = R(gcd(n, m), x) - apply Norfleet (2005), Theorem 3. Consequently, the polynomial sequence {R(n,x): n >= 1} is a divisibility sequence; that is, if n divides m then R(n,x) divides R(m,x) in Z[x]. (End)
From Miquel A. Fiol, Oct 04 2024: (Start)
For j>=1, T(i,j) is the independence number of the (i-j)-supertoken graph FF_(i-j)(S_j) of the star graph S_j with j points.
(Given a graph G on n vertices and an integer k>=1, the k-supertoken (or reduced k-th power) FF_k(G) of G has vertices representing configurations of k indistinguishable tokens in the (not necessarily different) vertices of G, with two configurations being adjacent if one can be obtained from the other by moving one token along an edge. See an example below.)
Following the suggestion of Peter Munn, the k-supertoken graph FF_k(S_j) can also be defined as follows: Consider the Lattice graph L(k,j), whose vertices are the k^j j-vectors with elements in the set {0,..,k-1}, two being adjacent if they differ in just one coordinate by one unity. Then, FF_k(S_j) is the subgraph of L(k+1,j) induced by the vertices at distance at most k from (0,..,0). (End)

Examples

			Triangle begins
  1;
  0,  1;
  1,  1,  1;
  0,  2,  2,  1;
  1,  2,  4,  3,  1;
  0,  3,  6,  7,  4,  1;
  1,  3,  9, 13, 11,  5,  1;
  0,  4, 12, 22, 24, 16,  6,  1;
  1,  4, 16, 34, 46, 40, 22,  7,  1;
  0,  5, 20, 50, 80, 86, 62, 29,  8,  1;
Sequences obtained with _Miquel A. Fiol_'s Sep 30 2024 formula of A(n,c1,c2) for other values of (c1,c2). (In the table, rows are indexed by c1=0..6 and columns by c2=0..6):
A000007  A000012  A000027  A025747  A000292* A000332* A000389*
A059841  A008619  A087811* A002623  A001752  A001753  A001769
A193356  A008794* A005993  A005994  -------  -------  -------
-------  -------  -------  A005995  A018210  -------  A052267
-------  -------  -------  -------  A018211  A018212  -------
-------  -------  -------  -------  -------  A018213  A018214
-------  -------  -------  -------  -------  -------  A062136
*requires offset adjustment.
The 2-supertoken FF_2(S_3) of the star graph S_3 with central vertex 1 and peripheral vertices 2,3,4. (The vertex `ij' of FF_2(S_3) represents the configuration of one token in `ì' and the other token in `j'). The T(5,3)=7 independent vertices are 22, 24, 44, 23, 11, 34, and 33.
     22--12---24---14---44
          | \    / |
         23   11   34
            \  |  /
              13
               |
              33

Links

Crossrefs

Cf. A059259. Row sums give A001045.
Seen as a square array read by antidiagonals this is the coefficient of x^k in expansion of 1/((1-x^2)*(1-x)^n) with rows A002620, A002623, A001752, A001753, A001769, A001779, A001780, A001781, A001786, A001808 etc. (allowing for signs). A058393 would then effectively provide the table for nonpositive n. - Henry Bottomley, Jun 25 2001
Cf. A026641, A014300.
Cf. A007318, A097805, A097808, A130595, A200139, A062135.

Programs

  • Maple
    read transforms; 1/(1-y-x*y-x^2); SERIES2(%,x,y,12); SERIES2TOLIST(%,x,y,12);
  • Mathematica
    t[n_, k_] := Sum[ (-1)^(n-j)*Binomial[j, k], {j, 0, n}]; Flatten[ Table[t[n, k], {n, 0, 12}, {k, 0, n}]] (* Jean-François Alcover, Oct 20 2011, after Paul Barry *)
  • PARI
    T(n, k) = sum(j=0, n, (-1)^(n - j)*binomial(j, k));
for(n=0, 12, for(k=0, n, print1(T(n, k),", ");); print();) \\ Indranil Ghosh, Apr 11 2017
  • Python
    from sympy import binomial
def T(n, k): return sum((-1)**(n - j)*binomial(j, k) for j in range(n + 1))
for n in range(13): print([T(n, k) for k in range(n + 1)]) # Indranil Ghosh, Apr 11 2017
  • Sage
    def A059260_row(n):
    @cached_function
    def prec(n, k):
        if k==n: return 1
        if k==0: return 0
        return -prec(n-1,k-1)-sum(prec(n,k+i-1) for i in (2..n-k+1))
    return [(-1)^(n-k+1)*prec(n+1, n-k+1) for k in (1..n)]
for n in (1..9): print(A059260_row(n)) # Peter Luschny, Mar 16 2016

Formula

G.f.: 1/(1-y-x*y-x^2) = 1 + y + x^2 + xy + y^2 + 2x^2y + 2xy^2 + y^3 + ...
E.g.f: (exp(-t)+(x+1)*exp((x+1)*t))/(x+2). - Tom Copeland, Mar 19 2014
O.g.f. (n-th row): ((-1)^n+(x+1)^(n+1))/(x+2). - Tom Copeland, Mar 19 2014
T(i, 0) = 1 if i is even or 0 if i is odd, T(0, i) = 1 and otherwise T(i, j) = T(i-1, j) + T(i, j-1); also T(i, j) = Sum_{m=j..i+j} (-1)^(i+j+m)*binomial(m, j). - Robert FERREOL, May 17 2002
T(i, j) ~ (i+j)/(2*i+j)*binomial(i+j, j); more precisely, abs(T(i, j)/binomial(i+j, j) - (i+j)/(2*i+j) )<=1/(4*(i+j)-2); the proof is by induction on i+j using the formula 2*T(i, j) = binomial(i+j, j)+T(i, j-1). - Claude Morin, May 21 2002
T(n, k) = Sum_{j=0..n} (-1)^(n-j)binomial(j, k). - Paul Barry, Aug 25 2004
T(n, k) = Sum_{j=0..n-k} binomial(n-j, j)*binomial(j, n-k-j). - Paul Barry, Jul 25 2005
Equals A097807 * A007318. - Gary W. Adamson, Feb 21 2007
Equals A128173 * A007318 as infinite lower triangular matrices. - Gary W. Adamson, Feb 17 2007
Equals A130595*A097805*A007318 = (inverse Pascal matrix)*(padded Pascal matrix)*(Pascal matrix) = A130595*A200139. Inverse is A097808 = A130595*(padded A130595)*A007318. - Tom Copeland, Nov 14 2016
T(i, j) = binomial(i+j, j)-T(i-1, j). - Laszlo Major, Apr 11 2017
Recurrence for row polynomials (with row indexing starting at n = 1): R(n,x) = x*R(n-1,x) + (x + 1)*R(n-2,x) with R(1,x) = 1 and R(2,x) = x. - Peter Bala, Feb 07 2024
From Miquel A. Fiol, Sep 30 2024: (Start)
The triangle can be seen as a slice of a 3-dimensional table that links it to well-known sequences as follows.
The j-th column of the triangle, T(i,j) for i >= j, equals A(n,c1,c2) = Sum_{k=0..floor(n/2)} binomial(c1+2*k-1,2*k)*binomial(c2+n-2*k-1,n-2*k) when c1=1, c2=j, and n=i-j.
This gives T(i,j) = Sum_{k=0..floor((i-j)/2)} binomial(i-2*k-1, j-1). For other values of (c1,c2), see the example below. (End)

Extensions

Formula corrected by Philippe Deléham, Jan 11 2014

A317532 Regular triangle read by rows: T(n,k) is the number of multiset partitions of normal multisets of size n into k blocks, where a multiset is normal if it spans an initial interval of positive integers.

Original entry on oeis.org

1, 2, 2, 4, 8, 4, 8, 34, 26, 8, 16, 124, 168, 76, 16, 32, 448, 962, 674, 208, 32, 64, 1568, 5224, 5344, 2392, 544, 64, 128, 5448, 27336, 39834, 24578, 7816, 1376, 128, 256, 18768, 139712, 283864, 236192, 99832, 24048, 3392, 256, 512, 64448, 702496, 1960320, 2161602, 1186866, 370976, 70656, 8192, 512
Offset: 1

Views

Author

Gus Wiseman, Jul 30 2018

Keywords

Examples

			The T(3,2) = 8 multiset partitions:
  {{1},{1,1}}
  {{1},{2,2}}
  {{2},{1,2}}
  {{1},{1,2}}
  {{2},{1,1}}
  {{1},{2,3}}
  {{2},{1,3}}
  {{3},{1,2}}
Triangle begins:
    1
    2    2
    4    8    4
    8   34   26    8
   16  124  168   76   16
   32  448  962  674  208   32
  ...

Links

Crossrefs

Row sums are A255906.
Cf. A007716, A034691, A255397, A255903.

Programs

  • Mathematica
    sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
allnorm[n_]:=Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1];
Table[Length[Select[Join@@mps/@allnorm[n],Length[#]==k&]],{n,7},{k,n}]
  • PARI
    \\ here B(n,k) is A239473(n,k).
B(n,k)={sum(r=k, n, binomial(r, k)*(-1)^(r-k))}
Row(n)={Vecrev(sum(j=1, n, B(n,j)*polcoef(1/prod(k=1, n, (1 - x^k*y + O(x*x^n))^binomial(k+j-1,j-1)), n))/y)}
{ for(n=1, 10, print(Row(n))) } \\ Andrew Howroyd, Dec 31 2019

Extensions

Terms a(29) and beyond from Andrew Howroyd, Dec 31 2019

A118800 Triangle read by rows: T satisfies the matrix products: C*T*C = T^-1 and T*C*T = C^-1, where C is Pascal's triangle.

Original entry on oeis.org

1, 1, -1, 2, -3, 1, 4, -8, 5, -1, 8, -20, 18, -7, 1, 16, -48, 56, -32, 9, -1, 32, -112, 160, -120, 50, -11, 1, 64, -256, 432, -400, 220, -72, 13, -1, 128, -576, 1120, -1232, 840, -364, 98, -15, 1, 256, -1280, 2816, -3584, 2912, -1568, 560, -128, 17, -1, 512, -2816, 6912, -9984, 9408, -6048, 2688, -816, 162, -19, 1
Offset: 0

Views

Author

Paul D. Hanna, May 02 2006

Keywords

Comments

The matrix square, T^2, consists of columns that are all the same.
Matrix inverse is triangle A118801. Row sums form {0^n, n>=0}.
Unsigned row sums equal A025192(n) = 2*3^(n-1), n>=1.
Row squared sums equal A051708.
Antidiagonal sums equals all 1's.
Unsigned antidiagonal sums form A078057 (with offset).
Antidiagonal squared sums form A002002(n) = Sum_{k=0..n-1} C(n,k+1)*C(n+k,k), n>=1.
From Paul Barry, Nov 10 2008: (Start)
T is [1,1,0,0,0,...] DELTA [ -1,0,0,0,0,...] or C(1,n) DELTA -C(0,n). (DELTA defined in A084938).
The positive matrix T_p is [1,1,0,0,0,...] DELTA [1,0,0,0,0,...]. T_p*C^-1 is
[0,1,0,0,0,....] DELTA [1,0,0,0,0,...] which is C(n-1,k-1) for n,k>=1. (End)
The triangle formed by deleting the minus signs is the mirror of the self-fusion of Pascal's triangle; see Comments at A081277 and A193722. - Clark Kimberling, Aug 04 2011
Riordan array ( (1 - x)/(1 - 2*x), -x/(1 - 2*x) ). Cf. A209149. The matrix square is the Riordan array ( (1 - x)^2/(1 - 2*x), x ), which belongs to the Appell subgroup of the Riordan group. See the Example section below. - Peter Bala, Jul 17 2013
From Peter Bala, Feb 23 2019: (Start)
There is a 1-parameter family of solutions to the simultaneous equations C*T*C = T^-1 and T*C*T = C^-1, where C is Pascal's triangle. Let T(k) denote the Riordan array ( (1 - k*x)/(1 - (k + 1)*x), -x/(1 - (k + 1)*x) ) so that T(1) = T. Then C*T(k)*C = T(k)^-1 and T(k)*C*T(k) = C^-1, for arbitrary k. For arbitrary m, the Riordan arrays (T(k)*C^m)^2 and (C^m*T(k))^2 both belong to the Appell subgroup of the Riordan group.
More generally, given a fixed m, we can ask for a lower triangular array X solving the simultaneous equations (C^m)*X*(C^m) = X^-1 and X*(C^m)*X = C^(-m). A 1-parameter family of solutions is given by the Riordan arrays X = ( (1 - m*k*x)/(1 - m*(k + 1)*x), -x/(1 - m*(k + 1)*x) ). The Riordan arrays X^2 , (X*C^n)^2 and (C^n*X)^2, for arbitrary n, all belong to the Appell subgroup of the Riordan group. (End)

Examples

			Triangle begins:
     1;
     1,    -1;
     2,    -3,     1;
     4,    -8,     5,     -1;
     8,   -20,    18,     -7,     1;
    16,   -48,    56,    -32,     9,     -1;
    32,  -112,   160,   -120,    50,    -11,     1;
    64,  -256,   432,   -400,   220,    -72,    13,    -1;
   128,  -576,  1120,  -1232,   840,   -364,    98,   -15,    1;
   256, -1280,  2816,  -3584,  2912,  -1568,   560,  -128,   17,   -1;
   512, -2816,  6912,  -9984,  9408,  -6048,  2688,  -816,  162,  -19,  1;
  1024, -6144, 16640, -26880, 28800, -21504, 11424, -4320, 1140, -200, 21, -1;
  ...
The matrix square, T^2, equals:
   1;
   0,  1;
   1,  0,  1;
   2,  1,  0,  1;
   4,  2,  1,  0,  1;
   8,  4,  2,  1,  0,  1;
  16,  8,  4,  2,  1,  0,  1;
  32, 16,  8,  4,  2,  1,  0,  1;
  64, 32, 16,  8,  4,  2,  1,  0,  1; ...
where all columns are the same.

Links

Crossrefs

Cf. A118801 (inverse), A025192 (unsigned row sums), A051708 (row squared sums), A078057 (unsigned antidiagonal sums), A002002 (antidiagonal squared sums).
Cf. A135387, A209149, A000012, A097805, A130595, A167374, A200139, A239473, A321620.

Programs

  • Mathematica
    (* This program generates A118800 as the mirror of the self-fusion of Pascal's triangle. *)
z = 8; a = 1; b = 1; c = 1; d = 1;
p[n_, x_] := (a*x + b)^n ; q[n_, x_] := (c*x + d)^n;
t[n_, k_] := Coefficient[p[n, x], x^k]; t[n_, 0] := p[n, 0];
w[n_, x_] := Sum[t[n, k]*q[n + 1 - k, x], {k, 0, n}]; w[-1, _] = 1;
g[n_] := CoefficientList[w[n, -x], x];
TableForm[Table[Reverse[Abs@g[n]], {n, -1, z}]]
Flatten[Table[Reverse[Abs@g[n]], {n, -1, z}]] (* A081277 *)
TableForm[Table[g[n], {n, -1, z}]]
Flatten[Table[g[n], {n, -1, z}]] (* A118800 *)
(* Clark Kimberling, Aug 04 2011 *)
T[ n_, k_] := If[ n<0 || k<0, 0, (-1)^k 2^(n-k) (Binomial[ n, k] + Binomial[ n-1, n-k]) / 2]; (* Michael Somos, Nov 25 2016 *)
  • PARI
    {T(n,k)=if(n==0&k==0,1,(-1)^k*2^(n-k)*(binomial(n,k)+binomial(n-1,k-1))/2)}
for(n=0,12,for(k=0,n,print1(T(n,k),", "));print(""))
  • PARI
    /* Chebyshev Polynomials as Antidiagonals: */
{T(n,k)=local(Ox=x*O(x^(2*k))); polcoeff(((1+sqrt(1-x^2+Ox))^(n+k)+(1-sqrt(1-x^2+Ox))^(n+k))/2,2*k,x)}
for(n=0,12,for(k=0,n,print1(T(n,k),", "));print(""))
  • Sage
    # uses[riordan_square from A321620]
# Computes the unsigned triangle.
riordan_square((1-x)/(1-2*x), 8) # Peter Luschny, Jan 03 2019

Formula

T(n,k) = (-1)^k * 2^(n-k) * ( C(n,k) + C(n-1,k-1) )/2 for n>=k>=0 with T(0,0) = 1. Antidiagonals form the coefficients of Chebyshev polynomials: T(n,k) = [x^(2*n)] [(1+sqrt(1-x^2))^(n+k) + (1-sqrt(1-x^2))^(n+k)]/2.
Rows of the triangle are generated by taking successive iterates of (A135387)^n * [1, 1, 0, 0, 0, ...]. - Gary W. Adamson, Dec 09 2007
O.g.f.: (1 - t)/(1 + t*(x - 2)) = 1 + (1 - x)*t + (2 - 3*x + x^2)^t^2 + (4 - 8*x + 5*x^2 - x^3)*t^3 + .... Row polynomial R(n,x) = (1 - x)*(2 - x)^(n-1) for n >= 1. - Peter Bala, Jul 17 2013
T(n,k)=2*T(n-1,k)-T(n-1,k-1) with T(0,0)=T(1,0)=1, T(1,1)=-1, T(n,k)=0 if k<0 or if k>n. - Philippe Deléham, Nov 25 2013
G.f. for row n (n>=1): Sum_{k=0..n} T(n,k)*x^k = (1-x)*(2-x)^(n-1). - Philippe Deléham, Nov 25 2013
From Tom Copeland, Nov 15 2016: (Start)
E.g.f. is [1 + (1-x)e^((2-x)t)]/(2-x), so the row polynomials are p_n(x) = (1-q,(x))^n, umbrally, where (q.(x))^k = q_k(x) are the row polynomials of A239473, or, equivalently, T = M*A239473, where M is the inverse Pascal matrix C^(-1) = A130595 with the odd rows negated, i.e., M(n,k) = (-1)^n C^(-1)(n,k) with e.g.f. exp[(1-x)t]. Cf. A200139: A200139(n,k) = (-1)^k* A118800(n,k).
TCT = C^(-1) = A130595 and A239473 = A000012*C^(-1) = S*C^(-1) imply (M*S)^2 = Identity matrix, i.e., M*S = (M*S)^(-1) = S^(-1)*M^(-1) = A167374*M^(-1). Note that M = M^(-1). Cf. A097805. (End)

A118801 Triangle T that satisfies the matrix products: C*[T^-1]*C = T and T*[C^-1]*T = C, where C is Pascal's triangle.

Original entry on oeis.org

1, 1, -1, 1, -3, 1, 1, -7, 5, -1, 1, -15, 17, -7, 1, 1, -31, 49, -31, 9, -1, 1, -63, 129, -111, 49, -11, 1, 1, -127, 321, -351, 209, -71, 13, -1, 1, -255, 769, -1023, 769, -351, 97, -15, 1, 1, -511, 1793, -2815, 2561, -1471, 545, -127, 17, -1, 1, -1023, 4097, -7423, 7937, -5503, 2561, -799, 161, -19, 1
Offset: 0

Views

Author

Paul D. Hanna, May 02 2006

Keywords

Comments

Matrix inverse is triangle A118800. Row sums are: (1-n). Unsigned row sums equal A007051(n) = (3^n + 1)/2. Row squared sums equal A118802. Antidiagonal sums equal A080956(n) = (n+1)(2-n)/2. Unsigned antidiagonal sums form A024537 (with offset).
T = C^2*D^-1 where matrix product D = C^-1*T*C = T^-1*C^2 has only 2 nonzero diagonals: D(n,n)=-D(n+1,n)=(-1)^n, with zeros elsewhere. Also, [B^-1]*T*[B^-1] = B*[T^-1]*B forms a self-inverse matrix, where B^2 = C and B(n,k) = C(n,k)/2^(n-k). - Paul D. Hanna, May 04 2006
Riordan array ( 1/(1 - x), -x/(1 - 2*x) ) The matrix square is the Riordan array ( (1 - 2*x)/(1 - x)^2, x ), which belongs to the Appell subgroup of the Riordan group. See the Example section below. - Peter Bala, Jul 17 2013

Examples

			Formulas for initial columns are, for n>=0:
T(n+1,1) = 1 - 2^(n+1);
T(n+2,2) = 1 + 2^(n+1)*n;
T(n+3,3) = 1 - 2^(n+1)*(n*(n+1)/2 + 1);
T(n+4,4) = 1 + 2^(n+1)*(n*(n+1)*(n+2)/6 + n);
T(n+5,5) = 1 - 2^(n+1)*(n*(n+1)*(n+2)*(n+3)/24 + n*(n+1)/2 + 1).
Triangle begins:
1;
1,-1;
1,-3,1;
1,-7,5,-1;
1,-15,17,-7,1;
1,-31,49,-31,9,-1;
1,-63,129,-111,49,-11,1;
1,-127,321,-351,209,-71,13,-1;
1,-255,769,-1023,769,-351,97,-15,1;
1,-511,1793,-2815,2561,-1471,545,-127,17,-1;
1,-1023,4097,-7423,7937,-5503,2561,-799,161,-19,1; ...
The matrix square, T^2, starts:
1;
0,1;
-1,0,1;
-2,-1,0,1;
-3,-2,-1,0,1;
-4,-3,-2,-1,0,1; ...
where all columns are the same.
The matrix product C^-1*T*C = T^-1*C^2 is:
1;
-1,-1;
0, 1, 1;
0, 0,-1,-1;
0, 0, 0, 1, 1; ...
where C(n,k) = n!/(n-k)!/k!.

Links

Crossrefs

Cf. A118800 (inverse), A007051 (unsigned row sums), A118802 (Row squared sums), A080956 (antidiagonal sums), A024537 (unsigned antidiagonal sums).
A145661, A119258 and A118801 are all essentially the same (see the Shattuck and Waldhauser paper). - Tamas Waldhauser, Jul 25 2011
Cf. A007318, A032807, A097805, A112857, A130595, A156644, A167374, A200139, A239473.

Programs

  • Mathematica
    Table[(1 + (-1)^k*2^(n - k + 1)*Sum[ Binomial[n - 2 j - 2, k - 2 j - 1], {j, 0, Floor[k/2]}]) - 4 Boole[And[n == 1, k == 0]], {n, 0, 10}, {k, 0, n}] // Flatten (* Michael De Vlieger, Nov 24 2016 *)
  • PARI
    {T(n,k)=if(n==0&k==0,1,1+(-1)^k*2^(n-k+1)*sum(j=0,k\2,binomial(n-2*j-2,k-2*j-1)))}

Formula

T(n,k) = 1 + (-1)^k*2^(n-k+1)*Sum_{j=0..[k/2]} C(n-2j-2,k-2j-1) for n>=k>=0 with T(0,0) = 1.
For k>0, T(n,k) = -T(n-1,k-1) + 2*T(n-1,k). - Gerald McGarvey, Aug 05 2006
O.g.f.: (1 - 2*t)/(1 - t) * 1/(1 + t*(x - 2)) = 1 + (1 - x)*t + (1 - 3*x + x^2)*t^2 + (1 - 7*x + 5*x^2 - x^3)*t^3 + .... - Peter Bala, Jul 17 2013
From Tom Copeland, Nov 17 2016: (Start)
Let M = A200139^(-1) = (unsigned A118800)^(-1) and NpdP be the signed padded Pascal matrix defined in A097805. Then T(n,k) = (-1)^n* M(n,k) and T = P*NpdP = (A239473)^(-1)*P^(-1) = P*A167374*P^(-1) = A156644*P^(-1), where P is the Pascal matrix A007318 with inverse A130595. Cf. A112857.
Signed P^2 = signed A032807 = T*A167374. (End)

A156644 Mirror image of triangle A080233.

Original entry on oeis.org

1, 0, 1, -1, 1, 1, -2, 0, 2, 1, -3, -2, 2, 3, 1, -4, -5, 0, 5, 4, 1, -5, -9, -5, 5, 9, 5, 1, -6, -14, -14, 0, 14, 14, 6, 1, -7, -20, -28, -14, 14, 28, 20, 7, 1, -8, -27, -48, -42, 0, 42, 48, 27, 8, 1, -9, -35, -75, -90, -42, 42, 90, 75, 35, 9, 1
Offset: 0

Views

Author

Philippe Deléham, Feb 12 2009

Keywords

Comments

Inverse of A239473. Equals A007318*A167374. - Tom Copeland, Nov 14 2016

Examples

			Triangle begins as:
   1;
   0,  1;
  -1,  1, 1;
  -2,  0, 2, 1;
  -3, -2, 2, 3, 1;
  -4, -5, 0, 5, 4, 1; ...

Links

Crossrefs

Cf. A024000, A080956, A097808, A120730.
Cf. A007318, A167374, A239473.

Programs

  • Magma
    A156644:= func< n,k | ((2*k-n+1)/(k+1))*Binomial(n,k) >;
[A156644(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Feb 28 2021
  • Mathematica
    Table[Binomial[n, k] -Binomial[n, k+1], {n,0,10}, {k,0,n}]//Flatten (* Michael De Vlieger, Nov 24 2016 *)
  • Sage
    def A156644(n,k): return ((2*k-n+1)/(k+1))*binomial(n,k)
flatten([[A156644(n,k) for k in (0..n)] for n in (0..12)]) # G. C. Greubel, Feb 28 2021

Formula

T(n,k) = A080233(n,n-k) = (-1)^(n-k)*A097808(n,k).
T(n,k) = ((2*k-n+1)/(k+1))*binomial(n,k).
T(n,k) = T(n-1,k-1) + T(n-1,k), k>0, with T(n,0) = 1-n = A024000(n), T(n,n) = 1.
T(n,k) = binomial(n,k) - binomial(n,k+1) = Sum_{i=-k-1..k+1} (-1)^(i+1) * binomial(n,k+1+i) * binomial(n+2,k+1-i). - Mircea Merca, Apr 28 2012
Sum_{k=0..n} T(n, k) = A000012(n) = 1^n. - G. C. Greubel, Feb 28 2021

A330787 Triangle read by rows: T(n,k) is the number of strict multiset partitions of normal multisets of size n into k blocks, where a multiset is normal if it spans an initial interval of positive integers.

Original entry on oeis.org

1, 2, 1, 4, 8, 1, 8, 32, 18, 1, 16, 124, 140, 32, 1, 32, 444, 888, 432, 50, 1, 64, 1568, 5016, 4196, 1060, 72, 1, 128, 5440, 26796, 34732, 15064, 2224, 98, 1, 256, 18768, 138292, 262200, 174240, 44348, 4172, 128, 1, 512, 64432, 698864, 1870840, 1781884, 692668, 112424, 7200, 162, 1
Offset: 1

Views

Author

Andrew Howroyd, Dec 31 2019

Keywords

Examples

			Triangle begins:
    1;
    2,    1;
    4,    8,     1;
    8,   32,    18,     1;
   16,  124,   140,    32,     1;
   32,  444,   888,   432,    50,    1;
   64, 1568,  5016,  4196,  1060,   72,  1;
  128, 5440, 26796, 34732, 15064, 2224, 98, 1;
  ...
The T(3,1) = 4 multiset partitions are {{1,1,1}}, {{1,1,2}}, {{1,2,2}}, {{1,2,3}}.
The T(3,2) = 8 multiset partitions are {{1},{1,1}}, {{1},{2,2}}, {{2},{1,2}}, {{1},{1,2}}, {{2},{1,1}}, {{1},{2,3}}, {{2},{1,3}}, {{3},{1,2}}.
The T(3,3) = 1 multiset partition is {{1},{2},{3}}.

Links

Crossrefs

Row sums are A317776.
Column 1 is A000079(n-1).
Main diagonal is A000012.
Cf. A317532, A327116.

Programs

  • Mathematica
    B[n_, k_] := Sum[Binomial[r, k] (-1)^(r-k), {r, k, n}];
row[n_] := Sum[B[n, j] SeriesCoefficient[ Product[(1 + x^k y)^Binomial[k + j - 1, j - 1], {k, 1, n}], {x, 0, n}], {j, 1, n}]/y + O[y]^n // CoefficientList[#, y]&;
Array[row, 10] // Flatten (* Jean-François Alcover, Dec 17 2020, after Andrew Howroyd *)
  • PARI
    \\ here B(n, k) is A239473(n, k)
B(n,k)={sum(r=k, n, binomial(r, k)*(-1)^(r-k))}
Row(n)={Vecrev(sum(j=1, n, B(n,j)*polcoef(prod(k=1, n, (1 + x^k*y + O(x*x^n))^binomial(k+j-1,j-1)), n))/y)}
{ for(n=1, 10, print(Row(n))) }
Showing 1-8 of 8 results.

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

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