A000431 Expansion of 2*x^3/((1-2*x)^2*(1-4*x)). (Formerly M2089 N0824)

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

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) [0] 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: A220505 A370192 A069440 * A281982 A207595 A253487

Adjacent sequences: A000428 A000429 A000430 * A000432 A000433 A000434

Keyword

nonn,easy

Author

N. J. A. Sloane

Status

approved