A164990 Number of square involutions of n.

1, 2, 4, 10, 22, 52, 114, 260, 564, 1256, 2698, 5908, 12588, 27224, 57620, 123432, 259816, 552400, 1157466, 2446004, 5105532, 10735352, 22334524, 46766200, 97021272, 202431152, 418935364, 871425160, 1799558584

Offset: 1

Author

Simone Rinaldi (rinaldi(AT)unisi.it), Sep 04 2009

Keywords

• easy
• nonn

Examples

			a(5)=22, in fact the 22 square involutions of 5 are given by all the involutions of 5, which are 26, minus 14325, 15342, 52341, 42315 which are not square.
		

References

• F. Disanto, A. Frosini, S. Rinaldi, Square Involutions, Proceedings of Permutation Patterns, July 13-17, 2009, Florence.
• T. Mansour, S. Severini, Grid polygons from permutations and their enumeration by the kernel method, 19th Conference on Formal Power Series and Algebraic Combinatorics, Tianjin, China, July 2-6, 2007.

Links

• G. C. Greubel, Table of n, a(n) for n = 1..1000
• F. Disanto, A. Frosini, S. Rinaldi, Square involutions, J. Int. Seq. 14 (2011) # 11.3.5.
• T. Mansour, S. Severini, Grid polygons from permutations and their enumeration by the kernel method, arXiv:math/0603225 [math.CO], 2006.

Crossrefs

Cf. A128652.

Programs

Magma

m:=30; R:=PowerSeriesRing(Rationals(), m); Coefficients(R!( x*(1-x)^2/(1-2*x)^2 - x^3/((1-2*x)*Sqrt(1-4*x^2)) )); // G. C. Greubel, Nov 25 2018

Mathematica

Rest[CoefficientList[Series[x(1-x)^2/(1-2x)^2 - x^3/((1-2x) Sqrt[1-4x^2]), {x, 0, 29}], x]] (* Michael De Vlieger, Nov 25 2018 *)

PARI

my(x='x+O('x^30)); Vec(x*(1-x)^2/(1-2*x)^2 - x^3/((1-2*x)*sqrt(1- 4*x^2))) \\ G. C. Greubel, Nov 25 2018

Sage

s=(x*(1-x)^2/(1-2*x)^2 -x^3/((1-2*x)*sqrt(1-4*x^2))).series(x, 30);  a= s.coefficients(x, sparse=False); a[1:] # G. C. Greubel, Nov 25 2018

Formula

a(n) = (n+2)*2^(n-3) - (n-2)*C(n-3,(n-3)/2), n > 1.

G.f.: x*(1-x)^2/(1-2*x)^2 - x^3/((1-2*x)*sqrt(1-4*x^2)).

(n-3)*(n-8)*a(n) + 2*(-n^2 + 10*n - 20)*a(n-1) + 4*(-n^2 + 12*n - 31)*a(n-2) + 8*(n-4)*(n-7)*a(n-3) = 0.- R. J. Mathar, Jul 24 2012