A006157 -id:A006157 - cp's OEIS frontend

A122843 Triangle read by rows: T(n,k) = the number of ascending runs of length k in the permutations of [n] for k <= n.

1, 2, 1, 7, 4, 1, 32, 21, 6, 1, 180, 130, 41, 8, 1, 1200, 930, 312, 67, 10, 1, 9240, 7560, 2646, 602, 99, 12, 1, 80640, 68880, 24864, 5880, 1024, 137, 14, 1, 786240, 695520, 257040, 62496, 11304, 1602, 181, 16, 1, 8467200, 7711200, 2903040, 720720, 133920, 19710, 2360, 231, 18, 1

Offset: 1

David Scambler, Sep 13 2006

Also T(n,k) = number of rising sequences of length k among all permutations. E.g., T(4,3)=6 because in the 24 permutations of n=4, there are 6 rising sequences of length 3: {1,2,3} in {1,2,4,3}, {1,2,3} in {1,4,2,3}, {2,3,4} in {2,1,3,4}, {2,3,4} in {2,3,1,4}, {2,3,4} in {2,3,4,1}, {1,2,3} in {4,1,2,3}. - Harlan J. Brothers, Jul 23 2008
Further comments and formulas from Harlan J. Brothers, Jul 23 2008: (Start)
The n-th row sums to (n+1)!/2, consistent with total count implied by the n-th row in the table of Eulerians, A008292.
Generating this triangle through use of the diagonal polynomials allows one to produce an arbitrary number of "imaginary" columns corresponding to runs of length 0, -1, -2, etc. These columns match A001286, A001048 and the factorial function respectively.
As n->inf, there is a limiting value for the count of each length expressed as a fraction of all rising sequences in the permutations of n. The numerators of the set of limit fractions are given by A028387 and the denominators by A001710.
As a table of diagonals d[i]:
d[1][n] = 1
d[2][n] = 2n
d[3][n] = 3n^2 + 5n - 1
d[4][n] = 4n^3 + 18n^2 + 16n - 6
d[5][n] = 5n^4 + 42n^3 + 106n^2 + 63n - 36
d[6][n] = 6n^5 + 80n^4 + 374n^3 + 688n^2 + 292n - 240
T[n,k] = n!(n(k^2 + k - 1) - k(k^2 - 4) + 1)/(k+2)! + floor(k/n)(1/(k(k+3)+2)), 0 < k <= n.  (End)

			T(3,2) = 4: There are 4 ascending runs of length 2 in the permutations of [3], namely 13 in 132 and in 213, 23 in 231, 12 in 312.
Triangle begins:
    1;
    2,   1;
    7,   4,   1;
   32,  21,   6,   1;
  180, 130,  41,   8,   1;
  ...

C. M. Grinstead and J. L. Snell, Introduction to Probability, American Mathematical Society, 1997, pp.120-131.
Donald E. Knuth. The Art of Computer Programming. Vol. 2. Addison-Wesley, Reading, MA, 1998. Seminumerical algorithms, Third edition, Section 3.3.2, p.67.

Alois P. Heinz, Rows n = 1..141, flattened
Persi Diaconis, Mathematical developments from the analysis of riffle shuffling, p.4.
Francis Edward Su, Rising Sequences in Card Shuffling

Cf. A008292, A097900, A001286, A001048, A000142, A028387, A001710.
Cf. A122844, A001710, A006157, A005460.
T(2n+j,n+j) for j = 0..10 gives A230382, A230251, A230342, A230343, A230344, A230345, A230346, A230347, A230348, A230349, A230350.

T:= (n, k)-> `if`(n=k, 1, n!/(k+1)!*(k*(n-k+1)+1
             -((k+1)*(n-k)+1)/(k+2))):
seq(seq(T(n,k), k=1..n), n=1..10);  # Alois P. Heinz, Sep 11 2013

Table[n!((n(k(k+1)-1)-k(k-2)(k+2)+1))/(k+2)!+Floor[k/n]1/(k(k+3)+2),{n,1,10},{k,1,n}]//TableForm (* Harlan J. Brothers, Jul 23 2008 *)

T(n,k) = n!(n(k(k+1)-1) - k(k-2)(k+2) + 1)/(k+2)! for 0 < k < n; T(n,n) = 1; T(n,k) = A122844(n,k) - A122844(n,k+1).

T(n,k) = A008304(n,k) for k > n/2. - Alois P. Heinz, Oct 17 2013

A008294 Triangle of coefficients in expansion of D^n (sec x) / sec x in powers of tan x.

Original entry on oeis.org

1, 1, 1, 2, 5, 6, 5, 28, 24, 61, 180, 120, 61, 662, 1320, 720, 1385, 7266, 10920, 5040, 1385, 24568, 83664, 100800, 40320, 50521, 408360, 1023120, 1028160, 362880, 50521, 1326122, 6749040, 13335840, 11491200, 3628800, 2702765, 30974526, 113760240

Offset: 0

N. J. A. Sloane

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
J. F. Barbero G., J. Salas and E. J. S. Villaseñor, Bivariate Generating Functions for a Class of Linear Recurrences. II. Applications, arXiv preprint arXiv:1307.5624 [math.CO], 2013-2015.
Dominique Foata and Guo-Niu Han, Multivariable Tangent and Secant q-derivative Polynomials. - _N. J. A. Sloane_, Oct 05 2012
J. Francon, Histoires de fichiers, RAIRO Informatique Théorique et Applications, 12 (1978), 49-62.
J. Francon, Histoires de fichiers, RAIRO Informatique Théorique et Applications, 12 (1978), 49-62. (Annotated scanned copy)
Gordon Haigh, A "natural" approach to Pick's theorem, Math. Gaz. 64 (1980), no. 429, 173-180.
Donald E. Knuth and Thomas J. Buckholtz, Computation of tangent, Euler and Bernoulli numbers, Math. Comp. 21 1967 663-688.

Cf. A008293. See A104035 for another version.

nmax = 11; t[0, 0] = 1; t[0, k_] = 0; t[n_, k_] := t[n, k] = k*t[n-1, k-1] + (k+1)*t[n-1, k+1]; Flatten[ Table[ t[n, k-1], {n, 0, nmax}, {k, Mod[n, 2]+1, n+1, 2}]] (* Jean-François Alcover, Nov 08 2011 *)

a(0, k) = delta(0, k); a(n+1, k) = k*a(n, k-1) + (k+1)*a(n, k+1).

A350970 Triangle T(n,k) (n>=0, 0<=k<=n) read by rows: T(0,0)=T(1,1)=1; T(n,0) is the Euler number A000111(n-1) for n>=1; T(n,n-1) = T(n,n) = (n-2)! for n>=2; interior entries are given by T(n,k) = mT(n-1,k-1)+(k+1)T(n-1,k+1) where m = k if n+k is even or k-1 if n+k is odd.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 5, 8, 6, 6, 5, 16, 28, 40, 24, 24, 16, 61, 136, 180, 240, 120, 120, 61, 272, 662, 1232, 1320, 1680, 720, 720, 272, 1385, 3968, 7266, 12096, 10920, 13440, 5040, 5040, 1385, 7936, 24568, 56320, 83664, 129024, 100800, 120960, 40320, 40320, 7936, 50521, 176896, 408360, 814080, 1023120, 1491840, 1028160, 1209600, 362880, 362880

Offset: 0

N. J. A. Sloane, Mar 03 2022

Triangle connects Euler numbers on left and factorial numbers on right.

			Triangle begins:
    1,
    1,    1,
    1,    1,    1,
    1,    2,    2,    2,
    2,    5,    8,    6,     6,
    5,   16,   28,   40,    24,    24,
   16,   61,  136,  180,   240,   120,   120,
   61,  272,  662, 1232,  1320,  1680,   720,  720,
  272, 1385, 3968, 7266, 12096, 10920, 13440, 5040, 5040,
  ...
This may also be constructed as a square array, with entries T(n,k), n >= 1, 0 <= k, whose columns have e.g.f. equal to sec(x)+tan(x) (if k=0) and sec(x)*tan(x)^(k-1)*(sec(x)+tan(x)) (if k>0):
1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
1, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
2, 5, 8, 6, 6, 0, 0, 0, 0, 0, 0, 0, 0, ...
5, 16, 28, 40, 24, 24, 0, 0, 0, 0, 0, 0, 0, ...
16, 61, 136, 180, 240, 120, 120, 0, 0, 0, 0, 0, 0, ...
61, 272, 662, 1232, 1320, 1680, 720, 720, 0, 0, 0, 0, 0, ...
272, 1385, 3968, 7266, 12096, 10920, 13440, 5040, 5040, 0, 0, 0, 0, ...
...

A. Boutin, Query 2784, L'Intermédiaire des Mathématiciens, 11 (1904), 252-254.
E. Estanave, Query 2784, L'Intermédiaire des Mathématiciens, 11 (1904), pp. 117-118.

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

The initial columns are A000111, A000111, A225689, A350971.
The diagonals, reading from the right, are (essentially) A000142, A000142, A002301, A006157, A002302, A350973, A002303, A350974, A350975.
Rows sums give A156142(n-1).
Cf. A007836.

for n from 0 to 12 do
T[n]:=Array(0..n,0);
T[0,0] := 1;
T[1,0] := 1; T[1,1] := 1;
if n>1 then
  T[n,0] := T[n-1,1];
for k from 1 to n-2 do
m:=k; if ((n+k) mod 2) = 0 then m:=k-1; fi;
T[n,k] := m*T[n-1,k-1] + (k+1)*T[n-1,k+1];
od:
T[n,n-1] := (n-1)*T[n-1,n-2];
T[n,n] := T[n,n-1];
fi;
lprint( [seq(T[n,k],k=0..n)] );
od:
# second Maple program:
b:= proc(n, i) option remember; `if`(i=0,
     `if`(n=0, 1, 0), b(n, i-1)+b(n-1, n-i))
    end:
T:= proc(n, k) option remember; `if`(n=0 and k=0, 1,
     `if`(k=0, b(n-1$2), `if`(n-k<=1, (n-1)!, (k+1)*
      T(n-1, k+1)+(k-irem(1+n+k, 2))*T(n-1, k-1))))
    end:
seq(seq(T(n, k), k=0..n), n=0..10);  # Alois P. Heinz, Mar 04 2022
# To produce the square array, N. J. A. Sloane, Mar 05 2022:
read(transforms):
myegf := (f,M) -> SERIESTOLISTMULT(series(f,x,M));
T:=proc(n,k,M) local i;
if k=0 then myegf((sec(x)+tan(x)),M)[n];
else
myegf(sec(x)*tan(x)^(k-1)*(sec(x)+tan(x)),M)[n];
fi;
end;
[seq(T(n,0,16),n=1..5)];
for n from 1 to 8 do
lprint([seq(T(n,k,16),k=0..12)]);
od:

b[n_, i_] := b[n, i] = If[i == 0,
     If[n == 0, 1, 0], b[n, i - 1] + b[n - 1, n - i]];
T[n_, k_] := T[n, k] = If[n == 0 && k == 0, 1,
     If[k == 0, b[n - 1, n - 1], If[n - k <= 1, (n - 1)!, (k + 1)*
     T[n - 1, k + 1] + (k - Mod[1 + n + k, 2])*T[n - 1, k - 1]]]];
Table[Table[T[n, k], {k, 0, n}], {n, 0, 10}] // Flatten (* Jean-François Alcover, Mar 12 2022, Alois P. Heinz *)

If we ignore the n=0 row, then the e.g.f. for column 0 is sec(x)+tan(x), and for column k >= 1 it is sec(x)*tan(x)^(k-1)*(sec(x)+tan(x)). See the initial rows of the square array in the EXAMPLES section. - N. J. A. Sloane, Mar 05 2022

abs(Sum_{k=0..n} (-1)^k * T(n,k)) = A007836(n) for n>=2. - Alois P. Heinz, Mar 04 2022

A014484 Expansion of (1+2x)/(1-2x)^4 (E.g.f.).

Original entry on oeis.org

1, 10, 112, 1440, 21120, 349440, 6451200, 131604480, 2941747200, 71530905600, 1880240947200, 53137244160000, 1606870263398400, 51776930709504000, 1771128112545792000, 64103411041173504000

Offset: 0

N. J. A. Sloane

Robert Israel, Table of n, a(n) for n = 0..400

Cf. A006157.

seq((n+1)*(n+2)*(2*n+3)/6 * 2^n * n!, n=0..30); # Robert Israel, Jul 11 2018

a(n)=(n+1)*(n+2)*(2*n+3)/6*2^n*n! \\ Charles R Greathouse IV, Jun 11 2013

a(n) = (n+1)(n+2)(2n+3)/6 * 2^n * n!. - Ralf Stephan, Mar 24 2004
Conjecture: a(n) +(-2*n-9)*a(n-1) +6*(n+1)*a(n-2)=0. - R. J. Mathar, Jun 11 2013
Conjecture verified by Robert Israel, Jul 11 2018

A097971 Number of alternating runs in all permutations of [n] (the permutation 732569148 has four alternating runs: 732, 2569, 91 and 148).

Original entry on oeis.org

2, 10, 56, 360, 2640, 21840, 201600, 2056320, 22982400, 279417600, 3672345600, 51891840000, 784604620800, 12640852224000, 216202162176000, 3912561709056000, 74694359900160000, 1500289571708928000, 31627726106296320000, 698242876346695680000

Offset: 2

Emeric Deutsch and Ira M. Gessel, Sep 07 2004

nonn

a(n) is also equal to the sum over all permutations p in S(n) of the number of elements in the set {(i, j): 0 < i < j < n+1 and |i - j| = |p(i) - p(j)|}.

			a(3) = 10 because the permutations 123, 132, 312, 213, 231, 321 have the following alternating runs: 123, 13, 32, 31, 12, 21, 13, 23, 31 and 321.

M. Bona, Combinatorics of Permutations, Chapman & Hall/CRC, Boca Raton, FL, 2004, pp. 24-30.
D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, 1973, Vol. 3, pp. 46 and 587-8.

Cf. A006157.

Maple
```
seq(n!*(2*n-1)/3, n=2..20);
```

a(n) = n!(2n-1)/3. E.g.f.: x^2*(3-x)/[3(1-x)^2]. a(n) = 2*A006157(n).

A122844 Triangle read by rows: T[n,k] = the number of ascending runs of length at least k in the permutations of [n] for k <= n.

Original entry on oeis.org

1, 3, 1, 12, 5, 1, 60, 28, 7, 1, 360, 180, 50, 9, 1, 2520, 1320, 390, 78, 11, 1, 20160, 10920, 3360, 714, 112, 13, 1, 181440, 100800, 31920, 7056, 1176, 152, 15, 1, 1814400, 1028160, 332640, 75600, 13104, 1800, 198, 17, 1

Offset: 1

David Scambler, Sep 13 2006

Column T[n,1] is essentially A001710 - all ascending runs in permutations of [n] Column T[n,2] is A006157 - ascending runs of length at least 2 in permutations of [n] Column T[n,3] is A005460 - ascending runs of length at least 3 in permutations of [n]

			1
3 1
12 5 1 ; there are 5 ascending runs of length at least 2 in the permutations of [3], namely 13 in 132 and in 213, 23 in 231, 12 in 312, 123 in 123. T[3,2] = 5.

Cf. A122844, A001710, A006157, A005460.

T[n,k] = n![k(n-k+1)+1]/(k+1)! for 0A122843(n,j) (partial row sums of A122843)

A350309 a(n) = (n+2)a(n-1) + (n+1)(A003422(n) - 4)/6 for n > 0 with a(0) = 1.

Original entry on oeis.org

1, 2, 7, 35, 215, 1535, 12455, 113255, 1141415, 12632615, 152341415, 1988514215, 27934434215, 420236744615, 6740662856615, 114841743944615, 2071122598472615, 39418302548552615, 789563088403016615, 16603426141551176615, 365724864314899016615, 8421063413387754056615

Offset: 0

Mikhail Kurkov, Dec 24 2021

nonn

G. C. Greubel, Table of n, a(n) for n = 0..445

Cf. A003422, A006157 (first differences).

[n le 2 select n else ((n-1)*(2*n+3)*Self(n-1) - n*(2*n-1)*Self(n-2))/(2*n-3): n in [1..30]]; // G. C. Greubel, Jan 07 2025

a[n_]:= a[n]= If[n<2, n+1, (n*(2*n+5)*a[n-1] - (n+1)*(2*n+1)*a[n-2])/(2*n-1)]; (* a = A350309 *)
Table[a[n], {n,0,30}] (* G. C. Greubel, Jan 07 2025 *)

lf(n) = sum(k=0, n-1, k!); \\ A003422
a(n) = if (n, (n+2)*a(n-1) + (n+1)*(lf(n) - 4)/6, 1); \\ Michel Marcus, Jan 11 2022

from sage.all import * # remove for SageMath
@CachedFunction # a = A350309
def a(n): return n+1 if n<2 else (n*(2*n+5)*a(n-1) - (n+1)*(2*n+1)*a(n-2))//(2*n-1)
print([a(n) for n in range(31)]) # G. C. Greubel, Jan 07 2025

Recurrence: (2*n-1)*a(n) = n*(2*n+5)*a(n-1) - (n+1)*(2*n+1)*a(n-2). - Vaclav Kotesovec, Nov 21 2024

cp's OEIS Frontend

A122843 Triangle read by rows: T(n,k) = the number of ascending runs of length k in the permutations of [n] for k <= n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A008294 Triangle of coefficients in expansion of D^n (sec x) / sec x in powers of tan x.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A350970 Triangle T(n,k) (n>=0, 0<=k<=n) read by rows: T(0,0)=T(1,1)=1; T(n,0) is the Euler number A000111(n-1) for n>=1; T(n,n-1) = T(n,n) = (n-2)! for n>=2; interior entries are given by T(n,k) = m*T(n-1,k-1)+(k+1)*T(n-1,k+1) where m = k if n+k is even or k-1 if n+k is odd.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A014484 Expansion of (1+2x)/(1-2x)^4 (E.g.f.).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

PARI

Formula

A097971 Number of alternating runs in all permutations of [n] (the permutation 732569148 has four alternating runs: 732, 2569, 91 and 148).

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs

Maple

Formula

A122844 Triangle read by rows: T[n,k] = the number of ascending runs of length at least k in the permutations of [n] for k <= n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A350309 a(n) = (n+2)*a(n-1) + (n+1)*(A003422(n) - 4)/6 for n > 0 with a(0) = 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Python

Formula

A350970 Triangle T(n,k) (n>=0, 0<=k<=n) read by rows: T(0,0)=T(1,1)=1; T(n,0) is the Euler number A000111(n-1) for n>=1; T(n,n-1) = T(n,n) = (n-2)! for n>=2; interior entries are given by T(n,k) = mT(n-1,k-1)+(k+1)T(n-1,k+1) where m = k if n+k is even or k-1 if n+k is odd.

A350309 a(n) = (n+2)a(n-1) + (n+1)(A003422(n) - 4)/6 for n > 0 with a(0) = 1.