login
A201689
Number of involutions avoiding the pattern 21 (with a dot over the 1).
2
1, 0, 1, 1, 4, 9, 31, 94, 337, 1185, 4540, 17581, 71875, 299646, 1299637, 5760973, 26357764, 123241185, 591877543, 2902472734, 14571525145, 74613410169, 390197960716, 2078859419077, 11290463266843, 62400316038462, 351037047533581, 2007507147853429
OFFSET
0,5
COMMENTS
Baril gives a formula for a(n), but when I evaluate it I get A201687, not the values shown here.
LINKS
J.-L. Baril, Classical sequences revisited with permutations avoiding dotted pattern, Electronic Journal of Combinatorics, 18 (2011), #P178. See Theorem 7 and Table 3.
FORMULA
G.f.: 1/(G(0)+x), where G(k) = 1 - x - x^2*(k+1)/G(k+1); (continued fraction). - Sergei N. Gladkovskii, Dec 15 2011
G.f.: B(x)/(1+x*B(x)) where B(x) is the o.g.f. for A000085. - Michael D. Weiner, Jan 10 2022
From Alois P. Heinz, Jan 10 2022: (Start)
a(n) = A000085(n) - Sum_{r=0..n-1} a(r)*A000085(n-1-r). [from Baril, corrected]
a(n) mod 2 = A204418(n). (End)
EXAMPLE
G.f.: 1 + x^2 + x^3 + 4*x^4 + 9*x^5 + 31*x^6 + 94*x^7 + 337*x^8 + ...
MAPLE
b:= proc(n) option remember; `if`(n<1, 1, b(n-1)+(n-1)*b(n-2)) end:
a:= proc(n) option remember; b(n)-add(a(r)*b(n-1-r), r=0..n-1) end:
seq(a(n), n=0..28); # Alois P. Heinz, Jan 10 2022
MATHEMATICA
b[n_] := b[n] = If[n < 1, 1, b[n - 1] + (n - 1)*b[n - 2]];
a[n_] := a[n] = b[n] - Sum[a[r]*b[n - 1 - r], {r, 0, n - 1}];
Table[a[n], {n, 0, 28}] (* Jean-François Alcover, Apr 14 2022, after Alois P. Heinz *)
PROG
(PARI) seq(n)={my(g=serlaplace(exp(x+x^2/2 + O(x*x^n)))); Vec(g/(1 + x*g))} \\ Andrew Howroyd, Jan 10 2022
CROSSREFS
Sequence in context: A141043 A111160 A192876 * A356650 A270909 A270152
KEYWORD
nonn
AUTHOR
N. J. A. Sloane, Dec 03 2011
EXTENSIONS
a(0)=1 prepended by Andrew Howroyd, Jan 10 2022
STATUS
approved