A092582 Triangle read by rows: T(n,k) is the number of permutations p of [n] having length of first run equal to k.

1, 1, 1, 3, 2, 1, 12, 8, 3, 1, 60, 40, 15, 4, 1, 360, 240, 90, 24, 5, 1, 2520, 1680, 630, 168, 35, 6, 1, 20160, 13440, 5040, 1344, 280, 48, 7, 1, 181440, 120960, 45360, 12096, 2520, 432, 63, 8, 1, 1814400, 1209600, 453600, 120960, 25200, 4320, 630, 80, 9, 1

Offset: 1

Author

Emeric Deutsch and Warren P. Johnson (wjohnson(AT)bates.edu), Apr 10 2004

Keywords

• nonn
• tabl

Comments

Row sums are the factorial numbers (A000142). First column is A001710.

T(n,k) = number of permutations of [n] in which 1,2,...,k is a subsequence but 1,2,...,k,k+1 is not. Example: T(4,2)=8 because 1324, 1342, 1432, 4132, 3124, 3142, 3412 and 4312, are the only permutations of [4] in which 12 is a subsequence but 123 is not. - Emeric Deutsch, Nov 12 2004

T(n,k) is the number of deco polyominoes of height n with k cells in the last column. (A deco polyomino is a directed column-convex polyomino in which the height, measured along the diagonal, is attained only in the last column). - Emeric Deutsch, Jan 06 2005

T(n,k) is the number of permutations p of [n] for which the smallest i such that p(i)Emeric Deutsch, Feb 23 2008

Adding columns 2,4,6,... one obtains the derangement numbers 0,1,2,9,44,... (A000166). See the Bona reference (p. 118, Exercises 41,42). - Emeric Deutsch, Feb 23 2008

Matrix inverse of A128227*A154990. - Mats Granvik, Feb 08 2009

Differences in the columns of A173333 which counts the n-permutations with an initial ascending run of length at least k. - Geoffrey Critzer, Jun 18 2017

The triangle with each row reversed is A130477. - Michael Somos, Jun 25 2017

Examples

			T(4,3) = 3 because 1243, 1342 and 2341 are the only permutations of [4] having length of first run equal to 3.
     1;
     1,    1;
     3,    2,   1;
    12,    8,   3,   1;
    60,   40,  15,   4,  1;
   360,  240,  90,  24,  5,  1;
  2520, 1680, 630, 168, 35,  6,  1;
  ...
		

References

• M. Bona, Combinatorics of Permutations, Chapman&Hall/CRC, Boca Raton, Florida, 2004.

Links

• Alois P. Heinz, Rows n = 1..141, flattened
• E. Barcucci, A. Del Lungo and R. Pinzani, "Deco" polyominoes, permutations and random generation, Theoretical Computer Science, 159, 1996, 29-42.
• Olivier Bodini, Antoine Genitrini, and Mehdi Naima, Ranked Schröder Trees, arXiv:1808.08376 [cs.DS], 2018.
• Olivier Bodini, Antoine Genitrini, Cécile Mailler, and Mehdi Naima, Strict monotonic trees arising from evolutionary processes: combinatorial and probabilistic study, hal-02865198 [math.CO] / [math.PR] / [cs.DS] / [cs.DM], 2020.
• Colin Defant and James Propp, Quantifying Noninvertibility in Discrete Dynamical Systems, arXiv:2002.07144 [math.CO], 2020.
• Emeric Deutsch and W. P. Johnson, Create your own permutation statistics, Math. Mag., 77, 130-134, 2004.

Crossrefs

Cf. A002260. - Gary W. Adamson, Feb 22 2012

Cf. A000166, A002627, A055596, A092580, A092956, A130477.

Cf. A000027, A001710, A001715, A001720, A001725, A005563.

Cf. A000522.

Programs

GAP

Flat(List([1..11],n->Concatenation([1],List([1..n-1],k->Factorial(n)*k/Factorial(k+1))))); # Muniru A Asiru, Jun 10 2018

Magma

A092582:= func< n,k | k eq n select 1 else k*Factorial(n)/Factorial(k+1) >;
[A092582(n,k): k in [1..n], n in [1..12]]; // G. C. Greubel, Sep 06 2022

Mathematica

Drop[Drop[Abs[Map[Select[#, # < 0 &] &, Map[Differences, nn = 10; Range[0, nn]! CoefficientList[Series[(Exp[y x] - 1)/(1 - x), {x, 0, nn}], {x, y}]]]], 1], -1] // Grid (* Geoffrey Critzer, Jun 18 2017 *)

PARI

{T(n, k) = if( n<1 || k>n, 0, k==n, 1, n! * k /(k+1)!)}; /* Michael Somos, Jun 25 2017 */

SageMath

def A092582(n,k): return 1 if (k==n) else k*factorial(n)/factorial(k+1)
flatten([[A092582(n,k) for k in (1..n)] for n in (1..12)]) # G. C. Greubel, Sep 06 2022

Formula

T(n, k) = n!*k/(k+1)! for k

Inverse of:

1;

-1, 1;

-1, -2, 1;

-1, -2, -3, 1;

-1, -2, -3, -4, 1;

... where A002260 = (1; 1,2; 1,2,3; ...). - Gary W. Adamson, Feb 22 2012

T(2n,n) = A092956(n-1) for n>0. - Alois P. Heinz, Jun 19 2017

From Alois P. Heinz, Dec 17 2021: (Start)

Sum_{k=1..n} k * T(n,k) = A002627(n).

|Sum_{k=1..n} (-1)^k * T(n,k)| = A055596(n) for n>=1. (End)

From G. C. Greubel, Sep 06 2022: (Start)

T(n, 1) = A001710(n).

T(n, 2) = 2*A001715(n) + [n=2]/3, n >= 2.

T(n, 3) = 3*A001720(n) + [n=3]/4, n >= 3.

T(n, 4) = 4*A001725(n) + [n=4]/5, n >= 4.

T(n, n-1) = A000027(n-1).

T(n, n-2) = A005563(n-1), n >= 3. (End)

Sum_{k=0..n} (k+1) * T(n,k) = A000522(n). - Alois P. Heinz, Apr 28 2023

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.