A059570 Number of fixed points in all 231-avoiding involutions in S_n.

1, 2, 6, 14, 34, 78, 178, 398, 882, 1934, 4210, 9102, 19570, 41870, 89202, 189326, 400498, 844686, 1776754, 3728270, 7806066, 16311182, 34020466, 70837134, 147266674, 305718158, 633805938, 1312351118, 2714180722, 5607318414, 11572550770, 23860929422

Offset: 1

Author

Emeric Deutsch, Feb 16 2001

Keywords

• nonn
• easy

Comments

Number of odd parts in all compositions (ordered partitions) of n: a(3)=6 because in 3=2+1=1+2=1+1+1 we have 6 odd parts. Number of even parts in all compositions (ordered partitions) of n+1: a(3)=6 because in 4=3+1=1+3=2+2=2+1+1=1+2+1=1+1+2=1+1+1+1 we have 6 even parts.

Convolved with (1, 2, 2, 2, ...) = A001787: (1, 4, 12, 32, 80, ...). - Gary W. Adamson, May 23 2009

An elephant sequence, see A175654. For the corner squares 36 A[5] vectors, with decimal values between 15 and 480, lead to this sequence. For the central square these vectors lead to the companion sequence 4*A172481, for n>=-1. - Johannes W. Meijer, Aug 15 2010

a(n) is the total number of runs of equal parts in the compositions of n. a(5) = 34 because there are 34 runs of equal parts in the compositions of 5, with parentheses enclosing each run: (5), (4)(1), (1)(4), (3)(2), (2)(3), (3)(1,1), (1)(3)(1), (1,1)(3), (2,2)(1), (2)(1)(2), (1)(2,2), (2)(1,1,1), (1)(2)(1,1), (1,1)(2)(1), (1,1,1)(2), (1,1,1,1,1). - Gregory L. Simay, Apr 28 2017

a(n) - a(n-2) is the number of 1's in all compositions of n and more generally, the number of k's in all compositions of n+k-1. - Gregory L. Simay, May 01 2017

Examples

			a(3) = 6 because in the 231-avoiding involutions of {1,2,3}, i.e., in 123, 132, 213, 321, we have altogether 6 fixed points (3+1+1+1).
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..1000
• Roland Bacher, Chebyshev polynomials, quadratic surds and a variation of Pascal's triangle, arXiv:1509.09054 [math.CO], 2015.
• S. Heubach and T. Mansour, Counting rises, levels and drops in compositions, arXiv:math/0310197 [math.CO], 2003.
• Brian Hopkins, Andrew V. Sills, Thotsaporn "Aek" Thanatipanonda, and Hua Wang, Parts and subword patterns in compositions, Preprint 2015.
• Silvana Ramaj, New Results on Cyclic Compositions and Multicompositions, Master's Thesis, Georgia Southern Univ., 2021. See p. 30.
• Index entries for linear recurrences with constant coefficients, signature (3,0,-4).

Crossrefs

Cf. A001787, A027934, A045623, A127984, A128255, A172481, A225084.

Programs

Magma

[(3*n+4)*2^n/18-2*(-1)^n/9: n in [1..40]]; // Vincenzo Librandi, May 01 2017

Mathematica

LinearRecurrence[{3,0,-4},{1,2,6},30] (* Harvey P. Dale, Dec 29 2013 *)
Table[(3 n + 4) 2^n/18 - 2 (-1)^n/9, {n, 30}] (* Vincenzo Librandi, May 01 2017 *)

Formula

a(n) = (3*n+4)*2^n/18 - 2*(-1)^n/9.

G.f.: z*(1-z)/((1+z)*(1-2*z)^2).

a(n) = Sum_{j=0..n} Sum_{k=0..n} binomial(n-k, k+j)*2^k. - Paul Barry, Aug 29 2004

a(n) = Sum_{k=0..n+1} (-1)^(k+1)*binomial(n+1, k+j)*A001045(k). - Paul Barry, Jan 30 2005

Convolution of "Expansion of (1-x)/(1-x-2*x^2)" (A078008) with "Powers of 2" (A000079), treating the result as if offset=1. - Graeme McRae, Jul 12 2006

Convolution of "Difference sequence of A045623" (A045891) with "Positive integers repeated" (A008619), treating the result as if offset=1. - Graeme McRae, Jul 12 2006

a(n) = 3*a(n-1)-4*a(n-3); a(1)=1,a(2)=2,a(3)=6. - Philippe Deléham, Aug 30 2006

Equals row sums of A128255. (1, 2, 6, 14, 34, ...) - (0, 0, 1, 2, 6, 14, 34, ...) = A045623: (1, 2, 5, 12, 28, 64, ...). - Gary W. Adamson, Feb 20 2007

Equals triangle A059260 * [1, 2, 3, ...] as a vector. - Gary W. Adamson, Mar 06 2012

a(n) + a(n-1) = A001792(n-1). - Gregory L. Simay, Apr 30 2017

a(n) - a(n-2) = A045623(n-1). - Gregory L. Simay, May 01 2017

a(n) = A045623(n-1) + A045623(n-3) + A045623(n-5) + ... - Gregory L. Simay, Feb 19 2018

a(n) = A225084(2n,n). - Alois P. Heinz, Aug 30 2018

Extensions

More terms from Eugene McDonnell (eemcd(AT)mac.com), Jan 13 2005