A027649 a(n) = 2*(3^n) - 2^n.

1, 4, 14, 46, 146, 454, 1394, 4246, 12866, 38854, 117074, 352246, 1058786, 3180454, 9549554, 28665046, 86027906, 258149254, 774578834, 2323998646, 6972520226, 20918609254, 62757924914, 188277969046, 564842295746, 1694543664454, 5083664547794, 15251060752246

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

Poly-Bernoulli numbers B_n^(k) with k=-2.

Binomial transform of A007051, if both sequences start at 0. Binomial transform of A000225(n+1). - Paul Barry, Mar 24 2003

Euler expands (1-z)/(1-5z+6z^2) and finds the general term. Section 226 of the Introductio indicates that he could have written down the recursion relation: a(n) = 5 a(n-1)-6 a(n-2). - V. Frederick Rickey (fred-rickey(AT)usma.edu), Feb 10 2006

Let R 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), xRy if x is a subset of y or y is a subset of x. Then a(n) = |R|. - Ross La Haye, Dec 22 2006

With regard to the comment by Ross La Haye: For proper subsets see A056182. - For nonempty subsets see A091344. - For nonempty proper subsets see a(n+1) in A260217. - Manfred Boergens, Aug 02 2023

If x, y are two n-bit binary strings then a(n) gives the number of pairs (x,y) such that XOR(x, y) = ABS(x - y). - Ramasamy Chandramouli, Feb 15 2009

Equals row sums of the triangular version of A038573. - Gary W. Adamson, Jun 04 2009

Inverse binomial transform of A085350. - Paul Curtz, Nov 14 2009

Related to the number of even a's in a nontrivial cycle (should one exist) in the 3x+1 Problem, where a <= floor(log_2(2*(3^n) - 2^n)). The value n correlates to the number of odds in such a nontrivial cycle. See page 1288 of Crandall's paper. Also, this relation gives another proof that the number of odds divided by the number of evens in a nontrivial cycle is bounded by log 2 / log 3 (this observation does not resolve the finite cycles conjecture as the value could be arbitrarily close to this bound). However, the same argument gives that log 2 / log 3 is less than or equal to the number of odds divided by the number of evens in a divergent sequence (should one exist), as log 2 / log 3 is the limit value for a cycle of an arbitrarily large length, where the length is given by the value n. - Jeffrey R. Goodwin, Aug 04 2011

Row sums of Riordan triangle A106516. - Wolfdieter Lang, Jan 09 2015

Number of restricted barred preferential arrangements having 3 bars in which the sections are all restricted sections such that (for fixed sections i and j) section i or section j is empty. - Sithembele Nkonkobe, Oct 12 2015

This is also row 2 of A281891: for n >= 1, when consecutive positive integers are written as a product of primes in nondecreasing order, a factor of 2 or 3 occurs in n-th position a(n) times out of every 6^n. - Peter Munn, May 18 2017

Also row sums of A124929. - Omar E. Pol, Jun 15 2017

This is the sum of A318921(n) for n in the range 2^(k+1) to 2^(k+2)-1. See A318921 for proof. - N. J. A. Sloane, Sep 25 2018

a(n) is also the number of acyclic orientations of the complete bipartite graph K_{2,n}. - Vincent Pilaud, Sep 15 2020

a(n-1) is also the number of n-digit numbers whose largest decimal digit is 2. - Stefano Spezia, Nov 15 2023

References

• Leonhard Euler, Introductio in analysin infinitorum (1748), section 216.

Links

• T. D. Noe, Table of n, a(n) for n = 0..200
• Taylor Brysiewicz, Holger Eble, and Lukas Kühne, Enumerating chambers of hyperplane arrangements with symmetry, arXiv:2105.14542 [math.CO], 2021.
• R. E. Crandall, On the 3x+1 problem, Math. Comp., 32 (1978) 1281-1292.
• Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, A Meta-Algorithm for Creating Fast Algorithms for Counting ON Cells in Odd-Rule Cellular Automata, arXiv:1503.01796 [math.CO], 2015; see also the Accompanying Maple Package.
• Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, Odd-Rule Cellular Automata on the Square Grid, arXiv:1503.04249 [math.CO], 2015.
• John Elias, Illustration of initial terms: Reflected Sierpinski triangle
• K. Imatomi, M. Kaneko, and E. Takeda, Multi-Poly-Bernoulli Numbers and Finite Multiple Zeta Values, J. Int. Seq. 17 (2014) # 14.4.5
• Ken Kamano, Sums of Products of Poly-Bernoulli Numbers of Negative Index, Journal of Integer Sequences, Vol. 15 (2012), #12.1.3.
• K. Kamano, Sums of Products of Bernoulli Numbers, Including Poly-Bernoulli Numbers, J. Int. Seq. 13 (2010), 10.5.2.
• Masanobu Kaneko, Poly-Bernoulli numbers, Journal de théorie des nombres de Bordeaux, 9 no. 1 (1997), Pages 221-228.
• Takao Komatsu, Some recurrence relations of poly-Cauchy numbers, J. Nonlinear Sci. Appl., (2019) Vol. 12, Issue 12, 829-845.
• Ross La Haye, Binary Relations on the Power Set of an n-Element Set, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.
• S. Nkonkobe and V. Murali, On some properties and relations between restricted barred preferential arrangements, multi-poly-bernoulli numbers and related numbers, arXiv:1509.07352 [math.CO], 2015.
• Eric Weisstein's World of Mathematics, Sierpinski Sieve
• Wikipedia, Sierpinski triangle
• Index entries for sequences related to Bernoulli numbers.
• Index entries for linear recurrences with constant coefficients, signature (5,-6).

Crossrefs

Row n = 2 of array A099594.

Also occurs as a row, column, diagonal or as row sums in A038573, A085870, A090888, A106516, A217764, A281891.

Cf. A000079, A000225, A001047, A007051, A053581, A056182, A085350, A091344, A124929, A166060, A260217, A318921.

Programs

Haskell

a027649 n = a027649_list !! n
a027649_list = map fst $ iterate (\(u, v) -> (3 * u + v, 2 * v)) (1, 1)
-- Reinhard Zumkeller, Jun 09 2013

Magma

[2*(3^n)-2^n: n in [0..30]]; // Vincenzo Librandi, Jul 17 2011

Maple

a(n, k):= (-1)^n*sum( (-1)^'m'*'m'!*Stirling2(n,'m')/('m'+1)^k,'m'=0..n);
seq(a(n, -2), n=0..30);

Mathematica

Table[2(3^n)-2^n,{n,0,30}] (* or *) LinearRecurrence[ {5,-6},{1,4},31]  (* Harvey P. Dale, Apr 22 2011 *)

PARI

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

PARI

Vec((1-x)/((1-2*x)*(1-3*x)) + O(x^50)) \\ Altug Alkan, Oct 12 2015

SageMath

[2*(3^n - 2^(n-1)) for n in (0..30)] # G. C. Greubel, Aug 01 2022

Formula

G.f.: (1-x)/((1-2*x)*(1-3*x)).

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

a(n) = Sum_{k=0..n} binomial(n, k)*(2^(k+1) - 1). - Paul Barry, Mar 24 2003

Partial sums of A053581. - Paul Barry, Jun 26 2003

Main diagonal of array (A085870) defined by T(i, 1) = 2^i - 1, T(1, j) = 2^j - 1, T(i, j) = T(i-1, j) + T(i-1, j-1). - Benoit Cloitre, Aug 05 2003

a(n) = A090888(n, 3). - Ross La Haye, Sep 21 2004

a(n) = Sum_{k=0..n} binomial(n+2, k+1)*Sum_{j=0..floor(k/2)} A001045(k-2j). - Paul Barry, Apr 17 2005

a(n) = Sum_{k=0..n} Sum_{j=0..n} binomial(n,j)*binomial(j+1,k+1). - Paul Barry, Sep 18 2006

a(n) = A166060(n+1)/6. - Philippe Deléham, Oct 21 2009

a(n) = 5*a(n-1) - 6*a(n-2), a(0)=1, a(1)=4. - Harvey P. Dale, Apr 22 2011

a(n) = A217764(n,2). - Ross La Haye, Mar 27 2013

For n>0, a(n) = 3 * a(n-1) + 2^(n-1) = 2 * (a(n-1) + 3^(n-1)). - J. Conrad, Oct 29 2015

for n>0, a(n) = 2 * (1 + 2^(n-2) + Sum_{x=1..n-2} Sum_{k=0..x-1} (binomial(x-1,k)*(2^(k+1) + 2^(n-x+k)))). - J. Conrad, Dec 10 2015

E.g.f.: exp(2*x)*(2*exp(x) - 1). - Stefano Spezia, May 18 2024

Extensions

Better formulas from David W. Wilson and Michael Somos

Incorrect formula removed by Charles R Greathouse IV, Mar 18 2010

Duplications (due to corrections to A numbers) removed by Peter Munn, Jun 15 2017