A097900 -id:A097900 - 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

A159920 Sums of the antidiagonals of Sundaram's sieve (A159919).

Original entry on oeis.org

4, 14, 32, 60, 100, 154, 224, 312, 420, 550, 704, 884, 1092, 1330, 1600, 1904, 2244, 2622, 3040, 3500, 4004, 4554, 5152, 5800, 6500, 7254, 8064, 8932, 9860, 10850, 11904, 13024, 14212, 15470, 16800, 18204, 19684, 21242, 22880, 24600, 26404

Offset: 2

Russell Walsmith, Apr 26 2009

For every n >= 2, a(n) is the sum of numbers in the (n-1)-th antidiagonal of the Sundaram sieve. (It is not clear why the offset was set to 2 rather than 1.) Thus, if T(j, k) is the element in row j and column k of the Sundaram sieve, we have a(n) = Sum_{i = 1..n-1} T(i, n-i) = Sum_{i = 1..n-1} (2*i*(n-i) + i + (n-i)) = (n - 1)*n*(n + 4)/3 for the sum of the numbers in the (n-1)-th antidiagonal. - Petros Hadjicostas, Jun 19 2019

			For n = 5, (4*5*9)/3 = 60. Indeed, T(1, 4) + T(2, 3) + T(3, 2) + T(4, 1) = 13 + 17 + 17 + 13 = 60 for the sum of the terms in the 4th antidiagonal of the Sundaram sieve.

G. C. Greubel, Table of n, a(n) for n = 2..1000
Andrew Baxter, Sundaram's Sieve.
Julian Havil, Sundaram's Sieve, Plus Magazine, March 2009.
New Zealand Maths, Newletter 18, October 2002.
Wikipedia, Sundaram's Sieve.
Index entries for linear recurrences with constant coefficients, signature (4,-6,4,-1).

Cf. A005581, A097900, A159919.

[n*(n-1)*(n+4)/3: n in [2..60]]; // G. C. Greubel, Oct 03 2022

A159920:=n->n*(n-1)*(n+4)/3; seq(A159920(k), k=2..100); # Wesley Ivan Hurt, Oct 19 2013

Table[(n-1)*n*(n+4)/3,{n,2,60}] (* Vladimir Joseph Stephan Orlovsky, Apr 28 2010 *)
LinearRecurrence[{4,-6,4,-1},{4,14,32,60},61]  (* Harvey P. Dale, Apr 23 2011 *)

[n*(n-1)*(n+4)/3 for n in range(2,60)] # G. C. Greubel, Oct 03 2022

a(n) = (n - 1)*n*(n + 4)/3.
a(n) = 4*a(n-1) - 6*a(n-2) + 4*a(n-3) - a(n-4).
a(n) = 2*A005581(n), n > 1.
a(n) = Sum_{i=1..n-1} i*(i + 3). - Wesley Ivan Hurt, Oct 19 2013
From G. C. Greubel, Oct 03 2022: (Start)
G.f.: 2*x^2*(2 - x)/(1-x)^4.
E.g.f.: (1/3)*x^2*(6 + x)*exp(x). (End)
a(n) = 2*A097900(n)/(n-2)! for n >= 2. - Cullen M. Vaney, Jul 14 2025

A141052 Number of runs or rising sequences of length 2 among all permutations of n.

Original entry on oeis.org

1, 4, 21, 130, 930, 7560, 68880, 695520, 7711200, 93139200, 1217462400, 17124307200, 257902444800, 4140968832000, 70614415872000, 1274546617344000, 24275666967552000, 486580401635328000, 10238462617743360000, 225651661258383360000, 5198503365971435520000

Offset: 2

Harlan J. Brothers, Jul 31 2008, Aug 24 2008

			a[3]=4 because of the 6 permutations of n=3, there are 4 ascending runs of length 2:
{1,3} in {1,3,2}
{1,3} in {2,1,3}
{2,3} in {2,3,1}
{1,2} in {3,1,2}
a[3]=4 because of the 6 permutations of n=3, there are 4 rising sequences of length 2:
{1,2} in {1,3,2}
{2,3} in {2,1,3}
{2,3} in {2,3,1}
{1,2} in {3,1,2}

Persi Diaconis, Mathematical developments from the analysis of riffle shuffling, p. 4.
Francis Edward Su, Rising Sequences in Card Shuffling
Charles M. Grinstead and J. Laurie Snell, Introduction to Probability, American Mathematical Society, 1997, pp.120-131.

Column 2 of A122843.

Cf. A008292, A097900, A001286, A001048, A000142, A028387, A001710.

Table[n!(5n + 1)/4! + Floor[2/n](1/12), {n, 2, 10}]

a(n) = n!*(5n+1)/4! + floor(2/n)*(1/12), n>=2.
Recurrence: a(n) = (n+1)*a(n-1)+(n-1)!/6, n>=2, with a(2)=1 and a(3)=4.
E.g.f.: x^2*(x-2)*(x-6)/(24*(x-1)^2).

First example and typo in second example corrected by Harlan J. Brothers, Apr 29 2013

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

A159920 Sums of the antidiagonals of Sundaram's sieve (A159919).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

A141052 Number of runs or rising sequences of length 2 among all permutations of n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions