A242783 -id:A242783 - cp's OEIS frontend

A242784 Number A(n,k) of permutations of [n] avoiding the consecutive step pattern given by the binary expansion of k, where 1=up and 0=down; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 4, 1, 1, 1, 1, 2, 5, 8, 1, 1, 1, 1, 2, 6, 17, 16, 1, 1, 1, 1, 2, 6, 21, 70, 32, 1, 1, 1, 1, 2, 6, 19, 90, 349, 64, 1, 1, 1, 1, 2, 6, 21, 70, 450, 2017, 128, 1, 1, 1, 1, 2, 6, 23, 90, 331, 2619, 13358, 256, 1, 1

Offset: 0

Alois P. Heinz, May 22 2014

			A(4,5) = 19 because there are 4! = 24 permutations of {1,2,3,4} and only 5 of them do not avoid the consecutive step pattern up, down, up given by the binary expansion of 5 = 101_2: (1,3,2,4), (1,4,2,3), (2,3,1,4), (2,4,1,3), (3,4,1,2).
Square array A(n,k) begins:
  1, 1,   1,     1,     1,     1,     1,     1,     1, ...
  1, 1,   1,     1,     1,     1,     1,     1,     1, ...
  1, 1,   2,     2,     2,     2,     2,     2,     2, ...
  1, 1,   4,     5,     6,     6,     6,     6,     6, ...
  1, 1,   8,    17,    21,    19,    21,    23,    24, ...
  1, 1,  16,    70,    90,    70,    90,   111,   116, ...
  1, 1,  32,   349,   450,   331,   450,   642,   672, ...
  1, 1,  64,  2017,  2619,  1863,  2619,  4326,  4536, ...
  1, 1, 128, 13358, 17334, 11637, 17334, 33333, 34944, ...

Alois P. Heinz, Antidiagonals n = 0..140, flattened

Columns give: 0, 1: A000012, 2: A011782, 3: A049774, 4, 6: A177479, 5: A177477, 7: A117158, 8, 14: A177518, 9: A177519, 10: A177520, 11, 13: A177521, 12: A177522, 15: A177523, 16, 30: A177524, 17: A177525, 18, 22: A177526, 19, 25: A177527, 20, 26: A177528, 21: A177529, 23, 29: A177530, 24, 28: A177531, 27: A177532, 31: A177533, 32, 62: A177534, 33: A177535, 34, 46: A177536, 35, 49: A177537, 36, 54: A177538, 37, 41: A177539, 38: A177540, 39, 57: A177541, 40, 58: A177542, 42: A177543, 43, 53: A177544, 44, 50: A177545, 45: A177546, 47, 61: A177547, 48, 60: A177548, 51: A177549, 52: A177550, 55, 59: A177551, 56: A177552, 63: A177553, 127: A230051, 255: A230231, 511: A230232, 1023: A230233, 2047: A254523.
Main diagonal gives A242785.
Cf. A242783, A335308.

A:= proc(n, k) option remember; local b, m, r, h;
      if k<2 then return 1 fi;
      m:= iquo(k, 2, 'r'); h:= 2^ilog2(k);
      b:= proc(u, o, t) option remember; `if`(u+o=0, 1,
      `if`(t=m and r=0, 0, add(b(u-j, o+j-1, irem(2*t, h)), j=1..u))+
      `if`(t=m and r=1, 0, add(b(u+j-1, o-j, irem(2*t+1, h)), j=1..o)))
      end; forget(b);
      b(n, 0, 0)
    end:
seq(seq(A(n, d-n), n=0..d), d=0..15);

Clear[A]; A[n_, k_] := A[n, k] = Module[{b, m, r, h}, If[k < 2, Return[1]]; {m, r} = QuotientRemainder[k, 2]; h = 2^Floor[Log[2, k]]; b[u_, o_, t_] := b[u, o, t] = If[u + o == 0, 1, If[t == m && r == 0, 0, Sum[b[u - j, o + j - 1, Mod[2*t, h]], {j, 1, u}]] + If[t == m && r == 1, 0, Sum[b[u + j - 1, o - j, Mod[2*t + 1, h]], {j, 1, o}]]]; b[n, 0, 0]]; Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 15}] // Flatten (* Jean-François Alcover, Sep 22 2014, translated from Maple *)

A008303 Triangle read by rows: T(n,k) (n >= 1, 0 <= k <= ceiling(n/2)-1) = number of permutations of [n] with k peaks.

Original entry on oeis.org

1, 2, 4, 2, 8, 16, 16, 88, 16, 32, 416, 272, 64, 1824, 2880, 272, 128, 7680, 24576, 7936, 256, 31616, 185856, 137216, 7936, 512, 128512, 1304832, 1841152, 353792, 1024, 518656, 8728576, 21253376, 9061376, 353792, 2048, 2084864, 56520704, 222398464, 175627264, 22368256

Offset: 1

N. J. A. Sloane

From Petros Hadjicostas, Aug 06 2019: (Start)
André (1895) first defined these numbers. In his notation, T(n, k) = Q(n+1, 2*(k+1)) for n >= 1 and 0 <= k <= ceiling(n/2)-1.
His triangle is as follows (p. 148):
  Q_{2,2}
  Q_{3,2}
  Q_{4,2} Q_{4,4}
  Q_{5,2} Q_{5,4}
  Q_{6,2} Q_{6,4} Q_{6,6}
  Q_{7,2} Q_{7,4} Q_{7,6}
  ...
He has Q(n, s) = 0 when either s is odd, or n <= 1, or s > n. Also, Q_{n,2} = 2^(n-2) for n >= 2.
His recurrence is Q(n, s) = s * Q(n-1, s) + (n - s + 1) * Q(n-1, s-2) for n >= 3 and s >= 2. (Obviously, for s odd, we get Q(n, s) = 0 + 0 = 0.)
In terms of the current array, André's (1895) recurrence becomes T(n, k) = (2*k + 2) * T(n-1, k) + (n - 2*k) * T(n-1, k-1) for n >= 2 and 1 <= k <= n with T(n, 0) = 2^(n-1) for n >= 1. In this recurrence, we assume T(n, k) = 0 for k >= ceiling(n/2) or k < 0. (End)
From Petros Hadjicostas, Aug 07 2019: (Start)
We clarify further the quantity Q(n, s) defined by André (1895). In his paper, André considers circular permutations of [n] and deals with maxima, minima, and so-called "séquences" in a permutation.
The term "séquence" in a permutation, as used by André in several of his papers in the 19th century, means a list of consecutive numbers in the permutation that go from a maximum to a minimum, or vice versa, and do not contain any interior minima or maxima. This terminology is also repeated in Ex. 13 (pp. 260-261) by Comtet (even though he refers to the corresponding indices rather than the numbers in the permutation itself).
Some authors call these so-called "séquences" (defined by André and Comtet) "alternate runs" (or just "runs"). Here we are actually dealing with "circular runs" if we read these so-called "séquences" in ascending order in one of the two directions on a circle.
Q(n, s) is the number of circular permutations of [n] (out of the (n-1)! in total) that have exactly s of these so-called "séquences" ("alternate runs").
André (1895) proves that, in a circular permutation of [n], the number of maxima equals the number of minima and that the number of his so-called "séquences" ("alternate runs") is always even (i.e., Q(n, s) = 0 for s odd).
He also shows that, if v = floor(n/2), then the only possible values for the length of a so-called "séquence" ("alternate run") in a circular permutation of [n] are 2, 4, ..., 2*v. That is why Q(n, s) = 0 when either s is odd, or n <= 1, or s > n.
Note that Sum_{t = 1..floor(n/2)} Q_{n, 2*t} = Sum_{t = 1..floor(n/2)} T(n-1, t-1) = (n-1)! = total number of circular permutations of [n].
Since T(n, k) = Q(n+1, 2*(k+1)) for n >= 1 and 0 <= k <= ceiling(n/2)-1, we conclude that the number of (linear) permutations of [n] with k peaks equals the number of circular permutations of [n+1] with exactly 2*(k+1) of these so-called "séquences" ("alternate runs"). (End)
From Petros Hadjicostas, Aug 08 2019: (Start)
The author of this array indirectly assumes that a "peak" of a (linear) permutation of [n] is an interior maximum of the permutation; i.e., we ignore maxima at the endpoints of a permutation.
Similarly, a "valley" of a (linear) permutation of [n] is an interior minimum of the permutation; i.e., we ignore minima at the endpoints of the permutation.
Since the complement of a permutation a_1 a_2 ... a_n (using one-line notation, not cycle notation) is (n+1-a_1) (n+1-a_2) ... (n+1-a_n), it follows that, for n >= 2 and 0 <= k <= ceiling(n/2) - 1, T(n, k) is also the number of (linear) permutations of [n] with exactly k valleys. (End)

			Triangle T(n,k) (with rows n >= 1 and columns k >= 0) starts as follows:
  [ 1]    1;
  [ 2]    2;
  [ 3]    4,       2;
  [ 4]    8,      16;
  [ 5]   16,      88,      16;
  [ 6]   32,     416,     272;
  [ 7]   64,    1824,    2880,     272;
  [ 8]  128,    7680,   24576,    7936;
  [ 9]  256,   31616,  185856,  137216,    7936;
  [10]  512,  128512, 1304832, 1841152,  353792;
    A000079, A000431, A000487, A000517, A179708, ...
T(3,1) = 2 because we have 132 and 231.
From _Petros Hadjicostas_, Aug 07 2019: (Start)
In terms of André's (1895) notation (see the comments above), we have Q(4, 2) = T(3, 0) = 4 and Q(4, 4) = T(3, 1) = 2.
Out of the (4-1)! = 6 circular permutations of [4], each of the permutations 1324 and 1423 has exactly 4 so-called "séquences" ("alternate runs"), while each of the rest (1234, 1243, 1342, and 1432) has exactly 2 so-called "séquences" ("alternate runs").
In detail, we list the so-called "séquences" ("alternate runs") of the above circular permutations:
  1234 --> 1234 and 41 (maximum 4 and minimum 1).
  1243 --> 124 and 431 (maximum 4 and minimum 1).
  1324 --> 13, 32, 24, and 41 (maxima 3, 4, and minima 1, 2).
  1342 --> 134 and 421 (maximum 4 and minimum 1).
  1423 --> 14, 42, 23, and 31 (maxima 3, 4 and minima 1, 2),
  1432 --> 14 and 4321 (maximum 4 and minimum 1).
(End)

Florence Nightingale David and D. E. Barton, Combinatorial Chance, Charles Griffin, 1962; see Table 10.6, p. 163. [They use the notation T_{N,t^*}^{**}, where N is the length of the permutation and t^* is the number of peaks in the permutation. They also give André's recurrence. So, here n = N and k = t^*. - Petros Hadjicostas, Aug 09 2019]
Florence Nightingale David, Maurice George Kendall, and D. E. Barton, Symmetric Functions and Allied Tables, Cambridge, 1966, p. 261, Table 7.3.
I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983, Ex. 3.3.46. - Emeric Deutsch, Jul 26 2009
T. K. Petersen, Eulerian Numbers, Birkhäuser, 2015, Chapter 4.

Alois P. Heinz, Rows n = 1..200, flattened (first 30 rows from Vincenzo Librandi)
Max A. Alekseyev, On the number of permutations with bounded run lengths, arXiv preprint arXiv:1205.4581 [math.CO], 2012-2013. - From _N. J. A. Sloane_, Oct 23 2012
Désiré André, Mémoire sur les séquences des permutations circulaires, Bulletin de la S. M. F., tome 23 (1895), pp. 122-184.
T. Austin, R. Fagen, T. Lehrer, and W. Penney, The distribution of the number of locally maximal elements in a random sample, Ann. Math. Statist. 28 (1957), 786-790. - _Ira M. Gessel_, Aug 06 2014
Jean-Luc Baril and José L. Ramírez, Some distributions in increasing and flattened permutations, arXiv:2410.15434 [math.CO], 2024. See p. 3.
S. Billey, K. Burdzy, and B. E. Sagan, Permutations with given peak set, 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.-O. Chow and S.-M. Ma, Counting signed permutations by their alternating runs, Discrete Mathematics, 323 (2014), 49-57.
C.-O. Chow, S.-M. Ma, T. Mansour, and M. Shattuck, Counting permutations by cyclic peaks and valleys, Annales Mathematicae et Informaticae 43 (2014), 43-54.
Kieran Clenaghan, In Praise of Sequence (Co-)Algebra and its implementation in Haskell, arXiv:1812.05878 [math.CO], 2019. See page 36.
Colin Defant, Troupes, Cumulants, and Stack-Sorting, arXiv:2004.11367 [math.CO], 2020.
Ming-Jian Ding and Bao-Xuan Zhu, Some results related to Hurwitz stability of combinatorial polynomials, Advances in Applied Mathematics, Volume 152, (2024), 102591. See p. 13.
S. Elizalde and M. Noy, Consecutive patterns in permutations, Adv. Appl. Math. 30 (2003), 110-125; see Section 5.
R. C. Entringer, Enumeration of permutations of (1,...,n) by number of maxima, Duke Math. J. 36 (1969), 575-579. - _Ira M. Gessel_, Oct 23 2013
C. J. Fewster and D. Siemssen, Enumerating Permutations by their Run Structure, arXiv preprint arXiv:1403.1723 [math.CO], 2014.
FindStat - Combinatorial Statistic Finder, The number of inner peaks of a permutation, The number of peaks of a permutation, The number of valleys of a permutation.
W. O. Kermack and A. G. McKendrick, Some distributions associated with a randomly arranged set of numbers, Proc. Royal Soc. of Edinburgh 67 (1937), 332-376.
W. O. Kermack and A. G. McKendrick, Some properties of points arranged on a Möbius surface, Mathematical Gazette 22 (1938), 66-72.
Shi-Mei Ma, Derivative polynomials and permutations by numbers of interior peaks and left peaks, arXiv preprint arXiv:1106.5781 [math.CO], 2011.
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.
Shi-Mei Ma, Toufik Mansour, David G.L. Wang, and Yeong-Nan Yeh, Several variants of the Dumont differential system and permutation statistics, Science China Mathematics 60 (2018).
Shi-Mei Ma, Jun Ma, Jean Yeh, and Yeong-Nan Yeh, The 1/k-Eulerian polynomials of type B, arXiv:2001.07833 [math.CO], 2020.
A. Mendes and J. B. Remmel, Permutations and words counted by consecutive patterns, Adv. Appl. Math. 37(4) (2006), 443-480.
Tom Roberts and Thomas Prellberg, Improving Convergence of Generalised Rosenbluth Sampling for Branched Polymer Models by Uniform Sampling, arXiv:2401.12201 [cond-mat.stat-mech], 2024. See p. 14.
Louis W. Shapiro, Wen-Jin Woan, and Seyoum Getu, Runs, slides and moments, SIAM J. Algebraic and Discrete Methods 4 (1983), 459-466; see p. 461.
Bao-Xuan Zhu, Stieltjes moment properties and continued fractions from combinatorial triangles, arXiv:2007.14924 [math.CO], 2020, see p. 27.
Yan Zhuang, Monoid networks and counting permutations by runs, arXiv preprint arXiv:1505.02308 [math.CO], 2015.
Yan Zhuang, Counting permutations by runs, J. Comb. Theory Ser. A 142 (2016), pp. 147-176.

From Emeric Deutsch, Jul 26 2009: (Start)
Sum of entries in row n is n! = A000142(n).
T(n,0) = 2^(n-1) = A000079(n-1).
T(n,1) = A000431(n).
T(n,2) = A000487(n).
T(n,3) = A000517(n).
T(2n, n-1) = T(2n+1, n) = A000182(n+1) (the tangent numbers). (End)
Columns k = 0-6 give: A011782, A000431, A000487, A000517, A179708, A179709, A179710.
Cf. A000111, A000182, A090672, A101280, A185896, A242783, A242784.

# The Maple program yields (by straightforward counting) the generating polynomial of the row n specified in the program.
n := 8: with(combinat): P := permute(n): st := proc (p) local ct, j: ct := 0: for j from 2 to nops(p)-1 do if p[j-1] < p[j] and p[j+1] < p[j] then ct := ct+1 else end if end do: ct end proc: sort(add(t^st(P[j]), j = 1 .. factorial(n))); # Emeric Deutsch, Jul 26 2009
# Second Maple program:
a := 1+sqrt(1-t): b := 1-sqrt(1-t): G := (exp(b*z)-exp(a*z))/(b*exp(a*z)-a*exp(b*z)): Gser := simplify(series(G, z = 0, 15)): for n to 12 do P[n] := sort(expand(factorial(n)*coeff(Gser, z, n))) end do: for n to 12 do seq(coeff(P[n], t, j), j = 0 .. ceil((1/2)*n)-1) end do; # yields sequence in triangular form - Emeric Deutsch, Jul 26 2009
# Third Maple program:
b:= proc(u, o, t) option remember; expand(`if`(u+o=0, 1,
      add(b(u-j, o+j-1, 0)*x^t, j=1..u)+
      add(b(u+j-1, o-j, 1), j=1..o)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$2)):
seq(T(n), n=1..15);  # Alois P. Heinz, May 22 2014
# Recurrence of D. André (1895).
T := proc(n, k) option remember;
if n < 1 or 2*k > (n-1) then return 0 fi;
if k = 0 then return 2^(n-1) fi;
(2*k + 2)*T(n-1, k) + (n - 2*k)*T(n-1, k-1) end:
seq(seq(T(n, k), k=0..(n-1)/2), n=1..12); # Peter Luschny, Aug 06 2019

From Luc Roy, Jul 08 2010: (Start)
It appears that one-half of the sequence A008303 can be obtained with this Mathematica program:
Expand[CoefficientList[Simplify[InverseSeries[Integrate[
Series[(1 + m Sinh[x]^2)^(-1), {x, 0, 15}, {m, 0, 15}], x]]], x]
Denominator[CoefficientList[Series[Exp[x], {x, 0, 15}], x]]]
(* Mathematica Output of Luc Roy's program *)
{0, 1, 0, 2 m, 0, 8 m + 16 m^2, 0, 32 m + 416 m^2 + 272 m^3, 0, 128 m + 7680 m^2 + 24576 m^3 + 7936 m^4, 0, 512 m + 128512 m^2 + 1304832 m^3 + 1841152 m^4 + 353792 m^5, 0, 2048 m + 2084864 m^2 + 56520704 m^3 + 222398464 m^4 + 175627264 m^5 + 22368256 m^6, 0, 8192 m + 33497088 m^2 + 2230947840 m^3 + 20261765120 m^4 + 41731645440 m^5 + 21016670208 m^6 + 1903757312 m^7}
(End)
(* Another Mathematica program *)
m = 14; a = 1 + Sqrt[1 - t]; b = 1 - Sqrt[1 - t];
g[z_] = (E^(b*z) - E^(a*z))/(b*E^(a*z) - a*E^(b*z));
gser = Series[g[z], {z, 0, m}];
Do[p[n]=n!*Coefficient[gser, z, n]//Simplify, {n, 0, m}];
Flatten[ Table[ Coefficient[p[n], t, j], {n, 0, m}, {j, 0, Ceiling[n/2] - 1}]]
(* Jean-François Alcover, May 27 2011, after Emeric Deutsch *)
(* To get the triangle from Jean-François Alcover's Mathematica program *)
FormTable[Table[Coefficient[p[n], t, j], {n, 0, m}, {j, 0, Ceiling[n/2] - 1}]]
(* Petros Hadjicostas, Aug 06 2019 *)
gf := Sqrt[x - 1] Cot[y Sqrt[x - 1]] - 1; ser := Series[1/gf, {y, 0, 16}];
cy[n_] := n! Coefficient[ser, y, n]; row[n_] := CoefficientList[cy[n], x];
Table[row[n], {n, 1, 12}] // Flatten (* Peter Luschny, Aug 06 2019 *)

{T(n, k) = if(n<1, 0, my(z = sqrt(1 - y + y*O(y^(n\2)))); n!*polcoef(polcoef(z/(z - tanh(x*z)), n, x), k))}; /* Michael Somos, May 24 2023 */

From Emeric Deutsch, Jul 26 2009: (Start)
E.g.f.: G(t,z)=[exp(bz)-exp(az)]/[b*exp(az)-a*exp(bz)], where a+b=2 and ab=t, i.e., a=1+sqrt(1-t), b=1-sqrt(1-t) (see the Goulden-Jackson reference). -
Sum_{k>=0} k*T(n,k) = n!*(n-2)/3 = A090672(n-1).
Row n has ceiling(n/2) terms. (End)
E.g.f.: tan(t*sqrt(x-1))/(sqrt(x-1)-tan(t*sqrt(x-1))) = Sum_{n>=0} P(n,x)*t^n/n! = t + 2*t^2/2! + (4+2*x)*t^3/3! + (8+16*x)*t^4/4! + .... The row generating polynomials P(n,x) satisfy x^(n-1)*P(n,1+1/x^2) = R(n-1,x), where R(n,x) are the row polynomials of A185896. A000670(n) = (3/2)^(n-1)*P(n,8/9). - Peter Bala, Oct 14 2011
From Jinyuan Wang, Dec 28 2020: (Start)
T(n, k) = (n - 2*k + 2)*T(n-1, k-1) + 2*k*T(n-1, k) for n > 1 and k > 1; T(n, 1) = 2^(n - 1); T(1, k) = 0 for k > 1.
T(2*k-1, k) = A000182(k). (End)
From Ammar Khatab, Aug 17 2024: (Start)
T(2*n,k) = 4^(n-k+1)* Sum_{p=0..k} (-1)^p * (2*p+2*n-2*k-1)/(p+2*n-2*k-1) binomial(p+2*n-2*k-1,p) (A008292(2*n,k-p+1)+A008292(2*n,2*n+p-k) ) for n>0.
T(2*n+1,k) = 4^(n-k)* Sum_{p=0..k} (-1)^p * (p+n-k)/(p+2*n-2*k) binomial(p+2*n-2*k,p) (A008292(2*n+1,k-p+1)+A008292(2*n,2*n+p-k+1) ) for k<>n. (End)

Additional comments from Emeric Deutsch, May 08 2004
More terms from R. J. Mathar and Vladeta Jovovic, Jun 26 2007
Corrected by Emeric Deutsch, Jul 26 2009
Edited definition - N. J. A. Sloane, May 25 2023

A162975 Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} having k doubledescents (0 <= k <= n-2). We say that i is a doubledescent (also called a double fall) of a permutation p if p(i) > p(i+1) > p(i+2).

Original entry on oeis.org

1, 1, 2, 5, 1, 17, 6, 1, 70, 41, 8, 1, 349, 274, 86, 10, 1, 2017, 2040, 803, 167, 12, 1, 13358, 16346, 8221, 2064, 316, 14, 1, 99377, 143571, 86214, 28143, 4961, 597, 16, 1, 822041, 1365354, 966114, 374166, 88482, 11486, 1138, 18, 1

Offset: 0

Emeric Deutsch, Jul 26 2009

Row n (n>=2) contains n-1 entries.
Sum of entries in row n is n! = A000142(n).
Sum_{k=0..n-2} k*T(n,k) = A005990(n-1).
The first Maple program yields (by straightforward counting) the generating polynomial of a specified row n.

			T(5,2) = 8 because we have 15432, 25431, 35421, 43215, 45321, 53214, 54213, and 54312.
Triangle starts:
    1;
    1;
    2;
    5,   1;
   17,   6,   1;
   70,  41,   8,   1;
  349, 274,  86,  10,   1;

I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, New York, 1983.

Alois P. Heinz, Rows n = 0..142, flattened
S. Elizalde and M. Noy, Consecutive patterns in permutations, Adv. Appl. Math. 30 (2003), 110-123.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 210
Yan Zhuang, Monoid networks and counting permutations by runs, arXiv preprint arXiv:1505.02308 [math.CO], 2015.
Y. Zhuang, Counting permutations by runs, J. Comb. Theory Ser. A 142 (2016), pp. 147-176.

Columns k=0..10 give A049774, A274997, A230621, A279292, A279293, A279294, A279295, A279296, A279297, A279298, A279299.

Cf. A000142, A005990, A162976, A242783, A242784.

n := 7: dds := proc (p) local ct, j: ct := 0: for j from 3 to nops(p) do if p[j] < p[j-1] and p[j-1] < p[j-2] then ct := ct+1 else end if end do: ct end proc: with(combinat): P := permute(n): f[n] := sort(add(t^dds(P[i]), i = 1 .. factorial(n)));
# second Maple program:
b:= proc(u, o, t) option remember; `if`(u+o=0, 1, expand(
      add(b(u-j, o+j-1, 1), j=1..u)+
      add(b(u+j-1, o-j, 2)*`if`(t=2, x, 1), j=1..o)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0, 1)):
seq(T(n), n=0..15);  # Alois P. Heinz, Oct 25 2013

nn=10; u=y-1; a=Apply[Plus, Table[Normal[Series[y x^3/(1-y x - y x^2), {x,0,nn}]][[n]]/(n+2)!, {n,1,nn-2}]]/.y->u; Range[0,nn]! CoefficientList[Series[1/(1-x-a), {x,0,nn}], {x,y}]//Grid  (* Geoffrey Critzer, Dec 12 2012 *)

E.g.f.: 1/(1 - x - Sum_{k,n} I(n,k)(y - 1)^k*x^n/n!) where I(n,k) is the coefficient of y^k*x^n in the ordinary generating function expansion of y x^3/(1 - y*x - y*x^2). See Flajolet and Sedgewick reference in Links section. - Geoffrey Critzer, Dec 12 2012

A242819 Number T(n,k) of permutations of [n] with exactly k occurrences of the consecutive step pattern up, down, down; triangle T(n,k), n>=0, 0<=k<=max(0,floor((n-1)/3)), read by rows.

Original entry on oeis.org

1, 1, 2, 6, 21, 3, 90, 30, 450, 270, 2619, 2322, 99, 17334, 20772, 2214, 129114, 195372, 38394, 1067661, 1958337, 591543, 11259, 9713682, 20933154, 8826246, 443718, 96393726, 238789782, 131367258, 12450834, 1036348587, 2900868876, 1989555210, 297195804, 3052323

Offset: 0

Alois P. Heinz, May 23 2014

T(n,k) is also the number of permutations of [n] with exactly k occurrences of the consecutive step pattern up, up, down.
From Vaclav Kotesovec, Aug 26 2014: (Start)
Column k is asymptotic to c(k) * (3*sqrt(3)/(2*Pi))^n * n! * n^k.
Conjecture: c(k) = c(0) * (c(0)-1)^k / (3^k * k!).
Verified numerically:
c(0) = 1.96650951227123825842868... = (1+exp(Pi/sqrt(3)))*sqrt(3)/(2*Pi)
c(1) = 0.63355004986067503869384...
c(2) = 0.10205535828170995196503...
c(3) = 0.01095971939528021798...
c(4) = 0.000882722753946826148...
c(5) = 0.00005687732922585807984...
c(6) = 0.000003054026651631929902...
c(7) = 0.0000001405593242634352116...
c(8) = 0.00000000566049683079281633...
c(9) = 0.0000000002026268159682390665...
c(10)= 0.00000000000652802483581788974...
c(20)= 1.172921625090753...*10^(-28)
c(30)= 1.2959323...*10^(-47)
c(40)= 5.0751...*10^(-68)
(End)

			T(4,1) = 3: (1,4,3,2), (2,4,3,1), (3,4,2,1).
Triangle T(n,k) begins:
:  0 :       1;
:  1 :       1;
:  2 :       2;
:  3 :       6;
:  4 :      21,        3;
:  5 :      90,       30;
:  6 :     450,      270;
:  7 :    2619,     2322,      99;
:  8 :   17334,    20772,    2214;
:  9 :  129114,   195372,   38394;
: 10 : 1067661,  1958337,  591543,  11259;
: 11 : 9713682, 20933154, 8826246, 443718;

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

Columns k=0-10 give: A177479, A246246, A246247, A246248, A246249, A246250, A246251, A246252, A246253, A246254, A246255.
Row sums give: A000142.
Cf. A242783, A242784, A295987.

b:= proc(u, o, t) option remember; `if`(u+o=0, 1, expand(
      add(b(u-j, o+j-1, [1, 3, 1][t])*`if`(t=3, x, 1), j=1..u)+
      add(b(u+j-1, o-j, 2), j=1..o)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0, 1)):
seq(T(n), n=0..15);

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

A295987 Number T(n,k) of permutations of [n] with exactly k (possibly overlapping) occurrences of the consecutive step patterns 010 or 101, where 1=up and 0=down; triangle T(n,k), n >= 0, k = max(0, n-3), read by rows.

Original entry on oeis.org

1, 1, 2, 6, 14, 10, 52, 36, 32, 204, 254, 140, 122, 1010, 1368, 1498, 620, 544, 5466, 9704, 9858, 9358, 3164, 2770, 34090, 67908, 90988, 72120, 63786, 18116, 15872, 233026, 545962, 762816, 839678, 560658, 470262, 115356, 101042, 1765836, 4604360, 7458522

Offset: 0

Alois P. Heinz, Dec 01 2017

			Triangle T(n,k) begins:
:      1;
:      1;
:      2;
:      6;
:     14,     10;
:     52,     36,     32;
:    204,    254,    140,    122;
:   1010,   1368,   1498,    620,    544;
:   5466,   9704,   9858,   9358,   3164,   2770;
:  34090,  67908,  90988,  72120,  63786,  18116,  15872;
: 233026, 545962, 762816, 839678, 560658, 470262, 115356, 101042;

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

Column k=0 gives A295974.
Last elements of rows for n>3 give: A001250, A260786, 2*A000111.
Row sums give A000142.
Cf. A227884, A230695, A230797, A231384, A232933, A242783, A242819, A242820, A296054.

b:= proc(u, o, t, h) option remember; expand(
           `if`(u+o=0, 1, `if`(t=0, add(b(u-j, j-1, 1$2), j=1..u),
       add(`if`(h=3, x, 1)*b(u-j, o+j-1, [1, 3, 1][t], 2), j=1..u)+
       add(`if`(t=3, x, 1)*b(u+j-1, o-j, 2, [1, 3, 1][h]), j=1..o))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$3)):
seq(T(n), n=0..12);

b[u_, o_, t_, h_] := b[u, o, t, h] = Expand[If[u + o == 0, 1, If[t == 0, Sum[b[u - j, j - 1, 1, 1], {j, 1, u}], Sum[If[h == 3, x, 1]*b[u - j, o + j - 1, {1, 3, 1}[[t]], 2], {j, 1, u}] + Sum[If[t == 3, x, 1]*b[u + j - 1, o - j, 2, {1, 3, 1}[[h]]], {j, 1, o}]]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][ b[n, 0, 0, 0]];
Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, Jun 07 2018, from Maple *)

A230797 Number T(n,k) of permutations of [n] with exactly k (possibly overlapping) occurrences of the consecutive step pattern up, down, up, down; triangle T(n,k), n>=0, 0<=k<=max(0,floor((n-3)/2)), read by rows.

Original entry on oeis.org

1, 1, 2, 6, 24, 104, 16, 528, 192, 3296, 1472, 272, 23168, 12800, 4352, 179712, 132352, 42880, 7936, 1573632, 1366016, 530432, 158720, 15207424, 14781952, 7662336, 1911296, 353792, 158880768, 178102272, 101713920, 31813632, 8491008, 1801996288, 2282645504

Offset: 0

Alois P. Heinz, Oct 30 2013

			T(5,1) = 16: 13254, 14253, 14352, 15243, 15342, 23154, 24153, 24351, 25143, 25341, 34152, 34251, 35142, 35241, 45132, 45231.
T(7,2) = 272: 1325476, 1326475, 1326574, ..., 6735241, 6745132, 6745231.
Triangle T(n,k) begins:
:  0 :       1;
:  1 :       1;
:  2 :       2;
:  3 :       6;
:  4 :      24;
:  5 :     104,      16;
:  6 :     528,     192;
:  7 :    3296,    1472,    272;
:  8 :   23168,   12800,   4352;
:  9 :  179712,  132352,  42880,   7936;
: 10 : 1573632, 1366016, 530432, 158720;

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

Columns k=0-2 give: A177520, A230832, A264077.
T(2n-1,n-2) gives A000182(n) for n>=3.
Row sums give: A000142.
Cf. A242783, A242784, A295987.

b:= proc(u, o, t) option remember; `if`(u+o=0, 1, expand(
      add(b(u-j, o+j-1, [1, 3, 1, 3][t])*`if`(t=4, x, 1), j=1..u)+
      add(b(u+j-1, o-j, [2, 2, 4, 2][t]), j=1..o)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0, 1)):
seq(T(n), n=0..15);  # Alois P. Heinz, Oct 30 2013

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

A227884 Number T(n,k) of permutations of [n] with exactly k (possibly overlapping) occurrences of the consecutive step pattern up, down, up; triangle T(n,k), n>=0, 0<=k<=max(0,floor(n/2)-1), read by rows.

Original entry on oeis.org

1, 1, 2, 6, 19, 5, 70, 50, 331, 328, 61, 1863, 2154, 1023, 11637, 16751, 10547, 1385, 81110, 144840, 102030, 34900, 635550, 1314149, 1109973, 518607, 50521, 5495339, 12735722, 13046040, 6858598, 1781101, 51590494, 134159743, 157195762, 97348436, 36004400

Offset: 0

Alois P. Heinz, Oct 25 2013

			T(4,1) = 5: 1324, 1423, 2314, 2413, 3412.
Triangle T(n,k) begins:
:  0 :      1;
:  1 :      1;
:  2 :      2;
:  3 :      6;
:  4 :     19,       5;
:  5 :     70,      50;
:  6 :    331,     328,      61;
:  7 :   1863,    2154,    1023;
:  8 :  11637,   16751,   10547,   1385;
:  9 :  81110,  144840,  102030,  34900;
: 10 : 635550, 1314149, 1109973, 518607, 50521;

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

Columns k=0-1 give: A177477, A227883.
T(2n,n-1) gives A000364(n) for n>=2.
Row sums give: A000142.
Cf. A000111, A242783, A242784, A295987.

b:= proc(u, o, t) option remember; `if`(u+o=0, 1, expand(
      add(b(u-j, o+j-1, [1, 3, 1][t]), j=1..u)+
      add(b(u+j-1, o-j, 2)*`if`(t=3, x, 1), j=1..o)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0, 1)):
seq(T(n), n=0..15);

b[u_, o_, t_] := b[u, o, t] = If[u+o==0, 1, Expand[Sum[b[u-j, o+j-1, {1, 3, 1}[[t]]], {j, 1, u}]+Sum[b[u+j-1, o-j, 2]*If[t==3, x, 1], {j, 1, o}]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][ b[n, 0, 1]];
Table[T[n], {n, 0, 15}] // Flatten (* Jean-François Alcover, Mar 29 2017, translated from Maple *)

A335308 Number of permutations p of [n] such that the sequence of ascents and descents of p is encoded by the 0's and 1's, respectively, in the binary expansion of n (read from right to left and using leading 0's if necessary).

Original entry on oeis.org

1, 0, 0, 1, 3, 16, 26, 20, 69, 370, 1006, 945, 1266, 3015, 2365, 1001, 4367, 24736, 76960, 69615, 138397, 322944, 286824, 133056, 159391, 546504, 978054, 674245, 531530, 957320, 495495, 142506, 906191, 5537808, 18828096, 16231039, 37000909, 81351936, 71761536

Offset: 0

Alois P. Heinz, Sep 12 2020

			a(0) = 1: (), the empty permutation.
a(3) = 1: 321 (down, down).
a(4) = 3: 1243, 1342, 2341 (up, up, down).
a(5) = 16: 21435, 21534, 31425, 31524, 32415, 32514, 41325, 41523, 42315, 42513, 43512, 51324, 51423, 52314, 52413, 53412 (down, up, down, up).
a(6) = 26: 143256, 153246, 154236, 163245, 164235, 165234, 243156, 253146, 254136, 263145, 264135, 265134, 342156, 352146, 354126, 362145, 364125, 365124, 452136, 453126, 462135, 463125, 465123, 562134, 563124, 564123 (up, down, down, up, up).
a(7) = 20: 4321567, 5321467, 5421367, 5431267, 6321457, 6421357, 6431257, 6521347, 6531247, 6541237, 7321456, 7421356, 7431256, 7521346, 7531246, 7541236, 7621345, 7631245, 7641235, 7651234 (down^3, up^3).

Alois P. Heinz, Table of n, a(n) for n = 0..4095

Cf. A060351, A242783, A242784, A242785.

b:= proc(u, o, t) option remember; `if`(u+o=0, `if`(t=0, 1, 0),
     `if`(irem(t, 2)=0, add(b(u-j, o+j-1, iquo(t, 2)), j=1..u),
      add(b(u+j-1, o-j, iquo(t, 2)), j=1..o)))
    end:
a:= n-> b(n, 0, 2*n):
seq(a(n), n=0..42);

a(n) = A060351(n,n).
a(2^n-1) = binomial(2^n-2,n).
a(2^n) = binomial(2^n,n+1)-1.

A230695 Number T(n,k) of permutations of [n] with exactly k (possibly overlapping) occurrences of the consecutive step pattern up, down, down, up; triangle T(n,k), n>=0, 0<=k<=max(0,floor((n-2)/3)), read by rows.

Original entry on oeis.org

1, 1, 2, 6, 24, 109, 11, 588, 132, 3654, 1386, 26125, 13606, 589, 209863, 139714, 13303, 1876502, 1508756, 243542, 18441367, 17429745, 3953529, 92159, 197776850, 214536114, 63334182, 3354454, 2297242583, 2815529811, 1020982869, 93265537, 28739304385

Offset: 0

Alois P. Heinz, Oct 27 2013

			T(5,1) = 11: 14325, 15324, 15423, 24315, 25314, 25413, 34215, 35214, 35412, 45213, 45312.
T(8,2) = 589: 14327658, 14328657, 14328756, ..., 78635412, 78645213, 78645312.
Triangle T(n,k) begins:
:  0 :        1;
:  1 :        1;
:  2 :        2;
:  3 :        6;
:  4 :       24;
:  5 :      109,       11;
:  6 :      588,      132;
:  7 :     3654,     1386;
:  8 :    26125,    13606,     589;
:  9 :   209863,   139714,   13303;
: 10 :  1876502,  1508756,  243542;
: 11 : 18441367, 17429745, 3953529, 92159;

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

Column k=0 gives: A177519.
Row sums give: A000142.
Cf. A242783, A242784, A295987.

b:= proc(u, o, t) option remember; `if`(u+o=0, 1, expand(
      add(b(u-j, o+j-1, [1, 3, 4, 1][t]), j=1..u)+
      add(b(u+j-1, o-j, 2)*`if`(t=4, x, 1), j=1..o)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0, 1)):
seq(T(n), n=0..15);

b[u_, o_, t_] := b[u, o, t] = If[u + o == 0, 1, Expand[
     Sum[b[u - j, o + j - 1, {1, 3, 4, 1}[[t]]], {j, 1, u}] +
     Sum[b[u + j - 1, o - j, 2]*If[t == 4, x, 1], {j, 1, o}]]];
T[n_] := CoefficientList[b[n, 0, 1], x];
T /@ Range[0, 15] // Flatten (* Jean-François Alcover, Mar 22 2021, after Alois P. Heinz *)

A242785 Number of permutations of [n] avoiding the consecutive step pattern given by the binary expansion of n, where 1=up and 0=down.

Original entry on oeis.org

1, 1, 2, 5, 21, 70, 450, 4326, 34944, 209863, 1573632, 21824925, 302273664, 2854894485, 60269056512, 1207441809209, 19346879737625, 252773481889854, 2918333808555034, 69792946997645295, 982945842995115000, 16085109561896603059, 402131210857811703926

Offset: 0

Alois P. Heinz, May 22 2014

nonn

			a(4) = 21 because there are 4! = 24 permutations of {1,2,3,4} and only 3 of them do not avoid the consecutive step pattern up, down, down given by the binary expansion of 4 = 100_2: (1,4,3,2), (2,4,3,1), (3,4,2,1).

Alois P. Heinz, Table of n, a(n) for n = 0..150

Column k=0 of A242783.
Main diagonal of A242784.
Cf. A335308.

a:= proc(n) option remember; local b, m, r, h;
      if n<2 then return 1 fi;
      m:= iquo(n, 2, 'r'); h:= 2^ilog2(n);
      b:= proc(u, o, t) option remember; `if`(u+o=0, 1,
      `if`(t=m and r=0, 0, add(b(u-j, o+j-1, irem(2*t, h)), j=1..u))+
      `if`(t=m and r=1, 0, add(b(u+j-1, o-j, irem(2*t+1, h)), j=1..o)))
      end; forget(b);
      b(n, 0, 0)
    end:
seq(a(n), n=0..30);

a[n_] := a[n] = Module[{b, m, r, h},
     If[n < 2, Return[1]]; {m, r} = QuotientRemainder[n, 2];
     h = 2^(Length@IntegerDigits[n, 2] - 1);
     b[u_, o_, t_] := b[u, o, t] = If[u + o == 0, 1,
     If[t == m && r == 0, 0,
          Sum[b[u - j, o + j - 1, Mod[2t, h]], {j, 1, u}]] +
     If[t == m && r == 1, 0,
          Sum[b[u + j - 1, o - j, Mod[2t+1, h]], {j, 1, o}]]];
     b[n, 0, 0]];
a /@ Range[0, 30] (* Jean-François Alcover, Mar 23 2021, after Alois P. Heinz *)

cp's OEIS Frontend

A242784 Number A(n,k) of permutations of [n] avoiding the consecutive step pattern given by the binary expansion of k, where 1=up and 0=down; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A008303 Triangle read by rows: T(n,k) (n >= 1, 0 <= k <= ceiling(n/2)-1) = number of permutations of [n] with k peaks.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A162975 Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} having k doubledescents (0 <= k <= n-2). We say that i is a doubledescent (also called a double fall) of a permutation p if p(i) > p(i+1) > p(i+2).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A242819 Number T(n,k) of permutations of [n] with exactly k occurrences of the consecutive step pattern up, down, down; triangle T(n,k), n>=0, 0<=k<=max(0,floor((n-1)/3)), read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A295987 Number T(n,k) of permutations of [n] with exactly k (possibly overlapping) occurrences of the consecutive step patterns 010 or 101, where 1=up and 0=down; triangle T(n,k), n >= 0, k = max(0, n-3), read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A230797 Number T(n,k) of permutations of [n] with exactly k (possibly overlapping) occurrences of the consecutive step pattern up, down, up, down; triangle T(n,k), n>=0, 0<=k<=max(0,floor((n-3)/2)), read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A227884 Number T(n,k) of permutations of [n] with exactly k (possibly overlapping) occurrences of the consecutive step pattern up, down, up; triangle T(n,k), n>=0, 0<=k<=max(0,floor(n/2)-1), read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica