login
Expansion of (1-x)/(1-2*x-2*x^3).
2

%I #25 Sep 08 2022 08:45:08

%S 1,1,2,6,14,32,76,180,424,1000,2360,5568,13136,30992,73120,172512,

%T 407008,960256,2265536,5345088,12610688,29752448,70195072,165611520,

%U 390727936,921846016,2174915072,5131286016,12106264064,28562358272,67387288576,158987105280

%N Expansion of (1-x)/(1-2*x-2*x^3).

%C a(n) = number of permutations on [n] that avoid nonconsecutive instances of the patterns 321 and 312. For example, a(4) does not count pi=4231 because 431 forms a 321 pattern in pi but 431 is not a consecutive (that is, contiguous) string in pi; also, the first 3 letters form a 312 pattern but that's not disqualifying because they do occur consecutively. Counting these permutations by various statistics yields the listed formulas/recurrences. - _David Callan_, Oct 26 2006

%C a(n) = term (1,1) of M^n, M = the 4 X 4 matrix [1,0,1,1; 1,1,0,0; 0,1,0,1; 1,0,0,1]. a(n)/a(n-1) tends to 2.3593040859..., an eigenvalue of the matrix and a root to the characteristic polynomial x^4 - 3x^3 + 2x^2 - 2x + 2. - _Gary W. Adamson_, Oct 01 2008

%H G. C. Greubel, <a href="/A077999/b077999.txt">Table of n, a(n) for n = 0..1000</a>

%H S. R. Finch, <a href="http://arxiv.org/abs/math/9810155">Several Constants Arising in Statistical Mechanics</a>, arXiv:math/9810155 [math.CO], 1998-1999. see p. 8.

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (2,0,2)

%F a(n) = 2*(a(n-1) + a(n-3)) counts the above permutations by first entry. a(n) = a(n-1) + a(n-2) + 3*Sum_{k=0..n-3} a(k) counts by last entry. a(n) = 2^(n-1) + Sum_{k=0..n-3} 2^(n-2-k)*a(k) counts by location of first 3xx pattern. a(n) = Sum_{k=0..floor(n/3)} ((n-k)/(n-2k))* binomial(n-2*k,k) * 2^(n-2*k-1) counts by number of 3xx patterns. - _David Callan_, Oct 26 2006

%F a(n) = A052912(n) - A052912(n-1). - _R. J. Mathar_, May 30 2014

%F a(n) = (-1)^n * A110524(n). - _G. C. Greubel_, Jun 27 2019

%t CoefficientList[Series[(1-x)/(1-2x-2x^3),{x,0,40}],x] (* or *) LinearRecurrence[{2,0,2},{1,1,2},40] (* _Harvey P. Dale_, Sep 10 2016 *)

%o (PARI) my(x='x+O('x^40)); Vec((1-x)/(1-2*x-2*x^3)) \\ _G. C. Greubel_, Jun 27 2019

%o (Magma) R<x>:=PowerSeriesRing(Integers(), 40); Coefficients(R!( (1-x)/( 1-2*x-2*x^3) )); // _G. C. Greubel_, Jun 27 2019

%o (Sage) ((1-x)/(1-2*x-2*x^3)).series(x, 40).coefficients(x, sparse=False) # _G. C. Greubel_, Jun 27 2019

%o (GAP) a:=[1,1,2];; for n in [4..40] do a[n]:=2*(a[n-1]+a[n-3]); od; a; # _G. C. Greubel_, Jun 27 2019

%Y Cf. A052912, A110524.

%K nonn,easy

%O 0,3

%A _N. J. A. Sloane_, Nov 17 2002