login
This site is supported by donations to The OEIS Foundation.

 

Logo

The OEIS is looking to hire part-time people to help edit core sequences, upload scanned documents, process citations, fix broken links, etc. - Neil Sloane, njasloane@gmail.com

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006356 a(n) = 2*a(n-1) + a(n-2) - a(n-3).
(Formerly M2578)
50
1, 3, 6, 14, 31, 70, 157, 353, 793, 1782, 4004, 8997, 20216, 45425, 102069, 229347, 515338, 1157954, 2601899, 5846414, 13136773, 29518061, 66326481, 149034250, 334876920, 752461609, 1690765888, 3799116465, 8536537209, 19181424995 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

Number of distributive lattices; also number of paths with n turns when light is reflected from 3 glass plates.

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

Also u(k)^2+v(k)^2+w(k)^2 = u(2k). - Gary W. Adamson, Dec 23 2003

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.

One such path (with 2 plates of glass and 3 reflections) might be:

...\........./..................

--------------------------------

....\/\..../....................

--------------------------------

........\/......................

--------------------------------

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/(2k+1)) and it is conjectured that z(k) is the root 1<x<2 of a polynomial of degree Phi(2k+1)/2.

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

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.

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

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

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

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

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.

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

Equals row sums of triangle A180262. - Gary W. Adamson, Aug 21 2010

The number of the one-sided n-step prudent walks, avoiding 2 or more consecutive east steps. - Shanzhen Gao, Apr 27 2011

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

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

REFERENCES

J. Berman and P. Koehler, Cardinalities of finite distributive lattices, Mitteilungen aus dem Mathematischen Seminar Giessen, 121 (1976), 103-124.

S. J. Cyvin and I. Gutman, Kekulé structures in benzenoid hydrocarbons, Lecture Notes in Chemistry, No. 46, Springer, New York, 1988 (see p. 120).

S. Gao, H. Niederhausen, Sequences Arising From Prudent Self-Avoiding Walks (submitted to INTEGERS: The Electronic Journal of Combinatorial Number Theory).

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 2nd edition, p. 291 (very briefly without generalizations).

J. Haubrich, Multinacci Rijen [Multinacci sequences], Euclides (Netherlands), Vol. 74, Issue 4, 1998, pp. 131-133.

Jay Kappraff, Beyond Measure, A Guided Tour Through Nature, Myth and Number, World Scientific, 2002.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

T. D. Noe, Table of n, a(n) for n=0..200

J. Berman and P. Koehler, Cardinalities of finite distributive lattices, Mitteilungen aus dem Mathematischen Seminar Giessen, 121 (1976), 103-124. [Annotated scanned copy]

Emma L. L. Gao, Sergey Kitaev, Philip B. Zhang, Pattern-avoiding alternating words, preprint, 2015.

Shanzhen Gao, Keh-Hsun Chen, Tackling Sequences From Prudent Self-Avoiding Walks, FCS'14, The 2014 International Conference on Foundations of Computer Science.

Manfred Goebel, Rewriting Techniques and Degree Bounds for Higher Order Symmetric Polynomials, Applicable Algebra in Engineering, Communication and Computing (AAECC), Volume 9, Issue 6 (1999), 559-573.

V. E. Hoggatt Jr. and M. Bicknell-Johnson, Reflections across two and three glass plates, Fibonacci Quarterly, volume 17 (1979), 118-142.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 451

L. E. Jeffery, Unit-primitive matrices

B. Junge and V. E. Hoggatt, Jr., Polynomials arising from reflections across multiple plates, Fib. Quart., 11 (1973), 285-291.

G. Kreweras, Les preordres totaux compatibles avec un ordre partiel, Math. Sci. Humaines No. 53 (1976), 5-30.

Julien Leroy, Michel Rigo, Manon Stipulanti, Behavior of Digital Sequences Through Exotic Numeration Systems, Electronic Journal of Combinatorics 24(1) (2017), #P1.44.

Leo Moser, Problem B-6: some reflections, Fib. Quart. Vol. 1, No. 4 (1963), 75-76.

Leo Moser and Max Wyman, Multiple reflections, Fib. Quart., 11 (1973).

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.

Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 1992.

P. Steinbach, Golden fields: a case for the heptagon, Math. Mag. 70 (1997), no. 1, 22-31.

R. Witula, D. Slota and A. Warzynski, Quasi-Fibonacci Numbers of the Seventh Order, J. Integer Seq., 9 (2006), Article 06.4.3.

Index entries for linear recurrences with constant coefficients, signature (2,1,-1).

FORMULA

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

G.f.: (1+x-x^2)/(1-2*x-x^2+x^3). - Paul D. Hanna, Feb 06 2006

a(n) = a(n-1) + a(n-2) + A006054(n+1). - Gary W. Adamson, Jun 05 2008

a(n) = A006054(n+2)+A006054(n+1)-A006054(n). - R. J. Mathar, Apr 07 2011

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

MAPLE

A006356:=-(-1-z+z**2)/(1-2*z-z**2+z**3); # conjectured by Simon Plouffe in his 1992 dissertation

MATHEMATICA

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

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

PROG

(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

(Maxima)

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

(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

(Haskell)

a006056 n = a006056_list !! n

a006056_list = 1 : 3 : 6 : zipWith (+) (map (2 *) $ drop 2 a006056_list)

   (zipWith (-) (tail a006056_list) a006056_list)

-- Reinhard Zumkeller, Oct 14 2011

(PARI) Vec((1+x-x^2)/(1-2*x-x^2+x^3)+O(x^66)) \\ Joerg Arndt, Apr 30 2013

CROSSREFS

Cf. A000217, A000330, A050446, A050447, A006054, A077998, A052534, A052994, A052949.

See also A006357-A006359, A025030, A030112-A030116.

Cf. A038196 (3-wave sequence).

Cf. A179542. - Gary W. Adamson, Jul 18 2010

Cf. A180262. - Gary W. Adamson, Aug 21 2010

Cf. A033303, A190360.

Sequence in context: A218982 A106803 A199853 * A077998 A209357 A090165

Adjacent sequences:  A006353 A006354 A006355 * A006357 A006358 A006359

KEYWORD

nonn,easy,nice,walk,changed

AUTHOR

N. J. A. Sloane

EXTENSIONS

Recurrence, alternative description from Jacques Haubrich (jhaubrich(AT)freeler.nl)

Alternative definition added by Andrew Niedermaier, Nov 11 2008

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy .

Last modified May 28 20:12 EDT 2017. Contains 287241 sequences.