A024023 a(n) = 3^n - 1.

0, 2, 8, 26, 80, 242, 728, 2186, 6560, 19682, 59048, 177146, 531440, 1594322, 4782968, 14348906, 43046720, 129140162, 387420488, 1162261466, 3486784400, 10460353202, 31381059608, 94143178826, 282429536480, 847288609442, 2541865828328, 7625597484986, 22876792454960

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Comments

Number of different directions along lines and hyper-diagonals in an n-dimensional cubic lattice for the attacking queens problem (A036464 in n=2, A068940 in n=3 and A068941 in n=4). The n-dimensional direction vectors have the a(n)+1 Cartesian coordinates (i,j,k,l,...) where i,j,k,l,... = -1, 0, or +1, excluding the zero-vector i=j=k=l=...=0. The corresponding hyper-line count is A003462. - R. J. Mathar, May 01 2006

Total number of sequences of length m=1,...,n with nonzero integer elements satisfying the condition Sum_{k=1..m} |n_k| <= n. See the K. A. Meissner link p. 6 (with a typo: it should be 3^([2a]-1)-1). - Wolfdieter Lang, Jan 21 2008

Let P(A) be the power set of an n-element set A and R be a relation on P(A) such that for all x, y of P(A), xRy if x and y are disjoint and either 0) x is a proper subset of y or y is a proper subset of x, or 1) x is not a subset of y and y is not a subset of x. Then a(n) = |R|. - Ross La Haye, Mar 19 2009

Number of neighbors in Moore's neighborhood in n dimensions. - Dmitry Zaitsev, Nov 30 2015

Number of terms in conjunctive normal form of Boolean expression with n variables. E.g., a(2) = 8: [~x, ~y, x, y, ~x|~y, ~x|y, x|~y, x|y]. - Yuchun Ji, May 12 2023

Number of rays of the Coxeter arrangement of type B_n. Equivalently, number of facets of the n-dimensional type B permutahedron. - Jose Bastidas, Sep 12 2023

Examples

			From _Zerinvary Lajos_, Jan 14 2007: (Start)
Ternary......decimal:
0...............0
2...............2
22..............8
222............26
2222...........80
22222.........242
222222........728
2222222......2186
22222222.....6560
222222222...19682
2222222222..59048
etc...........etc.
(End)
Sequence combinatorics: n=3: With length m=1: [1],[2],[3] each with 2 signs, with m=2: [1,1], [1,2], [2,1], each 2^2 = 4 times from choosing signs; m=3: [1,1,1] coming in 2^3 signed versions: 3*2 + 3*4 + 1*8 = 26 = a(3). The order is important, hence the M_0 multinomials A048996 enter as factors.
A027902 gives the 384 divisors of a(24). - _Reinhard Zumkeller_, Mar 11 2010
		

References

• Mordechai Ben-Ari, Mathematical Logic for Computer Science, Third edition, 173-203.

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..200
• Omran Ahmadi and Robert Granger, An efficient deterministic test for Kloosterman sum zeros, Mathematics of Computation, Vol. 83, No. 285 (2014), pp. 347-363; arXiv preprint, arXiv:1104.3882 [math.NT], 2011-2012. See 1st column of Table 2, p. 9.
• Feryal Alayont and Evan Henning, Edge Covers of Caterpillars, Cycles with Pendants, and Spider Graphs, J. Int. Seq. (2023) Vol. 26, Art. 23.9.4.
• Michael Baake, Franz Gähler, and Uwe Grimm, Examples of Substitution Systems and Their Factors, Journal of Integer Sequences, Vol. 16 (2013), #13.2.14.
• R. Samuel Buss, Herbrand's Theorem, University of California, Logic and Computational Complexity pp. 195-209, Lecture Notes in Computer Science, vol 960. Springer.
• Jan Draisma, Tyrrell B. McAllister and Benjamin Nill, Lattice width directions and Minkowski's 3^d-theorem, SIAM J. Discrete Math., Vol. 26, No. 3 (2012), pp. 1104-1107; arXiv preprint, arXiv:0901.1375 [math.CO], Jan 10 2009.
• Alessandro Farinelli, Herbrand Universe and Herbrand Base.
• 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.
• Krzysztof A. Meissner, Black hole entropy in Loop Quantum Gravity, Classical and Quantum Gravity, Vol. 21, No. 22 (2004), pp. 5245--5251; arXiv preprint, arXiv:gr-qc/0407052, 2004.
• Amir Sapir, The Tower of Hanoi with Forbidden Moves, The Computer J. 47 (1) (2004) 20, case three-in-a row, sequence b(n).
• Steven Schlicker, Roman Vasquez, and Rachel Wofford, Integer Sequences from Configurations in the Hausdorff Metric Geometry via Edge Covers of Bipartite Graphs, J. Int. Seq. (2023) Vol. 26, Art. 23.6.6.
• Amelia Carolina Sparavigna, The groupoids of Mersenne, Fermat, Cullen, Woodall and other Numbers and their representations by means of integer sequences, Politecnico di Torino, Italy (2019), [math.NT].
• Amelia Carolina Sparavigna, Some Groupoids and their Representations by Means of Integer Sequences, International Journal of Sciences (2019) Vol. 8, No. 10.
• Wikipedia, Herbrand Structure.
• Damiano Zanardini, Computational Logic, Slides, UPM European Master in Computational Logic (EMCL) School of Computer Science Technical University of Madrid, 2009-2010.
• Index entries for linear recurrences with constant coefficients, signature (4,-3).

Crossrefs

Cf. triangle A013609.

Cf. A003462, A007051, A034472, A214369.

Cf. second column of A145901.

Programs

Haskell

a024023 = subtract 1 . a000244  -- Reinhard Zumkeller, Jun 30 2013

Magma

[3^n-1: n in [0..35]]; // Vincenzo Librandi, Apr 30 2011

Mathematica

3^Range[0,30]-1 (* Paolo Xausa, Jul 15 2023 *)

PARI

a(n)=3^n-1 \\ Charles R Greathouse IV, Sep 24 2015

PARI

vector(50, n, sum(k=0, n, 2^k*binomial(n-1, k))-1) \\ Altug Alkan, Oct 04 2015

PARI

my(x='x+O('x^100)); concat([0], Vec(2*x/(-1+x)/(-1+3*x))) \\ Altug Alkan, Oct 16 2015

Formula

a(n) = A000244(n) - 1.

a(n) = 2*A003462(n). - R. J. Mathar, May 01 2006

A128760(a(n)) > 0. - Reinhard Zumkeller, Mar 25 2007

G.f.: 2*x/((-1+x)*(-1+3*x)) = 1/(-1+x) - 1/(-1+3*x). - R. J. Mathar, Nov 19 2007

a(n) = Sum_{k=1..n} Sum_{m=1..k} binomial(k-1,m-1)*2^m, n >= 1. a(0)=0. From the sequence combinatorics mentioned above. Twice partial sums of powers of 3.

E.g.f.: e^(3*x) - e^x. - Mohammad K. Azarian, Jan 14 2009

a(n) = A024101(n)/A034472(n). - Reinhard Zumkeller, Feb 14 2009

a(n) = 3*a(n-1) + 2 (with a(0)=0). - Vincenzo Librandi, Nov 19 2010

E.g.f.: -E(0) where E(k) = 1 - 3^k/(1 - x/(x - 3^k*(k+1)/E(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Dec 06 2012

a(n) = A227048(n,A020914(n)). - Reinhard Zumkeller, Jun 30 2013

Sum_{n>=1} 1/a(n) = A214369. - Amiram Eldar, Nov 11 2020

a(n) = Sum_{k=1..n} 2^k*binomial(n,k). - Ridouane Oudra, Jun 15 2025

From Peter Bala, Jul 01 2025: (Start)

For n >= 1, a(2*n)/a(n) = A034472(n) and a(3*n)/a(n) = A034513(n).

Modulo differences in offsets, exp( Sum_{n >= 1} a(k*n)/a(n)*x^n/n ) is the o.g.f. of A003462 (k = 2), A006100 (k = 3), A006101 (k = 4), A006102 (k = 5), A022196 (k = 6), A022197 (k = 7), A022198 (k = 8), A022199 (k = 9), A022200 (k = 10), A022201 (k = 11), A022202 (k = 12) and A022203 (k = 13).

The following are all examples of telescoping series:

Sum_{n >= 1} 3^n/(a(n)*a(n+1)) = 1/2^2; Sum_{n >= 1} 3^n/(a(n)*a(n+1)*a(n+2)) = 1/(2*8^2).

In general, for k >= 1, Sum_{n >= 1} 3^n/(a(n)*a(n+1)*...*a(n+k)) = 1/(a(1)*a(2)*...*a(k)*a(k)).

Sum_{n >= 1} 3^n/(a(n)*a(n+2)) = 5/64; Sum_{n >= 1} (-3)^n/(a(n)*a(n+2)) = -3/64.

Sum_{n >= 1} 3^n/(a(n)*a(n+4)) = 703/83200; Sum_{n >= 1} (-3)^n/(a(n)*a(n+4)) = - 417/83200. (End)