A201689 Number of involutions avoiding the pattern 21 (with a dot over the 1).

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

Author

N. J. A. Sloane, Dec 03 2011

Keywords

• nonn

Comments

Baril gives a formula for a(n), but when I evaluate it I get A201687, not the values shown here.

Examples

			G.f.: 1 + x^2 + x^3 + 4*x^4 + 9*x^5 + 31*x^6 + 94*x^7 + 337*x^8 + ...
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..800
• J.-L. Baril, Classical sequences revisited with permutations avoiding dotted pattern, Electronic Journal of Combinatorics, 18 (2011), #P178. See Theorem 7 and Table 3.

Crossrefs

Cf. A000085, A201687.

Programs

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 *)

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

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)

Extensions

a(0)=1 prepended by Andrew Howroyd, Jan 10 2022