|
%I M2089 N0824 #103 Sep 08 2022 08:44:28
%S 0,0,0,2,16,88,416,1824,7680,31616,128512,518656,2084864,8361984,
%T 33497088,134094848,536608768,2146926592,8588754944,34357248000,
%U 137433710592,549744803840,2199000186880,8796044787712,35184271425536,140737278640128,562949517213696
%N Expansion of 2*x^3/((1-2*x)^2*(1-4*x)).
%C Number of permutations of length n with exactly one valley. Also (for n>0), the number of ways to pick two of the 2^(n-1) vertices of an n-1 cube that are not connected by an edge. - _Aaron Meyerowitz_, Apr 21 2014
%C a(n+1), n >= 1: Number of independent vertex pairs for Q_n, n >= 1: 2^(n-1) * (2^n - (n+1)) = T_(2^n - 1) - n * 2^(n-1) = L_n - E_n = A006516(n) - A001787(n), where L_n is the number of vertex pairs and E_n is the number of vertex pairs yielding edges. (Cf. A027624.) - _Daniel Forgues_, Feb 19 2015
%C From _Petros Hadjicostas_, Aug 08 2019: (Start)
%C Apparently, by saying "valley" of a permutation of [n], _Aaron Meyerowitz_ indirectly assumes that a "valley" is an interior minimum of a permutation (i.e., we ignore possible minima at the endpoints). Since the complement of a permutation b_1 b_2 ... b_n (using one-line notation, not cycle notation) is (n+1-b_1) (n+1-b_2) ... (n+1-b_n), the current sequence is also the number of permutations of [n] with exactly one peak (that is, exactly one interior maximum).
%C Comtet (pp. 260-261 in his book) calls these peaks "intermediary peaks" to distinguish them from "left peaks" and "right peaks" (i.e., maxima at the endpoints).
%C (End)
%D F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 261.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A000431/b000431.txt">Table of n, a(n) for n = 0..200</a>
%H 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 Nelson H. F. Beebe, <a href="https://dx.doi.org/10.1007/978-3-319-64110-2_18">The Greek functions: gamma, psi, and zeta</a>, In: The Mathematical-Function Computation Handbook, 2017. See pp. 549-550.
%H S. Billey, K. Burdzy, and B. E. Sagan, <a href="http://arxiv.org/abs/1209.0693">Permutations with given peak set</a>, arXiv preprint arXiv:1209.0693 [math.CO], 2012.
%H S. Billey, K. Burdzy, and B. E. Sagan, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Billey/billey2.html">Permutations with given peak set</a>, J. Int. Seq. 16 (2013), #13.6.1.
%H C. J. Fewster, D. Siemssen, <a href="http://arxiv.org/abs/1403.1723">Enumerating Permutations by their Run Structure</a>, arXiv preprint arXiv:1403.1723 [math.CO], 2014.
%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992
%H R. G. Rieper and M. Zeleke, <a href="https://arxiv.org/abs/math/0005180">Valleyless Sequences</a>, arXiv:math/0005180 [math.CO], 2000.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (8,-20,16)
%F From _Mitch Harris_, Apr 02 2004: (Start)
%F a(n) = Sum_{1..2^(n+1) - 1} A007814(k).
%F a(n) = (4^n - n 2^(n+1))/8 for n >= 1.
%F (End)
%F a(n) = 2*A100575(n-1). - _R. J. Mathar_, Mar 14 2011
%F a(n) = 2^(n-2) * (2^(n-1) - n), n >= 1. - _Daniel Forgues_, Feb 24 2015
%e From _Petros Hadjicostas_, Aug 08 2019: (Start)
%e We have a(3) = 2 because the permutations 123, 132, 213, 231, 312, and 321 have exactly 0, 1, 0, 1, 0, and 0 peaks, respectively. Also, they have 0, 0, 1, 0, 1, and 0 valleys, respectively.
%e Note that permutations 132 and 231 (each one with 1 peak) are complements of permutations 312 and 213, respectively (each one with 1 valley).
%e Also, a(4) = 16 because
%e 1234 -> 0 peaks and 0 valleys (complement of 4321);
%e 1243 -> 1 peak and 0 valleys (complement of 4312);
%e 1324 -> 1 peak and 1 valley (complement of 4231);
%e 1342 -> 1 peak and 0 valleys (complement of 4213);
%e 1423 -> 1 peak and 1 valley (complement of 4132);
%e 1432 -> 1 peal and 0 valleys (complement of 4123);
%e 2134 -> 0 peaks and 1 valley (complement of 3421);
%e 2143 -> 1 peak and 1 valley (complement of 3412);
%e 2314 -> 1 peak and 1 valley (complement of 3241);
%e 2341 -> 1 peak and 0 valleys (complement of 3214);
%e 2413 -> 1 peak and 1 valley (complement of 3142);
%e 2431 -> 1 peak and 0 valleys (complement of 3124);
%e 3124 -> 0 peaks and 1 valley (complement of 2431);
%e 3142 -> 1 peak and 1 valley (complement of 2413);
%e 3214 -> 0 peaks and 1 valley (complement of 2341);
%e 3241 -> 1 peak and 1 valley (complement of 2314);
%e 3412 -> 1 peak and 1 valley (complement of 2143);
%e 3421 -> 1 peak and 0 valleys (complement of 2134);
%e 4123 -> 0 peaks and 1 valley (complement of 1432);
%e 4132 -> 1 peak and 1 valley (complement of 1423);
%e 4213 -> 0 peaks and 1 valley (complement of 1342);
%e 4231 -> 1 peak and 1 valleys (complement of 1324);
%e 4312 -> 0 peaks and 1 valley (complement of 1243);
%e 4321 -> 0 peaks and 0 valleys (complement of 1234).
%e (End)
%p A000431:=-2/(4*z-1)/(-1+2*z)**2; # Conjectured by _Simon Plouffe_ in his 1992 dissertation. [Proved by Désiré André, 1895, p.154, for circular permutations (see A008303). _Peter Luschny_, Aug 07 2019]
%p a:= n-> if n=0 then 0 else (Matrix([[2,0,0]]). Matrix(3, (i,j)-> if (i=j-1) then 1 elif j=1 then [8,-20,16][i] else 0 fi)^(n-1))[1,3] fi: seq(a(n), n=0..30); # _Alois P. Heinz_, Aug 26 2008
%t nn = 30; CoefficientList[Series[2*x^3/((1 - 2*x)^2*(1 - 4*x)), {x, 0, nn}], x] (* _T. D. Noe_, Jun 20 2012 *)
%t Join[{0}, LinearRecurrence[{8, -20, 16}, {0, 0, 2}, 30]] (* _Jean-François Alcover_, Jan 31 2016 *)
%o (Magma) [0] cat [(4^n - n*2^(n+1))/8: n in [1..30]]; // _Vincenzo Librandi_, Feb 18 2015
%o (PARI) concat(vector(3), Vec(2*x^3/((1-2*x)^2*(1-4*x)) + O(x^40))) \\ _Michel Marcus_, Jan 31 2016
%Y Cf. A000487, A000517, A027624.
%Y Column k=1 of A008303.
%K nonn,easy
%O 0,4
%A _N. J. A. Sloane_
| 