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,4

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)<p(i+1) is k (it is assumed that p(n+1)=infinity). Example: T(4,3)=3 because we have 4312, 4213 and 3214. - 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

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.

Formula

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

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

Example

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

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

Prog

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

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.

Sequence in context: A115085 A110616 A059418 * A213262 A280512 A068440

Adjacent sequences: A092579 A092580 A092581 * A092583 A092584 A092585

Keyword

nonn,tabl

Author

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

Status

approved