This site is supported by donations to The OEIS Foundation.
User:David Scambler/Paths on Basket Weave Tilings
Contents
Paths on Basket Weave Tilings
Basket Weave Tilings
A basket weave tiling is a grid of cells tiled alternately with horizontal and vertical strands.
Below are 3x3 grids tiled with 1, 2, 3 and 9 strands respectively in each direction.
The following 3x3 grids are tiled asymmetrically with (2,3), (3,2) and (10,3) strands.
Paths
Paths on basket weave tilings are introduced here as a different approach to visualizing some familiar combinatorial statistics. [a]
The diagram below shows a tiling 5 cells wide and 5 cells high, with each cell having either 3 vertical or 3 horizontal strands. The path shown lies weakly above the diagonal, has length 30 and can be written in terms of North and East steps as NNNNEEENNNNNEEENNEEENEEENNNEEE.
The number of such paths with n=5 (5x5 cells) and s=3 ((3,3) stranding) is given by A007564(5) = 562. The sequence A007564 also counts Motzkin paths of length n-1 in which the level steps have 4 colors and the up steps have 3.
This visualization of paths is different in that rather than varying the type, size or coloring of path steps, the steps remain simple whereas the lattice underneath them changes.
Simple Tilings
Simple tilings are based on a n x n grid and have s strands in both the vertical and horizontal directions.
Unrestricted paths
Unrestricted paths run from (0,0) to (n,n) using only North and East steps.
For 1 strand tiling the number of paths on an nxn grid are given by the central binomial coefficients, 1, 2, 6, 20, 70, 252, 924, 3432, ... (A000984).
For 2 strand tiling the number of paths on an nxn grid are given by the central Delannoy numbers, 1, 3, 13, 63, 321, 1683, 8989, 48639, ... (A001850). Unrestricted paths on 2 strand tiling are equivalent to Delannoy paths or King walks on an nxn board.
The diagram below illustrates the Delannoy numbers A001850(1) = 3 and A001850(2) = 13.
In general, n-paths on basket weave s-tiling are counted by the central coefficients of Pascal (1, s-1, 1)-Arrays.[1]
| s | Sequence | Pascal Array | Number of Paths (n>=0) | Number of Peaks / Valleys (n>0) |
| 1 | A000984 | A007318 | 1,2,6,20,70,252,924,3432,12870,48620,... | A002457(n-1): 1,6,30,140,630,2772,51480, … |
| 2 | A001850 | A008288 | 1,3,13,63,321,1683,8989,48639,265729,... | 2*A002695(n-1): 2,18,132,900,5910,37926,1497096,… |
| 3 | A069835 | A081577 | 1,4,22,136,886,5944,40636,281488,... | 3,34,318,2772,23290,191292,12375592, … |
| 4 | A084771 | A081578 | 1,5,33,245,1921,15525,127905,1067925,... | 4,54,606,6356,64320,636570,59828040, … |
| 5 | A084772 | A081579 | 1,6,46,396,3606,33876,324556,3151896,... | 5,78,1014,12348,145230,1671300, … |
| 6 | A098659 | A081580 | 1,7,61,595,6145,65527,712909,7863667,... | 6,106,1560,21540,287530,3757182, … |
| 7 | - | A081581 | 1,8,78,848,9766,116208,1411404,... | |
| 8 | - | A081582 | 1,9,97,1161,14721,192969,2582881,... | |
| 9 | - | A143683 | 1,10,118,1540,21286,304300,4443580,... | |
| 10 | - | A143685 | 1,11,141,1991,29761,460251,7272861,... |
Paths weakly above y = x
Paths weakly above y = x run from (0,0) to (n,n) using only North and East steps and may touch but not drop below the diagonal.
For 1 strand tiling the number of paths on an nxn grid are given by the Catalan numbers, 1, 1, 2, 5, 14, 42, 132, ... (A000108). These are the Dyck paths of semilength n.
For 2 strand tiling the number of paths on an nxn grid are given by the Super-Catalan numbers, 1, 1, 3, 11, 45, 197, 903, ... (A001003). Paths on 2 strand tiling are equivalent to little Schroeder paths on an nxn grid, or large Schroeder paths with no flat steps at ground level.
The diagram below illustrates the Super-Catalan numbers A001003(2) = 3 and A001003(3) = 11.
In general, n-paths weakly above y = x on basket weave s-tiling are counted by the following OEIS sequences:
| s | Sequence | Number of Paths (n>=0) | Number of Peaks (n>0) | Number of Valleys (n>1) |
| 1 | A000108 | 1,1,2,5,14,42,132,429,1430,4862,16796,... | A088218(n>0): 1,3,10,35,126,462,6435, … | A002054(n-2): 1,5,21,84,330,5005, … |
| 2 | A001003 | 1,1,3,11,45,197,903,4279,20793,103049,... | A035029(n-1): 1,5,26,138,743,4043, … | 2,15,93,546,3140,… |
| 3 | A007564 | 1,1,4,19,100,562,3304,20071,124996,... | 1,7,48,331,2302,16134,… | 3,29,231,1740,12830,… |
| 4 | A059231 | 1,1,5,29,185,1257,8925,65445,491825,... | 1,9,76,638,5379,45615,… | 4,47,453,4122,36690,… |
| 5 | A078009 | 1,1,6,41,306,2426,20076,171481,1500666,... | ||
| 6 | A078018 | 1,1,7,55,469,4237,39907,387739,3858505,... | ||
| 7 | A081178 | 1,1,8,71,680,6882,72528,788019,8766248,... | ||
| 8 | A082147 | 1,1,9,89,945,10577,123129,1476841,... | ||
| 9 | A082181 | 1,1,10,109,1270,15562,198100,2596645,... | ||
| 10 | A082148 | 1,1,11,131,1661,22101,305151,4335711,... |
Paths strictly above y = x
Paths strictly above y = x run from (0,0) to (n,n) using only North and East steps and do not touch the diagonal except at the end points.
For 1 strand tiling the number of paths on an nxn grid are given by the (n-1)th Catalan numbers, 1, 1, 2, 5, 14, 42, 132, ... (A000108).
For 2 strand tiling the number of paths on an nxn grid are given by the (n-1)th Large Schroeder numbers, 1, 2, 6, 22, 90, 394, ... (A006318). Paths on 2 strand tiling are equivalent to Schroeder paths on an n-1 x n-1 grid.
The diagram below illustrates the Schroeder numbers A006318(1) = 2 and A006318(2) = 6.
In general, (n+1)-paths strictly above y = x on basket weave s-tiling are counted by the following OEIS sequences:
| s | Sequence | Number of Paths (n>=0) | Number of Peaks (n>0) | Number of Valleys (n>1) |
| 1 | A000108 | 1,1,2,5,14,42,132,429,1430,4862,16796,... | A088218(n-1): 1,1,3,10,35,126,1716, … | A002054(n-3): 0,1,5,21,84,1287, … |
| 2 | A006318 | 1,2,6,22,90,394,1806,8558,41586,206098,... | A001850(n-1): 1,3,13,63,321,1683,48639, … | A026002(n-2): 1,7,41,231,1289,40081, … |
| 3 | A047891 | 1,3,12,57,300,1686,9912,60213,374988,... | 1,5,29,182,1193,8030,381596, … | 2,17,125,893,6344,321383, … |
| 4 | A082298 | 1,4,20,116,740,5028,35700,261780,... | 1,7,51,391,3107,25287,1752135, … | 3,31,275,2367,20259,1490355, … |
| 5 | A082301 | 1,5,30,205,1530,12130,100380,857405,... | ||
| 6 | A082302 | 1,6,42,330,2814,25422,239442,2326434,... | ||
| 7 | A082305 | 1,7,56,497,4760,48174,507696,5516133,... | ||
| 8 | A082366 | 1,8,72,712,7560,84616,985032,... | ||
| 9 | A082367 | 1,9,90,981,11430,140058,1782900,... | ||
| 10 | A143749 | 1,10,110,1310,16610,221010,3051510,... |
Bijections
Given the empirical correspondence of tiling paths to Delannoy, Schroeder and Motzkin paths, bijections should exist. However, only one simple bijection has been found so far.
2-tiling to Delannoy and Schroeder bijection
Unrestricted n-paths on basket weave 2-tiling can be converted to Delannoy n-paths by changing the NEN and ENE steps that pass through the center of cells to NE steps across the cell.
Restricting these Delannoy paths to weakly above or below the diagonal produces Schroeder paths. However with basket
weave tiling, tiles that are bisected by the diagonal cannot have ENE steps. This is equivalent to removing Schroeder
paths with NE steps on the diagonal and leads to little Schroeder paths.
(v,h)-tiling bijections - open questions
It is the case that n-paths weakly above the diagonal on s-tiling are equivalent to Motzkin paths of length n-1 with s+1 colors for the flat steps and s colors for the up steps.
However a bijective proof has not yet been found.
Enumeration
General Counting Procedure
Steps to enumerate paths on a (v,h)-tiling are as follows:
Mark the nodes along the top or elsewhere that have only 1 path to reach (n,n).
Mark internal nodes (a,b) with the sum of ways of reaching (a+1,b), (a,b+1) and (a+1,b+1), that is, the nodes to the N, E and NE of the node (a,b). There is only one path to N and to E but there are (v-1) or (h-1) paths to NE, depending on whether a vertical or horizontal cell is being traversed. Nodes on the diagonal can only connect northwards in this example.
The number of 3-paths weakly above y=x on (3,2)-tiling is 12.
Counting unrestricted paths
Consider unrestricted n-paths on 2-tiling.
The nodes along the top and the nodes down the right hand side only have 1 path to (n,n). T(i,n) = T(n,j) = 1.
For other nodes T(i,j) = T(i+1,j) + T(i,j+1) + (2-1) * T(i+1,j+1) = T(i+1,j) + T(i,j+1) + T(i+1,j+1).
This is precisely the definition of the Delannoy array A008288.
Consider unrestricted n-paths on s-tiling.
For internal nodes T(i,j) = T(i+1,j) + T(i,j+1) + (s-1) * T(i+1,j+1), which defines the Pascal (1,s-1,1)-Arrays.
Counting paths weakly above y=x
Consider n-paths weakly above y=x on 2-tiling.
The nodes along the top only have 1 path to (n,n), T(n,j) = 1. Nodes on the diagonal can only connect northwards so for i<n T(i,i) = T(i,i+1).
For other nodes T(i,j) = T(i+1,j) + T(i,j+1) + (2-1) * T(i+1,j+1) = T(i+1,j) + T(i,j+1) + T(i+1,j+1).
This is precisely the definition of the Super-Catalan triangle A144944.
Consider n-paths weakly above y=x on s-tiling.
For internal nodes T(i,j) = T(i+1,j) + T(i,j+1) + (s-1) * T(i+1,j+1), which defines a generalized (s-1)-Super-Catalan triangle in the same vein as the generalized Pascal arrays.
Counting paths strongly above y=x
Consider n-paths strongly above y=x on 2-tiling.
The nodes along the top only have 1 path to (n,n), T(n,j) = 1. Nodes on the diagonal cannot be used so for T(i,i) = 0. This reduces the triangle to (n-1) x (n-1).
For other nodes T(i,j) = T(i+1,j) + T(i,j+1) + (2-1) * T(i+1,j+1) = T(i+1,j) + T(i,j+1) + T(i+1,j+1).
This is the definition of the triangle related to Schroeder numbers A033877.
Consider n-paths strongly above y=x on s-tiling.
For internal nodes T(i,j) = T(i+1,j) + T(i,j+1) + (s-1) * T(i+1,j+1), which defines a generalized (s-1)-Schroeder triangle in the same vein as the generalized Pascal arrays.
Paths on (v,h)-tiling
These are counted like the paths on s-tiling but the general node formula becomes T(i+1,j) + T(i,j+1) + (f(i,j)-1) * T(i+1,j+1) where f(i,j) = v if ((i+j) mod 2) = 0, otherwise h.
Paul Barry (private communication) has shown that for n-paths strictly above x=y the sequences for
(2, r )-tiling have g.f. given by the continued fraction
- 1/(1-rx-x/(1-x-x/(1-rx-x/(1-x-x/(1-rx-x/(1-x-x/(1-....
so that their g.f. u(x) satisfies the equation
- u=1/(1-r*x-x/(1-x-x*u)).
Thus
- u(x)=- (sqrt(x-1)*(sqrt(r*x^2-x(r+5)+1)+sqrt(x-1)*sqrt(rx-1)))/(2*sqrt(r*x-1)).
The coefficient array of this family of polynomials is Emeric Deutsch's A101894.
Empirical Results
Paths on an n x k grid
Empirical results show that unrestricted s-paths from (0,0) to (n,k) are counted by coefficients of the Pascal (1, s-1, 1)-Arrays. Now confirmed.[^]
Paths on (v,h)-tiling
Asymmetric tiling with v vertical and h horizontal strands is denoted (v,h)-tiling. Some preliminary empirical results for the general case of n-paths on (v,h)-tiling are presented here.
Paths on (s,1)-tiling
Unrestricted n-paths on (s,1)-tiling form a family with recurrence formula: [b]
a(0)=1, a(1)=(s+1); a(n+2) = ((s+1) * (2n+3) * a(n+1) - (s-1)*(s+3) * (n+1) * a(n)) / (n+2)
Each row is the binomial transform of the previous row.
(2,1)-tiling: A026375 1,3,11,45,195,873,3989,18483,
(3,1)-tiling: A081671 1,4,18,88,454,2424,13236,73392,
(4,1)-tiling: A098409 1,5,27,155,931,5775,36645,236325,
(5,1)-tiling: A098410 1,6,38,252,1734,12276,88796,652728,
(6,1)-tiling: A104454 1,7,51,385,2995,23877,194109,1602447,
(7,1)-tiling: 1,8,66,560,4870,43248,390804,3582048,
Paths on (1,s)-tiling
n-paths with y>=x on (1,s)-tiling form a family with formula:
a(0)=a(1)=1; a(n+2) = ((s+1) * (2n+3) * a(n+1) - (s-1)*(s+3) * n * a(n)) / (n+3)
Ignoring the first term, each row is the binomial transform of the previous row.
(1,2)-tiling: A002212 1,1,3,10,36,137,543,2219,9285,
(1,3)-tiling: A005572* 1,1,4,17,76,354,1704,8421,42508,
(1,4)-tiling: A125906* 1,1,5,26,140,777,4425,25755,152675,
(1,5)-tiling: A025230* 1,1,6,37,234,1514,9996,67181,458562,3172478,
(1,6)-tiling: 1,1,7,50,364,2697,20307,155139,1200745,
- Some of these OEIS sequence "matches" have different 1st terms, and A125906 is a Riordan array with a matching column.
Other results
n-paths on (2,4)-tiling match the central coefficients of triangle A115991. Note that A115991 is the Riordan array (1/sqrt(1-2x-7x^2),(1+x-sqrt(1-2x-7x^2))/2). - Paul Barry 26 Feb 2011
Also, counts of n-paths with y>=x on 2-tiling decomposed by number of peaks gives A033282 - Triangle read by rows: T(n,k) is the number of diagonal dissections of a convex n-gon into k+1 regions.
And counts of unrestricted n-paths on 2-tiling decomposed by number of peaks gives A063007 - Triangle: T(n,k) = C(n,k)*C(n+k,k) read by rows.
And, counts of n-paths with y > x on 2-tiling decomposed by number of peaks gives A088617 - Triangle T(n,k) (n>=0, k=0..n) read by rows: T(n,k) = C(n+k,n)*C(n,k)/(k+1).
References
1. Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.
Notes
a) Paths on basket weave tiling were first introduced in a post by David Scambler to the Seqfan list on Thu Feb 17 2001.
b) Formula based on a suggestion from WolframAlpha.
