cp's OEIS Frontend

A028399 a(n) = 2^n - 4.

%I A028399 #111 Mar 24 2024 09:57:15
%S A028399 0,4,12,28,60,124,252,508,1020,2044,4092,8188,16380,32764,65532,
%T A028399 131068,262140,524284,1048572,2097148,4194300,8388604,16777212,
%U A028399 33554428,67108860,134217724,268435452,536870908,1073741820,2147483644,4294967292,8589934588,17179869180
%N A028399 a(n) = 2^n - 4.
%C A028399 Number of permutations of [n] with 2 sequences.
%C A028399 Number of 2 X n binary matrices that avoid simultaneously the right angled numbered polyomino patterns (ranpp) (00;1) and (11;0). An occurrence of a ranpp (xy;z) in a matrix A=(a(i,j)) is a triple (a(i1,j1), a(i1,j2), a(i2,j1)) where i1<i2, j1<j2 and these elements are in same relative order as those in the triple (x,y,z). - _Sergey Kitaev_, Nov 11 2004
%C A028399 The number of edges in the dual Edwards-Venn diagram graph with n-1 digits when n>2.
%C A028399 a(n) (n>=6) is the number of vertices in the molecular graph NS2[n-5], defined pictorially in the Ashrafi et al. reference (Fig. 2, where NS2[2] is shown). - _Emeric Deutsch_, May 16 2018
%C A028399 From _Petros Hadjicostas_, Aug 08 2019: (Start)
%C A028399 With regard to the comment above about a(n) being the "number of permutations of [n] with 2 sequences", we refer to Ex. 13 (pp. 260-261) of Comtet (1974), who uses the definition of a "séquence" given by André in several of his papers in the 19th century.
%C A028399 In the terminology of array A059427, these so-called "séquences" in permutations (defined by Comtet and André) are called "alternating runs" (or just "runs"). We discuss these so-called "séquences" below.
%C A028399 If b = (b_1, b_2, ..., b_n) is a permutation of [n], written in one-line notation (not in cycle notation), a "séquence" in a permutation of length l >= 2 (according to Comtet) is a maximal interval of integers {i, i+1, ..., i+l-1} for some i (where 1 <= i <= n-l+1) such that b_i < b_{i+1} < ... < b_{i+l-1} or b_i > b_{i+1} > ... > b_{i+l-1}. (The word "maximal" means that, in the first case, we have b_{i-1} > b_i and b_{i+l} < b_{i+l-1}, while in the second case, we have b_{i-1} < b_i and b_{i+l} > b_{i+l-1} provided b_{i-1} and b_{i+l} can be defined.)
%C A028399 When defining a "séquence", André (1884) actually refers to the list of terms (b_i, b_{i+1}, ..., b_{i+l-1}) rather than the corresponding index set {i, i+1, ..., i+l-1} (which is essentially the same thing).
%C A028399 For more details about these so-called "séquences" (or "alternate runs"), see the comments and examples for sequence A000708.
%C A028399 (End)
%C A028399 For n >= 1, a(n+2) is the number of shortest paths from (0,0) of a square grid to {(x,y): |x|+|y| = n} along the grid line. - _Jianing Song_, Aug 23 2021
%D A028399 L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 261.
%D A028399 A. W. F. Edwards, Cogwheels of the Mind, Johns Hopkins University Press, 2004, p. 82.
%H A028399 Muniru A Asiru, <a href="/A028399/b028399.txt">Table of n, a(n) for n = 2..700</a>
%H A028399 Désiré André, <a href="http://sites.mathdoc.fr/JMPA/PDF/JMPA_1881_3_7_A10_0.pdf">Sur les permutations alternées</a>, J. Math. Pur. Appl., 7 (1881), 167-184.
%H A028399 Désiré André, <a href="https://doi.org/10.24033/asens.235">Étude sur les maxima, minima et séquences des permutations</a>, Ann. Sci. Ecole Norm. Sup., 3, no. 1 (1884), 121-135.
%H A028399 Désiré André, <a href="http://sites.mathdoc.fr/JMPA/PDF/JMPA_1895_5_1_A7_0.pdf">Mémoire sur les permutations quasi-alternées</a>, Journal de mathématiques pures et appliquées 5e série, tome 1 (1895), 315-350.
%H A028399 Désiré André, <a href="https://doi.org/10.24033/bsmf.519">Mémoire sur les séquences des permutations circulaires</a>, Bulletin de la S. M. F., tome 23 (1895), pp. 122-184.
%H A028399 Ali Reza Ashrafi and Parisa Nikzad, <a href="http://www.chalcogen.ro/383_Ashrafi.pdf">Kekulé index and bounds of energy for nanostar dendrimers</a>, Digest J. of Nanomaterials and Biostructures, 4, No. 2, 2009, 383-388.
%H A028399 Sergey Kitaev, <a href="http://www.emis.de/journals/INTEGERS/papers/e21/e21.Abstract.html">On multi-avoidance of right angled numbered polyomino patterns</a>, Integers: Electronic Journal of Combinatorial Number Theory 4 (2004), A21, 20pp.
%H A028399 Sergey Kitaev, <a href="https://web.archive.org/web/20130625171839/http://www.ms.uky.edu/~math/MAreport/4-ser.ps">On multi-avoidance of right angled numbered polyomino patterns</a>, University of Kentucky Research Reports (2004).
%H A028399 László Németh, <a href="https://arxiv.org/abs/1701.06022">Pascal pyramid in the space H^2 x R</a>, arXiv:1701.06022 [math.CO], 2017 (3rd line of Table 2 is a(n+1)).
%H A028399 I. Strazdins, <a href="http://dx.doi.org/10.1023/A:1005769927571">Universal affine classification of Boolean functions</a>, Acta Applic. Math. 46 (1997), 147-167.
%H A028399 <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (3,-2).
%F A028399 O.g.f.: 4*x^3/((1-x)*(1-2*x)). - _R. J. Mathar_, Aug 07 2008
%F A028399 From _Reinhard Zumkeller_, Feb 28 2010: (Start)
%F A028399 a(n) = A175164(2*n)/A140504(n+2);
%F A028399 a(2*n) = A052548(n)*A000918(n) for n > 0;
%F A028399 a(n) = A173787(n,2). (End)
%F A028399 a(n) = a(n-1) + 2^(n-1) (with a(2)=0). - _Vincenzo Librandi_, Nov 22 2010
%F A028399 a(n) = 4*A000225(n-2). - _R. J. Mathar_, Dec 15 2015
%F A028399 E.g.f.: 3 + 2*x - 4*exp(x) + exp(2*x). - _Stefano Spezia_, Apr 06 2021
%F A028399 a(n) = sigma(A003945(n-2)) for n>=3. - _Flávio V. Fernandes_, Apr 20 2021
%e A028399 From _Petros Hadjicostas_, Aug 08 2019: (Start)
%e A028399 We have a(3) = 4 because each of the following permutations of [3] has the following so-called "séquences" ("alternate runs"):
%e A028399    123 -> 123 (one),
%e A028399    132 -> 13, 32 (two),
%e A028399    213 -> 21, 13 (two),
%e A028399    231 -> 23, 31 (two),
%e A028399    312 -> 31, 12 (two),
%e A028399    321 -> 321 (one).
%e A028399 Recall that a so-called "séquence" ("alternate run") must start with a "maximum" and end with "minimum", or vice versa, and it should not contain any other maxima and minima in between. Two consecutive such "séquences" ("alternate runs") have exactly one minimum or exactly one maximum in common.
%e A028399 (End)
%p A028399 seq(2^n-4, n=2..40); # _Muniru A Asiru_, May 17 2018
%t A028399 2^Range[2,40]-4 (* _Harvey P. Dale_, Jul 05 2019 *)
%o A028399 (PARI) a(n)=if(n<2, 0, 2^n-4)
%o A028399 (GAP) a:=List([2..40], n->2^n-4); # _Muniru A Asiru_, May 17 2018
%o A028399 (Python)
%o A028399 def A028399(n): return (1<<n)-4 # _Chai Wah Wu_, Jun 27 2023
%Y A028399 Column k = 2 of A059427.
%Y A028399 Row n = 2 of A371064.
%Y A028399 Cf. A000225, A000918, A052548, A140504, A175164.
%Y A028399 Cf. A000203, A003945.
%K A028399 nonn,easy
%O A028399 2,2
%A A028399 _N. J. A. Sloane_
%E A028399 Additional comments from Barbara Haas Margolius (margolius(AT)math.csuohio.edu), Dec 02 2001