A008303 -id:A008303 - cp's OEIS frontend

A334774 Triangle read by rows: T(n,k) is the number of permutations of 2 indistinguishable copies of 1..n with exactly k local maxima.

1, 3, 3, 9, 57, 24, 27, 705, 1449, 339, 81, 7617, 48615, 49695, 7392, 243, 78357, 1290234, 3650706, 2234643, 230217, 729, 791589, 30630618, 197457468, 314306943, 128203119, 9689934, 2187, 7944321, 686779323, 9080961729, 30829608729, 31435152267, 9159564513, 529634931

Offset: 1

Andrew Howroyd, May 11 2020

Also the number of permutations of 2 indistinguishable copies of 1..n with exactly k-1 peaks. A peak is an interior maximum.

			Triangle begins:
    1;
    3,      3;
    9,     57,       24;
   27,    705,     1449,       339;
   81,   7617,    48615,     49695,      7392;
  243,  78357,  1290234,   3650706,   2234643,    230217;
  729, 791589, 30630618, 197457468, 314306943, 128203119, 9689934;
  ...
The T(2,1) = 3 permutations of 1122 with 1 local maxima are 1122, 1221, 2211.
The T(2,2) = 3 permutations of 1122 with 2 local maxima are 1212, 2112, 2121.
The T(2,1) = 3 permutations of 1122 with 0 peaks are 2211, 2112, 1122.
The T(2,2) = 3 permutations of 1122 with 1 peak are 2121, 1221, 1212.

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50)

Columns k=1..6 are A000244(n-1), 3*A152494, 3*A152495, 3*A152496, 3*A152497, 3*A152498.
Row sums are A000680.
Main diagonal is A334775.
The version for permutations of 1..n is A008303(n,k-1).
Cf. A154283, A334773, A334776, A334777, A334778.

PeaksBySig(sig, D)={
  my(F(lev,p,q) = my(key=[lev,p,q], z); if(!mapisdefined(FC, key, &z),
    my(m=sig[lev]); z = if(lev==1, if(p==0, binomial(m-1, q), 0), sum(i=0, p, sum(j=0, min(m-i, q), self()(lev-1, p-i, q-j+i) * binomial(m+2*(q-j)+1, 2*q+i-j+1) * binomial(q-j+i, i) * binomial(q+1, j) )));
    mapput(FC, key, z)); z);
  local(FC=Map());
  vector(#D, i, F(#sig, D[i], 0));
}
Row(n)={ PeaksBySig(vector(n,i,2), [0..n-1]) }
{ for(n=1, 8, print(Row(n))) }

T(n,k) = F(2,n,k-1,0) where F(m,n,p,q) = Sum_{i=0..p} Sum_{j=0..min(m-i, q)} F(m, n-1, p-i, q-j+i) * binomial(m+2*(q-j)+1, 2*q+i-j+1) * binomial(q-j+i, i) * binomial(q+1, j) for n > 1 with F(m,1,0,q) = binomial(m-1, q), F(m,1,p,q) = 0 for p > 0.
A334776(n) = Sum_{k=1..n} (k-1)*T(n,k).
A334777(n) = Sum_{k=1..n} k*T(n,k).

A242783 Number T(n,k) of permutations of [n] with exactly k (possibly overlapping) occurrences of the consecutive step pattern given by the binary expansion of n, where 1=up and 0=down; triangle T(n,k), n>=0, read by rows.

Original entry on oeis.org

1, 1, 2, 5, 1, 21, 3, 70, 50, 450, 270, 4326, 602, 99, 12, 1, 34944, 5376, 209863, 139714, 13303, 1573632, 1366016, 530432, 158720, 21824925, 15302031, 2715243, 74601, 302273664, 161855232, 14872704, 2854894485, 2600075865, 712988175, 59062275

Offset: 0

Alois P. Heinz, May 22 2014

Sum_{k>0} k*T(n,k) = A249249(n).

			T(7,3) = 12 because 12 permutations of {1,2,3,4,5,6,7} have exactly 3 (possibly overlapping) occurrences of the consecutive step pattern up, up, up given by the binary expansion of 7 = 111_2: (1,2,3,4,5,7,6), (1,2,3,4,6,7,5), (1,2,3,5,6,7,4), (1,2,4,5,6,7,3), (1,3,4,5,6,7,2), (2,1,3,4,5,6,7), (2,3,4,5,6,7,1), (3,1,2,4,5,6,7), (4,1,2,3,5,6,7), (5,1,2,3,4,6,7), (6,1,2,3,4,5,7), (7,1,2,3,4,5,6).
Triangle T(n,k) begins:
: n\k :       0        1       2       3  4  ...
+-----+------------------------------------
:  0  :       1;
:  1  :       1;                             [row  1 of A008292]
:  2  :       2;                             [row  2 of A008303]
:  3  :       5,       1;                    [row  3 of A162975]
:  4  :      21,       3;                    [row  4 of A242819]
:  5  :      70,      50;                    [row  5 of A227884]
:  6  :     450,     270;                    [row  6 of A242819]
:  7  :    4326,     602,     99,     12, 1; [row  7 of A220183]
:  8  :   34944,    5376;                    [row  8 of A242820]
:  9  :  209863,  139714,  13303;            [row  9 of A230695]
: 10  : 1573632, 1366016, 530432, 158720;    [row 10 of A230797]

Alois P. Heinz, Rows n = 0..130, flattened

Column k=0-10 give: A242785, A246221, A246222, A246223, A246224, A246225, A246226, A246227, A246228, A246229, A243105.
Row sums give A000142.
Cf. A242784, A249249, A295987, A335308.

T:= proc(n) option remember; local b, k, r, h;
      k:= iquo(n,2,'r'); h:= 2^ilog2(n);
      b:= proc(u, o, t) option remember; `if`(u+o=0, 1, expand(
      add(b(u-j, o+j-1, irem(2*t,   h))*`if`(r=0 and t=k, x, 1), j=1..u)+
      add(b(u+j-1, o-j, irem(2*t+1, h))*`if`(r=1 and t=k, x, 1), j=1..o)))
      end: forget(b);
      (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0, 0))
    end:
seq(T(n), n=0..15);

T[n_] := T[n] = Module[{b, k, r, h}, {k, r} = QuotientRemainder[n, 2]; h = 2^Floor[Log[2, n]]; b[u_, o_, t_] := b[u, o, t] = If[u + o == 0, 1, Expand[ Sum[b[u - j, o + j - 1, Mod[2*t, h]]*If[r == 0 && t == k, x, 1], {j, 1, u}] + Sum[b[u + j - 1, o - j, Mod[2*t + 1, h]]*If[r == 1 && t == k, x, 1], {j, 1, o}]]]; Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][b[n, 0, 0]]]; Table[T[n], {n, 0, 15}] // Flatten (* Jean-François Alcover, Feb 20 2016, after Alois P. Heinz *)

A008970 Triangle T(n,k) = P(n,k)/2, n >= 2, 1 <= k < n, of one-half of number of permutations of 1..n such that the differences have k runs with the same signs.

Original entry on oeis.org

1, 1, 2, 1, 6, 5, 1, 14, 29, 16, 1, 30, 118, 150, 61, 1, 62, 418, 926, 841, 272, 1, 126, 1383, 4788, 7311, 5166, 1385, 1, 254, 4407, 22548, 51663, 59982, 34649, 7936, 1, 510, 13736, 100530, 325446, 553410, 517496, 252750, 50521, 1, 1022, 42236, 433162, 1910706, 4474002, 6031076, 4717222, 1995181, 353792

Offset: 2

N. J. A. Sloane

			Triangle starts
  1;
  1,  2;
  1,  6,   5;
  1, 14,  29,  16;
  1, 30, 118, 150, 61;
  ...

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 261, #13, P_{n,k}.
F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 260, Table 7.2.1.

Vincenzo Librandi, Rows n = 2..100, flattened
Désiré André, Mémoire sur les permutations alternées, J. Math. Pur. Appl., 7 (1881), 167-184.
Désiré André, Etude sur les maxima, minima et sequences des permutations, Ann. Sci. Ecole Norm. Sup., 3, no. 1 (1884), 121-135.
Désiré André, Mémoire sur les permutations quasi-alternées, Journal de mathématiques pures et appliquées 5e série, tome 1 (1895), 315-350.
Désiré André, Mémoire sur les séquences des permutations circulaires, Bulletin de la S. M. F., tome 23 (1895), pp. 122-184.
M. Bona and R. Ehrenborg, A combinatorial proof of the log-concavity of the numbers of permutations with k runs, arXiv:math/9902020 [math.CO], 1999.
F. Morley, A generating function for the number of permutations with an assigned number of sequences, Bull. Amer. Math. Soc. 4 (1897), 23-28. Shows the transpose of this triangle.

Diagonals give A000352, A000486, A000506, A000111, A000708, A091303.
A059427 gives triangle of P(n, k).
A008303 gives circular version of P(n, k).
T(2n,n) gives A360426.

T:= proc(n, k) option remember; `if`(n<2, 0, `if`(k=1, 1,
      k*T(n-1, k) + 2*T(n-1, k-1) + (n-k)*T(n-1, k-2)))
    end:
seq(seq(T(n,k), k=1..n-1), n=2..12);  # Alois P. Heinz, Feb 08 2023

p[n_ /; n >= 2, 1] = 2; p[n_ /; n >= 2, k_] /; 1 <= k <= n := p[n, k] = k*p[n-1, k] + 2*p[n-1, k-1] + (n-k)*p[n-1, k-2]; p[n_, k_] = 0; t[n_, k_] := p[n, k]/2; A008970 = Flatten[ Table[ t[n, k], {n, 2, 11}, {k, 1, n-1}]] (* Jean-François Alcover, Apr 03 2012, after given recurrence *)

Let P(n, k) = number of permutations of [1..n] with k "sequences". Note that A008970 gives P(n, k)/2. Then g.f.: Sum_{n, k} P(n, k) *u^k * t^n/n! = (1 + u)^(-1) * ((1 - u) * (1 - sin(v + t * cos(v))-1) where u = sin(v).

P(n, 1) = 2, P(n, k) = k*P(n-1, k) + 2*P(n-1, k-1) + (n-k)*P(n-1, k-2).

More terms from Larry Reeves (larryr(AT)acm.org), Feb 01 2001

A059427 Triangle read by rows: T(n,k) is the number of permutations of [n] with k alternating runs (n>=2, k>=1).

Original entry on oeis.org

2, 2, 4, 2, 12, 10, 2, 28, 58, 32, 2, 60, 236, 300, 122, 2, 124, 836, 1852, 1682, 544, 2, 252, 2766, 9576, 14622, 10332, 2770, 2, 508, 8814, 45096, 103326, 119964, 69298, 15872, 2, 1020, 27472, 201060, 650892, 1106820, 1034992, 505500, 101042, 2, 2044

Offset: 2

N. J. A. Sloane, Jan 31 2001

The permutation 732569148 has 4 alternating runs: 732, 2569, 91 and 148.

			T(3,2) = 4 because each of the permutations 132, 312, 213, 231 has two alternating runs: (13, 32), (31, 12), (21, 13), (23, 31); each of 123 and 321 has 1 alternating run.
Triangle (with rows n >= 2 and columns k >= 1) begins as follows:
  2;
  2,   4;
  2,  12,  10;
  2,  28,  58,   32;
  2,  60, 236,  300,  122;
  2, 124, 836, 1852, 1682, 544;
  ...

L. Comtet, Advanced Combinatorics, Reidel, Dordrecht, Holland, 1974, p. 261, #13.
F. N. David and D. E. Barton, Combinatorial Chance, Hafner, NY, 1962, pp. 157-162.
F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 262, Table 7.2.1 doubled.
D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, 1973, Vol. 3, pp. 46 and 587-8.

T. D. Noe, Rows n = 2..50 of triangle, flattened
Désiré André, Sur les permutations alternées, J. Math. Pur. Appl., 7 (1881), 167-184.
Désiré André, Étude sur les maxima, minima et séquences des permutations, Ann. Sci. Ecole Norm. Sup., 3, no. 1 (1884), 121-135.
Désiré André, Mémoire sur les permutations quasi-alternées, Journal de mathématiques pures et appliquées 5e série, tome 1 (1895), 315-350.
Désiré André, Mémoire sur les séquences des permutations circulaires, Bulletin de la S. M. F., tome 23 (1895), pp. 122-184.
M. Bona and R. Ehrenborg, A combinatorial proof of the log-concavity of the numbers of permutations with k runs, J. Comb. Theory, Ser. A, 90, 293-303, 2003.
E. Rodney Canfield and Herbert S. Wilf, Counting permutations by their runs up and down, arXiv:math/0609704 [math.CO], 2006.
E. R. Canfield and H. S. Wilf, Counting permutations by their alternating runs, J. Combin. Theory Ser. A 115 (2008), 213-225.
L. Carlitz, Enumeration of permutations by sequences, Fib. Quart., 16 (1978), 259-268.
L. Carlitz, The number of permutations with a given number of sequences, Fib. Quart., 18 (1980), 347-352.
C.-O. Chow and S.-M. Ma, Counting signed permutations by their alternating runs, Discrete Mathematics, Volume 323, 28 May 2014, Pages 49-57.
C.-O. Chow, S.-M. Ma, T. Mansour, and M. Shattuck, Counting permutations by cyclic peaks and valleys, Annales Mathematicae et Informaticae, (2014), Vol. 43, pp. 43-54.
Qi Fang, Ya-Nan Feng, and Shi-Mei Ma, Alternating runs of permutations and the central factorial numbers, arXiv:2202.13978 [math.CO], 2022.
Ira M. Gessel and Yan Zhuang, Counting permutations by alternating descents , arXiv:1408.1886 [math.CO], 2014.
Shi-Mei Ma, An explicit formula for the number of permutations with a given number of alternating runs, arXiv preprint arXiv:1110.6779 [math.CO], 2011 [Version 1 references the OEIS and sequence A059427; this reference was deleted in Version 2]
Shi-Mei Ma, Enumeration of permutations by number of alternating runs, arXiv:1110.5014 [math.CO], 2011-2012.
Shi-Mei Ma, Enumeration of permutations by number of alternating runs, Discrete Math., 313 (2013), 1816-1822.
S.-M. Ma, T. Mansour and D. G. L. Wang, Combinatorics of Dumont differential system on the Jacobi elliptic functions, arXiv preprint arXiv:1403.0233 [math.CO], 2014-2018.
S.-M. Ma and T. Mansour, The 1/k-Eulerian polynomials and k-Stirling permutations, arXiv preprint arXiv:1409.6525 [math.CO], 2014.
Shi-Mei Ma and Hai-Na Wang, Enumeration of a dual set of Stirling permutations by their alternating runs, arXiv:1506.08716 [math.CO], 2015.
R. P. Stanley, Longest alternating subsequences of permutations, arXiv:math/0511419 [math.CO], 2005.
R. P. Stanley, Longest alternating subsequences of permutations, Michigan Math. J. 57 (2008), 675-687.
Yan Zhuang, Monoid networks and counting permutations by runs, arXiv preprint arXiv:1505.02308 [math.CO], 2015-2016.
Y. Zhuang, Counting permutations by runs, J. Comb. Theory Ser. A 142 (2016), pp. 147-176.

Diagonals give A001250, A001758. Column k = 2 is A028399.
Cf. A008303 (circular version of this array), A008970.
T(2n,n) gives 2*A360426.

P := proc(n,k) if n<2 or k<1 or k>=n then 0 elif n=2 and k=1 then 2 else k*P(n-1,k)+2*P(n-1,k-1)+(n-k)*P(n-1,k-2) fi end: p:=(n,k)->P(n+1,k): matrix(9,9,p);

t[n_, k_] := t[n, k] = k*t[n-1, k] + 2*t[n-1, k-1] + (n-k)*t[n-1, k-2];
t[2, 1] = 2; t[n_, k_] /; n < 2 || k < 1 || k >= n = 0;
Flatten[Table[t[n, k], {n,2,11}, {k, 1, n-1}]][[1 ;; 47]]
(* Jean-François Alcover, Jun 16 2011, after recurrence *)

P(n, k) = 0 if n < 2 or k < 1 or k >= n; P(2, 1) = 2; P(n, k) = k*P(n-1, k) + 2*P(n-1, k-1) + (n-k)*P(n-1, k-2) [André]. - Emeric Deutsch, Feb 21 2004
The row generating polynomials P[n] satisfy P[n] = t*[(1 - t^2) * dP[n-1]/dt + (2 + (n-2) * t) * P[n-1]] and P[2] = 2*t.
T(n, n-1) = 2*A000111(n) = A001250(n-1).
T(n, k) = k*T(n-1, k) + 2*T(n-1, k-1) + (n-k)*T(n-1, k-2), where we set T(2, 1) = 2 and T(n, k) = 0 if n < 2 or k < 1 or k >= n.
E.g.f.: Sum_{n, k >= 0} T(n, k) * x^n * t^k/n! = 2*(1 - t^2 + t * sqrt(1-t^2) * sinh(x * sqrt(1 - t^2)))/((1 + t)^2*(1-t*cosh(x * sqrt(1 - t^2)))) - 2(1 + t*x)/(1 + t).
T(n, k) = 2*A008970(n, k).

Edited by Emeric Deutsch and Ira M. Gessel, Dec 06 2004

André reference from Philippe Deléham, Jul 26 2006

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

Original entry on oeis.org

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

N. J. A. Sloane

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)

			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)

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

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)

Cf. A000487, A000517, A027624.

Column k=1 of A008303.

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

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

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

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

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

A000708 a(n) = E(n+1) - 2*E(n), where E(i) is the Euler number A000111(i).

Original entry on oeis.org

-1, -1, 0, 1, 6, 29, 150, 841, 5166, 34649, 252750, 1995181, 16962726, 154624469, 1505035350, 15583997521, 171082318686, 1985148989489, 24279125761950, 312193418011861, 4210755676649046, 59445878286889709, 876726137720576550, 13483686390543382201

Offset: 0

N. J. A. Sloane

sign

a(n) mod 10 for n >= 2 is the periodic sequence repeat: 0, 1, 6, 9.
For n >= 2, a(n) is the number of permutations on [n] that have n-2 "sequences" (which are maximal monotone runs in Comtet terminology) and start increasing. - Michael Somos, Aug 28 2013
From Petros Hadjicostas, Aug 07 2019: (Start)
With regard to the comment by Michael Somos above, a "sequence" in a permutation according to Ex. 13 (pp. 260-261) of Comtet (1974) is actually a "séquence" in a permutation according to André. He uses this terminology in several of his papers cited in the links below.
In the terminology of array A059427, these so-called "séquences" in permutations defined by Comtet and André are called "alternate runs" (or just "runs"). We discuss these so-called "sequences" below.
We clarify that a(n) is actually one-half the number of permutations on [n] that have n-2 "séquences" as defined by Comtet and André.
André (1884) defines a "maximum" of a permutation of [n] to be any number in the permutation that is greater than both of its neighbors, if it is an interior number, or greater than its single neighbor, if it is either at the beginning or at the end of the permutation.
André (1884) also defines a "minimum" of a permutation of [n] to be any number in the permutation that is less than both of its neighbors, if it is an interior number, or less than its single neighbor, if it is either at the beginning or at the end of the permutation.
A "séquence" in a permutation of [n] according to André and Comtet is a list of consecutive numbers in the permutation that begins with a maximum and ends with a minimum, or vice versa, but has no interior maxima and minima. As mentioned above, other authors call these so-called "séquences" "alternate runs" (or just "runs").
For example, in the permutation 78125436 of [8], we have three maxima, 8, 5, and 6; three minima, 7, 1, and 3; and the so-called "séquences" ("alternate runs") 78, 81, 125, 543, 36 (see p. 122 in André (1884)).
If in the above permutation we take the difference 8-7, 1-8, 2-1, 5-2, 4-5, 3-4, 6-3, we may form a word (list) of signs of consecutive differences: +-++--+.
In general, if in a permutation of [n], say a_1,a_2,...,a_n (written in one-line notation, but not in cycle notation), we form the differences a_2 - a_1, a_3 - a_2, ..., a_n - a_{n-1}, then we get a list of n-1 signs (+ or -).
For n >= 2, André (1885) calls a permutation of [n] "alternate" if it has n - 1 so-called "séquences" ("alternate runs"); i.e., if the corresponding list of signs alternates between + and -. See the documentation and references for sequences A000111 and A001250.
For n >= 2, André (1885) calls a permutation of [n] "quasi-alternate" if it has n - 2 so-called "séquences" ("alternate runs"); i.e., if the corresponding list of signs alternates between + and - except for a single ++ or a single --, but not both.
In the above example, the permutation 78125436 has 5 so-called "séquences" ("alternate signs") and 5 < 8-2 < 8-1; that is, it is neither alternate nor quasi-alternate. We can reach the same conclusion by looking at its corresponding list of signs +-++--+. The permutation is neither alternate nor quasi-alternate because we have one ++ and one --.
On p. 316, André (1885) gives the following two examples of permutations of [8]: 31426587 and 32541768 (using one-line notation for permutations). The first one has list of signs -+-+-+- while the second one has list of signs -+--+-+. The first one is alternate while the second one is quasi-alternate (because of a single --). Alternatively, the first one has n-1 = 7 so-called "séquences" ("alternate runs")--31, 14, 42, 26, 65, 58, 87--while the second one has n-2 = 6 so-called "séquences" ("alternate runs")--32, 25, 541, 17, 76, 68.
Here 2*a(n) is the total number of quasi-alternate permutations of [n]. Actually, André (1884, 1885) uses P_{n,s} to denote the number of permutations of [n] with exactly s of his so-called "séquences" ("alternate runs"). He uses the notation A_n to denote half the number of alternate permutations of [n] and B_n to denote half the number of quasi-alternate permutations of [n].
Thus, P_{n,n-1} = 2*A_n = 2*A000111(n) = A001250(n) for n >= 2 and P_{n,n-2} = 2*B_n = 2*a(n) for n >= 2.
We have P_{n,s} = A059427(n,s) for n >= 2 and s >= 1. See also p. 261 in Comtet (1974). They satisfy André's recurrence P_{n,s} = s*P_{n-1,s} + 2*P_{n-1,s-1} + (n-s)*P_{n-1,s-2} for n >= 3 and s >= 3 with P(n, 1) = 2 for n >= 2 and P(n, s) = 0 for s >= n.
The numbers Q(n,s) that count the circular permutations of [n] with exactly s so-called "séquences" ("alternate runs") appear in array A008303. They have also been studied by Désiré André (see the references there).
(End)

			G.f. = -1 - x + x^3 + 6*x^4 + 29*x^5 + 150*x^6 + 841*x^7 + 5166*x^8 + 34649*x^9 + ...
a(3) = 1 with permutation 123. a(4) = 6 with permutations 1243, 1342, 1432, 2341, 2431, 3421.
From _Petros Hadjicostas_, Aug 07 2019: (Start)
We elaborate on the example above. For the permutations of [3], we have the following sign sequences:
123 -> ++; 132 --> +-; 213 -> -+; 213 -> 213; 231 -> +-; 312 -> -+; 321 --> --.
Thus, 123 and 321 are quasi-alternate and a(3) = 2/2 = 1.
For the permutations of [4] we have:
  1234 -> +++ (neither alternate nor quasi-alternate);
  1243 -> ++- (quasi-alternate);
  1324 -> +-+ (alternate);
  1342 -> ++- (quasi-alternate);
  1423 -> +-+ (alternate);
  1432 -> +-- (quasi-alternate);
  2134 -> -++ (quasi-alternate);
  2143 -> -+- (alternate);
  2314 -> +-+ (alternate);
  2341 -> ++- (quasi-alternate);
  2413 -> +-+ (alternate);
  2431 -> +-- (quasi-alternate);
  3124 -> -++ (quasi-alternate);
  3142 -> -+- (alternate);
  3214 -> --+ (quasi-alternate);
  3241 -> -+- (alternate);
  3412 -> +-+ (alternate);
  3421 -> +-- (quasi-alternate);
  4123 -> -++ (quasi-alternate);
  4132 -> -+- (alternate);
  4213 -> --+ (quasi-alternate);
  4231 -> -+- (alternate);
  4312 -> --+ (quasi-alternate);
  4321 -> --- (neither alternate nor quasi-alternate).
Thus we have 10 = 2*A000111(4) = A001250(4) alternate permutations of [4] and 2*a(4) = 2*6 = 12 quasi-alternate permutations of [4]. The remaining 2 permutations (1234 and 4321) each have one so-called "séquence" ("alternate run").
Thus, P_{n=4, s=1} = 2, P_{n=4, s=2} = 12, and P_{n=4, s=10} = 10 (see row n = 4 for array A059427).
(End)

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 261.
E. Netto, Lehrbuch der Combinatorik. 2nd ed., Teubner, Leipzig, 1927, p. 113.
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).

John Cerkan, Table of n, a(n) for n = 0..482
Data (data.bnf.fr), Désiré André (1840-1918).
Désiré André, Mémoire sur les permutations alternées, J. Math. Pur. Appl., 7 (1881), 167-184.
Désiré André, Étude sur les maxima, minima et séquences des permutations, Annales scientifiques de l'École Normale Supérieure, Serie 3, Vol. 1 (1884), 121-134.
Désiré André, Mémoire sur les permutations quasi-alternées, Journal de mathématiques pures et appliquées 5e série, tome 1 (1895), 315-350.
E. Estanave, Sur les coefficients des développements en séries de tang x, séc x et d'autres fonctions. Caractères de périodicité que présentent les chiffres des unités de ces coefficients, Bulletin de la S.M.F., 30 (1902), pp. 220-226.
F. Morley, A generating function for the number of permutations with an assigned number of sequences, Bull. Amer. Math. Soc. 4 (1897), 23-28. [Discusses the so-called "séquences" of Désiré André. A shifted version of the current sequence appears in column r = 1 in the table on p. 24. His definition, however, of a "run" is highly not standard! The definition of the letter r in his paper is the number of triplets of adjacent numbers in the permutation that appear in order of magnitude (ascending or descending). He proves that in any permutation b of [n] we have r + s = n-1, where s is the number of the so-called "séquences" of André (i.e., number of "alternate runs"). Thus, r = 1 if and only s = n - 2. - _Petros Hadjicostas_, Aug 09 2019]
Eugen Netto, Lehrbuch der Combinatorik, 1901, Annotated scanned copy of pages 112-113 only.
Eugen Netto, Lehrbuch der Combinatorik, Verlag von B. G. Teubner, Leipzig, 1901 (archived copy of the whole book).
Eric Weisstein's MathWorld, Polylogarithm.

Apart from initial terms, equals (1/2)*A001758. A diagonal of A008970.

Cf. A000111, A001250, A008303, A059427.

seq(i! * coeff(series((1 + (tan(t) + sec(t))^2 - 4*(tan(t) + sec(t))) / 2, t, 35), t, i), i=0..24); # Barbara Haas Margolius (margolius(AT)math.csuohio.edu), Mar 12 2001

a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ (1 - 2 Cos[x]) / (1 - Sin[x]), {x, 0, n}]]; (* Michael Somos, Aug 28 2013 *)
nmax = 22; ee = Table[2^n*EulerE[n, 1] + EulerE[n], {n, 0, nmax+1}]; dd = Table[Differences[ee, n][[1]] // Abs, {n, 0, nmax+1}]; a[n_] := dd[[n+2]] - 2dd[[n+1]]; a[0] = -1; Table[a[n], {n, 0, nmax}] (* Jean-François Alcover, Feb 10 2016, after Paul Curtz *)
Table[If[n == 0, -1, 2 Abs[PolyLog[-n-1, I]] - 4 Abs[PolyLog[-n, I]]], {n, 0, 22}] (* Jean-François Alcover, Jul 01 2017 *)

x='x+O('x^99); Vec(serlaplace((1-2*cos(x))/(1-sin(x))))

from mpmath import polylog, j, mp
mp.dps=20
def a(n): return -1 if n==0 else int(2*abs(polylog(-n - 1, j)) - 4*abs(polylog(-n, j)))
print([a(n) for n in range(23)])  # Indranil Ghosh, Jul 02 2017

from itertools import count, islice, accumulate
def A000708_gen(): # generator of terms
    yield -1
    blist = (0,1)
    for n in count(2):
        yield -2*blist[-1]+(blist:=tuple(accumulate(reversed(blist),initial=0)))[-1]
A000708_list = list(islice(A000708_gen(),40)) # Chai Wah Wu, Jun 09-11 2022

E.g.f.: (1 - 2*cos(x)) / (1 - sin(x)).
a(n) ~ n! * 2*n*(2/Pi)^(n+2). - Vaclav Kotesovec, Oct 08 2013
a(n) = 2*abs(PolyLog(-n-1, i)) - 4*abs(PolyLog(-n, i)) for n > 0, with a(0) = -1. - Jean-François Alcover, Jul 02 2017

More terms from Barbara Haas Margolius (margolius(AT)math.csuohio.edu), Mar 12 2001
Corrected and extended by T. D. Noe, Oct 25 2006
Edited by N. J. A. Sloane, Aug 27 2012

A183270 T(n,k) is the number of singly defective permutations of 1..n+2*k-2 with exactly k maxima.

Original entry on oeis.org

0, 3, 2, 120, 80, 15, 4760, 3552, 860, 64, 249984, 199168, 57064, 6576, 220, 17512704, 14548480, 4643712, 681984, 42112, 672, 1599330304, 1367568384, 469942528, 80506880, 6849792, 242688, 1904, 185616337920, 162107703296, 58754129408

Offset: 1

R. H. Hardin, Jan 03 2011

A singly defective permutation omits one value and repeats another value.
T(1,1) is zero because there are no defective permutations of a single element.
T(n,k) is divisible by n + 2*k - 2. - Andrew Howroyd, May 12 2020

			Table starts:
     0      3     120     4760    249984   17512704 1599330304 ...
     2     80    3552   199168  14548480 1367568384 ...
    15    860   57064  4643712 469942528 ...
    64   6576  681984 80506880 ...
   220  42112 6849792 ...
   672 242688 ...
  1904 ...
  ...
Some solutions for n=4 with 2 maxima:
(6,1,4,4,3,2) (4,3,1,5,6,6) (4,2,1,2,3,5) (3,2,1,6,4,3) (5,5,6,1,2,3).

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (terms 1..36 from R. H. Hardin)

Columns 1..6 are A183264, A183265, A183266, A183267, A183268, A183269.

Cf. A001804, A008303, A334774.

\\ PeaksBySig defined in A334774.
T(n,k) = {my(m=n+2*k-3); (m+1)*sum(i=1, m, PeaksBySig(vector(m,j,if(i==j,2,1)), [k-1])[1])} \\ Andrew Howroyd, May 12 2020

A001804(n) = Sum_{k=1..2*n+1} T(n+2-2*k, k). - Andrew Howroyd, May 12 2020

A263789 Triangle read by rows: T(n,k) (n>=0, 0<=k<=floor(n/2)) is the number of permutations of n and k valleys (considered cyclically).

Original entry on oeis.org

1, 1, 0, 2, 0, 6, 0, 16, 8, 0, 40, 80, 0, 96, 528, 96, 0, 224, 2912, 1904, 0, 512, 14592, 23040, 2176, 0, 1152, 69120, 221184, 71424, 0, 2560, 316160, 1858560, 1372160, 79360, 0, 5632, 1413632, 14353152, 20252672, 3891712, 0, 12288, 6223872, 104742912

Offset: 0

Christian Stump, Oct 26 2015

Conjecture: column k > 0 is asymptotic to n * 2^(n-2*k) * k^(n-1). - Vaclav Kotesovec, Oct 26 2015

			Triangle begins:
  1;
  1;
  0,  2;
  0,  6;
  0, 16,   8;
  0, 40,  80;
  0, 96, 528, 96;
  ...

Alois P. Heinz, Rows n = 0..200, flattened
FindStat - Combinatorial Statistic Finder, The number of cyclic valleys and cyclic peaks of a permutation.

Columns k=1-6 give: A057711 (for n>1), A159710, A159711, A159712, A159713, A159714.
Row sums give A000142.
Cf. A000142, A008303.

b:= proc(u, o, t) option remember; expand(`if`(u+o=0, x,
      add(b(u-j, o+j-1, 0), j=1..u)*`if`(min(t, n)>0, x, 1)+
      add(b(u+j-1, o-j, 1), j=1..o)))
    end:
T:= n-> `if`(n<2, 1, (p-> seq(n*coeff(p, x, i)
        , i=0..degree(p)))(b(n-1, 0$2))):
seq(T(n), n=0..14);  # Alois P. Heinz, Oct 28 2015

b[u_, o_, t_] := b[u, o, t] = Expand[If[u+o == 0, x, Sum[b[u-j, o+j-1, 0], {j, 1, u}]*If[Min[t, n] > 0, x, 1] + Sum[b[u+j-1, o-j, 1], {j, 1, o}]]]; T[n_] := If[n<2, 1, Function[p, Table[n*Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][b[n-1, 0, 0]]]; Table[T[n], {n, 0, 14}] // Flatten (* Jean-François Alcover, Jan 24 2017, after Alois P. Heinz *)

T(n,k) = n*A008303(n-1, k-1) for n > 1. - Andrew Howroyd, May 13 2020

More terms from Alois P. Heinz, Oct 26 2015

A000487 Number of permutations of length n with exactly two valleys.

Original entry on oeis.org

16, 272, 2880, 24576, 185856, 1304832, 8728576, 56520704, 357888000, 2230947840, 13754155008, 84134068224, 511780323328, 3100738912256, 18733264797696, 112949304754176, 680032201605120, 4090088616099840, 24582312700149760, 147669797096652800

Offset: 5

N. J. A. Sloane

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

T. D. Noe, Table of n, a(n) for n = 5..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.
C. J. Fewster, D. Siemssen, Enumerating Permutations by their Run Structure, arXiv preprint arXiv:1403.1723 [math.CO], 2014.
R. G. Rieper and M. Zeleke, Valleyless Sequences, arXiv:math/0005180 [math.CO], 2000.
Index entries for linear recurrences with constant coefficients, signature (20,-160,656,-1456,1664,-768).

Cf. A000431, A000517, A130651.

Column k=2 of A008303.

nn = 30; Drop[CoefficientList[Series[16 x^5 (1 - 3 x)/((1 - 2 x)^3*(1 - 4 x)^2*(1 - 6 x)), {x, 0, nn}], x], 5] (* T. D. Noe, Jun 20 2012 *)

G.f.: 16x^5(1-3x)/((1-2x)^3*(1-4x)^2*(1-6x)). - Ralf Stephan, Sep 18 2003 [Proved by Désiré André, 1895, p. 154, for circular permutations (see A008303). Peter Luschny, Aug 07 2019]

a(n) = (6^n + (2 - 2n)4^n + (2n^2 - 4n - 1)2^n)/32. - Mitchell Harris, Apr 02 2004

More terms from Ralf Stephan, Sep 18 2003

A000517 Number of permutations of length n with exactly three valleys.

Original entry on oeis.org

272, 7936, 137216, 1841152, 21253376, 222398464, 2174832640, 20261765120, 182172651520, 1594922762240, 13684856848384, 115620218667008, 965271355195392, 7984436548730880, 65569731961159680, 535438370914959360, 4353038473793372160, 35266789418949672960

Offset: 7

N. J. A. Sloane

nonn

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

T. D. Noe, Table of n, a(n) for n = 7..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.
C. J. Fewster, D. Siemssen, Enumerating Permutations by their Run Structure, arXiv preprint arXiv:1403.1723 [math.CO], 2014.
R. G. Rieper and M. Zeleke, Valleyless Sequences, arXiv:math/0005180 [math.CO], 2000.
Index entries for linear recurrences with constant coefficients, signature (40, -700, 7056, -45360, 194304, -561728, 1082624, -1332224, 946176, -294912).

Cf. A000431, A000487.

Column k=3 of A008303.

nn = 20; Drop[CoefficientList[Series[16 x^7 (17 - 184 x + 636 x^2 - 720 x^3)/((1 - 2 x)^4*(1 - 4 x)^3*(1 - 6 x)^2*(1 - 8 x)), {x, 0, nn}], x], 7] (* T. D. Noe, Jun 20 2012 *)
LinearRecurrence[{40, -700, 7056, -45360, 194304, -561728, 1082624, -1332224, 946176, -294912}, {272, 7936, 137216, 1841152, 21253376, 222398464, 2174832640, 20261765120, 182172651520, 1594922762240}, 20] (* Jean-François Alcover, Feb 09 2016 *)

G.f.: 16x^7(17-184x+636x^2-720x^3)/((1-2x)^4*(1-4x)^3*(1-6x)^2*(1-8x)). - Ralf Stephan, Sep 18 2003 [Proved by Désiré André, 1895, p.154, for circular permutations (see A008303). Peter Luschny, Aug 07 2019]

More terms from Ralf Stephan, Sep 18 2003

cp's OEIS Frontend

A334774 Triangle read by rows: T(n,k) is the number of permutations of 2 indistinguishable copies of 1..n with exactly k local maxima.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A242783 Number T(n,k) of permutations of [n] with exactly k (possibly overlapping) occurrences of the consecutive step pattern given by the binary expansion of n, where 1=up and 0=down; triangle T(n,k), n>=0, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A008970 Triangle T(n,k) = P(n,k)/2, n >= 2, 1 <= k < n, of one-half of number of permutations of 1..n such that the differences have k runs with the same signs.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A059427 Triangle read by rows: T(n,k) is the number of permutations of [n] with k alternating runs (n>=2, k>=1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A000708 a(n) = E(n+1) - 2*E(n), where E(i) is the Euler number A000111(i).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Python

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