|
|
A279563
|
|
Number of length n inversion sequences avoiding the patterns 102, 201, and 210.
|
|
23
|
|
|
1, 1, 2, 6, 22, 85, 328, 1253, 4754, 17994, 68158, 258808, 985906, 3768466, 14451386, 55585014, 214377618, 828795169, 3211030684, 12464308997, 48465092366, 188733879657, 735977084412, 2873525548315, 11231884145434, 43947466923095, 172115939825516
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
A length n inversion sequence e_1e_2...e_n is a sequence of integers where 0 <= e_i <= i-1. The term a(n) counts those length n inversion sequences with no entries e_i, e_j, e_k (where i<j<k) such that e_i > e_j <> e_k and e_i <> e_k. This is the same as the set of length n inversion sequences avoiding 102, 201, and 210.
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
The length 4 inversion sequences avoiding (102, 201, 210) are 0000, 0001, 0002, 0003, 0010, 0011, 0012, 0013, 0020, 0021, 0022, 0023, 0100, 0101, 0110, 0111, 0112, 0113, 0120, 0121, 0122, 0123.
|
|
MAPLE
|
a:= proc(n) option remember; `if`(n<4, n!,
((2*(12*n^3-91*n^2+213*n-149))*a(n-1)
-(3*(21*n^3-162*n^2+392*n-291))*a(n-2)
+(2*(33*n^3-257*n^2+633*n-484))*a(n-3)
-(4*(2*n-7))*(3*n^2-13*n+13)*a(n-4))
/ ((n-1)*(3*n^2-19*n+29)))
end:
|
|
MATHEMATICA
|
a[n_] := a[n] = If[n < 4, n!, ((2*(12*n^3 - 91*n^2 + 213*n - 149))*a[n-1] - (3*(21*n^3 - 162*n^2 + 392*n - 291))*a[n-2] + (2*(33*n^3 - 257*n^2 + 633*n - 484))*a[n-3] - (4*(2*n - 7))*(3*n^2 - 13*n + 13)*a[n-4]) / ((n - 1)*(3*n^2 - 19*n + 29))]; Array[a, 30, 0] (* Jean-François Alcover, Nov 06 2017, after Alois P. Heinz *)
|
|
CROSSREFS
|
Cf. A000108, A057552, A263777, A263778, A263779, A263780, A279551, A279552, A279553, A279554, A279555, A279556, A279557, A279558, A279559, A279560, A279561, A279562, A279564, A279565, A279566, A279567, A279568, A279569, A279570, A279571, A279572, A279573.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|