A112844 -id:A112844 - cp's OEIS frontend

A112833 Number of domino tilings of a 3-pillow of order n.

1, 2, 5, 20, 117, 1024, 13357, 259920, 7539421, 326177280, 21040987113, 2024032315968, 290333133984905, 62102074862600192, 19808204598680574457, 9421371079480456587520, 6682097668647718038428569, 7067102111711681259234263040, 11145503882824383823706372042925

Offset: 0

Christopher Hanusa (chanusa(AT)math.binghamton.edu), Sep 21 2005

nonn

A 3-pillow is also called an Aztec pillow. The 3-pillow of order n is a rotationally-symmetric region. It has a 2 X 2n central band of squares and then steps up from this band with steps of 3 horizontal squares to every 1 vertical square and steps down with steps of 1 horizontal square to every 1 vertical square.

a(n)^(1/n^2) tends to 1.2211384384439007690866503099... - Vaclav Kotesovec, May 19 2020

			The number of domino tilings of the 3-pillow of order 4 is 117=3^2*13.

Alois P. Heinz, Table of n, a(n) for n = 0..100
C. Hanusa, A Gessel-Viennot-Type Method for Cycle Systems with Applications to Aztec Pillows, PhD Thesis, 2005, University of Washington, Seattle, USA.

This sequence breaks down as A112834^2 times A112835, where A112835 is not necessarily squarefree.
5-pillows: A112836-A112838; 7-pillows: A112839-A112841; 9-pillows: A112842-A112844.
Related to A071101 and A071100.

with(LinearAlgebra):
b:= proc(x, y, k) option remember;
      `if`(y>x or y Matrix(n, (i, j)-> b(i-1, i-1, j-1)):
R:= n-> Matrix(n, (i, j)-> `if`(i+j=n+1, 1, 0)):
a:= n-> Determinant(P(n)+R(n).(P(n)^(-1)).R(n)):
seq(a(n), n=0..20);  # Alois P. Heinz, Apr 26 2013

b[x_, y_, k_] := b[x, y, k] = If[y>x || yJean-François Alcover, Nov 08 2015, after Alois P. Heinz *)

A112835 Small-number statistic from the enumeration of domino tilings of a 3-pillow of order n.

Original entry on oeis.org

1, 2, 5, 5, 13, 16, 37, 45, 109, 130, 313, 377, 905, 1088, 2617, 3145, 7561, 9090, 21853, 26269, 63157, 75920, 182525, 219413, 527509, 634114, 1524529, 1832625, 4405969, 5296384, 12733489, 15306833, 36800465, 44237570, 106355317

Offset: 0

Christopher Hanusa (chanusa(AT)math.binghamton.edu), Sep 21 2005

A 3-pillow is also called an Aztec pillow. The 3-pillow of order n is a rotationally-symmetric region. It has a 2 X 2n central band of squares and then steps up from this band with steps of 3 horizontal squares to every 1 vertical square and steps down with steps of 1 horizontal square to every 1 vertical square.

Plotting A112835(n+2)/A112835(n) gives an intriguing damped sine curve.

			1 + 2*x + 5*x^2 + 5*x^3 + 13*x^4 + 16*x^5 + 37*x^6 + 45*x^7 + 109*x^8 + ...
The number of domino tilings of the 3-pillow of order 4 is 117=3^2*13. A112835(4)=13.

C. Hanusa (2005). A Gessel-Viennot-Type Method for Cycle Systems with Applications to Aztec Pillows. PhD Thesis. University of Washington, Seattle, USA.

A D Mednykh, I A Mednykh, The number of spanning trees in circulant graphs, its arithmetic properties and asymptotic, arXiv preprint arXiv:1711.00175, 2017. See Section 4.

A112833 breaks down as A112834^2 times A112835, where A112835 is not necessarily squarefree.
5-pillows: A112836-A112838; 7-pillows: A112839-A112841; 9-pillows: A112842-A112844.
Cf. A071100, A071101.

{a(n) = local(m = abs(n+3)); polcoeff( (x + x^2 - x^3 + x^5 - x^6 - x^7) / (1 - 2*x^2 - 2*x^4 - 2*x^6 + x^8)  + x * O(x^m), m)} /* Michael Somos, Dec 15 2011 */

a(2*n + 2) = A071100(n). a(2*n + 3) = A071101(n).
G.f.: (1 + x - x^2 + x^4 - x^5 - x^6) / (1 - 2*x^2 - 2*x^4 - 2*x^6 + x^8) = (1 + x) * (1 - x^2) * (1 + x^3) / (1 - 2*x^2 - 2*x^4 - 2*x^6 + x^8). - Michael Somos, Dec 15 2011
a(-n) = a(-6 + n). a(-1) = a(-2) = 1, a(-3) = 0. a(n) = 2*a(n-2) + 2*a(n-4) + 2*a(n-6) - a(n-8). - Michael Somos, Dec 15 2011

A112839 Number of domino tilings of a 7-pillow of order n.

Original entry on oeis.org

1, 2, 5, 13, 34, 136, 666, 3577, 23353, 200704, 2062593, 24878084, 373006265, 6917185552, 153624835953, 4155902941554, 138450383756352, 5602635336941568, 274540864716936000, 16486029239132118530, 1209110712606533552257

Offset: 0

Christopher Hanusa (chanusa(AT)math.binghamton.edu), Sep 21 2005

nonn

A 7-pillow is a generalized Aztec pillow. The 7-pillow of order n is a rotationally-symmetric region. It has a 2 X 2n central band of squares and then steps up from this band with steps of 7 horizontal squares to every 1 vertical square and steps down with steps of 1 horizontal square to every 1 vertical square.

			The number of domino tilings of the 7-pillow of order 8 is 23353=11^2*193.

C. Hanusa (2005). A Gessel-Viennot-Type Method for Cycle Systems with Applications to Aztec Pillows. PhD Thesis. University of Washington, Seattle, USA.

A112839 breaks down as A112840^2 times A112841, where A112841 is not necessarily squarefree.

3-pillows: A112833-A112835; 5-pillows: A112836-A112838; 9-pillows: A112842-A112844.

A112842 Number of domino tilings of a 9-pillow of order n.

Original entry on oeis.org

1, 2, 5, 13, 34, 89, 356, 1737, 9065, 49610, 325832, 2795584, 28098632, 310726442, 3877921669, 58896208285, 1083370353616, 22901813128125, 548749450880000, 15471093192996501, 522297110942557556, 20691062026775504896

Offset: 0

Christopher Hanusa (chanusa(AT)math.binghamton.edu), Sep 21 2005

nonn

A 9-pillow is a generalized Aztec pillow. The 9-pillow of order n is a rotationally-symmetric region. It has a 2 X 2n central band of squares and then steps up from this band with steps of 9 horizontal squares to every 1 vertical square and steps down with steps of 1 horizontal square to every 1 vertical square.

			The number of domino tilings of the 9-pillow of order 8 is 9065=7^2*185.

C. Hanusa (2005). A Gessel-Viennot-Type Method for Cycle Systems with Applications to Aztec Pillows. PhD Thesis. University of Washington, Seattle, USA.

A112842 breaks down as A112843^2 times A112844, where A112844 is not necessarily squarefree.

3-pillows: A112833-A112835; 5-pillows: A112836-A112838; 7-pillows: A112839-A112841.

A112841 Small-number statistic from the enumeration of domino tilings of a 7-pillow of order n.

Original entry on oeis.org

1, 2, 5, 13, 34, 34, 74, 73, 193, 256, 793, 1049, 2465, 2857, 6577, 8226, 21348, 28872, 74740, 91970, 222217, 268769, 669265, 852305, 2201945, 2805760, 7000777, 8636081, 21311098, 26588770, 67091170, 85150213

Offset: 0

Christopher Hanusa (chanusa(AT)math.binghamton.edu), Sep 21 2005

A 7-pillow is a generalized Aztec pillow. The 7-pillow of order n is a rotationally-symmetric region. It has a 2 X 2n central band of squares and then steps up from this band with steps of 7 horizontal squares to every 1 vertical square and steps down with steps of 1 horizontal square to every 1 vertical square.

Plotting A112841(n+2)/A112841(n) gives an intriguing damped sine curve.

			The number of domino tilings of the 7-pillow of order 8 is 23353=11^2*193. A112841(n)=193.

C. Hanusa (2005). A Gessel-Viennot-Type Method for Cycle Systems with Applications to Aztec Pillows. PhD Thesis. University of Washington, Seattle, USA.

A112839 breaks down as A112840^2 times A112841, where A112841 is not necessarily squarefree.

3-pillows: A112833-A112835; 5-pillows: A112836-A112838; 9-pillows: A112842-A112844.

A112836 Number of domino tilings of a 5-pillow of order n.

Original entry on oeis.org

1, 2, 5, 13, 52, 261, 1666, 14400, 159250, 2308545, 43718544, 1079620569, 34863330980, 1466458546176, 80646187346132, 5787269582487581, 541901038236234048, 66279540183479379277, 10578427028263503488000

Offset: 0

Christopher Hanusa (chanusa(AT)math.binghamton.edu), Sep 21 2005

nonn

A 5-pillow is a generalized Aztec pillow. The 5-pillow of order n is a rotationally-symmetric region. It has a 2 X 2n central band of squares and then steps up from this band with steps of 5 horizontal squares to every 1 vertical square and steps down with steps of 1 horizontal square to every 1 vertical square.

			The number of domino tilings of the 5-pillow of order 6 is 1666=7^2*34.

C. Hanusa (2005). A Gessel-Viennot-Type Method for Cycle Systems with Applications to Aztec Pillows. PhD Thesis. University of Washington, Seattle, USA.

A112836 can be decomposed as A112837^2 times A112838, where A112838 is not necessarily squarefree.

3-pillows: A112833-A112835; 7-pillows: A112839-A112841; 9-pillows: A112842-A112844.

A112838 Small-number statistic from the enumeration of domino tilings of a 5-pillow of order n.

Original entry on oeis.org

1, 2, 5, 13, 13, 29, 34, 100, 130, 305, 361, 881, 1145, 2906, 3557, 8669, 10693, 26893, 33680, 83360, 102800, 254565, 317165, 790037, 980237, 2428298, 3011265, 7483801, 9301217, 23092857, 28646722, 71093860

Offset: 0

Christopher Hanusa (chanusa(AT)math.binghamton.edu), Sep 21 2005

A 5-pillow is a generalized Aztec pillow. The 5-pillow of order n is a rotationally-symmetric region. It has a 2 X 2n central band of squares and then steps up from this band with steps of 5 horizontal squares to every 1 vertical square and steps down with steps of 1 horizontal square to every 1 vertical square.

Plotting A112838(n+2)/A112838(n) gives an intriguing damped sine curve.

			The number of domino tilings of the 5-pillow of order 6 is 1666=7^2*34. A112838(n)=34.

C. Hanusa (2005). A Gessel-Viennot-Type Method for Cycle Systems with Applications to Aztec Pillows. PhD Thesis. University of Washington, Seattle, USA.

A112833 breaks down as A112834^2 times A112835, where A112835 is not necessarily squarefree.

3-pillows: A112833-A112835; 7-pillows: A112839-A112841; 9-pillows: A112842-A112844.

A114292 Modified Schroeder numbers for q=3.

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 5, 5, 2, 1, 16, 16, 6, 2, 1, 57, 57, 21, 6, 2, 1, 224, 224, 82, 22, 6, 2, 1, 934, 934, 341, 89, 22, 6, 2, 1, 4092, 4092, 1492, 384, 90, 22, 6, 2, 1, 18581, 18581, 6770, 1729, 393, 90, 22, 6, 2, 1, 86888, 86888, 31644, 8044, 1794, 394, 90, 22, 6, 2, 1

Offset: 0

Christopher Hanusa (chanusa(AT)math.binghamton.edu), Nov 21 2005

a(i,j) is the number of paths from (i,i) to (j,j) using steps of length (0,1), (1,0) and (1,1), not passing above the line y=x nor below the line y=x/2. The Hamburger Theorem implies that we can use this table to calculate the number of domino tilings of an Aztec 3-pillow (A112833). To calculate this quantity, let P_n = the principal n X n submatrix of this array. If J_n = the back-diagonal matrix of order n, then A112833(n)=det(P_n+J_nP_n^(-1)J_n).

			The number of paths from (0,0) to (3,3) staying between the lines y=x and y=x/2 using steps of length (0,1), (1,0) and (1,1) is a(0,3)=5.
Triangle begins:
1;
1, 1;
2, 2, 1;
5, 5, 2, 1;
16, 16, 6, 2, 1;
57, 57, 21, 6, 2, 1;
224, 224, 82, 22, 6, 2, 1;
934, 934, 341, 89, 22, 6, 2, 1;
4092, 4092, 1492, 384, 90, 22, 6, 2, 1;

C. Hanusa (2005). A Gessel-Viennot-Type Method for Cycle Systems with Applications to Aztec Pillows. PhD Thesis. University of Washington, Seattle, USA.

Alois P. Heinz, Rows n = 0..140, flattened

See also A112833-A112844 and A114293-A114299.

b:= proc(x, y, k) option remember;
      `if`(y>x or y b(n, n, k):
seq(seq(a(n,k), k=0..n), n=0..12); # Alois P. Heinz, Apr 26 2013

b[x_, y_, k_] := b[x, y, k] = If[y>x || yJean-François Alcover, Mar 06 2015, after Alois P. Heinz *)

A114299 First row of Modified Schroeder numbers for q=9 (A114295).

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 5, 13, 34, 89, 288, 1029, 3794, 14113, 52624, 210428, 883881, 3805858, 16570925, 72497060, 325602364, 1498899060, 7017126473, 33185818242, 157858754637, 759960988368, 3706528583080, 18273586377144, 90805138443560, 453695642109973

Offset: 0

Christopher Hanusa (chanusa(AT)math.binghamton.edu), Nov 21 2005

nonn

a(i) is the number of paths from (0,0) to (i,i) using steps of length (0,1), (1,0) and (1,1), not passing above the line y=x nor below the line y=4x/5.

			The number of paths from (0,0) to (6,6) staying between the lines y=x and y=4x/5 using steps of length (0,1), (1,0) and (1,1) is a(6)=5.

Alois P. Heinz, Table of n, a(n) for n = 0..500
C. Hanusa, A Gessel-Viennot-Type Method for Cycle Systems with Applications to Aztec Pillows, PhD Thesis, 2005, University of Washington, Seattle, USA.

See also A112833-A112844 and A114292-A114298.

b:= proc(x, y) option remember; `if`(y>x or y<4*x/5, 0,
       `if`(x=0, 1, b(x, y-1)+b(x-1, y)+b(x-1, y-1)))
    end:
a:= n-> b(n, n):
seq(a(n), n=0..35);  # Alois P. Heinz, Apr 25 2013

b[x_, y_] := b[x, y] = If[y > x || y < 4*x/5, 0, If[x == 0, 1, b[x, y-1] + b[x-1, y] + b[x-1, y-1]]]; a[n_] := b[n, n]; Table[a[n], {n, 0, 35}] (* Jean-François Alcover, Dec 19 2015, after Alois P. Heinz *)

A035508 a(n) = Fibonacci(2*n+2) - 1.

Original entry on oeis.org

0, 2, 7, 20, 54, 143, 376, 986, 2583, 6764, 17710, 46367, 121392, 317810, 832039, 2178308, 5702886, 14930351, 39088168, 102334154, 267914295, 701408732, 1836311902, 4807526975, 12586269024, 32951280098, 86267571271, 225851433716

Offset: 0

N. J. A. Sloane

Except for 0, numbers whose dual Zeckendorf representation (A104326) has the same number of 0's as 1's. - Amiram Eldar, Mar 22 2021

Guo-Niu Han, Enumeration of Standard Puzzles, 2011. [Cached copy]
Guo-Niu Han, Enumeration of Standard Puzzles, arXiv:2006.14070 [math.CO], 2020.
Clark Kimberling, Interspersions and Dispersions.
Clark Kimberling, Interspersions and dispersions, Proceedings of the American Mathematical Society, Vol. 117, No. 2 (1993), pp. 313-321.
N. J. A. Sloane, Classic Sequences.
Index entries for linear recurrences with constant coefficients, signature (4,-4,1).

With different offset: 2nd row of Inverse Stolarsky array A035507.

Cf. A001906, A104326, A112844, A152891 (partial sums).

[Fibonacci(2*n+2)-1: n in [0..30]]; // Vincenzo Librandi, Apr 18 2011

g:=z/(1-3*z+z^2): gser:=series(g, z=0, 43): seq(abs(coeff(gser, z, n)-1), n=1..26); # Zerinvary Lajos, Mar 22 2009
with(combinat):seq(fibonacci(4*n+2) mod fibonacci(2*n+2),n=0..25);

Fibonacci[2*Range[0, 5!]] - 1 (* Vladimir Joseph Stephan Orlovsky, May 18 2010 *)
LinearRecurrence[{4,-4,1},{0,2,7},40] (* Harvey P. Dale, Jan 15 2025 *)

makelist(fib(2*n+2)-1,n,0,30); /* Martin Ettl, Oct 21 2012 */

numlib::fibonacci(2*n)-1 $ n = 1..38; // Zerinvary Lajos, May 08 2008

[lucas_number1(n, 3, 1)-1 for n in range(1, 27)] # Zerinvary Lajos, Dec 07 2009

a(n) = A001906(n) - 1.
G.f.: x*(2 - x)/((1 - x)*(1 - 3*x + x^2)). a(n) = 4*a(n-1) - 4*a(n-2) + a(n-3). - R. J. Mathar, Dec 15 2008; adapted to the offset by Bruno Berselli, Apr 19 2011
a(n) = Fibonacci(4*n+2) mod Fibonacci(2*n+2). - Gary Detlefs, Nov 22 2010
a(n+1) = Sum_{k=0..n} Fibonacci(2*k+3). - Gary Detlefs, Dec 24 2010
a(n) = Sum_{i=1..n} A112844(i). - R. J. Mathar, Apr 19 2011
a(n) = floor(Fibonacci(2*n+2) - Fibonacci(n+1)^2/Fibonacci(2*n+2)). - Gary Detlefs, Dec 21 2012
From Peter Bala, Nov 14 2021: (Start)
a(n) = Fibonacci(2*n+4)*(Fibonacci(2*n+1) - 1)/(Fibonacci(2*n+3) - 1).
a(n)= -2 + Sum_{k = 1..2*n+3} (-1)^(k+1)*Fibonacci(k). (End)

cp's OEIS Frontend

A112833 Number of domino tilings of a 3-pillow of order n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A112835 Small-number statistic from the enumeration of domino tilings of a 3-pillow of order n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Formula

A112839 Number of domino tilings of a 7-pillow of order n.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

A112842 Number of domino tilings of a 9-pillow of order n.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

A112841 Small-number statistic from the enumeration of domino tilings of a 7-pillow of order n.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

A112836 Number of domino tilings of a 5-pillow of order n.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

A112838 Small-number statistic from the enumeration of domino tilings of a 5-pillow of order n.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

A114292 Modified Schroeder numbers for q=3.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

A114299 First row of Modified Schroeder numbers for q=9 (A114295).

Views

Author

Keywords