A201689 - OEIS

%I #49 Apr 14 2022 08:00:40

%S 1,0,1,1,4,9,31,94,337,1185,4540,17581,71875,299646,1299637,5760973,

%T 26357764,123241185,591877543,2902472734,14571525145,74613410169,

%U 390197960716,2078859419077,11290463266843,62400316038462,351037047533581,2007507147853429

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

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

%H Alois P. Heinz, <a href="/A201689/b201689.txt">Table of n, a(n) for n = 0..800</a>

%H J.-L. Baril, <a href="https://doi.org/10.37236/665">Classical sequences revisited with permutations avoiding dotted pattern</a>, Electronic Journal of Combinatorics, 18 (2011), #P178. See Theorem 7 and Table 3.

%F 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

%F G.f.: B(x)/(1+x*B(x)) where B(x) is the o.g.f. for A000085. - _Michael D. Weiner_, Jan 10 2022

%F From _Alois P. Heinz_, Jan 10 2022: (Start)

%F a(n) = A000085(n) - Sum_{r=0..n-1} a(r)*A000085(n-1-r). [from Baril, corrected]

%F a(n) mod 2 = A204418(n). (End)

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

%p b:= proc(n) option remember; `if`(n<1, 1, b(n-1)+(n-1)*b(n-2)) end:

%p a:= proc(n) option remember; b(n)-add(a(r)*b(n-1-r), r=0..n-1) end:

%p seq(a(n), n=0..28);  # _Alois P. Heinz_, Jan 10 2022

%t b[n_] := b[n] = If[n < 1, 1, b[n - 1] + (n - 1)*b[n - 2]];

%t a[n_] := a[n] = b[n] - Sum[a[r]*b[n - 1 - r], {r, 0, n - 1}];

%t Table[a[n], {n, 0, 28}] (* _Jean-François Alcover_, Apr 14 2022, after _Alois P. Heinz_ *)

%o (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

%Y Cf. A000085, A201687.

%K nonn

%O 0,5

%A _N. J. A. Sloane_, Dec 03 2011

%E a(0)=1 prepended by _Andrew Howroyd_, Jan 10 2022