The OEIS is supported by the many generous donors to the OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A000431 Expansion of 2*x^3/((1-2*x)^2*(1-4*x)). (Formerly M2089 N0824) 8
 0, 0, 0, 2, 16, 88, 416, 1824, 7680, 31616, 128512, 518656, 2084864, 8361984, 33497088, 134094848, 536608768, 2146926592, 8588754944, 34357248000, 137433710592, 549744803840, 2199000186880, 8796044787712, 35184271425536, 140737278640128, 562949517213696 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,4 COMMENTS 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 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 From Petros Hadjicostas, Aug 08 2019: (Start) 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). 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). (End) REFERENCES F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 261. N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence). N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence). LINKS T. D. Noe, Table of n, a(n) for n = 0..200 Désiré André, Mémoire sur les séquences des permutations circulaires, Bulletin de la S. M. F., tome 23 (1895), pp. 122-184. Nelson H. F. Beebe, The Greek functions: gamma, psi, and zeta, In: The Mathematical-Function Computation Handbook, 2017. See pp. 549-550. S. Billey, K. Burdzy, and B. E. Sagan, Permutations with given peak set, arXiv preprint arXiv:1209.0693 [math.CO], 2012. S. Billey, K. Burdzy, and B. E. Sagan, Permutations with given peak set, J. Int. Seq. 16 (2013), #13.6.1. C. J. Fewster, D. Siemssen, Enumerating Permutations by their Run Structure, arXiv preprint arXiv:1403.1723 [math.CO], 2014. Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009. Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992 R. G. Rieper and M. Zeleke, Valleyless Sequences, arXiv:math/0005180 [math.CO], 2000. Index entries for linear recurrences with constant coefficients, signature (8,-20,16) FORMULA From Mitch Harris, Apr 02 2004: (Start) a(n) = Sum_{1..2^(n+1) - 1} A007814(k). a(n) = (4^n - n 2^(n+1))/8 for n >= 1. (End) a(n) = 2*A100575(n-1). - R. J. Mathar, Mar 14 2011 a(n) = 2^(n-2) * (2^(n-1) - n), n >= 1. - Daniel Forgues, Feb 24 2015 EXAMPLE From Petros Hadjicostas, Aug 08 2019: (Start) 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. Note that permutations 132 and 231 (each one with 1 peak) are complements of permutations 312 and 213, respectively (each one with 1 valley). Also, a(4) = 16 because 1234 -> 0 peaks and 0 valleys (complement of 4321); 1243 -> 1 peak and 0 valleys (complement of 4312); 1324 -> 1 peak and 1 valley (complement of 4231); 1342 -> 1 peak and 0 valleys (complement of 4213); 1423 -> 1 peak and 1 valley (complement of 4132); 1432 -> 1 peal and 0 valleys (complement of 4123); 2134 -> 0 peaks and 1 valley (complement of 3421); 2143 -> 1 peak and 1 valley (complement of 3412); 2314 -> 1 peak and 1 valley (complement of 3241); 2341 -> 1 peak and 0 valleys (complement of 3214); 2413 -> 1 peak and 1 valley (complement of 3142); 2431 -> 1 peak and 0 valleys (complement of 3124); 3124 -> 0 peaks and 1 valley (complement of 2431); 3142 -> 1 peak and 1 valley (complement of 2413); 3214 -> 0 peaks and 1 valley (complement of 2341); 3241 -> 1 peak and 1 valley (complement of 2314); 3412 -> 1 peak and 1 valley (complement of 2143); 3421 -> 1 peak and 0 valleys (complement of 2134); 4123 -> 0 peaks and 1 valley (complement of 1432); 4132 -> 1 peak and 1 valley (complement of 1423); 4213 -> 0 peaks and 1 valley (complement of 1342); 4231 -> 1 peak and 1 valleys (complement of 1324); 4312 -> 0 peaks and 1 valley (complement of 1243); 4321 -> 0 peaks and 0 valleys (complement of 1234). (End) MAPLE 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] 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 MATHEMATICA nn = 30; CoefficientList[Series[2*x^3/((1 - 2*x)^2*(1 - 4*x)), {x, 0, nn}], x] (* T. D. Noe, Jun 20 2012 *) Join[{0}, LinearRecurrence[{8, -20, 16}, {0, 0, 2}, 30]] (* Jean-François Alcover, Jan 31 2016 *) PROG (Magma)  cat [(4^n - n*2^(n+1))/8: n in [1..30]]; // Vincenzo Librandi, Feb 18 2015 (PARI) concat(vector(3), Vec(2*x^3/((1-2*x)^2*(1-4*x)) + O(x^40))) \\ Michel Marcus, Jan 31 2016 CROSSREFS Cf. A000487, A000517, A027624. Column k=1 of A008303. Sequence in context: A071893 A220505 A069440 * A281982 A207595 A253487 Adjacent sequences: A000428 A000429 A000430 * A000432 A000433 A000434 KEYWORD nonn,easy AUTHOR STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified March 28 03:48 EDT 2023. Contains 361577 sequences. (Running on oeis4.)