×

Sequences involving square zig-zag shapes. (English) Zbl 1471.11036

Summary: We define a so-called square \(k\)-zig-zag shape as a part of the regular square grid. Considering the shape as a \(k\)-zig-zag digraph, we give values of its vertices according to the number of the shortest paths from a base vertex. It provides several integer sequences, whose higher-order homogeneous recurrences are determined by the help of a special matrix recurrence.

MSC:

11B37 Recurrences
11Y55 Calculation of integer sequences
05A10 Factorials, binomial coefficients, combinatorial functions

Software:

OEIS
PDFBibTeX XMLCite
Full Text: arXiv Link

Online Encyclopedia of Integer Sequences:

Number of groups of order n.
a(n) = 3*a(n-1) - a(n-2) for n >= 2, with a(0) = a(1) = 1.
F(2n) = bisection of Fibonacci sequence: a(n) = 3*a(n-1) - a(n-2).
a(n) = (3^n - 1)/2.
Random walks (binomial transform of A006054).
a(n) = a(n-1) + 2*a(n-2) - a(n-3), with a(0) = a(1) = 0, a(2) = 1.
a(n) = 4*a(n-1) - 2*a(n-2) with a(0) = 1, a(1) = 4.
Expansion of g.f. (x^3 - 6*x^2 + 5*x - 1)/((2*x - 1)*(2*x^2 - 4*x + 1)).
Expansion of g.f. (1-x^2)/(1-x-2*x^2+x^3).
Scaled Chebyshev U-polynomial evaluated at sqrt(5)/2.
a(n) = Sum_{k=0..n} binomial(n,k) * binomial(Fibonacci(k)+1,2).
Expansion of (1-2*x)*(1-x)/(1-5*x+6*x^2-x^3).
a(n) = a(n-1) + 3*a(n-2) - 3*a(n-3), with a(0)=a(1)=1, a(2)=4.
Row sums of triangle A060556.
Number of Catalan paths (nonnegative, starting and ending at 0, step +/-1) of 2*n steps with all values <= 5.
Number of Catalan paths (nonnegative, starting and ending at 0, step +-1) of 2*n steps with all values less than or equal to 7.
Binomial transform of Fibonacci(2n).
Expansion of x / ( (x-1)*(x^3 - 9*x^2 + 6*x - 1) ).
Number of (s(0), s(1), ..., s(2n+1)) such that 0 < s(i) < 10 and |s(i) - s(i-1)| = 1 for i = 1,2,...,2n+1, s(0) = 1, s(2n+1) = 4.
Number of (s(0), s(1), ..., s(2n+1)) such that 0 < s(i) < 10 and |s(i) - s(i-1)| = 1 for i = 1,2,...,2n+1, s(0) = 1, s(2n+1) = 6.
Number of (s(0), s(1), ..., s(2n+1)) such that 0 < s(i) < 7 and |s(i) - s(i-1)| = 1 for i = 1,2,...,2n+1, s(0) = 1, s(2n+1) = 4.
Number of (s(0), s(1), ..., s(2n)) such that 0 < s(i) < 7 and |s(i) - s(i-1)| = 1 for i = 1,2,...,2*n, s(0) = 1, s(2n) = 3.
Number of (s(0), s(1), ..., s(2n)) such that 0 < s(i) < 8 and |s(i) - s(i-1)| = 1 for i = 1,2,...,2n, s(0) = 1, s(2n) = 3.
Number of (s(0), s(1), ..., s(2n)) such that 0 < s(i) < 8 and |s(i) - s(i-1)| = 1 for i = 1,2,...,2n, s(0) = 1, s(2n) = 5.
Number of (s(0), s(1), ..., s(2n+1)) such that 0 < s(i) < 8 and |s(i) - s(i-1)| = 1 for i = 1,2,...,2n+1, s(0) = 1, s(2n+1) = 6.
Number of (s(0), s(1), ..., s(2n)) such that 0 < s(i) < 10 and |s(i) - s(i-1)| = 1 for i = 1,2,...,2n, s(0) = 1, s(2n) = 7.
Number of (s(0), s(1), ..., s(2n)) such that 0 < s(i) < 9 and |s(i) - s(i-1)| = 1 for i = 1,2,...,2n, s(0) = 1, s(2n) = 3.
Number of (s(0), s(1), ..., s(2n+1)) such that 0 < s(i) < 9 and |s(i) - s(i-1)| = 1 for i = 1,2,...,2n+1, s(0) = 1, s(2n+1) = 4.
Number of (s(0), s(1), ..., s(2n)) such that 0 < s(i) < 9 and |s(i) - s(i-1)| = 1 for i = 1,2,...,2n, s(0) = 1, s(2n) = 5.
Number of (s(0), s(1), ..., s(2n+1)) such that 0 < s(i) < 9 and |s(i) - s(i-1)| = 1 for i = 1,2,...,2n+1, s(0) = 1, s(2n+1) = 6.
Expansion of x^3/((1-3*x+x^2)*(1-5*x+5*x^2)).
Number of set partitions with at most 3 blocks; number of Dyck paths of height at most 4; dimension of space of symmetric polynomials in 3 noncommuting variables.
Expansion of (1-8*x+21*x^2-20*x^3+5*x^4)/(1-9*x+28*x^2-35*x^3+15*x^4-x^5).
Expansion of 1 / ((1-2*x)*(1-4*x+x^2)).
Expansion of (1-3*x+x^2)/(1-9*x+28*x^2-35*x^3+15*x^4-x^5).
Expansion of (1-x)*(1-3*x)/(1-9*x+28*x^2-35*x^3+15*x^4-x^5).
a(2n) = (3^n - 1)/2, a(2n+1) = 3^n.

References:

[1] S. Ahmad, H. M. A. Siddiqui, A. Ali, M. R. Farahani, M. Imran, and I. N. Cangul, On Wiener index and Wiener polarity index of some polyomino chains,J. Discrete Math. Sci. Cryptogr.22(2019), 1151-1164.
[2] Y. Baryshnikov and D. Romik, Enumeration formulas for Young tableaux in a diagonal strip,Israel J. Math.178(2010), 157-186. · Zbl 1206.05011
[3] H. Belbachir, L. N´emeth, and L. Szalay, Hyperbolic Pascal triangles,Appl. Math. Comput.273(2016), 453-464. · Zbl 1410.11021
[4] H. Belbachir and L. Szalay, On the arithmetic triangles,Siauliai Math. Sem.˘9(2014), 15-26. · Zbl 1309.05012
[5] H. Belbachir, T. Komatsu, and L. Szalay, Linear recurrences associated to rays in Pascal’s triangle and combinatorial identities,Math. Slovaca64(2014), 287-300. · Zbl 1349.11037
[6] L. N´emeth, The growing ration of hyperbolic regular mosaics with bounded cells,Armen. J. Math.9(2017), 1-19. · Zbl 1379.52022
[7] L. N´emeth and L. Szalay, Recurrence sequences in the hyperbolic Pascal triangle corresponding to the regular mosaic{4,5},Ann. Math. Inform.46(2016), 165-173. · Zbl 1374.11019
[8] L. N´emeth and L. Szalay, Power sums in hyperbolic Pascal triangles,An. S¸tiint¸. Univ. “Ovidius” Constant¸a Ser. Mat.26(2018), 189-203. · Zbl 1438.05003
[9] N. J. A. Sloane et al.,The On-Line Encyclopedia of Integer Sequences, 2021. Available athttps://oeis.org. · Zbl 1044.11108
[10] R. P. Stanley, A survey of alternating permutations, combinatorics and graphs,Contemp. Math.531(2010), 165-196 · Zbl 1231.05288
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.