|
%I #127 Apr 18 2023 09:44:09
%S 0,1,2,6,16,40,96,224,512,1152,2560,5632,12288,26624,57344,122880,
%T 262144,557056,1179648,2490368,5242880,11010048,23068672,48234496,
%U 100663296,209715200,436207616,905969664,1879048192,3892314112,8053063680
%N a(0)=0, a(1)=1, a(n) = n*2^(n-2) for n >= 2.
%C Number of states in the planning domain FERRY, when n-3 cars are at one of two shores while the (n-2)nd car may be on the ferry or at one of the shores.
%C If the ferry could board any number of cars (instead of only one), the number of states would form the Pisot sequence P(2,6) (A008776). In addition, if k shores existed, the sequence would form the Pisot sequence P(k,k(k+1)). This corresponds to the BRIEFCASE planning domain.
%C a(i) is the number of occurrences of the number 1 in all palindromic compositions of n = 2*(i+1). - Silvia Heubach (sheubac(AT)calstatela.edu), Jan 10 2003. E.g., there are 5 palindromic compositions of 6, namely 111111 11211 2112 1221 141, containing a total of 16 1's.
%C Number of occurrences of 00's in all circular binary words of length n. Example: a(3)=6 because in the circular binary words 000, 001, 010, 011, 100, 101, 110 and 111 we have a total of 3+1+1+0+1+0+0+0=6 occurrences of 00. a(n) = Sum_{k=0..n} k*A119458(n,k). - _Emeric Deutsch_, May 20 2006
%C a(n) is the number of permutations on [n] for which the entries of each left factor form a circular subinterval of [n]. A subset I of [n] forms a circular subinterval of [n] if it is an ordinary interval [a,b] or has the form [1,a]-union-[b,n] for 1 <= a < b <= n. For example, (5,4,2) is a left factor of the permutation (5,4,2,1,3) which does not form a circular subinterval of [5] and a(4)=16 counts all 24 permutations of [4] except the eight whose first two entries are 1,3 (in either order) or 2,4. - _David Callan_, Mar 30 2007
%C a(n) is the total number of runs in all Boolean (n-1)-strings. For example, the 8 Boolean 3-strings, 000, 001, 010, 011, 100, 101, 110, 111 have 1, 2, 3, 2, 2, 3, 2, 1 runs respectively. - _David Callan_, Jul 22 2008
%C From _Gary W. Adamson_, Jul 31 2010: (Start)
%C Starting with "1" = (1, 2, 4, 8, ...) convolved with (1, 0, 2, 4, 8, ...).
%C Example: a(6) = 96 = (32, 16, 8, 4, 2, 1) dot (1, 0, 2, 4, 8, 16) = (32 + 0 + 16 + 16 + 16, + 16) = 32 + 4*16 (End)
%C An elephant sequence, see A175654. For the corner squares 24 A[5] vectors, with decimal values between 27 and 432, lead to this sequence (without the leading 0). For the central square these vectors lead to the companion sequence A087447 (without the first leading 1). - _Johannes W. Meijer_, Aug 15 2010
%C Starting with 1 = (1, 1, 2, 4, 8, 16, ...) convolved with (1, 1, 3, 7, 15, 31, ...). - _Gary W. Adamson_, Oct 26 2010
%C a(n) is the number of ways to draw simple polygonal chains for n vertices lying on a circle. - _Anton Zakharov_, Dec 31 2016
%C Also the number of edges, maximal cliques, and maximum cliques in the n-folded cube graph for n > 3. - _Eric W. Weisstein_, Dec 01 2017 and Mar 21 2018
%C Number of pairs of compositions of n corresponding to a seaweed algebra of index n-2 for n > 2. - _Nick Mayers_, Jun 25 2018
%C Starting with 1, 2, 6, 16, ..., number of permutations of length n>0 avoiding the partially ordered pattern (POP) {1>2, 1>3} of length 4. That is, number of length n permutations having no subsequences of length 4 in which the first element is larger than the second and third elements. - _Sergey Kitaev_, Dec 08 2020
%H Vincenzo Librandi, <a href="/A057711/b057711.txt">Table of n, a(n) for n = 0..1000</a>
%H O. Aichholzer, A. Asinowski, and T. Miltzow, <a href="http://arxiv.org/abs/1403.5546">Disjoint compatibility graph of non-crossing matchings of points in convex position</a>, arXiv preprint arXiv:1403.5546 [math.CO], 2014.
%H A. Burstein, S. Kitaev, and T. Mansour, <a href="http://puma.dimai.unifi.it/19_2_3/3.pdf">Partially ordered patterns and their combinatorial interpretations</a>, PU. M. A. Vol. 19 (2008), No. 2-3, pp. 27-38.
%H P. Chinn, R. Grimaldi and S. Heubach, <a href="https://www.calstatela.edu/sites/default/files/users/u1231/Papers/freqs.pdf">The frequency of summands of a particular size in Palindromic Compositions</a>, Ars Combin. 69 (2003), 65-78.
%H Vincent Coll et al., <a href="https://doi.org/10.4172/1736-4337.1000227">Meander graphs and Frobenius seaweed Lie algebras II</a>, Journal of Generalized Lie Theory and Applications 9.1 (2015).
%H Vladimir Dergachev and Alexandre Kirillov, <a href="https://www.emis.de/journals/JLT/vol.10_no.2/6.html">Index of Lie algebras of seaweed type</a>, J. Lie Theory 10.2 (2000): 331-343.
%H Alice L. L. Gao and Sergey Kitaev, <a href="https://arxiv.org/abs/1903.08946">On partially ordered patterns of length 4 and 5 in permutations</a>, arXiv:1903.08946 [math.CO], 2019.
%H Alice L. L. Gao and Sergey Kitaev, <a href="https://doi.org/10.37236/8605">On partially ordered patterns of length 4 and 5 in permutations</a>, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.
%H M. Ghallab et al., <a href="ftp://ftp.cs.yale.edu/pub/mcdermott/software/pddl.tar.gz">FERRY domain</a>
%H M. Ghallab, A. Howe et al., <a href="https://www.researchgate.net/publication/2278933_PDDL_-_The_Planning_Domain_Definition_Language">PDDL - The Planning Domain Definition Language, Version 1.2</a>, Technical Report CVC TR-98-003/DCS TR-1165. Yale Center for Computational Vision and Control, 1998.
%H Anna Khmelnitskaya, Gerard van der Laan, and Dolf Talmanm, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Talman/talman2.html">The Number of Ways to Construct a Connected Graph: A Graph-Based Generalization of the Binomial Coefficients</a>, J. Int. Seq. (2023) Art. 23.4.3. See p. 12.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/FoldedCubeGraph.html">Folded Cube Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MaximalClique.html">Maximal Clique</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MaximumClique.html">Maximum Clique</a>
%H B. Wolf, <a href="http://ki.cs.tu-berlin.de/diplomarbeiten/wolf/da.html">Creating state sets</a>
%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (4,-4).
%F a(n) = ceiling(n*2^(n-2)).
%F Binomial transform of (0, 1, 0, 3, 0, 5, 0, 7, ...).
%F From _Paul Barry_, Apr 06 2003: (Start)
%F a(0)=0, a(n) = n*(0^(n-1) + 2^(n-1))/2, n > 0.
%F a(n) = Sum_{k=0..n} binomial(n, 2k+1)*(2k+1).
%F E.g.f.: x*exp(x)*cosh(x). (End)
%F The sequence 1, 1, 6, 16, ... is the binomial transform of A016813 with interpolated zeros. - _Paul Barry_, Jul 25 2003
%F For n > 1, a(n) = Sum_{k=0..n} (k-n/2)^2 C(n, k). (n+1)*a(n) = A001788(n). - Mario Catalani (mario.catalani(AT)unito.it), Nov 26 2003
%F From _Paul Barry_, May 07 2004: (Start)
%F a(n) = n*2^(n-2) - Sum_{k=0..n} binomial(n, k)*k*(-1)^k.
%F G.f.: x*(1-2*x+2*x^2)/(1-2*x)^2. (End)
%F a(n+1) = ceiling(binomial(n+1,1)*2^(n-1)). - _Zerinvary Lajos_, Nov 01 2006
%F a(n+1) = Sum_{k=0..n} A196389(n,k)*2^k. - _Philippe Deléham_, Oct 31 2011
%F a(0)=0, a(1)=1, a(2)=2, a(3)=6, a(n+1) = 4*a(n)-4*a(n-1) for n >= 3. - _Philippe Deléham_, Feb 20 2013
%F a(n) = A002064(n-1) - A002064(n-2), for n >= 2. - _Ivan N. Ianakiev_, Dec 29 2013
%F From _Amiram Eldar_, Aug 05 2020: (Start)
%F Sum_{n>=1} 1/a(n) = 4*log(2) - 1.
%F Sum_{n>=1} (-1)^(n+1)/a(n) = 4*log(3/2) - 1. (End)
%e a(1)=6 because the palindromic compositions of n=4 are 4, 1+2+1, 1+1+1+1 and 2+2 and they contain 6 ones. - Silvia Heubach (sheubac(AT)calstatela.edu), Jan 10 2003
%t Join[{0, 1}, Table[n 2^(n - 2), {n, 2, 30}]] (* _Eric W. Weisstein_, Dec 01 2017 *)
%t Join[{0, 1}, LinearRecurrence[{4, -4}, {2, 6}, 20]] (* _Eric W. Weisstein_, Dec 01 2017 *)
%t CoefficientList[Series[x (1 - 2 x + 2 x^2)/(1 - 2 x)^2, {x, 0, 20}], x] (* _Eric W. Weisstein_, Dec 01 2017 *)
%o (Magma) [Ceiling(n*2^(n-2)) : n in [0..40]]; // _Vincenzo Librandi_, Sep 22 2011
%o (PARI) a(n)=ceil(n*2^(n-2)) \\ _Charles R Greathouse IV_, Oct 31 2011
%o (PARI) x='x+O('x^50); concat(0, Vec(x*(1-2*x+2*x^2)/(1-2*x)^2)) \\ _Altug Alkan_, Nov 01 2015
%Y Cf. A082133, A082134, A082135, A082136.
%Y Pisot sequence P(2, 6) (A008776), Pisot sequence P(k, k(k+1))
%Y Cf. A119458.
%Y Cf. A082140, A082141, A082138, A082139, A080951, A080929.
%K easy,nonn
%O 0,3
%A Bernhard Wolf (wolf(AT)cs.tu-berlin.de), Oct 24 2000
|
