|
%I #83 Feb 05 2022 16:54:14
%S 1,2,6,14,34,78,178,398,882,1934,4210,9102,19570,41870,89202,189326,
%T 400498,844686,1776754,3728270,7806066,16311182,34020466,70837134,
%U 147266674,305718158,633805938,1312351118,2714180722,5607318414,11572550770,23860929422
%N Number of fixed points in all 231-avoiding involutions in S_n.
%C 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.
%C Convolved with (1, 2, 2, 2, ...) = A001787: (1, 4, 12, 32, 80, ...). - _Gary W. Adamson_, May 23 2009
%C 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
%C 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
%C 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
%H Vincenzo Librandi, <a href="/A059570/b059570.txt">Table of n, a(n) for n = 1..1000</a>
%H Roland Bacher, <a href="http://arxiv.org/abs/1509.09054">Chebyshev polynomials, quadratic surds and a variation of Pascal's triangle</a>, arXiv:1509.09054 [math.CO], 2015.
%H S. Heubach and T. Mansour, <a href="https://arxiv.org/abs/math/0310197">Counting rises, levels and drops in compositions</a>, arXiv:math/0310197 [math.CO], 2003.
%H Brian Hopkins, Andrew V. Sills, Thotsaporn "Aek" Thanatipanonda, and Hua Wang, <a href="http://thotsaporn.com/composition.pdf">Parts and subword patterns in compositions</a>, Preprint 2015.
%H Silvana Ramaj, <a href="https://digitalcommons.georgiasouthern.edu/cgi/viewcontent.cgi?article=3464&context=etd">New Results on Cyclic Compositions and Multicompositions</a>, Master's Thesis, Georgia Southern Univ., 2021. See p. 30.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,0,-4).
%F a(n) = (3*n+4)*2^n/18 - 2*(-1)^n/9.
%F G.f.: z*(1-z)/((1+z)*(1-2*z)^2).
%F a(n) = Sum_{j=0..n} Sum_{k=0..n} binomial(n-k, k+j)*2^k. - _Paul Barry_, Aug 29 2004
%F a(n) = Sum_{k=0..n+1} (-1)^(k+1)*binomial(n+1, k+j)*A001045(k). - _Paul Barry_, Jan 30 2005
%F 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
%F Convolution of "Difference sequence of A045623" (A045891) with "Positive integers repeated" (A008619), treating the result as if offset=1. - _Graeme McRae_, Jul 12 2006
%F 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
%F 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
%F Equals triangle A059260 * [1, 2, 3, ...] as a vector. - _Gary W. Adamson_, Mar 06 2012
%F a(n) + a(n-1) = A001792(n-1). - _Gregory L. Simay_, Apr 30 2017
%F a(n) - a(n-2) = A045623(n-1). - _Gregory L. Simay_, May 01 2017
%F a(n) = A045623(n-1) + A045623(n-3) + A045623(n-5) + ... - _Gregory L. Simay_, Feb 19 2018
%F a(n) = A225084(2n,n). - _Alois P. Heinz_, Aug 30 2018
%e 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).
%t LinearRecurrence[{3,0,-4},{1,2,6},30] (* _Harvey P. Dale_, Dec 29 2013 *)
%t Table[(3 n + 4) 2^n/18 - 2 (-1)^n/9, {n, 30}] (* _Vincenzo Librandi_, May 01 2017 *)
%o (Magma) [(3*n+4)*2^n/18-2*(-1)^n/9: n in [1..40]]; // _Vincenzo Librandi_, May 01 2017
%Y Cf. A001787, A027934, A045623, A127984, A128255, A172481, A225084.
%K nonn,easy
%O 1,2
%A _Emeric Deutsch_, Feb 16 2001
%E More terms from Eugene McDonnell (eemcd(AT)mac.com), Jan 13 2005
|
