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

1, 1, 3, 6, 13, 26, 54, 108, 221, 442, 898, 1796, 3634, 7268, 14668, 29336, 59101, 118202, 237834, 475668, 956198, 1912396, 3841588, 7683176, 15425138, 30850276, 61908564, 123817128, 248377156, 496754312

Offset: 1

Author

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

Keywords

• nonn
• easy

Comments

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

For n >= 2 also row sums of A258445. - Wolfdieter Lang, Jun 27 2015

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

• 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, A128650, A258445.

Programs

Mathematica

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

PARI

a(n) =  2^(n-1) - binomial(n-2, (n-2)\2) \\ Michel Marcus, May 27 2013

Formula

a(n) = 2^(n-1) - binomial(n-2, floor((n-2)/2)) for n>1, a(1)=1.

From Wolfdieter Lang, Jun 27 2015: (Start)

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

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

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

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