login
Number of square involutions of n.
1

%I #24 Sep 08 2022 08:45:47

%S 1,2,4,10,22,52,114,260,564,1256,2698,5908,12588,27224,57620,123432,

%T 259816,552400,1157466,2446004,5105532,10735352,22334524,46766200,

%U 97021272,202431152,418935364,871425160,1799558584

%N Number of square involutions of n.

%D F. Disanto, A. Frosini, S. Rinaldi, Square Involutions, Proceedings of Permutation Patterns, July 13-17, 2009, Florence.

%D 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.

%H G. C. Greubel, <a href="/A164990/b164990.txt">Table of n, a(n) for n = 1..1000</a>

%H F. Disanto, A. Frosini, S. Rinaldi, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Rinaldi/square.html">Square involutions</a>, J. Int. Seq. 14 (2011) # 11.3.5.

%H T. Mansour, S. Severini, <a href="https://arxiv.org/abs/math/0603225">Grid polygons from permutations and their enumeration by the kernel method</a>, arXiv:math/0603225 [math.CO], 2006.

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

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

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

%e 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.

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

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

%o (Magma) m:=30; R<x>:=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

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

%Y Cf. A128652.

%K easy,nonn

%O 1,2

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