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(2*k). - 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/(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.
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 [See the comments for sequence A306334. - Petros Hadjicostas, Nov 17 2019]
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
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.
- Gary W. Adamson, Aug 08 2019
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
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
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).
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]
J. Berman and P. Köhler, On Dedekind Numbers and Two Sequences of Knuth, J. Int. Seq., Vol. 24 (2021), Article 21.10.7.
Emma L. L. Gao, Sergey Kitaev, and Philip B. Zhang, Pattern-avoiding alternating words, arXiv:1505.04078 [math.CO], 2015.
Shanzhen Gao and Keh-Hsun Chen, Tackling Sequences From Prudent Self-Avoiding Walks, FCS'14, The 2014 International Conference on Foundations of Computer Science.
S. Gao and H. Niederhausen, Sequences Arising From Prudent Self-Avoiding Walks, 2010.
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.
Peter Köhler, The Central Decomposition of FD_01(n), Order (2021).
G. Kreweras, Les préordres totaux compatibles avec un ordre partiel, Math. Sci. Humaines No. 53 (1976), 5-30.
G. Kreweras, Les préordres totaux compatibles avec un ordre partiel, Math. Sci. Humaines No. 53 (1976), 5-30. (Annotated scanned copy)
Julien Leroy, Michel Rigo, and 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).
Gregg Musiker, Ralf Schiffler, Nicholas Ovenhouse, and Sylvester Zhang, Higher Dimer Covers on Snake Graphs, arXiv:2306.14389 [math.CO], 2023.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 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-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
Sum_{k=0..n} a(k) = a(n+1) - a(n-1) - 1. - Greg Dresden and Mina BH Arsanious, Aug 23 2023
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, Feb 06 2006
(PARI) Vec((1+x-x^2)/(1-2*x-x^2+x^3)+O(x^66)) \\ Joerg Arndt, Apr 30 2013
(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
(Python)
from math import comb
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
CROSSREFS
Cf. A038196 (3-wave sequence).
Cf. A179542. - Gary W. Adamson, Jul 18 2010
Cf. A180262. - Gary W. Adamson, Aug 21 2010
KEYWORD
nonn,easy,nice,walk
AUTHOR
EXTENSIONS
Recurrence, alternative description from Jacques Haubrich (jhaubrich(AT)freeler.nl)
Alternative definition added by Andrew Niedermaier, Nov 11 2008
STATUS
approved