%I M3862 #75 Apr 20 2024 10:48:57
%S 1,5,15,55,190,671,2353,8272,29056,102091,358671,1260143,4427294,
%T 15554592,54648506,191998646,674555937,2369942427,8326406594,
%U 29253473175,102777312308,361091343583,1268635610806,4457144547354
%N Number of distributive lattices; also number of paths with n turns when light is reflected from 5 glass plates.
%C Let M denotes the 5 X 5 matrix = row by row (1,1,1,1,1)(1,1,1,1,0)(1,1,1,0,0)(1,1,0,0,0)(1,0,0,0,0) and A(n) the vector (x(n),y(n),z(n),t(n),u(n)) = M^n*A where A is the vector (1,1,1,1,1); then a(n)=y(n). - _Benoit Cloitre_, Apr 02 2002
%D J. Berman and P. Koehler, Cardinalities of finite distributive lattices, Mitteilungen aus dem Mathematischen Seminar Giessen, 121 (1976), 103-124.
%D S. J. Cyvin and I. Gutman, Kekulé structures in benzenoid hydrocarbons, Lecture Notes in Chemistry, No. 46, Springer, New York, 1988 (see p. 120).
%D J. Haubrich, Multinacci Rijen [Multinacci sequences], Euclides (Netherlands), Vol. 74, Issue 4, 1998, pp. 131-133.
%D D. E. Knuth, Art of Computer Programming, Vol. 3, Sect. 5.4.3, Column T1.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A006358/b006358.txt">Table of n, a(n) for n = 0..200</a>
%H J. Berman and P. Koehler, <a href="/A006356/a006356.pdf">Cardinalities of finite distributive lattices</a>, Mitteilungen aus dem Mathematischen Seminar Giessen, 121 (1976), 103-124. [Annotated scanned copy]
%H Emma L. L. Gao, Sergey Kitaev, and Philip B. Zhang, <a href="https://arxiv.org/abs/1505.04078">Pattern-avoiding alternating words</a>, arXiv:1505.04078 [math.CO], 2015.
%H Manfred Goebel, <a href="http://dx.doi.org/10.1007/s002000050118">Rewriting Techniques and Degree Bounds for Higher Order Symmetric Polynomials</a>, Applicable Algebra in Engineering, Communication and Computing (AAECC), Volume 9, Issue 6 (1999), 559-573.
%H G. Kreweras, <a href="http://www.numdam.org/item?id=MSH_1976__53__5_0">Les préordres totaux compatibles avec un ordre partiel</a>, Math. Sci. Humaines No. 53 (1976), 5-30.
%H G. Kreweras, <a href="/A019538/a019538.pdf">Les préordres totaux compatibles avec un ordre partiel</a>, Math. Sci. Humaines No. 53 (1976), 5-30. (Annotated scanned copy)
%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992
%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (3,3,-4,-1,1).
%F a(n) = 3*a(n-1) + 3*a(n-2) - 4*a(n-3) - a(n-4) + a(n-5).
%F a(n) is asymptotic to z(5)*w(5)^n where w(5) = (1/2)/cos(5*Pi/11) and z(5) is the root 1 < x < 2 of P(5, X) = -1 + 55*X + 847*X^2 - 5324*X^3 - 14641*X^4 + 14641*X^5. - _Benoit Cloitre_, Oct 16 2002
%F G.f.: A(x) = (1 + 2*x - 3*x^2 - x^3 + x^4)/(1 - 3*x - 3*x^2 + 4*x^3 + x^4 - x^5). - _Paul D. Hanna_, Feb 06 2006
%p A=seq(a.j,j=0..4):grammar1:=[Q4,{ seq(Q.i=Union(Epsilon,seq(Prod(a.j,Q.j),j=4-i..4)),i=0..4), seq(a.j=Z,j=0..4) }, unlabeled]: seq(count(grammar1,size=j),j=0..23); # _Zerinvary Lajos_, Mar 09 2007
%p A006358:=-(z-1)*(z**3-3*z-1)/(-1+3*z+3*z**2-4*z**3-z**4+z**5); # conjectured by _Simon Plouffe_ in his 1992 dissertation
%t m = Table[ If[j <= 6-i, 1, 0], {i, 1, 5}, {j, 1, 5}] ; a[n_] := MatrixPower[m, n].Table[1, {5}]; Table[ a[n], {n, 0, 23}][[All, 1]] (* _Jean-François Alcover_, Dec 08 2011, after _Benoit Cloitre_ *)
%t LinearRecurrence[{3,3,-4,-1,1},{1,5,15,55,190},30] (* _Harvey P. Dale_, Jun 16 2016 *)
%o (PARI) k=5; M(k)=matrix(k,k,i,j,if(1-sign(i+j-k),0,1)); v(k)=vector(k,i,1); a(n)=vecmax(v(k)*M(k)^n)
%o (PARI) {a(n)=local(p=5);polcoeff(sum(k=0,p-1,(-1)^((k+1)\2)*binomial((p+k-1)\2,k)* (-x)^k)/sum(k=0,p,(-1)^((k+1)\2)*binomial((p+k)\2,k)*x^k+x*O(x^n)),n)}
%Y Cf. A000217, A000330, A050446, A050447.
%Y See also A006356-A006359, A025030, A030112-A030116.
%Y Cf. A038201 (5-wave sequence).
%K nonn,easy,nice
%O 0,2
%A _N. J. A. Sloane_
%E Alternative description and formula from Jacques Haubrich (jhaubrich(AT)freeler.nl)
%E More terms from _James A. Sellers_, Dec 24 1999