login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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.
3
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
Sequence in context: A180915 A240783 A327083 * A073135 A063804 A213800
KEYWORD
nonn,tabl
AUTHOR
Ralf Stephan, Feb 26 2005
STATUS
approved