A104002 Triangle T(n,k) read by rows: number of permutations in S_n avoiding all k-length patterns that start with 1 except one fixed pattern and containing it exactly once.

1, 2, 1, 3, 4, 1, 4, 12, 6, 1, 5, 32, 27, 8, 1, 6, 80, 108, 48, 10, 1, 7, 192, 405, 256, 75, 12, 1, 8, 448, 1458, 1280, 500, 108, 14, 1, 9, 1024, 5103, 6144, 3125, 864, 147, 16, 1, 10, 2304, 17496, 28672, 18750, 6480, 1372, 192, 18, 1, 11, 5120, 59049, 131072

Offset

2,2

Comments

T(n+k,k+1) = total number of occurrences of any given letter in all possible n-length words on a k-letter alphabet. For example, with the 2 letter alphabet {0,1} there are 4 possible 2-length words: {00,01,10,11}. The letter 0 occurs 4 times altogether, as does the letter 1. T(4,3) = 4. - Ross La Haye, Jan 03 2007

Table T(n,k) = k*n^(k-1) n,k > 0 read by antidiagonals. - Boris Putievskiy, Dec 17 2012

Links

Michael De Vlieger, Table of n, a(n) for n = 2..11176 (rows 2 <= n <= 150).

T. Mansour, Permutations containing and avoiding certain patterns, arXiv:math/9911243 [math.CO], 1999-2000.

Boris Putievskiy, Transformations Integer Sequences And Pairing Functions, arXiv:1212.2732 [math.CO], 2012.

Franck Ramaharo, A generating polynomial for the pretzel knot, arXiv:1805.10680 [math.CO], 2018.

Formula

T(n, k) = (n-k+1) * (k-1)^(n-k), k<=n.

As a linear array, the sequence is a(n) = A004736(n)*A002260(n)^(A004736(n)-1) or a(n) = ((t*t+3*t+4)/2-n)*(n-(t*(t+1)/2))^((t*t+3*t+4)/2-n-1), where t=floor((-1+sqrt(8*n-7))/2). - Boris Putievskiy, Dec 17 2012

Example

Triangle begins:
  1;
  2,   1;
  3,   4,    1;
  4,  12,    6,    1;
  5,  32,   27,    8,   1;
  6,  80,  108,   48,  10,   1;
  7, 192,  405,  256,  75,  12,  1;
  8, 448, 1458, 1280, 500, 108, 14, 1;

Mathematica

Table[(n - k + 1) (k - 1)^(n - k), {n, 2, 12}, {k, 2, n}] // Flatten (* Michael De Vlieger, Aug 22 2018 *)

Crossrefs

Cf. Left-edge columns include A001787, A027471, A002697, A053464, A053469, A027473, A053539, A053540, A053541, A081127, A081128.

Sequence in context: A180915 A240783 A327083 * A073135 A063804 A213800

Adjacent sequences: A103999 A104000 A104001 * A104003 A104004 A104005

Keyword

nonn,tabl

Author

Ralf Stephan, Feb 26 2005

Status

approved