login
Number of triangular involutions of n. A triangular involution is a square involution with at most three faces.
2

%I #27 Nov 25 2018 13:15:24

%S 1,1,3,6,13,26,54,108,221,442,898,1796,3634,7268,14668,29336,59101,

%T 118202,237834,475668,956198,1912396,3841588,7683176,15425138,

%U 30850276,61908564,123817128,248377156,496754312

%N Number of triangular involutions of n. A triangular involution is a square involution with at most three faces.

%C The sequence 2^(n+1) - binomial(n, floor(n/2)), which begins 1,3,6,... has Hankel transform (-1)^n*(2*n+1) (A157142). - _Paul Barry_, Nov 03 2010

%C For n >= 2 also row sums of A258445. - _Wolfdieter Lang_, Jun 27 2015

%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 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) = 2^(n-1) - binomial(n-2, floor((n-2)/2)) for n>1, a(1)=1.

%F From _Wolfdieter Lang_, Jun 27 2015: (Start)

%F a(n) = Sum_{k = 1..2*n-3} A258445(n-1, k), n >= 2.

%F a(2*k+1) = 4*Sum_{j = 0..(k-2)} binomial(2*k-1,j) + 3*binomial(2*k-1,k-1), k >= 1.

%F a(2*k) = 4*Sum_{j = 0..(k-2)} binomial(2*(k-1),j) + binomial(2*(k-1),k-1), k >= 1. (End)

%F (-n+1)*a(n) + 2*(n-1)*a(n-1) + 4*(n-4)*a(n-2) + 8*(-n+4)*a(n-3) = 0. - _R. J. Mathar_, Aug 09 2017

%t Join[{1},Table[2^(n-1)-Binomial[n-2,Floor[(n-2)/2]],{n,2,30}]] (* _Harvey P. Dale_, Dec 26 2015 *)

%o (PARI) a(n) = 2^(n-1) - binomial(n-2, (n-2)\2) \\ _Michel Marcus_, May 27 2013

%Y Cf. A128652, A128650, A258445.

%K nonn,easy

%O 1,3

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