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

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

Author

N. J. A. Sloane

Keywords

• nonn
• easy

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)

Examples

			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)
		

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.
• Jean-Luc Baril and José L. Ramírez, Some distributions in increasing and flattened permutations, arXiv:2410.15434 [math.CO], 2024. See p. 5.
• 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)

Crossrefs

Cf. A000487, A000517, A027624.

Column k=1 of A008303.

Programs

Magma

[0] cat [(4^n - n*2^(n+1))/8: n in [1..30]]; // Vincenzo Librandi, Feb 18 2015

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 *)

PARI

concat(vector(3), Vec(2*x^3/((1-2*x)^2*(1-4*x)) + O(x^40))) \\ Michel Marcus, Jan 31 2016

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