Displaying 1-10 of 209 results found.
page
1
2
3
4
5
6
7
8
9
10
... 21
Powers of 2: a(n) = 2^n.
(Formerly M1129 N0432)
+10
3182
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592
COMMENTS
2^0 = 1 is the only odd power of 2.
Number of subsets of an n-set.
There are 2^(n-1) compositions (ordered partitions) of n (see for example Riordan). This is the unlabeled analog of the preferential labelings sequence A000670. This is also the number of weakly unimodal permutations of 1..n + 1, that is, permutations with exactly one local maximum. E.g., a(4) = 16: 12345, 12354, 12453, 12543, 13452, 13542, 14532 and 15432 and their reversals. - Jon Perry, Jul 27 2003 [Proof: see next line! See also A087783.] Proof: n must appear somewhere and there are 2^(n-1) possible choices for the subset that precedes it. These must appear in increasing order and the rest must follow n in decreasing order. QED. - N. J. A. Sloane, Oct 26 2003 a(n+1) is the smallest number that is not the sum of any number of (distinct) earlier terms.
Same as Pisot sequences E(1, 2), L(1, 2), P(1, 2), T(1, 2). See A008776 for definitions of Pisot sequences. With initial 1 omitted, same as Pisot sequences E(2, 4), L(2, 4), P(2, 4), T(2, 4). - David W. WilsonNot the sum of two or more consecutive numbers. - Lekraj Beedassy, May 14 2004 Least deficient or near-perfect numbers (i.e., n such that sigma(n) = A000203(n) = 2n - 1). - Lekraj Beedassy, Jun 03 2004. [Comment from Max Alekseyev, Jan 26 2005: All the powers of 2 are least deficient numbers but it is not known if there exists a least deficient number that is not a power of 2.] Almost-perfect numbers referred to as least deficient or slightly defective (Singh 1997) numbers. Does "near-perfect numbers" refer to both almost-perfect numbers (sigma(n) = 2n - 1) and quasi-perfect numbers (sigma(n) = 2n + 1)? There are no known quasi-perfect or least abundant or slightly excessive (Singh 1997) numbers.
The sum of the numbers in the n-th row of Pascal's triangle; the sum of the coefficients of x in the expansion of (x+1)^n.
The Collatz conjecture (the hailstone sequence will eventually reach the number 1, regardless of which positive integer is chosen initially) may be restated as (the hailstone sequence will eventually reach a power of 2, regardless of which positive integer is chosen initially).
The only hailstone sequence which doesn't rebound (except "on the ground"). - Alexandre Wajnberg, Jan 29 2005 With p(n) as the number of integer partitions of n, p(i) is the number of parts of the i-th partition of n, d(i) is the number of different parts of the i-th partition of n, m(i,j) is the multiplicity of the j-th part of the i-th partition of n, one has: a(n) = Sum_{i = 1..p(n)} (p(i)! / (Product_{j=1..d(i)} m(i,j)!)). - Thomas Wieder, May 18 2005 The number of binary relations on an n-element set that are both symmetric and antisymmetric. Also the number of binary relations on an n-element set that are symmetric, antisymmetric and transitive.
a(n) is the largest number with shortest addition chain involving n additions. - David W. Wilson, Apr 23 2006 Beginning with a(1) = 0, numbers not equal to the sum of previous distinct natural numbers. - Giovanni Teofilatto, Aug 06 2006 For n >= 1, a(n) is equal to the number of functions f:{1, 2, ..., n} -> {1, 2} such that for a fixed x in {1, 2, ..., n} and a fixed y in {1, 2} we have f(x) != y. - Aleksandar M. Janjic and Milan Janjic, Mar 27 2007 Let P(A) be the power set of an n-element set A. Then a(n) is the number of pairs of elements {x,y} of P(A) for which x = y. - Ross La Haye, Jan 09 2008 a(n) is the number of different ways to run up a staircase with n steps, taking steps of sizes 1, 2, 3, ... and r (r <= n), where the order IS important and there is no restriction on the number or the size of each step taken. - Mohammad K. Azarian, May 21 2008 a(n) is the number of permutations on [n+1] such that every initial segment is an interval of integers. Example: a(3) counts 1234, 2134, 2314, 2341, 3214, 3241, 3421, 4321. The map "p -> ascents of p" is a bijection from these permutations to subsets of [n]. An ascent of a permutation p is a position i such that p(i) < p(i+1). The permutations shown map to 123, 23, 13, 12, 3, 2, 1 and the empty set respectively. - David Callan, Jul 25 2008 2^(n-1) is the largest number having n divisors (in the sense of A077569); A005179(n) is the smallest. - T. D. Noe, Sep 02 2008 a(n) appears to match the number of divisors of the modified primorials (excluding 2, 3 and 5). Very limited range examined, PARI example shown. - Bill McEachen, Oct 29 2008 Successive k such that phi(k)/k = 1/2, where phi is Euler's totient function. - Artur Jasinski, Nov 07 2008 This is also the (L)-sieve transform of {2, 4, 6, 8, ..., 2n, ...} = A005843. (See A152009 for the definition of the (L)-sieve transform.) - John W. Layman, Jan 23 2009 For n >= 0, a(n) is the number of leaves in a complete binary tree of height n. For n > 0, a(n) is the number of nodes in an n-cube. - K.V.Iyer, May 04 2009 Permutations of n+1 elements where no element is more than one position right of its original place. For example, there are 4 such permutations of three elements: 123, 132, 213, and 312. The 8 such permutations of four elements are 1234, 1243, 1324, 1423, 2134, 2143, 3124, and 4123. - Joerg Arndt, Jun 24 2009 a(n) written in base 2: 1,10,100,1000,10000,..., i.e., (n+1) times 1, n times 0 ( A011557(n)). - Jaroslav Krizek, Aug 02 2009 These are the 2-smooth numbers, positive integers with no prime factors greater than 2. - Michael B. Porter, Oct 04 2009 a(n) is the largest number m such that the number of steps of iterations of {r - (largest divisor d < r)} needed to reach 1 starting at r = m is equal to n. Example (a(5) = 32): 32 - 16 = 16; 16 - 8 = 8; 8 - 4 = 4; 4 - 2 = 2; 2 - 1 = 1; number 32 has 5 steps and is the largest such number. See A105017, A064097, A175125. - Jaroslav Krizek, Feb 15 2010 The powers-of-2 triangle T(n, k), n >= 0 and 0 <= k <= n, begins with: {1}; {2, 4}; {8, 16, 32}; {64, 128, 256, 512}; ... . The first left hand diagonal T(n, 0) = A006125(n + 1), the first right hand diagonal T(n, n) = A036442(n + 1) and the center diagonal T(2*n, n) = A053765(n + 1). Some triangle sums, see A180662, are: Row1(n) = A122743(n), Row2(n) = A181174(n), Fi1(n) = A181175(n), Fi2(2*n) = A181175(2*n) and Fi2(2*n + 1) = 2* A181175(2*n + 1). - Johannes W. Meijer, Oct 10 2010 The compositions of n in which each natural number is colored by one of p different colors are called p-colored compositions of n. For n>=1, a(n) equals the number of 2-colored compositions of n such that no adjacent parts have the same color. - Milan Janjic, Nov 17 2011 Equals A001405 convolved with its right-shifted variant: (1 + 2x + 4x^2 + ...) = (1 + x + 2x^2 + 3x^3 + 6x^4 + 10x^5 + ...) * (1 + x + x^2 + 2x^3 + 3x^4 + 6x^5 + ...). - Gary W. Adamson, Nov 23 2011 The number of odd-sized subsets of an n+1-set. For example, there are 2^3 odd-sized subsets of {1, 2, 3, 4}, namely {1}, {2}, {3}, {4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, and {2, 3, 4}. Also, note that 2^n = Sum_{k=1..floor((n+1)/2)} C(n+1, 2k-1). - Dennis P. Walsh, Dec 15 2011 a(n) is the number of 1's in any row of Pascal's triangle (mod 2) whose row number has exactly n 1's in its binary expansion (see A007318 and A047999). (The result of putting together A001316 and A000120.) - Marcus Jaiclin, Jan 31 2012 For n>=1 apparently the number of distinct finite languages over a unary alphabet, whose minimum regular expression has alphabetic width n (verified up to n=17), see the Gruber/Lee/Shallit link. - Hermann Gruber, May 09 2012 This is the lexicographically earliest sequence which contains no arithmetic progression of length 3. - Daniel E. Frohardt, Apr 03 2013
a(n-2) is the number of bipartitions of {1..n} (i.e., set partitions into two parts) such that 1 and 2 are not in the same subset. - Jon Perry, May 19 2013 Numbers n such that the n-th cyclotomic polynomial has a root mod 2; numbers n such that the n-th cyclotomic polynomial has an even number of odd coefficients. - Eric M. Schmidt, Jul 31 2013 More is known now about non-power-of-2 "Almost Perfect Numbers" as described in Dagal. - Jonathan Vos Post, Sep 01 2013 Number of symmetric Ferrers diagrams that fit into an n X n box. - Graham H. Hawkes, Oct 18 2013 a(1), ..., a(floor(n/2)) are all values of permanent on set of square (0,1)-matrices of order n>=2 with row and column sums 2. - Vladimir Shevelev, Nov 26 2013 Numbers whose base-2 expansion has exactly one bit set to 1, and thus has base-2 sum of digits equal to one. - Stanislav Sykora, Nov 29 2013 a(n) is the largest number k such that (k^n-2)/(k-2) is an integer (for n > 1); (k^a(n)+1)/(k+1) is never an integer (for k > 1 and n > 0). - Derek Orr, May 22 2014 The mini-sequence b(n) = least number k > 0 such that 2^k ends in n identical digits is given by {1, 18, 39}. The repeating digits are {2, 4, 8} respectively. Note that these are consecutive powers of 2 (2^1, 2^2, 2^3), and these are the only powers of 2 (2^k, k > 0) that are only one digit. Further, this sequence is finite. The number of n-digit endings for a power of 2 with n or more digits id 4*5^(n-1). Thus, for b(4) to exist, one only needs to check exponents up to 4*5^3 = 500. Since b(4) does not exist, it is clear that no other number will exist. - Derek Orr, Jun 14 2014 The least number k > 0 such that 2^k ends in n consecutive decreasing digits is a 3-number sequence given by {1, 5, 25}. The consecutive decreasing digits are {2, 32, 432}. There are 100 different 3-digit endings for 2^k. There are no k-values such that 2^k ends in '987', '876', '765', '654', '543', '321', or '210'. The k-values for which 2^k ends in '432' are given by 25 mod 100. For k = 25 + 100*x, the digit immediately before the run of '432' is {4, 6, 8, 0, 2, 4, 6, 8, 0, 2, ...} for x = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...}, respectively. Thus, we see the digit before '432' will never be a 5. So, this sequence is complete. - Derek Orr, Jul 03 2014 a(n) is the number of permutations of length n avoiding both 231 and 321 in the classical sense which are breadth-first search reading words of increasing unary-binary trees. For more details, see the entry for permutations avoiding 231 at A245898. - Manda Riehl, Aug 05 2014 This is a B_2 sequence: for i < j, differences a(j) - a(i) are all distinct. Here 2*a(n) < a(n+1) + 1, so a(n) - a(0) < a(n+1) - a(n). - Thomas Ordowski, Sep 23 2014 a(n) counts n-walks (closed) on the graph G(1-vertex; 1-loop, 1-loop). - David Neil McGrath, Dec 11 2014 a(n-1) counts walks (closed) on the graph G(1-vertex; 1-loop, 2-loop, 3-loop, 4-loop, ...). - David Neil McGrath, Jan 01 2015 b(0) = 4; b(n+1) is the smallest number not in the sequence such that b(n+1) - Prod_{i=0..n} b(i) divides b(n+1) - Sum_{i=0..n} b(i). Then b(n) = a(n) for n > 2. - Derek Orr, Jan 15 2015 a(n) counts the permutations of length n+2 whose first element is 2 such that the permutation has exactly one descent. - Ran Pan, Apr 17 2015 a(0)-a(30) appear, with a(26)-a(30) in error, in tablet M 08613 (see CDLI link) from the Old Babylonian period (c. 1900-1600 BC). - Charles R Greathouse IV, Sep 03 2015 Number of monotone maps f : [0..n] -> [0..n] which are order-increasing (i <= f(i)) and idempotent (f(f(i)) = f(i)). In other words, monads on the n-th ordinal (seen as a posetal category). Any monad f determines a subset of [0..n] that contains n, by considering its set of monad algebras = fixed points { i | f(i) = i }. Conversely, any subset S of [0..n] containing n determines a monad on [0..n], by the function i |-> min { j | i <= j, j in S }. - Noam Zeilberger, Dec 11 2016 Consider n points lying on a circle. Then for n>=2 a(n-2) gives the number of ways to connect two adjacent points with nonintersecting chords. - Anton Zakharov, Dec 31 2016 Satisfies Benford's law [Diaconis, 1977; Berger-Hill, 2017] - N. J. A. Sloane, Feb 07 2017 Also the number of independent vertex sets and vertex covers in the n-empty graph. - Eric W. Weisstein, Sep 21 2017 Also the number of maximum cliques in the n-halved cube graph for n > 4. - Eric W. Weisstein, Dec 04 2017 Number of pairs of compositions of n corresponding to a seaweed algebra of index n-1. - Nick Mayers, Jun 25 2018 The multiplicative group of integers modulo a(n) is cyclic if and only if n = 0, 1, 2. For n >= 3, it is a product of two cyclic groups. - Jianing Song, Jun 27 2018 k^n is the determinant of n X n matrix M_(i, j) = binomial(k + i + j - 2, j) - binomial(i+j-2, j), in this case k=2. - Tony Foster III, May 12 2019 a(n-1) is the number of subsets of {1,2,...,n} which have an element that is the size of the set. For example, for n = 4, a(3) = 8 and the subsets are {1}, {1,2}, {2,3}, {2,4}, {1,2,3}, {1,3,4}, {2,3,4}, {1,2,3,4}. - Enrique Navarrete, Nov 21 2020 a(n) is the number of self-inverse (n+1)-order permutations with 231-avoiding. E.g., a(3) = 8: [1234, 1243, 1324, 1432, 2134, 2143, 3214, 4321]. - Yuchun Ji, Feb 26 2021 For any fixed k > 0, a(n) is the number of ways to tile a strip of length n+1 with tiles of length 1, 2, ... k, where the tile of length k can be black or white, with the restriction that the first tile cannot be black. - Greg Dresden and Bora Bursalı, Aug 31 2023
REFERENCES
Milton Abramowitz and Irene A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 1016.
Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem, Mathematics and Computer Education Journal, Vol. 31, No. 1, pp. 24-28, Winter 1997.
Paul J. Nahin, An Imaginary Tale: The Story of sqrt(-1), Princeton University Press, Princeton, NJ. 1998, pp. 69-70.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 124.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
V. E. Tarakanov, Combinatorial problems on binary matrices, Combin. Analysis, MSU, 5 (1980), 4-15. (Russian)
S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 55.
LINKS
Milton Abramowitz and Irene A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy]. Anicius Manlius Severinus Boethius, De arithmetica, Book 1, section 9. Eric Weisstein's World of Mathematics, AbundanceEric Weisstein's World of Mathematics, ErfEric Weisstein's World of Mathematics, HypercubeEric Weisstein's World of Mathematics, Subset
FORMULA
a(n) = 2^n.
a(0) = 1; a(n) = 2*a(n-1).
G.f.: 1/(1 - 2*x).
E.g.f.: exp(2*x).
a(n)= Sum_{k = 0..n} binomial(n, k).
a(n) is the number of occurrences of n in A000523. a(n) = A001045(n) + A001045(n+1). a(n) = 1 + Sum_{k = 0..(n - 1)} a(k). The Hankel transform of this sequence gives A000007 = [1, 0, 0, 0, 0, 0, ...]. - Philippe Deléham, Feb 25 2004 a(n + 1) = a(n) XOR 3*a(n) where XOR is the binary exclusive OR operator. - Philippe Deléham, Jun 19 2005 a(n) = StirlingS2(n + 1, 2) + 1. - Ross La Haye, Jan 09 2008 a(n+2) = 6a(n+1) - 8a(n), n = 1, 2, 3, ... with a(1) = 1, a(2) = 2. - Yosu Yurramendi, Aug 06 2008 a(n) = ka(n-1) + (4 - 2k)a(n-2) for any integer k and n > 1, with a(0) = 1, a(1) = 2. - Jaume Oliver Lafont, Dec 05 2008 a(n) = Sum_{l_1 = 0..n + 1} Sum_{l_2 = 0..n}...Sum_{l_i = 0..n - i}...Sum_{l_n = 0..1} delta(l_1, l_2, ..., l_i, ..., l_n) where delta(l_1, l_2, ..., l_i, ..., l_n) = 0 if any l_i <= l_(i+1) and l_(i+1) != 0 and delta(l_1, l_2, ..., l_i, ..., l_n) = 1 otherwise. - Thomas Wieder, Feb 25 2009 If p[i] = i - 1 and if A is the Hessenberg matrix of order n defined by: A[i, j] = p[j - i + 1], (i <= j), A[i, j] = -1, (i = j + 1), and A[i, j] = 0 otherwise. Then, for n >= 1, a(n-1) = det A. - Milan Janjic, May 02 2010 If p[i] = Fibonacci(i-2) and if A is the Hessenberg matrix of order n defined by: A[i, j] = p[j - i + 1], (i <= j), A[i, j] = -1, (i = j + 1), and A[i, j] = 0 otherwise. Then, for n >= 2, a(n-2) = det A. - Milan Janjic, May 08 2010 The sum of reciprocals, 1/1 + 1/2 + 1/4 + 1/8 + ... + 1/(2^n) + ... = 2. - Mohammad K. Azarian, Dec 29 2010 a(n) = Hypergeometric([-n], [], -1). - Peter Luschny, Nov 01 2011 G.f.: A(x) = B(x)/x, B(x) satisfies B(B(x)) = x/(1 - x)^2. - Vladimir Kruchinin, Nov 10 2011 2^n = Sum_{k = 1..floor((n+1)/2)} C(n+1, 2k-1). - Dennis P. Walsh, Dec 15 2011 Sum_{n >= 1} mobius(n)/a(n) = 0.1020113348178103647430363939318... - R. J. Mathar, Aug 12 2012 E.g.f.: 1 + 2*x/(U(0) - x) where U(k) = 6*k + 1 + x^2/(6*k+3 + x^2/(6*k + 5 + x^2/U(k+1) )); (continued fraction, 3-step). - Sergei N. Gladkovskii, Dec 04 2012 a(n) = det(|s(i+2,j)|, 1 <= i,j <= n), where s(n,k) are Stirling numbers of the first kind. - Mircea Merca, Apr 04 2013 a(n) = det(|ps(i+1,j)|, 1 <= i,j <= n), where ps(n,k) are Legendre-Stirling numbers of the first kind ( A129467). - Mircea Merca, Apr 06 2013 G.f.: W(0), where W(k) = 1 + 2*x*(k+1)/(1 - 2*x*(k+1)/( 2*x*(k+2) + 1/W(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 28 2013 a(n-1) = Sum_{t_1 + 2*t_2 + ... + n*t_n = n} multinomial(t_1 + t_2 + ... + t_n; t_1, t_2, ..., t_n). - Mircea Merca, Dec 06 2013 Construct the power matrix T(n,j) = [A^*j]*[S^*(j-1)] where A(n)=(1,1,1,...) and S(n)=(0,1,0,0,...) (where * is convolution operation). Then a(n-1) = Sum_{j=1..n} T(n,j). - David Neil McGrath, Jan 01 2015 Exponential convolution of A000012 with themselves. Sum_{n>=0} a(n)/n! = exp(2) = A072334. Sum_{n>=0} (-1)^n*a(n)/n! = exp(-2) = A092553. (End) G.f.: (r(x) * r(x^2) * r(x^4) * r(x^8) * ...) where r(x) = A090129(x) = (1 + 2x + 2x^2 + 4x^3 + 8x^4 + ...). - Gary W. Adamson, Sep 13 2016 a(n)= n + 1 + Sum_{k=3..n+1} (2*k-5)*J(n+2-k), where Jacobsthal number J(n) = A001045(n). - Michael A. Allen, Jan 12 2022 Integral_{x=0..Pi} cos(x)^n*cos(n*x) dx = Pi/a(n) (see Nahin, pp. 69-70). - Stefano Spezia, May 17 2023
EXAMPLE
There are 2^3 = 8 subsets of a 3-element set {1,2,3}, namely { -, 1, 2, 3, 12, 13, 23, 123 }.
MAPLE
A000079 := n->2^n; [ seq(2^n, n=0..50) ];
isA000079 := proc(n)
local fs;
fs := numtheory[factorset](n) ;
if n = 1 then
true ;
elif nops(fs) <> 1 then
false;
elif op(1, fs) = 2 then
true;
else
false ;
end if;
MATHEMATICA
Table[2^n, {n, 0, 50}]
CoefficientList[Series[1/(1 - 2 x), {x, 0, 20}], x] (* Eric W. Weisstein, Sep 21 2017 *)
PROG
(PARI) unimodal(n)=local(x, d, um, umc); umc=0; for (c=0, n!-1, x=numtoperm(n, c); d=0; um=1; for (j=2, n, if (x[j]<x[j-1], d=1); if (x[j]>x[j-1] && d==1, um=0); if (um==0, break)); if (um==1, print(x)); umc+=um); umc
(PARI) x=1; for (n=0, 1000, write("b000079.txt", n, " ", x); x+=x); \\ Harry J. Smith, Apr 26 2009 (Haskell)
a000079 = (2 ^)
a000079_list = iterate (* 2) 1
(Magma) [n le 2 select n else 5*Self(n-1)-6*Self(n-2): n in [1..40]]; // Vincenzo Librandi, Feb 17 2014 (Scala) (List.fill(20)(2: BigInt)).scanLeft(1: BigInt)(_ * _) // Alonso del Arte, Jan 16 2020 (Python)
def a(n): return 1<<n
CROSSREFS
Cf. A000225, A038754, A133464, A140730, A037124, A001787, A001788, A001789, A003472, A054849, A002409, A054851, A140325, A140354, A000041, A152537, A001405, A007318, A000120, A000265, A000593, A001227, A077020, A077021. The following are parallel families: A000079 (2^n), A004094 (2^n reversed), A028909 (2^n sorted up), A028910 (2^n sorted down), A036447 (double and reverse), A057615 (double and sort up), A263451 (double and sort down); A000244 (3^n), A004167 (3^n reversed), A321540 (3^n sorted up), A321539 (3^n sorted down), A163632 (triple and reverse), A321542 (triple and sort up), A321541 (triple and sort down).
Powers of 3: a(n) = 3^n.
(Formerly M2807 N1129)
+10
850
1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 1162261467, 3486784401, 10460353203, 31381059609, 94143178827, 282429536481, 847288609443, 2541865828329, 7625597484987
COMMENTS
Same as Pisot sequences E(1, 3), L(1, 3), P(1, 3), T(1, 3). Essentially same as Pisot sequences E(3, 9), L(3, 9), P(3, 9), T(3, 9). See A008776 for definitions of Pisot sequences. Number of (s(0), s(1), ..., s(2n+2)) such that 0 < s(i) < 6 and |s(i) - s(i-1)| = 1 for i = 1, 2, ..., 2n + 2, s(0) = 1, s(2n+2) = 3. - Herbert Kociemba, Jun 10 2004 a(1) = 1, a(n+1) is the least number such that there are a(n) even numbers between a(n) and a(n+1). Generalization for the sequence of powers of k: 1, k, k^2, k^3, k^4, ... There are a(n) multiples of k-1 between a(n) and a(n+1). - Amarnath Murthy, Nov 28 2004 With p(n) being the number of integer partitions of n, p(i) being the number of parts of the i-th partition of n, d(i) being the number of different parts of the i-th partition of n, m(i, j) being the multiplicity of the j-th part of the i-th partition of n, Sum_{i = 1..p(n)} being the sum over i and Product_{j = 1..d(i)} being the product over j, one has: a(n) = Sum_{i = 1..p(n)} (p(i)!/(Product_{j = 1..d(i)} m(i, j)!))*2^(p(i) - 1). - Thomas Wieder, May 18 2005 For any k > 1 in the sequence, k is the first prime power appearing in the prime decomposition of repunit R_k, i.e., of A002275(k). - Lekraj Beedassy, Apr 24 2006 a(n-1) is the number of compositions of compositions. In general, (k+1)^(n-1) is the number of k-levels nested compositions (e.g., 4^(n-1) is the number of compositions of compositions of compositions, etc.). Each of the n - 1 spaces between elements can be a break for one of the k levels, or not a break at all. - Franklin T. Adams-Watters, Dec 06 2006 Let S be a binary relation on the power set P(A) of a set A having n = |A| elements such that for every element x, y of P(A), xSy if x is a subset of y. Then a(n) = |S|. - Ross La Haye, Dec 22 2006 With regard to the comment by Ross La Haye:
Cf. A001047 if either nonempty subsets are considered or x is a proper subset of y. Cf. a(n+1) in A028243 if nonempty subsets are considered and x is a proper subset of y. (End) If X_1, X_2, ..., X_n is a partition of the set {1, 2, ..., 2*n} into blocks of size 2 then, for n >= 1, a(n) is equal to the number of functions f : {1, 2, ..., 2*n} -> {1, 2} such that for fixed y_1, y_2, ..., y_n in {1, 2} we have f(X_i) <> {y_i}, (i = 1, 2, ..., n). - Milan Janjic, May 24 2007 This is a general comment on all sequences of the form a(n) = [(2^k)-1]^n for all positive integers k. Example 1.1.16 of Stanley's "Enumerative Combinatorics" offers a slightly different version. a(n) in the number of functions f:[n] into P([k]) - {}. a(n) is also the number of functions f:[k] into P([n]) such that the generalized intersection of f(i) for all i in [k] is the empty set. Where [n] = {1, 2, ..., n}, P([n]) is the power set of [n] and {} is the empty set. - Geoffrey Critzer, Feb 28 2009 3^(n+1) = (1, 2, 2, 2, ...) dot (1, 1, 3, 9, ..., 3^n); e.g., 3^3 = 27 = (1, 2, 2, 2) dot (1, 1, 3, 9) = (1 + 2 + 6 + 18). - Gary W. Adamson, May 17 2010 a(n) is the number of generalized compositions of n when there are 3*2^i different types of i, (i = 1, 2, ...). - Milan Janjic, Sep 24 2010 For n >= 1, a(n-1) is the number of generalized compositions of n when there are 2^(i-1) different types of i, (i = 1, 2, ...). - Milan Janjic, Sep 24 2010 The sequence in question ("Powers of 3") also describes the number of moves of the k-th disk solving the [RED ; BLUE ; BLUE] or [RED ; RED ; BLUE] pre-colored Magnetic Tower of Hanoi puzzle (cf. A183111 - A183125). a(n) is the number of Stern polynomials of degree n. See A057526. - T. D. Noe, Mar 01 2011 Sum of coefficients of the expansion of (1+x+x^2)^n. - Adi Dani, Jun 21 2011 a(n) is the number of compositions of n elements among {0, 1, 2}; e.g., a(2) = 9 since there are the 9 compositions 0 + 0, 0 + 1, 1 + 0, 0 + 2, 1 + 1, 2 + 0, 1 + 2, 2 + 1, and 2 + 2. [From Adi Dani, Jun 21 2011; modified by editors.] Except the first two terms, these are odd numbers n such that no x with 2 <= x <= n - 2 satisfy x^(n-1) == 1 (mod n). - Arkadiusz Wesolowski, Jul 03 2011 The compositions of n in which each natural number is colored by one of p different colors are called p-colored compositions of n. For n >= 1, a(n) equals the number of 3-colored compositions of n such that no adjacent parts have the same color. - Milan Janjic, Nov 17 2011 Since the preceding comment appears in a large number of sequences, it might be worth adding a proof.
The number of compositions of n into exactly k parts is binomial(n-1,k-1).
For a p-colored composition of n such that no adjacent parts have the same color, there are exactly p choices for the color of the first part, and p-1 choices for the color of each additional part (any color other than the color of the previous one). So, for a partition into k parts, there are p (p-1)^(k-1) valid colorings.
Thus the number of p-colored compositions of n into exactly k parts such that no adjacent parts have the same color is binomial(n-1,k-1) p (p-1)^(k-1).
The total number of p-colored compositions of n such that no adjacent parts have the same color is then
Sum_{k=1..n} binomial(n-1,k-1) * p * (p-1)^(k-1) = p^n.
To see this, note that the binomial expansion of ((p - 1) + 1)^(n - 1) = Sum_{k = 0..n - 1} binomial(n - 1, k) (p - 1)^k 1^(n - 1 - k) = Sum_{k = 1..n} binomial(n - 1, k - 1) (p - 1)^(k - 1).
(End)
Also, first and least element of the matrix [1, sqrt(2); sqrt(2), 2]^(n+1). - M. F. Hasler, Nov 25 2011 Form an array with m(0,n) = m(n,0) = 2^n; m(i,j) equals the sum of the terms to the left of m(i,j) and the sum of the terms above m(i,j), which is m(i,j) = Sum_{k=0..j-1} m(i,k) + Sum_{k=0..i-1} m(k,j). The sum of the terms in antidiagonal(n+1) = 4*a(n). - J. M. Bergot, Jul 10 2013 a(n) = A007051(n+1) - A007051(n), and A007051 are the antidiagonal sums of an array defined by m(0,k) = 1 and m(n,k) = Sum_{c = 0..k - 1} m(n, c) + Sum_{r = 0..n - 1} m(r, k), which is the sum of the terms to left of m(n, k) plus those above m(n, k). m(1, k) = A000079(k); m(2, k) = A045623(k + 1); m(k + 1, k) = A084771(k). - J. M. Bergot, Jul 16 2013 Define an array to have m(0,k) = 2^k and m(n,k) = Sum_{c = 0..k - 1} m(n, c) + Sum_{r = 0..n - 1} m(r, k), which is the sum of the terms to the left of m(n, k) plus those above m(n, k). Row n = 0 of the array comprises A000079, column k = 0 comprises A011782, row n = 1 comprises A001792. Antidiagonal sums of the array are a(n): 1 = 3^0, 1 + 2 = 3^1, 2 + 3 + 4 = 3^2, 4 + 7 + 8 + 8 = 3^3. - J. M. Bergot, Aug 02 2013 The sequence with interspersed zeros and o.g.f. x/(1 - 3*x^2), A(2*k) = 0, A(2*k + 1) = 3^k = a(k), k >= 0, can be called hexagon numbers. This is because the algebraic number rho(6) = 2*cos(Pi/6) = sqrt(3) of degree 2, with minimal polynomial C(6, x) = x^2 - 3 (see A187360, n = 6), is the length ratio of the smaller diagonal and the side in the hexagon. Hence rho(6)^n = A(n-1)*1 + A(n)*rho(6), in the power basis of the quadratic number field Q(rho(6)). One needs also A(-1) = 1. See also a Dec 02 2010 comment and the P. Steinbach reference given in A049310. - Wolfdieter Lang, Oct 02 2013 All powers of 3 are perfect totient numbers ( A082897), since phi(3^n) = 2 * 3^(n - 1) for n > 0, and thus Sum_{i = 0..n} phi(3^i) = 3^n. - Alonso del Arte, Apr 20 2014 The least number k > 0 such that 3^k ends in n consecutive decreasing digits is a 3-term sequence given by {1, 13, 93}. The consecutive increasing digits are {3, 23, 123}. There are 100 different 3-digit endings for 3^k. There are no k-values such that 3^k ends in '012', '234', '345', '456', '567', '678', or '789'. The k-values for which 3^k ends in '123' are given by 93 mod 100. For k = 93 + 100*x, the digit immediately before the run of '123' is {9, 5, 1, 7, 3, 9, 5, 1, 3, 7, ...} for x = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...}, respectively. Thus we see the digit before '123' will never be a 0. So there are no further terms. - Derek Orr, Jul 03 2014 All elements of A^n where A = (1, 1, 1; 1, 1, 1; 1, 1, 1). - David Neil McGrath, Jul 23 2014 Counts all walks of length n (open or closed) on the vertices of a triangle containing a loop at each vertex starting from any given vertex. - David Neil McGrath, Oct 03 2014 a(n) counts walks (closed) on the graph G(1-vertex;1-loop,1-loop,1-loop). - David Neil McGrath, Dec 11 2014 2*a(n-2) counts all permutations of a solitary closed walk of length (n) from the vertex of a triangle that contains 2 loops on each of the remaining vertices. In addition, C(m,k)=2*(2^m)*B(m+k-2,m) counts permutations of walks that contain (m) loops and (k) arcs. - David Neil McGrath, Dec 11 2014 a(n) is the sum of the coefficients of the n-th layer of Pascal's pyramid (a.k.a., Pascal's tetrahedron - see A046816). - Bob Selcoe, Apr 02 2016 Numbers n such that the trinomial x^(2*n) + x^n + 1 is irreducible over GF(2). Of these only the trinomial for n=1 is primitive. - Joerg Arndt, May 16 2016 Satisfies Benford's law [Berger-Hill, 2011]. - N. J. A. Sloane, Feb 08 2017 a(n-1) is also the number of compositions of n if the parts can be runs of any length from 1 to n, and can contain any integers from 1 to n. - Gregory L. Simay, May 26 2017 Also the number of independent vertex sets and vertex covers in the n-ladder rung graph n P_2. - Eric W. Weisstein, Sep 21 2017 Also the number of (not necessarily maximal) cliques in the n-cocktail party graph. - Eric W. Weisstein, Nov 29 2017 a(n-1) is the number of 2-compositions of n; see Hopkins & Ouvry reference. - Brian Hopkins, Aug 15 2020 a(n) is the number of faces of any dimension (vertices, edges, square faces, etc.) of the n-dimensional hypercube. For example, the 0-dimensional hypercube is a point, and its only face is itself. The 1-dimensional hypercube is a line, which has two vertices and an edge. The 2-dimensional hypercube is a square, which has four vertices, four edges, and a square face. - Kevin Long, Mar 14 2023 Number of pairs (A,B) of subsets of M={1,2,...,n} with union(A,B)=M. For nonempty subsets cf. A058481. - Manfred Boergens, Mar 28 2023 a(n) is the number of disjunctive clauses of n variables up to equivalence. A disjunctive clause is a propositional formula of the form l_1 OR ... OR l_m, where l_1, ..., l_m are distinct elements in {x_1, ..., x_n, NOT x_1, ..., NOT x_n} for n variables x_1, ... x_n, and no x_i and NOT x_i appear at the same time. For each 1 <= i <= n, we can have neither of x_i or NOT x_i, only x_i or only NOT x_i appearing in a disjunctive clause, so the number of such clauses is 3^n. Viewing the propositional formulas of n variables as functions {0,1}^n -> {0,1}, a disjunctive clause corresponds to a function f such that the inverse image of 0 is of the form A_1 X ... X A_n, where A_i is nonempty for all 1 <= i <= n. Since each A_i has 3 choices ({0}, {1} or {0,1}), we also find that the number of disjunctive clauses of n variables is 3^n.
Equivalently, a(n) is the number of conjunctive clauses of n variables. (End)
The finite subsequence a(2), a(3), a(4), a(5) = 9, 27, 81, 243 is one of only two geometric sequences that can be formed with all interior angles (all integer, in degrees) of a simple polygon. The other sequence is a subsequence of A007283 (see comment there). - Felix Huber, Feb 15 2024
REFERENCES
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
Eric Weisstein's World of Mathematics, CliqueDoron Zeilberger, The Amazing 3^n Theorem and its even more Amazing Proof [Discovered by Xavier G. Viennot and his École Bordelaise gang], arXiv:1208.2258, 2012.
FORMULA
a(n) = 3^n.
a(0) = 1; a(n) = 3*a(n-1).
G.f.: 1/(1-3*x).
E.g.f.: exp(3*x).
a(n) = n!*Sum_{i + j + k = n, i, j, k >= 0} 1/(i!*j!*k!). - Benoit Cloitre, Nov 01 2002 a(n) = Sum_{k = 0..n} 2^k*binomial(n, k), binomial transform of A000079. a(n) = 2*StirlingS2(n+1,3) + StirlingS2(n+2,2) = 2*(StirlingS2(n+1,3) + StirlingS2(n+1,2)) + 1. - Ross La Haye, Jun 26 2008 a(n) = 2*StirlingS2(n+1, 3) + StirlingS2(n+2, 2) = 2*(StirlingS2(n+1, 3) + StirlingS2(n+1, 2)) + 1. - Ross La Haye, Jun 09 2008 If p(i) = Fibonacci(2i-2) and if A is the Hessenberg matrix of order n defined by A(i, j) = p(j-i+1), (i <= j), A(i, j) = -1, (i = j+1), and A(i, j) = 0 otherwise, then, for n >= 1, a(n-1) = det A. - Milan Janjic, May 08 2010 2/3 + 3/3^2 + 2/3^3 + 3/3^4 + 2/3^5 + ... = 9/8. [Jolley, Summation of Series, Dover, 1961]
Sum_{n > 0} Mobius(n)/a(n) = 0.181995386702633887827... (see A238271). - Alonso del Arte, Aug 09 2012. See also the sodium 3s orbital energy in table V of J. Chem. Phys. 53 (1970) 348. a(n-1) = binomial(2*n-1, n) + Sum_{k >= 1} binomial(2*n, n+3*k)*(-1)^k. - Greg Dresden, Oct 14 2022 G.f.: Sum_{k >= 0} x^k/(1-2*x)^(k+1). - Kevin Long, Mar 14 2023
EXAMPLE
G.f. = 1 + 3*x + 9*x^2 + 27*x^3 + 81*x^4 + 243*x^5 + 729*x^6 + 2187*x^7 + ...
MAPLE
A000244 := n->3^n; [ seq(3^n, n=0..50) ];
MATHEMATICA
CoefficientList[Series[1/(1 - 3 x), {x, 0, 20}], x] (* Eric W. Weisstein, Sep 21 2017 *)
PROG
(Haskell)
(Maxima) makelist(3^n, n, 0, 30); /* Martin Ettl, Nov 05 2012 */ (Scala) val powersOf3: LazyList[BigInt] = LazyList.iterate(1: BigInt)(_ * 3)
(Python)
CROSSREFS
Cf. A008776 (2*a(n), and first differences). The following are parallel families: A000079 (2^n), A004094 (2^n reversed), A028909 (2^n sorted up), A028910 (2^n sorted down), A036447 (double and reverse), A057615 (double and sort up), A263451 (double and sort down); A000244 (3^n), A004167 (3^n reversed), A321540 (3^n sorted up), A321539 (3^n sorted down), A163632 (triple and reverse), A321542 (triple and sort up), A321541 (triple and sort down).
a(n) = 2^n + 1.
(Formerly M0717 N0266)
+10
843
2, 3, 5, 9, 17, 33, 65, 129, 257, 513, 1025, 2049, 4097, 8193, 16385, 32769, 65537, 131073, 262145, 524289, 1048577, 2097153, 4194305, 8388609, 16777217, 33554433, 67108865, 134217729, 268435457, 536870913, 1073741825, 2147483649, 4294967297, 8589934593
COMMENTS
Same as Pisot sequence L(2,3).
Length of the continued fraction for Sum_{k=0..n} 1/3^(2^k). - Benoit Cloitre, Nov 12 2003 From the second term on (n>=1), in base 2, these numbers present the pattern 1000...0001 (with n-1 zeros), which is the "opposite" of the binary 2^n-2: (0)111...1110 (cf. A000918). - Alexandre Wajnberg, May 31 2005 Let A be the Hessenberg matrix of order n, defined by: A[1,j]=1, A[i,i]:=5, (i>1), A[i,i-1]=-1, and A[i,j]=0 otherwise. Then, for n>=1, a(n-1)=(-1)^(n-1)* charpoly(A,3). - Milan Janjic, Jan 27 2010 Pisano period lengths: 1, 1, 2, 1, 4, 2, 3, 1, 6, 4, 10, 2, 12, 3, 4, 1, 8, 6, 18, 4, ... . - R. J. Mathar, Aug 10 2012 Is the mentioned Pisano period lengths (see above) the same as A007733? - Omar E. Pol, Aug 10 2012 Only positive integers that are not 1 mod (2k+1) for any k>1. - Jon Perry, Oct 16 2012 For n >= 1, a(n) is the total length of the segments of the Hilbert curve after n iterations. - Kival Ngaokrajang, Mar 30 2014 Frénicle de Bessy (1657) proved that a(3) = 9 is the only square in this sequence. - Charles R Greathouse IV, May 13 2014 a(n) is the number of distinct possible sums made with at most two elements in {1,...,a(n-1)} for n > 0. - Derek Orr, Dec 13 2014 For n > 0, given any set of a(n) lattice points in R^n, there exist 2 distinct members in this set whose midpoint is also a lattice point. - Melvin Peralta, Jan 28 2017 Also the number of independent vertex sets, irredundant sets, and vertex covers in the (n+1)-star graph. - Eric W. Weisstein, Aug 04 and Sep 21 2017 Also the number of maximum matchings in the 2(n-1)-crossed prism graph. - Eric W. Weisstein, Dec 31 2017 Conjecture: For any integer n >= 0, a(n) is the permanent of the (n+1) X (n+1) matrix with M(j, k) = -floor((j - k - 1)/(n + 1)). This conjecture is inspired by the conjecture of Zhi-Wei Sun in A036968. - Peter Luschny, Sep 07 2021
REFERENCES
Paul Bachmann, Niedere Zahlentheorie (1902, 1910), reprinted Chelsea, NY, 1968, vol. 2, p. 75.
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
Eric Weisstein's World of Mathematics, Star Graph.
FORMULA
a(n) = 2*a(n-1) - 1 = 3*a(n-1) - 2*a(n-2).
G.f.: (2-3*x)/((1-x)*(1-2*x)).
a(0) = 1, then a(n) = (Sum_{i=0..n-1} a(i)) - (n-2). - Gerald McGarvey, Jul 10 2004 Inverse binomial transform of A007689. Also, V sequence in Lucas sequence L(3, 2). - Ross La Haye, Feb 07 2005 Equals binomial transform of [2, 1, 1, 1, ...]. - Gary W. Adamson, Apr 23 2008 A weighted binomial sum of the Bernoulli numbers A027641/ A027642 with A027641(1)=1 (which amounts to the definition B_{n} = B_{n}(1)). a(n) = Sum_{k=0..n} C(n,k)*B_{n-k}*2^(k+1)/(k+1). (See also A052584.) (End) a(n) is the a(n-1)-th odd number for n >= 1. - Jaroslav Krizek, Apr 25 2009 If p[i]=Fibonacci(i-4) and if A is the Hessenberg matrix of order n defined by: A[i,j]=p[j-i+1], (i<=j), A[i,j]=-1, (i=j+1), and A[i,j]=0 otherwise, then, for n>=1, a(n-1)= det A. - Milan Janjic, May 08 2010
MAPLE
a := n -> add(binomial(n, k)*bernoulli(n-k, 1)*2^(k+1)/(k+1), k=0..n); # Peter Luschny, Apr 20 2009
MATHEMATICA
Table[2^n + 1, {n, 0, 33}]
PROG
(PARI) a(n)=2^n+1
(PARI) first(n) = Vec((2 - 3*x)/((1 - x)*(1 - 2*x)) + O(x^n)) \\ Iain Fox, Dec 31 2017 (Haskell)
a000051 = (+ 1) . a000079
a000051_list = iterate ((subtract 1) . (* 2)) 2
(Python)
CROSSREFS
Apart from the initial 1, identical to A094373. See A008776 for definitions of Pisot sequences. Cf. A034472, A052539, A034474, A062394, A034491, A036968, A062395, A062396, A062397, A007689, A063376, A063481, A074600- A074624, A034524, A178248, A228081, A173786, A052944, A000079, A005126, A176691, A194455, A323482. Cf. A007583 (a((n-1)/2)/3 for odd n).
Pell numbers: a(0) = 0, a(1) = 1; for n > 1, a(n) = 2*a(n-1) + a(n-2).
(Formerly M1413 N0552)
+10
762
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
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.
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. WilsonThe 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 (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 Related convergents (numerator/denominator):
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 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.
(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 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 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 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
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 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.
Thomas Koshy, Pell and Pell-Lucas Numbers with Applications, Springer, New York, 2014.
Serge Lang, Introduction to Diophantine Approximations, Addison-Wesley, New York, 1966.
P. Ribenboim, The Book of Prime Number Records. Springer-Verlag, NY, 2nd ed., 1989, p. 43.
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
Elena Barcucci, Antonio Bernini, and Renzo Pinzani, A Gray code for a regular language, Semantic Sensor Networks Workshop 2018, CEUR Workshop Proceedings (2018) Vol. 2113. M. A. Gruber, Artemas Martin, A. H. Bell, J. H. Drummond, A. H. Holmes and H. C. Wilkes, Problem 47, Amer. Math. Monthly, 4 (1897), 25-28. A. F. Horadam, Pell Identities, Fib. Quart., Vol. 9, No. 3, 1971, pp. 245-252, 263. Shirley Law, Hopf Algebra of Sashes, in FPSAC 2014, Chicago, USA; Discrete Mathematics and Theoretical Computer Science (DMTCS) Proceedings, 2014, 621-632. Eric Weisstein's World of Mathematics, Matching.
FORMULA
G.f.: x/(1 - 2*x - x^2). - Simon Plouffe in his 1992 dissertation. 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) = 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(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 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+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) = F(n, 2), the n-th Fibonacci polynomial evaluated at x=2. - T. D. Noe, Jan 19 2006 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) = 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 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 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 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 (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)
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(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) = 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 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) a(m+r)*a(n+s) - a(m+s)*a(n+r) = -(-1)^(n+s)*a(m-n)*a(r-s).
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).
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)
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 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)
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
EXAMPLE
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 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).
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)):
MATHEMATICA
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 *) a[ n_] := ChebyshevU[n - 1, I] / I^(n - 1); (* Michael Somos, Oct 30 2021 *)
PROG
(PARI) default(realprecision, 2000); 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) = polchebyshev(n-1, 2, I) / I^(n-1)}; /* Michael Somos, Oct 30 2021 */ (Sage) [lucas_number1(n, 2, -1) for n in range(30)] # Zerinvary Lajos, Apr 22 2009 (Haskell)
a000129 n = a000129_list !! n
a000129_list = 0 : 1 : zipWith (+) a000129_list (map (2 *) $ tail a000129_list)
(Maxima)
a[0]:0$
a[1]:1$
a[n]:=2*a[n-1]+a[n-2]$
(Maxima) makelist((%i)^(n-1)*ultraspherical(n-1, 1, -%i), n, 0, 24), expand; /* Emanuele Munarini, Mar 07 2018 */ (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 (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 (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
CROSSREFS
a(n) = A054456(n-1, 0), n>=1 (first column of triangle). INVERT transform of Fibonacci numbers ( A000045). 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. 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).
KEYWORD
nonn,easy,core,cofr,nice,frac
Powers of 4: a(n) = 4^n.
(Formerly M3518 N1428)
+10
547
1, 4, 16, 64, 256, 1024, 4096, 16384, 65536, 262144, 1048576, 4194304, 16777216, 67108864, 268435456, 1073741824, 4294967296, 17179869184, 68719476736, 274877906944, 1099511627776, 4398046511104, 17592186044416, 70368744177664, 281474976710656
COMMENTS
Same as Pisot sequences E(1, 4), L(1, 4), P(1, 4), T(1, 4). Essentially same as Pisot sequences E(4, 16), L(4, 16), P(4, 16), T(4, 16). See A008776 for definitions of Pisot sequences. The convolution square root of this sequence is A000984, the central binomial coefficients: C(2n,n). - T. D. Noe, Jun 11 2002 With P(n) being the number of integer partitions of n, p(i) as the number of parts of the i-th partition of n, d(i) as the number of different parts of the i-th partition of n, m(i, j) the multiplicity of the j-th part of the i-th partition of n, one has a(n) = Sum_{i = 1..P(n)} p(i)!/(Product_{j = 1..d(i)} m(i, j)!) * 2^(n-1). - Thomas Wieder, May 18 2005 Equals the Catalan sequence: (1, 1, 2, 5, 14, ...), convolved with A032443: (1, 3, 11, 42, ...). - Gary W. Adamson, May 15 2009 Sum of coefficients of expansion of (1 + x + x^2 + x^3)^n.
a(n) is number of compositions of natural numbers into n parts less than 4. For example, a(2) = 16 since there are 16 compositions of natural numbers into 2 parts less than 4.
The compositions of n in which each natural number is colored by one of p different colors are called p-colored compositions of n. For n >= 1, a(n) equals the number of 4-colored compositions of n such that no adjacent parts have the same color. - Milan Janjic, Nov 17 2011 Row sums of Pascal's triangle using the rule that going left increases the value by a factor of k = 3. For example, the first three rows are {1}, {3, 1}, and {9, 6, 1}. Using this rule gives row sums as (k+1)^n. - Jon Perry, Oct 11 2012 Sum of all peak heights in Dyck paths of semilength n+1. - David Scambler, Apr 22 2013 a(n) is equal to 1 plus the sum for 0 < k < 2^n of the numerators and denominators of the reduced fractions k/2^n. - J. M. Bergot, Jul 13 2015 Number of nodes at level n regular 4-ary tree.
Satisfies Benford's law [Berger-Hill, 2011]. - N. J. A. Sloane, Feb 08 2017 Also the number of connected dominating sets in the (n+1)-barbell graph. - Eric W. Weisstein, Jun 29 2017 Side length of the cells at level n in a pyramid scheme where a square grid is decomposed into overlapping 2 X 2 blocks (cf. Kropatsch, 1985). - Felix Fröhlich, Jul 04 2019 a(n-1) is the number of 3-compositions of n; see Hopkins & Ouvry reference. - Brian Hopkins, Aug 15 2020
REFERENCES
H. W. Gould, Combinatorial Identities, 1972, eq. (1.93), p. 12.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 2nd. ed., 1994, eq. (5.39), p. 187.
D. Phulara and L. W. Shapiro, Descendants in ordered trees with a marked vertex, Congressus Numerantium, 205 (2011), 121-128.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 55.
FORMULA
a(n) = 4^n.
a(0) = 1; a(n) = 4*a(n-1).
G.f.: 1/(1-4*x).
E.g.f.: exp(4*x).
a(n) = Sum_{k = 0..n} binomial(2k, k) * binomial(2(n - k), n - k). - Benoit Cloitre, Jan 26 2003 [See Graham et al., eq. (5.39), p. 187. - Wolfdieter Lang, Aug 16 2019] 1 = Sum_{n >= 1} 3/a(n) = 3/4 + 3/16 + 3/64 + 3/256 + 3/1024, ...; with partial sums: 3/4, 15/16, 63/64, 255/256, 1023/1024, ... - Gary W. Adamson, Jun 16 2003 a(n) = Sum_{j = 0..n} 2^(n - j)*binomial(n + j, j). - Peter C. Heinig (algorithms(AT)gmx.de), Apr 06 2007
a(n) = 6*Stirling2(n+1, 4) + 6*Stirling2(n+1, 3) + 3*Stirling2(n+1, 2) + 1 = 2*Stirling2(2^n, 2^n - 1) + Stirling2(n+1, 2) + 1. - Ross La Haye, Jun 26 2008 a(n) = Sum_{k = 0..n} binomial(2*n+1, k). - Mircea Merca, Jun 25 2011 Sum_{n >= 1} Mobius(n)/a(n) = 0.1710822479183... - R. J. Mathar, Aug 12 2012 a(n) = Sum_{k = 0..n} binomial(2*k + x, k)*binomial(2*(n - k) - x, n - k) for every real number x. - Rui Duarte and António Guedes de Oliveira, Feb 16 2013 a(n) = (2*n+1) * binomial(2*n,n) * Sum_{j=0..n} (-1)^j/(2*j+1)*binomial(n,j). - Vaclav Kotesovec, Sep 15 2013 a(n) = (1/2) * Product_{k = 0..n} (1 + (2*n + 1)/(2*k + 1)). - Peter Bala, Mar 06 2018 a(n) = denominator(zeta_star({2}_(n + 1))/zeta(2*n + 2)) where zeta_star is the multiple zeta star values and ({2}_n) represents (2, ..., 2) where the multiplicity of 2 is n. - Roudy El Haddad, Feb 22 2022 a(n) = 1 + 3*Sum_{k=0..n} binomial(2*n, n+k)*(k|9), where (k|9) is the Jacobi symbol. - Greg Dresden, Oct 11 2022 a(n) = Sum_{k = 0..n} binomial(2*n+1, 2*k) = Sum_{k = 0..n} binomial(2*n+1, 2*k+1). - Sela Fried, Mar 23 2023
MAPLE
for n from 0 to 10 do sum(2^(n-j)*binomial(n+j, j), j=0..n); od; # Peter C. Heinig (algorithms(AT)gmx.de), Apr 06 2007
MATHEMATICA
CoefficientList[Series[1/(1 - 4 x), {x, 0, 50}], x] (* Vincenzo Librandi, May 29 2014 *)
PROG
(Haskell)
a000302 = (4 ^)
(Scala) (List.fill(20)(4: BigInt)).scanLeft(1: BigInt)(_ * _) // Alonso del Arte, Jun 22 2019
F(2n) = bisection of Fibonacci sequence: a(n) = 3*a(n-1) - a(n-2).
(Formerly M2741 N1101)
+10
426
0, 1, 3, 8, 21, 55, 144, 377, 987, 2584, 6765, 17711, 46368, 121393, 317811, 832040, 2178309, 5702887, 14930352, 39088169, 102334155, 267914296, 701408733, 1836311903, 4807526976, 12586269025, 32951280099, 86267571272, 225851433717, 591286729879, 1548008755920
COMMENTS
Apart from initial term, same as A088305. Apart from initial terms, also Pisot sequences E(3,8), P(3,8), T(3,8). See A008776 for definitions of Pisot sequences. Number of walks of length 2n+1 in the path graph P_4 from one end to the other one. Example: a(2)=3 because in the path ABCD we have ABABCD, ABCBCD and ABCDCD. - Emeric Deutsch, Apr 02 2004 Simplest example of a second-order recurrence with the sixth term a square.
Number of (s(0), s(1), ..., s(2n)) such that 0 < s(i) < 5 and |s(i) - s(i-1)| = 1 for i = 1,2,...,2n, s(0) = 1, s(2n) = 3. - Lekraj Beedassy, Jun 11 2004 a(n) (for n > 0) is the smallest positive integer that cannot be created by summing at most n values chosen among the previous terms (with repeats allowed). - Andrew Weimholt, Jul 20 2004 All nonnegative integer solutions of Pell equation b(n)^2 - 5*a(n)^2 = +4 together with b(n) = A005248(n), n >= 0. - Wolfdieter Lang, Aug 31 2004 a(n+1) is a Chebyshev transform of 3^n ( A000244), where the sequence with g.f. G(x) is sent to the sequence with g.f. (1/(1+x^2))G(x/(1+x^2)). - Paul Barry, Oct 25 2004 a(n) is the number of distinct products of matrices A, B, C, in (A+B+C)^n where commutator [A,B] = 0 but C does not commute with A or B. - Paul D. Hanna and Max Alekseyev, Feb 01 2006 Number of binary words with exactly k-1 strictly increasing runs. Example: a(3)=F(6)=8 because we have 0|0,1|0,1|1,0|01,01|0,1|01,01|1 and 01|01. Column sums of A119900. - Emeric Deutsch, Jul 23 2006 Inverse: With phi = (sqrt(5) + 1)/2, log_phi((sqrt(5) a(n) + sqrt(5 a(n)^2 + 4))/2) = n. - David W. Cantrell (DWCantrell(AT)sigmaxi.net), Feb 19 2007
[1,3,8,21,55,144,...] is the Hankel transform of [1,1,4,17,75,339,1558,...](see A026378). - Philippe Deléham, Apr 13 2007 The Diophantine equation a(n) = m has a solution (for m >= 1) if and only if floor(arcsinh(sqrt(5)*m/2)/log(phi)) <> floor(arccosh(sqrt(5)*m/2)/log(phi)) where phi is the golden ratio. An equivalent condition is A130259(m) = A130260(m). - Hieronymus Fischer, May 25 2007 a(n+1) = AB^(n)(1), n >= 0, with compositions of Wythoff's complementary A(n):= A000201(n) and B(n)= A001950(n) sequences. See the W. Lang link under A135817 for the Wythoff representation of numbers (with A as 1 and B as 0 and the argument 1 omitted). E.g., 1=`1`, 3=`10`, 8=`100`, 21=`1000`, ..., in Wythoff code. a(n) is also the number of idempotent order-preserving partial transformations (of an n-element chain) of width n (width(alpha) = max(Im(alpha))). Equivalently, it is the number of idempotent order-preserving full transformations (of an n-element chain). - Abdullahi Umar, Sep 08 2008 a(n) is the number of ways that a string of 0,1 and 2 of size (n-1) can be arranged with no 12-pairs. - Udita Katugampola, Sep 24 2008 As a fraction: 1/71 = 0.01408450... or 1/9701 = 0.0001030821.... - Mark Dols, May 18 2010 Sum of the products of the elements in the compositions of n (example for n=3: the compositions are 1+1+1, 1+2, 2+1, and 3; a(3) = 1*1*1 + 1*2 + 2*1 + 3 = 8). - Dylon Hamilton, Jun 20 2010, Geoffrey Critzer, Joerg Arndt, Dec 06 2010 a(n) relates to regular polygons with even numbers of edges such that Product_{k=1..(n-2)/2} (1 + 4*cos^2 k*Pi/n) = even-indexed Fibonacci numbers with a(n) relating to the 2*n-gons. The constants as products = roots to even-indexed rows of triangle A152063. For example: a(5) = 55 satisfies the product formula relating to the 10-gon. - Gary W. Adamson, Aug 15 2010 Alternatively, product of roots to x^4 - 12x^3 + 51x^2 - 90x + 55, (10th row of triangle A152063) = (4.618...)*(3.618...)*(2.381...)*(1.381...) = 55. - Gary W. Adamson, Aug 15 2010 a(n) is the number of generalized compositions of n when there are i different types of i, (i=1,2,...). - Milan Janjic, Aug 26 2010 a(2) = 3 is the only prime.
Number of nonisomorphic graded posets with 0 and uniform hasse graph of rank n > 0, with exactly 2 elements of each rank level above 0. (Uniform used in the sense of Retakh, Serconek, and Wilson. Graded used in Stanley's sense that every maximal chain has the same length n.) - David Nacin, Feb 13 2012 Pisano period lengths: 1, 3, 4, 3, 10, 12, 8, 6, 12, 30, 5, 12, 14, 24, 20, 12, 18, 12, 9, 30, ... - R. J. Mathar, Aug 10 2012 Solutions (x, y) = (a(n), a(n+1)) satisfying x^2 + y^2 = 3xy + 1. - Michel Lagneau, Feb 01 2014 For n >= 1, a(n) equals the number of 01-avoiding words of length n-1 on alphabet {0,1,2}. - Milan Janjic, Jan 25 2015 With a(0) = 0, for n > 1, a(n) is the smallest number not already in the sequence such that a(n)^2 - a(n-1)^2 is a Fibonacci number. - Derek Orr, Jun 08 2015 Let T be the tree generated by these rules: 0 is in T, and if p is in T, then p + 1 is in T and x*p is in T and y*p is in T. The n-th generation of T consists of A001906(n) polynomials, for n >= 0. - Clark Kimberling, Nov 24 2015 For n > 0, a(n) = exactly the maximum area of a quadrilateral with sides in order of lengths F(n), F(n), L(n), and L(n) with L(n)= A000032(n). - J. M. Bergot, Jan 20 2016 a(n) = twice the area of a triangle with vertices at (L(n+1), L(n+2)), (F(n+1), F(n+1)), and (L(n+2), L(n+1)), with L(n)= A000032(n). - J. M. Bergot, Apr 20 2016 Except for the initial 0, this is the p-INVERT of (1,1,1,1,1,...) for p(S) = 1 - S - S^2; see A291000. - Clark Kimberling, Aug 24 2017 a(n+1) is the number of spanning trees of the graph T_n, where T_n is a sequence of n triangles, where adjacent triangles share an edge. - Kevin Long, May 07 2018 a(n) is the number of ways to partition [n] such that each block is a run of consecutive numbers, and each block has a fixed point, e.g., for n=3, 12|3 with 1 and 3 as fixed points is valid, but 13|2 is not valid as 1 and 3 do not form a run. Consequently, a(n) also counts the spanning trees of the graph given by taking a path with n vertices and adding another vertex adjacent to all of them. - Kevin Long, May 11 2018 The preceding comment can be paraphrased as follows. a(n) is the row sum of the array A305309 for n >= 1. The array A305309(n, k) gives the sum of the products of the block lengths of the set partition of [n] := {1, 2, ..., n} with A048996(n, k) blocks of consecutive numbers, corresponding to the compositions obtained from the k-th partition of n in Abramowitz-Stegun order. See the comments and examples at A305309. {a(n)} also gives the infinite sequence of nonnegative numbers k for which k * ||k*phi|| < 1/sqrt(5), where the irrational number phi = A001622 (golden section), and ||x|| is the absolute value of the difference between x and the nearest integer. See, e.g., the Havil reference, pp. 171-172. (End) This Chebyshev sequence a(n) = S(n-1, 3) (see a formula below) is related to the bisection of Fibonacci sequences {F(a,b;n)}_{n>=0} with input F(a,b;0) = a and F(a,b;1) = b, by F(a,b;2*k) = (a+b)*S(k-1, 3) - a*S(k-2, 3) and F(a,b;2*k+1) = b*S(k, 3) + (a-b)*S(k-1, 3), for k >= 0, and S(-2, 3) = -1. Proof via the o.g.f.s GFeven(a,b,t) = (a - t*(2*a-b))/(1 - 3*t + t^2) and GFodd(a,b,t) = (b + t*(a-b))/(1 - 3*t + t^2). The special case a = 0, b = 1 gives back F(2*k) = S(k-1, 3) = a(k). - Wolfdieter Lang, Jun 07 2019 a(n) is the number of tilings of two n X 1 rectangles joined orthogonally at a common end-square (so to have 2n-1 squares in a right-angle V shape) with only 1 X 1 and 2 X 1 tiles. This is a consequence of F(2n) = F(n+1)*F(n) + F(n)*F(n-1). - Nathaniel Gregg, Oct 10 2021 These are the denominators of the upper convergents to the golden ratio, tau; they are also the numerators of the lower convergents (viz. 1/1 < 3/2 < 8/5 < 21/13 < ... < tau < ... 13/8 < 5/3 < 2/1). - Clark Kimberling, Jan 02 2022 For n > 1, a(n) is the smallest Fibonacci number of unit equilateral triangle tiles needed to make an isosceles trapezoid of height F(n) triangles. - Kiran Ananthpur Bacche, Sep 01 2024
REFERENCES
Mohammad K. Azarian, The Generating Function for the Fibonacci Sequence, Missouri Journal of Mathematical Sciences, Vol. 2, No. 2, Spring 1990, pp. 78-79. Zentralblatt MATH, Zbl 1097.11516.
Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem II, Missouri Journal of Mathematical Sciences, Vol. 16, No. 1, Winter 2004, pp. 12-17.
A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 2,5,6,14,33,55.
R. J. Douglas, Tournaments that admit exactly one Hamiltonian cycle, Proc. London Math. Soc., 21 (1970), 716-730.
G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.
A. Gerardin, Reply to Query 4389, L'Intermédiaire des Mathématiciens, 22 (1915), 23.
Julian Havil, The Irrationals, Princeton University Press, Princeton and Oxford, 2012, pp. 171-172.
Howie, J. M. Combinatorial and probabilistic results in transformation semigroups. Words, languages and combinatorics, II (Kyoto, 1992), 200--206, World Sci. Publ., River Edge, NJ, (1994).
Laradji, A. and Umar, A. Combinatorial results for semigroups of order-preserving full transformations. Semigroup Forum 72 (2006), 51-62.
I. Lukovits, A. Graovac, E. Kalman, G. Kaptay, P. Nagy, S. Nikolic, J. Sytchev and N. Trinajstich, "Nanotubes: Number of Kekulé Structures and Aromaticity", J. Chem. Inf. Comput. Sci, vol. 43 (2003), pp. 609-614. See Equation 6 on page 611.
T. Mansour, M. Shattuck, A statistic on n-color compositions and related sequences, Proc. Indian Acad. Sci. (Math. Sci.) Vol. 124, No. 2, May 2014, pp. 127-140.
H. Mathieu, Query 3932, L'Intermédiaire des Mathématiciens, 18 (1911), 222. - N. J. A. Sloane, Mar 08 2022 I. Niven and H. S. Zuckerman, An Introduction to the Theory of Numbers. 2nd ed., Wiley, NY, 1966, p. 101.
Paulo Ribenboim, Primes in Lucas sequences (Chap 4), in 'My Numbers, My Friends', Springer-Verlag 2000 NY, page 27.
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. Stanley, Enumerative combinatorics, Vol. 1, Cambridge University Press, Cambridge, 1997, pp. 96-100.
LINKS
P. J. Cameron, Some sequences of integers, Discrete Math., 75 (1989), 89-102; also in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89-102. A. Gougenheim, About the linear sequence of integers such that each term is the sum of the two preceding Part 1 Part 2, Fib. Quart., 9 (1971), 277-295, 298. G. Kreweras, Sur les éventails de segments, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #15 (1970), 3-41. [Annotated scanned copy] J. Salas and A. D. Sokal, Transfer Matrices and Partition-Function Zeros for Antiferromagnetic Potts Models. V. Further Results for the Square-Lattice Chromatic Polynomial, J. Stat. Phys. 135 (2009) 279-373, arXiv:0711.1738. Mentions this sequence.
FORMULA
G.f.: x / (1 - 3*x + x^2). - Simon Plouffe in his 1992 dissertation a(n) = 3*a(n-1) - a(n-2) = A000045(2*n). a(n) = -a(-n).
a(n) = (ap^n - am^n)/(ap-am), with ap := (3+sqrt(5))/2, am := (3-sqrt(5))/2.
Invert transform of natural numbers: a(n) = Sum_{k=1..n} k*a(n-k), a(0) = 1. - Vladeta Jovovic, Apr 27 2001 a(n) = S(n-1, 3) with S(n, x) = U(n, x/2) Chebyshev's polynomials of the 2nd kind, see A049310. a(n) = Sum_{k=0..n} binomial(n, k)*F(k). - Benoit Cloitre, Sep 03 2002 Limit_{n->infinity} a(n)/a(n-1) = 1 + phi = (3 + sqrt(5))/2. This sequence includes all of the elements of A033888 combined with A033890. a(0)=0, a(1)=1, a(2)=3, a(n)*a(n-2) + 1 = a(n-1)^2. - Benoit Cloitre, Dec 06 2002 E.g.f.: (2/sqrt(5))*exp(3*x/2)*sinh(sqrt(5)*x/2). - Paul Barry, Apr 11 2003 Second diagonal of array defined by T(i, 1) = T(1, j) = 1, T(i, j) = Max(T(i-1, j) + T(i-1, j-1); T(i-1, j-1) + T(i, j-1)). - Benoit Cloitre, Aug 05 2003 F(2n+2) = 1, 3, 8, ... is the binomial transform of F(n+2). - Paul Barry, Apr 24 2004 a(n) = Sum_{i=0..n-1} binomial(2*n-1-i, i)*5^(n-i-1)*(-1)^i. - Mario Catalani (mario.catalani(AT)unito.it), Jul 23 2004
a(n) = Sum_{k=0..n} binomial(n+k, n-k-1) = Sum_{k=0..n} binomial(n+k, 2k+1).
a(n+1) = Sum_{k=0..floor(n/2)} binomial(n-k, k)*(-1)^k*3^(n-2*k). - Paul Barry, Oct 25 2004 a(n) = (n*L(n) - F(n))/5 = Sum_{k=0..n-1} (-1)^n*L(2*n-2*k-1).
The i-th term of the sequence is the entry (1, 2) in the i-th power of the 2 X 2 matrix M = ((1, 1), (1, 2)). - Simone Severini, Oct 15 2005 Computation suggests that this sequence is the Hankel transform of A005807. The Hankel transform of {a(n)} is Det[{{a(1), ..., a(n)}, {a(2), ..., a(n+1)}, ..., {a(n), ..., a(2n-1)}}]. - John W. Layman, Jul 21 2000 a(n+1) = Sum_{i=0..n} Sum_{j=0..n} binomial(n-i, j)*binomial(n-j, i). - N. J. A. Sloane, Feb 20 2005 a(n) = (2/sqrt(5))*sinh(2*n*psi), where psi:=log(phi) and phi=(1+sqrt(5))/2. - Hieronymus Fischer, Apr 24 2007 a(n)^2 = Sum_{k=1..n} a(2*k-1). This is a property of any sequence S(n) such that S(n) = B*S(n-1) - S(n-2) with S(0) = 0 and S(1) = 1 including {0,1,2,3,...} where B = 2. - Kenneth J Ramsey, Mar 23 2008 a(n) = 1/sqrt(5)*(phi^(2*n+2) - phi^(-2*n-2)), where phi = (1+sqrt(5))/2, the golden ratio. - Udita Katugampola (SIU), Sep 24 2008 If p[i] = i 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, May 02 2010 If p[i] = Stirling2(i,2) and if A is the Hessenberg matrix of order n defined by: A[i,j] = p[j-i+1], (i<=j), A[i,j] = -1, (i = j+1), and A[i,j] = 0 otherwise. Then, for n >= 1, a(n-1) = det(A). - Milan Janjic, May 08 2010 a(n) = F(2*n+10) mod F(2*n+5).
a(n) = 1 + a(n-1) + Sum_{i=1..n-1} a(i), with a(0)=0. - Gary W. Adamson, Feb 19 2011 a(n) is equal to the permanent of the (n-1) X (n-1) Hessenberg matrix with 3's along the main diagonal, i's along the superdiagonal and the subdiagonal (i is the imaginary unit), and 0's everywhere else. - John M. Campbell, Jun 09 2011 a(n), n > 1 is equal to the determinant of an (n-x) X (n-1) tridiagonal matrix with 3's in the main diagonal, 1's in the super and subdiagonals, and the rest 0's. - Gary W. Adamson, Jun 27 2011 a(n) = b such that Integral_{x=0..Pi/2} sin(n*x)/(3/2-cos(x)) dx = c + b*log(3). - Francesco Daddi, Aug 01 2011 G.f.: A(x) = x/(1-3*x+x^2) = G(0)/sqrt(5); where G(k)= 1 -(a^k)/(1 - b*x/(b*x - 2*(a^k)/G(k+1))), a = (7-3*sqrt(5))/2, b = 3+sqrt(5), if |x|<(3-sqrt(5))/2 = 0.3819660...; (continued fraction 3 kind, 3-step ). - Sergei N. Gladkovskii, Jun 25 2012 a(n) = 2^n*b(n;1/2) = -b(n;-1), where b(n;d), n=0,1,...,d, denote the delta-Fibonacci numbers defined in comments to A000045 (see also Witula's et al. papers). - Roman Witula, Jul 12 2012 Product_{n>=1} (1 + 1/a(n)) = 1 + sqrt(5). - Peter Bala, Dec 23 2012 Product_{n>=2} (1 - 1/a(n)) = (1/6)*(1 + sqrt(5)). - Peter Bala, Dec 23 2012 G.f.: x/(1-2*x) + x^2/(1-2*x)/(Q(0)-x) where Q(k) = 1 - x/(x*k+1)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Feb 23 2013 G.f.: G(0)/2 - 1, where G(k) = 1 + 1/( 1 - x/(x + (1-x)^2/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jul 16 2013 G.f.: x*G(0)/(2-3*x), where G(k) = 1 + 1/( 1 - x*(5*k-9)/(x*(5*k-4) - 6/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jul 17 2013 a(n) = U(n-1,3/2) where U(n-1,x) is Chebyshev polynomial of the second kind. - Milan Janjic, Jan 25 2015 The o.g.f. A(x) satisfies A(x) + A(-x) + 6*A(x)*A(-x) = 0. The o.g.f. for A004187 equals -A(sqrt(x))*A(-sqrt(x)). - Peter Bala, Apr 02 2015 For n > 1, a(n) = (3*F(n+1)^2 + 2*F(n-2)*F(n+1) - F(n-2)^2)/4. - J. M. Bergot, Feb 16 2016 For n > 3, a(n) = floor(MA) - 4 for n even and floor(MA) + 5 for n odd. MA is the maximum area of a quadrilateral with lengths of sides in order L(n), L(n), F(n-3), F(n+3), with L(n)= A000032(n). The ratio of the longer diagonal to the shorter approaches 5/3. - J. M. Bergot, Feb 16 2016 a(n+1) = Sum_{j=0..n} Sum_{k=0..j} binomial(n-j,k)*binomial(j,k)*2^(j-k). - Tony Foster III, Sep 18 2017 a(n) = Sum_{k=0..n-1} Sum_{i=0..n-1} C(k+i,k-i). - Wesley Ivan Hurt, Sep 21 2017 a(n) = H(2*n, 1, 1/2) for n > 0 where H(n, a, b) -> hypergeom([a - n/2, b - n/2], [1 - n], -4). - Peter Luschny, Sep 03 2019 a(n) = -2/(sqrt(5)*tan(2*arctan(phi^(2*n)))), where phi = A001622 is the golden ratio. - Diego Rattaggi, Nov 21 2021 a(n) = sinh(2*n*arcsinh(1/2))/sqrt(5/4). - Peter Luschny, May 21 2022
EXAMPLE
G.f. = x + 3*x^2 + 8*x^3 + 21*x^4 + 55*x^5 + 144*x^6 + 377*x^7 + 987*x^8 + ...
a(3) = 8 because there are exactly 8 idempotent order-preserving full transformations on a 3-element chain, namely: (1,2,3)->(1,1,1),(1,2,3)->(2,2,2),(1,2,3)->(3,3,3),(1,2,3)->(1,1,3),(1,2,3)->(2,2,3),(1,2,3)->(1,2,2),(1,2,3)->(1,3,3),(1,2,3)->(1,2,3)-mappings are coordinate-wise. - Abdullahi Umar, Sep 08 2008
MAPLE
with(combstruct): SeqSeqSeqL := [T, {T=Sequence(S, card > 0), S=Sequence(U, card > 1), U=Sequence(Z, card >0)}, unlabeled]: seq(count(SeqSeqSeqL, size=n+1), n=0..28); # Zerinvary Lajos, Apr 04 2009 H := (n, a, b) -> hypergeom([a - n/2, b - n/2], [1 - n], -4):
a := n -> `if`(n = 0, 0, H(2*n, 1, 1/2)):
combinat[fibonacci](2*n) ;
end proc:
MATHEMATICA
f[n_] := Fibonacci[2n]; Array[f, 28, 0] (* or *)
Take[Fibonacci[Range[0, 60]], {1, -1, 2}] (* Harvey P. Dale, May 23 2012 *) CoefficientList[Series[(x)/(1 - 3x + x^2), {x, 0, 30}], x] (* Vincenzo Librandi, Sep 10 2014 *)
PROG
(PARI) {a(n) = subst( poltchebi(n+1)*4 - poltchebi(n)*6, x, 3/2)/5}; /* Michael Somos, Dec 06 2002 */ (PARI) {a(n) = polchebyshev( n-1, 2, 3/2)}; /* Michael Somos Jun 18 2011 */ (Sage) [lucas_number1(n, 3, 1) for n in range(27)] # Zerinvary Lajos, Jun 25 2008 (Sage) [fibonacci(2*n) for n in range(0, 28)] # Zerinvary Lajos, May 15 2009 (MuPAD) numlib::fibonacci(2*n) $ n = 0..35; // Zerinvary Lajos, May 09 2008 (Haskell)
a001906 n = a001906_list !! n
a001906_list =
0 : 1 : zipWith (-) (map (* 3) $ tail a001906_list) a001906_list
(Python)
def a(n, adict={0:0, 1:1}):
if n in adict:
return adict[n]
adict[n]=3*a(n-1) - a(n-2)
(Maxima) makelist(fib(2*n), n, 0, 30); /* Martin Ettl, Oct 21 2012 */
Powers of 10: a(n) = 10^n.
+10
390
1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 10000000000, 100000000000, 1000000000000, 10000000000000, 100000000000000, 1000000000000000, 10000000000000000, 100000000000000000, 1000000000000000000
COMMENTS
Same as Pisot sequences E(1, 10), L(1, 10), P(1, 10), T(1, 10). Essentially same as Pisot sequences E(10, 100), L(10, 100), P(10, 100), T(10, 100). See A008776 for definitions of Pisot sequences. The compositions of n in which each natural number is colored by one of p different colors are called p-colored compositions of n. For n >= 1, a(n) equals the number of 10-colored compositions of n such that no adjacent parts have the same color. - Milan Janjic, Nov 17 2011 Smallest n+1 digit number greater than 0 (with offset 0). - Wesley Ivan Hurt, Jan 17 2014
REFERENCES
Philip Morrison et al., Powers of Ten, Scientific American Press, 1982 and later editions.
S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 55.
LINKS
Eric Weisstein's World of Mathematics, 10
FORMULA
a(n) = 10^n.
a(n) = 10*a(n-1).
G.f.: 1/(1-10*x).
E.g.f.: exp(10*x).
PROG
(Haskell)
a011557 = (10 ^)
a011557_list = iterate (* 10) 1
(Python)
CROSSREFS
Cf. A178501: this sequence with 0 prefixed.
EXTENSIONS
Links to "Powers of Ten" books and videos added by N. J. A. Sloane, Nov 07 2009
Powers of 5: a(n) = 5^n.
(Formerly M3937 N1620)
+10
311
1, 5, 25, 125, 625, 3125, 15625, 78125, 390625, 1953125, 9765625, 48828125, 244140625, 1220703125, 6103515625, 30517578125, 152587890625, 762939453125, 3814697265625, 19073486328125, 95367431640625, 476837158203125, 2384185791015625, 11920928955078125
COMMENTS
Same as Pisot sequences E(1, 5), L(1, 5), P(1, 5), T(1, 5). Essentially same as Pisot sequences E(5, 25), L(5, 25), P(5, 25), T(5, 25). See A008776 for definitions of Pisot sequences. With interpolated zeros 0, 1, 0, 5, 0, 25, ... (g.f.: x/(1 - 5*x^2)) second inverse binomial transform of Fibonacci(3n)/Fibonacci(3) ( A001076). Binomial transform is A085449. - Paul Barry, Mar 14 2004 Sum of coefficients of expansion of (1 + x + x^2 + x^3 + x^4)^n. a(n) is number of compositions of natural numbers into n parts less than 5. a(2) = 25 there are 25 compositions of natural numbers into 2 parts less than 5. - Adi Dani, Jun 22 2011 The compositions of n in which each natural number is colored by one of p different colors are called p-colored compositions of n. For n >= 1, a(n) equals the number of 5-colored compositions of n such that no adjacent parts have the same color. - Milan Janjic, Nov 17 2011 Numbers n such that sigma(5n) = 5n + sigma(n). In fact we have this theorem: p is a prime if and only if all solutions of the equation sigma(p*x) = p*x + sigma(x) are powers of p. - Jahangeer Kholdi, Nov 23 2013 Empirical observation: Where n is an odd multiple of 3, let x = (a(n) + 1)/9 and let y be the decimal expansion of x/a(n); then y*(x+1)/x + 1 = y rotated to the left.
Example:
a(3) = 125;
x = (125 + 1)/9 = 14;
y = 112, which is the decimal expansion of 14/125 = 0.112;
112*(14 + 1)/14 + 1 = 121 = 112 rotated to the left.
(End)
a(n) is the number of n-digit integers that contain only odd digits ( A014261). - Bernard Schott, Nov 12 2022 Number of pyramids in the Sierpinski fractal square-based pyramid at the n-th step, while A279511 gives the corresponding number of vertices (see IREM link with drawings). - Bernard Schott, Nov 29 2022
REFERENCES
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).
FORMULA
a(n) = 5^n.
a(0) = 1; a(n) = 5*a(n-1) for n > 0.
G.f.: 1/(1 - 5*x).
E.g.f.: exp(5*x).
Sum_{n>=0} 1/a(n) = 5/4.
Sum_{n>=0} (-1)^n/a(n) = 5/6. (End)
PROG
(Haskell)
a000351 = (5 ^)
(Maxima) makelist(5^n, n, 0, 20); /* Martin Ettl, Dec 27 2012 */ (Scala) (List.fill(50)(5: BigInt)).scanLeft(1: BigInt)(_ * _) // Alonso del Arte, May 31 2019 (Python)
def a(n): return 5**n
CROSSREFS
Sierpinski fractal square-based pyramid: A020858 (Hausdorff dimension), A279511 (number of vertices), this sequence (number of pyramids).
a(n) = 3*2^n.
(Formerly M2561)
+10
242
3, 6, 12, 24, 48, 96, 192, 384, 768, 1536, 3072, 6144, 12288, 24576, 49152, 98304, 196608, 393216, 786432, 1572864, 3145728, 6291456, 12582912, 25165824, 50331648, 100663296, 201326592, 402653184, 805306368, 1610612736, 3221225472, 6442450944, 12884901888
COMMENTS
Same as Pisot sequences E(3, 6), L(3, 6), P(3, 6), T(3, 6). See A008776 for definitions of Pisot sequences. Also least number m such that 2^n is the smallest proper divisor of m which is also a suffix of m in binary representation, see A080940. - Reinhard Zumkeller, Feb 25 2003 Length of the period of the sequence Fibonacci(k) (mod 2^(n+1)). - Benoit Cloitre, Mar 12 2003 Total number of Latin n-dimensional hypercubes (Latin polyhedra) of order 3. - Kenji Ohkuma (k-ookuma(AT)ipa.go.jp), Jan 10 2007
Number of different ternary hypercubes of dimension n. - Edwin Soedarmadji (edwin(AT)systems.caltech.edu), Dec 10 2005
For n >= 1, a(n) is equal to the number of functions f:{1, 2, ..., n + 1} -> {1, 2, 3} such that for fixed, different x_1, x_2,...,x_n in {1, 2, ..., n + 1} and fixed y_1, y_2,...,y_n in {1, 2, 3} we have f(x_i) <> y_i, (i = 1,2,...,n). - Milan Janjic, May 10 2007 a(n) written in base 2: 11, 110, 11000, 110000, ..., i.e.: 2 times 1, n times 0 (see A003953). - Jaroslav Krizek, Aug 17 2009 Numbers containing the number 3 in their Collatz trajectories. - Reinhard Zumkeller, Feb 20 2012 a(n-1) gives the number of ternary numbers with n digits with no two adjacent digits in common; e.g., for n=3 we have 010, 012, 020, 021, 101, 102, 120, 121, 201, 202, 210 and 212. - Jon Perry, Oct 10 2012 If n > 1, then a(n) is a solution for the equation sigma(x) + phi(x) = 3x-4. This equation also has solutions 84, 3348, 1450092, ... which are not of the form 3*2^n. - Farideh Firoozbakht, Nov 30 2013 a(n) is the upper bound for the "X-ray number" of any convex body in E^(n + 2), conjectured by Bezdek and Zamfirescu, and proved in the plane E^2 (see the paper by Bezdek and Zamfirescu). - L. Edson Jeffery, Jan 11 2014 If T is a topology on a set V of size n and T is not the discrete topology, then T has at most 3 * 2^(n-2) many open sets. See Brown and Stephen references. - Ross La Haye, Jan 19 2014 Comment from Charles Fefferman, courtesy of Doron Zeilberger, Dec 02 2014: (Start) Fix a dimension n. For a real-valued function f defined on a finite set E in R^n, let Norm(f, E) denote the inf of the C^2 norms of all functions F on R^n that agree with f on E. Then there exist constants k and C depending only on the dimension n such that Norm(f, E) <= C*max{ Norm(f, S) }, where the max is taken over all k-point subsets S in E. Moreover, the best possible k is 3 * 2^(n-1).
The analogous result, with the same k, holds when the C^2 norm is replaced, e.g., by the C^1, alpha norm (0 < alpha <= 1). However, the optimal analogous k, e.g., for the C^3 norm is unknown.
For the above results, see Y. Brudnyi and P. Shvartsman (1994). (End)
Also, coordination sequence for (infinity, infinity, infinity) tiling of hyperbolic plane. - N. J. A. Sloane, Dec 29 2015 The average of consecutive powers of 2 beginning with 2^1. - Melvin Peralta and Miriam Ong Ante, May 14 2016 For n > 1, a(n) is the smallest Zumkeller number with n divisors that are also Zumkeller numbers ( A083207). - Ivan N. Ianakiev, Dec 09 2016 Also, for n >= 2, the number of length-n strings over the alphabet {0,1,2,3} having only the single letters as nonempty palindromic subwords. (Corollary 21 in Fleischer and Shallit) - Jeffrey Shallit, Dec 02 2019 Also, a(n) is the minimum link-length of any covering trail, circuit, path, and cycle for the set of the 2^(n+2) vertices of an (n+2)-dimensional hypercube. - Marco Ripà, Aug 22 2022 The finite subsequence a(3), a(4), a(5), a(6) = 24, 48, 96, 192 is one of only two geometric sequences that can be formed with all interior angles (all integer, in degrees) of a simple polygon. The other sequence is a subsequence of A000244 (see comment there). - Felix Huber, Feb 15 2024 A level 1 Sierpiński triangle is a triangle. Level n+1 is formed from three copies of level n by identifying pairs of corner vertices of each pair of triangles. For n>2, a(n-3) is the radius of the level n Sierpiński triangle graph. - Allan Bickle, Aug 03 2024
REFERENCES
Jason I. Brown, Discrete Structures and Their Interactions, CRC Press, 2013, p. 71.
T. Ito, Method, equipment, program and storage media for producing tables, Publication number JP2004-272104A, Japan Patent Office (written in Japanese, a(2)=12, a(3)=24, a(4)=48, a(5)=96, a(6)=192, a(7)=384 (a(7)=284 was corrected)).
Kenji Ohkuma, Atsuhiro Yamagishi and Toru Ito, Cryptography Research Group Technical report, IT Security Center, Information-Technology Promotion Agency, JAPAN.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
FORMULA
G.f.: 3/(1-2*x).
a(n) = 2*a(n - 1), n > 0; a(0) = 3.
a(n) = Sum_{k = 0..n} (-1)^(k reduced (mod 3))*binomial(n, k). - Benoit Cloitre, Aug 20 2002 a(n) = abs(b(n) - b(n+3)) with b(n) = (-1)^n* A084247(n). (End)
PROG
(PARI) a(n)=3*2^n
(Haskell)
a007283 = (* 3) . (2 ^)
a007283_list = iterate (* 2) 3
(Scala) (List.fill(40)(2: BigInt)).scanLeft(1: BigInt)(_ * _).map(3 * _) // Alonso del Arte, Nov 28 2019 (Python)
CROSSREFS
Coordination sequences for triangular tilings of hyperbolic space: A001630, A007283, A054886, A078042, A096231, A163876, A179070, A265057, A265058, A265059, A265060, A265061, A265062, A265063, A265064, A265065, A265066, A265067, A265068, A265069, A265070, A265071, A265072, A265073, A265074, A265075, A265076, A265077. Subsequence of the following sequences: A029744, A029747, A029748, A029750, A362804 (after 3), A364494, A364496, A364289, A364291, A364292, A364295, A364497, A364964, A365422. Row sums of (5, 1)-Pascal triangle A093562 and of (1, 5) Pascal triangle A096940.
Powers of 6: a(n) = 6^n.
(Formerly M4224 N1765)
+10
174
1, 6, 36, 216, 1296, 7776, 46656, 279936, 1679616, 10077696, 60466176, 362797056, 2176782336, 13060694016, 78364164096, 470184984576, 2821109907456, 16926659444736, 101559956668416, 609359740010496, 3656158440062976, 21936950640377856, 131621703842267136
COMMENTS
Same as Pisot sequences E(1, 6), L(1, 6), P(1, 6), T(1, 6). Essentially same as Pisot sequences E(6, 36), L(6, 36), P(6, 36), T(6, 36). See A008776 for definitions of Pisot sequences. Sum of coefficients of expansion of (1 + x + x^2 + x^3 + x^4 + x^5)^n.
a(n) is number of compositions of natural numbers into n parts less than 6. For example, a(2) = 36, and there are 36 compositions of natural numbers into 2 parts less than 6.
The compositions of n in which each part is colored by one of p different colors are called p-colored compositions of n. For n >= 1, a(n) equals the number of 5-colored compositions of n such that no adjacent parts have the same color.
Number of words of length n over the alphabet of six letters. - Joerg Arndt, Sep 16 2014 The number of ordered triples (x, y, z) of binary words of length n such that D(x,z) = D(x, y) + D(y, z) where D(a, b) is the Hamming distance from a to b. - Geoffrey Critzer, Mar 06 2017 a(n) is the area of a triangle with vertices at (2^n, 3^n), (2^(n+1), 3^(n+1)), and (2^(n+2), 3^(n+2)); a(n) is also one fifth the area of a triangle with vertices at (2^n, 3^(n+2)), (2^(n+1), 3^(n+1)), and (2^(n+2), 3^n). - J. M. Bergot, May 07 2018 a(n) is the number of possible outcomes of n distinguishable 6-sided dice. - Stefano Spezia, Jul 06 2024
REFERENCES
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).
FORMULA
a(n) = 6^n.
a(0) = 1; a(n) = 6*a(n-1).
E.g.f.: exp(6*x).
a(n) = det(|s(i+3,j)|, 1 <= i,j <= n), where s(n,k) are Stirling numbers of the first kind. - Mircea Merca, Apr 04 2013
PROG
(Haskell)
a000400 = (6 ^)
(Scala) (List.fill(50)(6: BigInt)).scanLeft(1: BigInt)(_ * _) // Alonso del Arte, May 31 2019
Search completed in 0.124 seconds
| 
