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,5

Comments

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

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.

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

Cf. A000085, A201687.

Sequence in context: A141043 A111160 A192876 * A356650 A270909 A270152

Adjacent sequences: A201686 A201687 A201688 * A201690 A201691 A201692

Keyword

nonn

Author

N. J. A. Sloane, Dec 03 2011

Extensions

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

Status

approved