login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A092582 Triangle read by rows: T(n,k) is the number of permutations p of [n] having length of first run equal to k. 8
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 (list; table; graph; refs; listen; history; text; internal format)
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

Table of n, a(n) for n=1..55.

Muniru A Asiru, Row n = 1..100

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, Mehdi Naima, Ranked Schröder Trees, arXiv:1808.08376 [cs.DS], 2018.

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

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

CROSSREFS

Cf. A000166.

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

Cf. A092956, A130477.

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 17 12:10 EST 2019. Contains 320219 sequences. (Running on oeis4.)