|
%I M2578 #210 Feb 19 2024 14:17:58
%S 1,3,6,14,31,70,157,353,793,1782,4004,8997,20216,45425,102069,229347,
%T 515338,1157954,2601899,5846414,13136773,29518061,66326481,149034250,
%U 334876920,752461609,1690765888,3799116465,8536537209,19181424995
%N a(n) = 2*a(n-1) + a(n-2) - a(n-3) for n >= 3, starting with a(0) = 1, a(1) = 3, and a(2) = 6.
%C Number of distributive lattices; also number of paths with n turns when light is reflected from 3 glass plates.
%C Let u(k), v(k), w(k) be defined by u(1) = 1, v(1) = 0, w(1) = 0 and u(k+1) = u(k) + v(k) + w(k), v(k+1) = u(k) + v(k), w(k+1) = u(k); then {u(n)} = 1, 1, 3, 6, 14, 31, ... (this sequence with an extra initial 1), {v(n)} = 0, 1, 2, 5, 11, 25, ... (A006054 with its initial 0 deleted) and {w(n)} = {u(n)} prefixed by an extra 0 = A077998 with an extra initial 0. - _Benoit Cloitre_, Apr 05 2002
%C Also u(k)^2 + v(k)^2 + w(k)^2 = u(2*k). - _Gary W. Adamson_, Dec 23 2003
%C The n-th term of the series is the number of paths for a ray of light that enters two layers of glass and then is reflected exactly n times before leaving the layers of glass.
%C One such path (with 2 plates of glass and 3 reflections) might be:
%C ...\........./..................
%C --------------------------------
%C ....\/\..../....................
%C --------------------------------
%C ........\/......................
%C --------------------------------
%C For a k-glass sequence, say a(n,k), a(n,k) is always asymptotic to z(k)*w(k)^n where w(k) = (1/2)/cos(k*Pi/(2*k+1)) and it is conjectured that z(k) is the root 1 < x < 2 of a polynomial of degree Phi(2k+1)/2.
%C Number of ternary sequences of length n-1 such that every pair of consecutive digits has a sum less than 3. That is to say, the pairs (1,2), (2,1) and (2,2) do not appear. - George J. Schaeffer (gschaeff(AT)andrew.cmu.edu), Sep 07 2004
%C Number of weakly up-down sequences of length n using the digits {1,2,3}. When n=2 the sequences are 11, 12, 13, 22, 23, 33.
%C Form the graph with matrix A = [1, 1, 1; 1, 0, 0; 1, 0, 1]. Then A006356 counts walks of length n that start at the degree 4 vertex. - _Paul Barry_, Oct 02 2004
%C In general, the g.f. for p glass plates is: A(x) = F_{p-1}(-x)/F_p(x) where F_p(x) = Sum_{k=0..p} (-1)^[(k+1)/2]*C([(p+k)/2],k)*x^k. - _Paul D. Hanna_, Feb 06 2006
%C Equals the INVERT transform of (1, 2, 1, 1, 1, ...) equivalent to a(n) = a(n-1) + 2*a(n-2) + a(n-3) + a(n-4) + ... + 1. a(6) = 70 = (31 + 2*14 + 6 + 3 + 1 + 1). - _Gary W. Adamson_, Apr 27 2009
%C a(n) = the number of terms in the n-th iterate of sequence A179542 generated from the rules a(0) = 1, then (1->1,2,3), (2->1,2), (3->1).
%C Example: 3rd iterate = (1,2,3,1,2,1,1,2,3,1,2,1,2,3) = 14 terms composed of a frequency of (6, 5, 3): (1's, 2's, and 3's), where a(3) = 14, and the [6, 5, 3] = top row and left column of the 3rd power of M, the matrix generator [1,1,1; 1,1,0; 1,0,0] or a(2) = 6, A006054(4) = 5, and a(1) = 3.
%C Given the heptagon diagonal lengths with edge = 1: (a = 1, b = 1.80193773... and c = 2.24697... = (1, 2*cos(Pi/7), (1 + 2*cos(2*Pi/7))), and using the diagonal product formulas in [Steinbach], we obtain: c^n = c*a(n-2) + b*A006054(n) + a(n-3) corresponding to the top row of M^(n-1), in the case M^3 = [6, 5, 3]. Example: c^4 = 25.491566... = 6*c + 5*b + 3 = 13.481... + 9.00968... + 3. - _Gary W. Adamson_, Jul 18 2010
%C Equals row sums of triangle A180262. - _Gary W. Adamson_, Aug 21 2010
%C The number of the one-sided n-step prudent walks, avoiding 2 or more consecutive east steps. - _Shanzhen Gao_, Apr 27 2011
%C a(n) = [A_{7,2}^(n+2)]_(1,1), where A_{7,2} is the 3 X 3 unit-primitive matrix (see [Jeffery]) A_{7,2} = [0,0,1; 0,1,1; 1,1,1]. The denominator of the generating function for this sequence is also the characteristic polynomial of A_{7,2}. - _L. Edson Jeffery_, Dec 06 2011 [See the comments for sequence A306334. - _Petros Hadjicostas_, Nov 17 2019]
%C a(n) is the top left entry of the n-th power of the 3 X 3 matrix [1, 1, 1; 1, 0, 0; 1, 0, 1] or of the 3 X 3 matrix [1, 1, 1; 1, 1, 0; 1, 0, 0]. - _R. J. Mathar_, Feb 03 2014
%C Successive sequences in this set (A006356, A006357, A006358, etc.) can be generated as follows: Begin with (1, 1, 1, 1, 1, 1, ...); and perform an operation with three steps to get the next sequence in the series. First, put alternate signs in the current series: With (1, 1, 1, ...) this equals (1, -1, 1, -1, ...); then take the inverse, getting (1, 1, 0, 0, 0, ...). Take the INVERT transform of the last step, getting (1, 2, 3, 5, 8, ...). Repeat the three steps using (1, 2, 3, 5, ...) --> (1, -2, 3, -5) --> (1, 2, 1, 1, 1, ...) --> (1, 3, 6, 14, 31, ...). Repeat the three steps using (1, 3, 6, 14, 31, ...), getting (1, 4, 10, 30, 85, ...) = A006357; and so on.
%C - _Gary W. Adamson_, Aug 08 2019
%C Let W_n be the fence poset (a.k.a. zig-zag poset) of size n. Let [2] be a chain of size 2. Then a(n) is the number of antichains in the product poset W_n X [2]. See Berman- Koehler link. - _Geoffrey Critzer_, Jun 13 2023
%C a(n) is the number of double-dimer covers of the 2 X (n+1) square grid graph. See Musiker et al. link. - _Nicholas Ovenhouse_, Jan 07 2024
%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 R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 2nd edition, p. 291 (very briefly without generalizations).
%D J. Haubrich, Multinacci Rijen [Multinacci sequences], Euclides (Netherlands), Vol. 74, Issue 4, 1998, pp. 131-133.
%D Jay Kappraff, Beyond Measure, A Guided Tour Through Nature, Myth and Number, World Scientific, 2002.
%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="/A006356/b006356.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 J. Berman and P. Köhler, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL24/Koehler/koehler5.html">On Dedekind Numbers and Two Sequences of Knuth</a>, J. Int. Seq., Vol. 24 (2021), Article 21.10.7.
%H Emma L. L. Gao, Sergey Kitaev, and Philip B. Zhang, <a href="https://personal.cis.strath.ac.uk/sergey.kitaev/index_files/Papers/pat-av-alt-words.pdf">Pattern-avoiding alternating words</a>, preprint, 2015.
%H Shanzhen Gao and Keh-Hsun Chen, <a href="http://worldcomp-proceedings.com/proc/p2014/FCS2696.pdf">Tackling Sequences From Prudent Self-Avoiding Walks</a>, FCS'14, The 2014 International Conference on Foundations of Computer Science.
%H S. Gao and H. Niederhausen, <a href="http://math.fau.edu/Niederhausen/HTML/Papers/Sequences%20Arising%20From%20Prudent%20Self-Avoiding%20Walks-February%2001-2010.pdf">Sequences Arising From Prudent Self-Avoiding Walks</a>, 2010.
%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 V. E. Hoggatt Jr. and M. Bicknell-Johnson, <a href="http://www.fq.math.ca/Scanned/17-2/hoggatt.pdf">Reflections across two and three glass plates</a>, Fibonacci Quarterly, volume 17 (1979), 118-142.
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=451">Encyclopedia of Combinatorial Structures 451</a>
%H L. E. Jeffery, <a href="/wiki/User:L._Edson_Jeffery/Unit-Primitive_Matrices">Unit-primitive matrices</a>
%H B. Junge and V. E. Hoggatt, Jr., <a href="http://www.fq.math.ca/Scanned/11-3/junge.pdf">Polynomials arising from reflections across multiple plates</a>, Fib. Quart., 11 (1973), 285-291.
%H Peter Köhler, <a href="https://doi.org/10.1007/s11083-021-09572-5">The Central Decomposition of FD_01(n)</a>, Order (2021).
%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 Julien Leroy, Michel Rigo, and Manon Stipulanti, <a href="https://doi.org/10.37236/6581">Behavior of Digital Sequences Through Exotic Numeration Systems</a>, Electronic Journal of Combinatorics 24(1) (2017), #P1.44.
%H Leo Moser, <a href="http://www.fq.math.ca/Scanned/1-4/elementary1-4.pdf">Problem B-6: some reflections</a>, Fib. Quart. Vol. 1, No. 4 (1963), 75-76.
%H Leo Moser and Max Wyman, <a href="http://www.fq.math.ca/Scanned/11-3/moser.pdf">Multiple reflections</a>, Fib. Quart., 11 (1973).
%H Gregg Musiker, Ralf Schiffler, Nicholas Ovenhouse, and Sylvester Zhang, <a href="https://arxiv.org/abs/2306.14389">Higher Dimer Covers on Snake Graphs</a>, arXiv:2306.14389 [math.CO], 2023.
%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 P. Steinbach, <a href="http://www.jstor.org/stable/2691048">Golden fields: a case for the heptagon</a>, Math. Mag. 70 (1997), no. 1, 22-31.
%H R. Witula, D. Slota and A. Warzynski, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Slota/slota57.html">Quasi-Fibonacci Numbers of the Seventh Order</a>, J. Integer Seq., 9 (2006), Article 06.4.3.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (2,1,-1).
%F a(n) is asymptotic to z(3)*w(3)^n where w(3) = (1/2)/cos(3*Pi/7) and z(3) is the root 1 < X < 2 of P(3, X) = 1 - 14*X - 49*X^2 + 49*X^3. w(3) = 2.2469796.... z(3) = 1.220410935...
%F G.f.: (1 + x - x^2)/(1 - 2*x - x^2 + x^3). - _Paul D. Hanna_, Feb 06 2006
%F a(n) = a(n-1) + a(n-2) + A006054(n+1). - _Gary W. Adamson_, Jun 05 2008
%F a(n) = A006054(n+2) + A006054(n+1) - A006054(n). - _R. J. Mathar_, Apr 07 2011
%F a(n-1) = Sum_{k = 1..n} Sum_{i = k..n} Sum_{j = 0..k} binomial(j, -3*k+2*j+i) * (-1)^(j-k) * binomial(k, j) * binomial(n+k-i-1, k-1). - _Vladimir Kruchinin_, May 05 2011
%F Sum_{k=0..n} a(k) = a(n+1) - a(n-1) - 1. - _Greg Dresden_ and _Mina BH Arsanious_, Aug 23 2023
%p A006356:=-(-1-z+z**2)/(1-2*z-z**2+z**3); # conjectured by _Simon Plouffe_ in his 1992 dissertation
%t LinearRecurrence[{2,1,-1},{1,3,6},30] (* or *) CoefficientList[ Series[ (1+x-x^2)/(1-2x-x^2+x^3),{x,0,30}],x] (* _Harvey P. Dale_, Jul 06 2011 *)
%t Table[If[n==0, a2=0; a1=1; a0=1, a3=a2; a2=a1; a1=a0; a0=2*a1+a2-a3], {n, 0, 29}] (* _Jean-François Alcover_, Apr 30 2013 *)
%o (PARI) {a(n)=local(p=3);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)} \\ _Paul D. Hanna_, Feb 06 2006
%o (PARI) Vec((1+x-x^2)/(1-2*x-x^2+x^3)+O(x^66)) \\ _Joerg Arndt_, Apr 30 2013
%o (Maxima)
%o a(n):=sum(sum((sum(binomial(j,-3*k+2*j+i)*(-1)^(j-k)*binomial(k,j),j,0,k))*binomial(n+k-i-1,k-1),i,k,n),k,1,n); \\ _Vladimir Kruchinin_, May 05 2011
%o (Magma) [ n eq 1 select 1 else n eq 2 select 3 else n eq 3 select 6 else 2*Self(n-1)+Self(n-2)- Self(n-3): n in [1..40] ] ; // _Vincenzo Librandi_, Aug 20 2011
%o (Haskell)
%o a006056 n = a006056_list !! n
%o a006056_list = 1 : 3 : 6 : zipWith (+) (map (2 *) $ drop 2 a006056_list)
%o (zipWith (-) (tail a006056_list) a006056_list)
%o -- _Reinhard Zumkeller_, Oct 14 2011
%o (Python)
%o from math import comb
%o def A006356(n): return sum(comb(j,a)*comb(k,j)*comb(n+k-i,k-1)*(-1 if j-k&1 else 1) for k in range(1,n+2) for i in range(k,n+2) for j in range(k+1) if (a:=-3*k+2*j+i)>=0) # _Chai Wah Wu_, Feb 19 2024
%Y Cf. A000217, A000330, A050446, A050447, A006054, A077998, A052534, A052994, A052949.
%Y See also A006357-A006359, A025030, A030112-A030116.
%Y Cf. A038196 (3-wave sequence).
%Y Cf. A179542. - _Gary W. Adamson_, Jul 18 2010
%Y Cf. A180262. - _Gary W. Adamson_, Aug 21 2010
%Y Cf. A033303, A190360, A306334.
%K nonn,easy,nice,walk
%O 0,2
%A _N. J. A. Sloane_
%E Recurrence, alternative description from Jacques Haubrich (jhaubrich(AT)freeler.nl)
%E Alternative definition added by _Andrew Niedermaier_, Nov 11 2008
|
