A334156 Triangle read by rows: T(n,m) is the number of length n decorated permutations avoiding the word 0^m = 0...0 of m 0's, where 1 <= m <= n.

1, 2, 4, 6, 12, 15, 24, 48, 60, 64, 120, 240, 300, 320, 325, 720, 1440, 1800, 1920, 1950, 1956, 5040, 10080, 12600, 13440, 13650, 13692, 13699, 40320, 80640, 100800, 107520, 109200, 109536, 109592, 109600, 362880, 725760, 907200, 967680, 982800, 985824, 986328, 986400, 986409

Offset

1,2

Comments

A length n decorated permutation is a word w = w_1....w_n on the letters {0,...,n} such that the restriction of w to its nonzero entries is an ordinary permutation in one-line notation. Then w avoids 0^m if w contains at most m-1 0's as letters, and w contains 0^m if w contains m 0's among its letters (not necessarily consecutive).

Links

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50)

S. Corteel, Crossings and alignments of permutations, Adv. Appl. Math 38 (2007) 149-163.

A. Postnikov, Total positivity, Grassmannians, and networks, arXiv:math/0609764 [math.CO], 2006.

Formula

T(n,m) = Sum_{j=0..m-1} n!/j!.

Example

For (n,m) = (3,2), the T(3,2) = 12 length 3 decorated permutations avoiding 0^2 = 00 are 012, 102, 120, 021, 201, 210, 123, 132, 213, 231, 312, and 321.
Triangle begins:
    1
    2,   4
    6,  12,  15
   24,  48,  60,  64
  120, 240, 300, 320, 325

Mathematica

Array[Accumulate[#!/Range[0, #-1]!]&, 10] (* Paolo Xausa, Jan 08 2024 *)

Prog

(PARI) T(n, m)={sum(j=0, m-1, n!/j!)} \\ Andrew Howroyd, May 11 2020

Crossrefs

Cf. A000142 (1st column), A007526 (right diagonal).

Row sums are A093964.

Sequence in context: A141113 A324851 A348572 * A255001 A341663 A050584

Adjacent sequences: A334153 A334154 A334155 * A334157 A334158 A334159

Keyword

nonn,tabl

Author

Jordan Weaver, Apr 16 2020

Extensions

Terms a(37) and beyond from Andrew Howroyd, Jan 07 2024

Status

approved