%I #214 Feb 07 2024 01:18:12
%S 0,2,8,26,80,242,728,2186,6560,19682,59048,177146,531440,1594322,
%T 4782968,14348906,43046720,129140162,387420488,1162261466,3486784400,
%U 10460353202,31381059608,94143178826,282429536480,847288609442,2541865828328,7625597484986,22876792454960
%N a(n) = 3^n - 1.
%C 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
%C 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
%C 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
%C Number of neighbors in Moore's neighborhood in n dimensions. - _Dmitry Zaitsev_, Nov 30 2015
%C 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
%C 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
%D Mordechai Ben-Ari, Mathematical Logic for Computer Science, Third edition, 173-203.
%H Vincenzo Librandi, <a href="/A024023/b024023.txt">Table of n, a(n) for n = 0..200</a>
%H Omran Ahmadi and Robert Granger, <a href="https://doi.org/10.1090/S0025-5718-2013-02705-6">An efficient deterministic test for Kloosterman sum zeros</a>, Mathematics of Computation, Vol. 83, No. 285 (2014), pp. 347-363; <a href="https://arxiv.org/abs/1104.3882">arXiv preprint</a>, arXiv:1104.3882 [math.NT], 2011-2012. See 1st column of Table 2, p. 9.
%H Feryal Alayont and Evan Henning, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Alayont/ala4.html">Edge Covers of Caterpillars, Cycles with Pendants, and Spider Graphs</a>, J. Int. Seq. (2023) Vol. 26, Art. 23.9.4.
%H Michael Baake, Franz Gähler, and Uwe Grimm, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Baake/baake3.html">Examples of Substitution Systems and Their Factors</a>, Journal of Integer Sequences, Vol. 16 (2013), #13.2.14.
%H R. Samuel Buss, <a href="http://math.ucsd.edu/~sbuss/ResearchWeb/herbrandtheorem/paper.pdf">Herbrand's Theorem</a>, University of California, Logic and Computational Complexity pp. 195-209, Lecture Notes in Computer Science, vol 960. Springer.
%H Jan Draisma, Tyrrell B. McAllister and Benjamin Nill, <a href="https://doi.org/10.1137/120877635">Lattice width directions and Minkowski's 3^d-theorem</a>, SIAM J. Discrete Math., Vol. 26, No. 3 (2012), pp. 1104-1107; <a href="http://arxiv.org/abs/0901.1375">arXiv preprint</a>, arXiv:0901.1375 [math.CO], Jan 10 2009. - Jonathan Vos Post, Jan 13 2009
%H Alessandro Farinelli, <a href="http://profs.sci.univr.it/~farinelli/courses/ar/slides/herbrand.pdf">Herbrand Universe and Herbrand Base</a>.
%H Ross La Haye, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/LaHaye/lahaye5.html">Binary Relations on the Power Set of an n-Element Set</a>, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.
%H Krzysztof A. Meissner, <a href="https://doi.org/10.1088/0264-9381/21/22/015">Black hole entropy in Loop Quantum Gravity</a>, Classical and Quantum Gravity, Vol. 21, No. 22 (2004), pp. 5245--5251; <a href="https://arxiv.org/abs/gr-qc/0407052">arXiv preprint</a>, arXiv:gr-qc/0407052, 2004.
%H Amir Sapir, <a href="https://doi.org/10.1093/comjnl/47.1.20">The Tower of Hanoi with Forbidden Moves</a>, The Computer J. 47 (1) (2004) 20, case three-in-a row, sequence b(n).
%H Steven Schlicker, Roman Vasquez, and Rachel Wofford, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Wofford/wofford4.html">Integer Sequences from Configurations in the Hausdorff Metric Geometry via Edge Covers of Bipartite Graphs</a>, J. Int. Seq. (2023) Vol. 26, Art. 23.6.6.
%H Amelia Carolina Sparavigna, <a href="https://doi.org/10.5281/zenodo.3471358">The groupoids of Mersenne, Fermat, Cullen, Woodall and other Numbers and their representations by means of integer sequences</a>, Politecnico di Torino, Italy (2019), [math.NT].
%H Amelia Carolina Sparavigna, <a href="https://doi.org/10.18483/ijSci.2188">Some Groupoids and their Representations by Means of Integer Sequences</a>, International Journal of Sciences (2019) Vol. 8, No. 10.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Herbrand_structure">Herbrand Structure</a>.
%H Damiano Zanardini, <a href="https://costa.fdi.ucm.es/~damiano/teaching/emcl/cl_09_10/slides/04interpretation.pdf">Computational Logic</a>, Slides, UPM European Master in Computational Logic (EMCL) School of Computer Science Technical University of Madrid, 2009-2010.
%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (4,-3).
%F a(n) = A000244(n) - 1.
%F a(n) = 2*A003462(n). - _R. J. Mathar_, May 01 2006
%F A128760(a(n)) > 0. - _Reinhard Zumkeller_, Mar 25 2007
%F G.f.: 2*x/((-1+x)*(-1+3*x)) = 1/(-1+x) - 1/(-1+3*x). - _R. J. Mathar_, Nov 19 2007
%F 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.
%F E.g.f.: e^(3*x) - e^x. - _Mohammad K. Azarian_, Jan 14 2009
%F a(n) = A024101(n)/A034472(n). - _Reinhard Zumkeller_, Feb 14 2009
%F a(n) = 3*a(n-1) + 2 (with a(0)=0). - _Vincenzo Librandi_, Nov 19 2010
%F 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
%F a(n) = A227048(n,A020914(n)). - _Reinhard Zumkeller_, Jun 30 2013
%F Sum_{n>=1} 1/a(n) = A214369. - _Amiram Eldar_, Nov 11 2020
%e From _Zerinvary Lajos_, Jan 14 2007: (Start)
%e Ternary......decimal:
%e 0...............0
%e 2...............2
%e 22..............8
%e 222............26
%e 2222...........80
%e 22222.........242
%e 222222........728
%e 2222222......2186
%e 22222222.....6560
%e 222222222...19682
%e 2222222222..59048
%e etc...........etc.
%e (End)
%e 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.
%e A027902 gives the 384 divisors of a(24). - _Reinhard Zumkeller_, Mar 11 2010
%t 3^Range[0,30]-1 (* _Paolo Xausa_, Jul 15 2023 *)
%o (Magma) [3^n-1: n in [0..35]]; // _Vincenzo Librandi_, Apr 30 2011
%o (Haskell)
%o a024023 = subtract 1 . a000244 -- _Reinhard Zumkeller_, Jun 30 2013
%o (PARI) a(n)=3^n-1 \\ _Charles R Greathouse IV_, Sep 24 2015
%o (PARI) vector(50, n, sum(k=0, n, 2^k*binomial(n-1, k))-1) \\ _Altug Alkan_, Oct 04 2015
%o (PARI) my(x='x+O('x^100)); concat([0], Vec(2*x/(-1+x)/(-1+3*x))) \\ _Altug Alkan_, Oct 16 2015
%Y Cf. triangle A013609.
%Y Cf. A003462, A007051, A034472, A214369.
%Y Cf. second column of A145901.
%K nonn,easy
%O 0,2
%A _N. J. A. Sloane_