login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A059570 Number of fixed points in all 231-avoiding involutions in S_n. 28
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

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

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).

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

EXAMPLE

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).

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

PROG

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

CROSSREFS

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

Sequence in context: A296626 A124614 A070933 * A208902 A018016 A182644

Adjacent sequences:  A059567 A059568 A059569 * A059571 A059572 A059573

KEYWORD

nonn,easy

AUTHOR

Emeric Deutsch, Feb 16 2001

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 14 16:53 EDT 2022. Contains 356122 sequences. (Running on oeis4.)