A058481 a(n) = 3^n - 2.

1, 7, 25, 79, 241, 727, 2185, 6559, 19681, 59047, 177145, 531439, 1594321, 4782967, 14348905, 43046719, 129140161, 387420487, 1162261465, 3486784399, 10460353201, 31381059607, 94143178825, 282429536479, 847288609441

Offset: 1

Author

Vladeta Jovovic, Nov 26 2000

Keywords

• easy
• nonn
• nice

Comments

a(n) = number of 2 X n binary matrices with no zero rows or columns.

a(n)^2 + 2*a(n+1) + 1 is a square number, i.e., a(n)^2 + 2*a(n+1) + 1 = (a(n)+3)^2: for n=2, a(2)^2 + 2*a(3) + 1 = 7^2 + 2*25 + 1 = 100 = (7+3)^2; for n=3, a(3)^2 + 2*a(4) + 1 = 25^2 + 2*79 + 1 = 784 = (25+3)^2. - Bruno Berselli, Apr 23 2010

Sum of n-th row of triangle of powers of 3: 1; 3 1 3; 9 3 1 3 9; 27 9 3 1 3 9 27; ... . - Philippe Deléham, Feb 24 2014

a(n) = least k such that k*3^n + 1 is a square. Thus, the square is given by (3^n-1)^2. - Derek Orr, Mar 23 2014

Binomial transform of A058481: (1, 6, 12, 24, 48, 96, ...) and second binomial transform of (1, 5, 1, 5, 1, 5, ...). - Gary W. Adamson, Aug 24 2016

Number of ordered pairs of nonempty sets whose union is [n]. a(2) = 7: ({1,2},{1,2}), ({1,2},{1}), ({1,2},{2}), ({1},{1,2}), ({1},{2}), ({2},{1,2}), ({2},{1}). If "nonempty" is omitted we get A000244. - Manfred Boergens, Mar 29 2023

Examples

			G.f. = x + 7*x^2 + 25*x^3 + 79*x^4 + 241*x^5 + 727*x^6 + 2185*x^7 + 6559*x^8 + ...
a(1) = 1;
a(2) = 3 + 1 + 3 = 7;
a(3) = 9 + 3 + 1 + 3 + 9 = 25;
a(4) = 27 + 9 + 3 + 1 + 3 + 9 + 27 = 79; etc. - _Philippe Deléham_, Feb 24 2014
		

Links

• G. C. Greubel, Table of n, a(n) for n = 1..1000
• John Elias, Illustration: Union of Triple-Sierpinski Triangles
• Index entries for linear recurrences with constant coefficients, signature (4,-3).

Crossrefs

Cf. A055602, A024206 (unlabeled case), A055609, A058482, A000244.

Cf. A003462, A007051, A034472, A024023, A067771, A029858, A134931, A115099, A100774, A079004.

Programs

Maple

A058481:=n->3^n-2; seq(A058481(n), n=1..30); # Wesley Ivan Hurt, Mar 24 2014

Mathematica

a=1;lst={a};Do[a=a*3+4;AppendTo[lst,a],{n,0,5!}];lst (* Vladimir Joseph Stephan Orlovsky, Dec 25 2008 *)
3^Range[30]-2  (* Harvey P. Dale, Mar 28 2011 *)
LinearRecurrence[{4, -3}, {1, 7}, 25] (* G. C. Greubel, Aug 25 2016 *)

PARI

a(n)=3^n-2 \\ Charles R Greathouse IV, Feb 06 2017

PARI

{a(n) = if( n<1, 0, 3^n - 2)}; /* Michael Somos, Feb 17 2017 */

Formula

Number of m X n binary matrices with no zero rows or columns is Sum_{j=0..m} (-1)^j*C(m, j)*(2^(m-j)-1)^n.

From Mohammad K. Azarian, Jan 14 2009: (Start)

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

E.g.f.: e^(3*x)-2*(e^x)+1. (End)

a(n) = 3*a(n-1) + 4 (with a(1)=1). - Vincenzo Librandi, Aug 07 2010

a(n) = 4*a(n-1) - 3*a(n-2). - G. C. Greubel, Aug 25 2016

Extensions

More terms from Larry Reeves (larryr(AT)acm.org), Dec 04 2000