A003692 -id:A003692 - cp's OEIS frontend

A005178 Number of domino tilings of 4 X (n-1) board.

0, 1, 1, 5, 11, 36, 95, 281, 781, 2245, 6336, 18061, 51205, 145601, 413351, 1174500, 3335651, 9475901, 26915305, 76455961, 217172736, 616891945, 1752296281, 4977472781, 14138673395, 40161441636, 114079985111, 324048393905

Offset: 0

N. J. A. Sloane, David Singmaster, Frans J. Faase

Or, number of perfect matchings in graph P_4 X P_{n-1}.
a(0) = 0, a(1) = 1 by convention.
It is easy to see that the g.f. for indecomposable tilings, i.e., those that cannot be split vertically into smaller tilings, is g = x + 4x^2 + 2x^3 + 3x^4 + 2x^5 + 3x^6 + 2x^7 + 3x^8 + ... = x + 4x^2 + x^3*(2+3x)/(1-x^2); then g.f. = 1/(1-g) = (1-x^2)/(1-x-5x^2-x^3+x^4). - Emeric Deutsch, Oct 16 2006
This is a divisibility sequence; that is, if n divides m, then a(n) divides a(m). - T. D. Noe, Dec 22 2008
From Artur Jasinski, Dec 20 2008: (Start)
All numbers in this sequence are:
congruent to 0 mod 100 if n is congruent to 14 or 29 mod 30
congruent to 1 mod 100 if n is congruent to 0 or 1 or 12 or 16 or 27 or 28 mod 30
congruent to 5 mod 100 if n is congruent to 2 or 11 or 17 or 26 mod 30
congruent to 11 mod 100 if n is congruent to 3 or 25 mod 30
congruent to 36 mod 100 if n is congruent to 4 or 9 or 19 or 24 mod 30
congruent to 45 mod 100 if n is congruent to 8 or 20 mod 30
congruent to 51 mod 100 if n is congruent to 13 or 15 mod 30
congruent to 61 mod 100 if n is congruent to 10 or 18 mod 30
congruent to 81 mod 100 if n is congruent to 6 or 7 or 21 or 22 mod 30
congruent to 95 mod 100 if n is congruent to 5 or 23 mod 30
(End)
This is the case P1 = 1, P2 = -7, Q = 1 of the 3 parameter family of 4th-order linear divisibility sequences found by Williams and Guy. - Peter Bala, Mar 31 2014

			For n=2 the graph is
  o-o-o-o
and there is one perfect tiling:
  o-o o-o
For n=3 the graph is
  o-o-o-o
  | | | |
  o-o-o-o
and there are five perfect tilings:
  o o o o
  | | | |
  o o o o
two like:
  o o o-o
  | | ...
  o o o-o
and this
  o-o o-o
  .......
  o-o o-o
and this
  o o-o o
  | ... |
  o o-o o
a(n+1)=r(n)-r(n-2), r(n)=if n=0 then 1 else sum(sum(binomial(k,j)*sum(binomial(j,i-j)*5^(i-j)*binomial(k-j,n-i-3*(k-j))*(-1)^(n-i-3*(k-j)),i,j,n-k+j),j,0,k),k,1,n), n>1. - _Vladimir Kruchinin_, Sep 08 2010

F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P. Stanley, Enumerative Combinatorics I, p. 292.

T. D. Noe, Table of n, a(n) for n = 0..200
Steve Butler, Jason Ekstrand, and Steven Osborne, Counting Tilings by Taking Walks in a Graph, A Project-Based Guide to Undergraduate Research in Mathematics, Birkhäuser, Cham (2020), see page 158.
Curtis Cooper and Robert E. Kennedy, Problem B-735: Soln 1, Problem B-735: Soln 2, Square Root of a Recurrence, The Fibonacci Quarterly, 32(2):185-186, May 1994, and 32(4):374-375, Aug 1994.
F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129-154.
F. Faase, Counting Hamiltonian cycles in product graphs
F. Faase, Results from the counting program
Vladimir Victorovich Kruchinin, Composition of ordinary generating functions, arXiv:1009.2565 [math.CO], 2010.
R. J. Mathar, Paving Rectangular Regions with Rectangular Tiles: Tatami and Non-Tatami Tilings, arXiv:1311.6135 [math.CO], 2013, Table 3.
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
Simone Rinaldi and D. G. Rogers, Indecomposability: polyominoes and polyomino tilings, The Mathematical Gazette 92.524 (2008): 193-204.
David Singmaster, Letter to N. J. A. Sloane, Oct 3 1982.
Thotsaporn "Aek" Thanatipanonda, Statistics of Domino Tilings on a Rectangular Board, Fibonacci Quart. 57 (2019), no. 5, 145-153. See p. 151.
Herman Tulleken, Polyominoes 2.2: How they fit together, (2019).
H. C. Williams and R. K. Guy, Some fourth-order linear divisibility sequences, Intl. J. Number Theory 7 (5) (2011) 1255-1277
H. C. Williams and R. K. Guy, Some Monoapparitic Fourth Order Linear Divisibility Sequences Integers, Volume 12A (2012) The John Selfridge Memorial Volume.
Li Zhou, Northwestern University Math Problem Solving Group, Christopher Carl Heckman and Jerry Minkus, Tiling 4-Rowed Rectangles with Dominoes: 11187, The American Mathematical Monthly 114 (2007): 554-556.
Index to divisibility sequences
Index entries for sequences related to dominoes
Index entries for linear recurrences with constant coefficients, signature (1,5,1,-1).

Row 4 of array A099390.
For all matchings see A033507.
Cf. A003775, A028468, A028469, A028470.
Cf. A003757. - T. D. Noe, Dec 22 2008
Bisection (odd part) gives A188899. - Alois P. Heinz, Oct 28 2012
Column k=2 of A250662.

a[0]:=1: a[1]:=1: a[2]:=5: a[3]:=11: for n from 4 to 26 do a[n]:=a[n-1]+5*a[n-2]+a[n-3]-a[n-4] od: seq(a[n],n=0..26); # Emeric Deutsch, Oct 16 2006
A005178:=-(-1-4*z-z**2+z**3)/(1-z-5*z**2-z**3+z**4) # conjectured (correctly) by Simon Plouffe in his 1992 dissertation; gives sequence apart from an initial 1

CoefficientList[Series[x(1-x^2)/(1-x-5x^2-x^3+x^4), {x,0,30}], x] (* T. D. Noe, Dec 22 2008 *)
LinearRecurrence[{1, 5, 1, -1}, {0, 1, 1, 5}, 28] (* Robert G. Wilson v, Aug 08 2011 *)
a[0] = 0; a[n_] := Product[2(2+Cos[2j Pi/5]+Cos[2k Pi/n]), {k, 1, (n-1)/2}, {j, 1, 2}] // Round;
Table[a[n], {n, 0, 27}] (* Jean-François Alcover, Aug 20 2018 *)

r(n):=if n=0 then 1 else sum(sum(binomial(k,j)*sum(binomial(j,i-j)*5^(i-j)*binomial(k-j,n-i-3*(k-j))*(-1)^(n-i-3*(k-j)),i,j,n-k+j),j,0,k),k,1,n); a(n):=r(n)-r(n-2); /* Vladimir Kruchinin, Sep 08 2010 */

a(n) = a(n-1) + 5*a(n-2) + a(n-3) - a(n-4).
G.f.: x*(1 - x^2)/(1 - x - 5*x^2 - x^3 + x^4).
Limit_{n->oo} a(n)/a(n-1) = (1 + sqrt(29) + sqrt(14 + 2*sqrt(29)))/4 = 2.84053619409... - Philippe Deléham, Jun 12 2005
a(n) = (5*sqrt(29)/145)*(((1+sqrt(29)+sqrt(14+2*sqrt(29)))/4)^n+((1+sqrt(29)-sqrt(14+2*sqrt(29)))/4)^n-((1-sqrt(29)+sqrt(14-2*sqrt(29)))/4)^n-((1-sqrt(29)-sqrt(14-2*sqrt(29)))/4)^n). - Tim Monahan, Jul 30 2011
From Peter Bala, Mar 31 2014: (Start)
a(n) = ( T(n,alpha) - T(n,beta) )/(alpha - beta), where alpha = (1 + sqrt(29))/4 and beta = (1 - sqrt(29))/4 and T(n,x) denotes the Chebyshev polynomial of the first kind.
a(n) = the bottom left entry of the 2 X 2 matrix T(n, M), where M is the 2 X 2 matrix [0, 7/4; 1, 1/2].
a(n) = U(n-1,i*(1 + sqrt(5))/4)*U(n-1,i*(1 - sqrt(5))/4), where U(n,x) denotes the Chebyshev polynomial of the second kind.
See the remarks in A100047 for the general connection between Chebyshev polynomials and 4th-order linear divisibility sequences. (End)
a(n) = A129113(n+2) - A129113(n). - R. J. Mathar, May 03 2021

Amalgamated with (former) A003692, Dec 30 1995
Name changed and 0 prepended by T. D. Noe, Dec 22 2008
Edited by N. J. A. Sloane, Nov 15 2009

A089975 Array read by ascending antidiagonals: T(n,k) is the number of n-letter words from a k-letter alphabet such that no letter appears more than twice.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 0, 4, 3, 1, 0, 0, 6, 9, 4, 1, 0, 0, 6, 24, 16, 5, 1, 0, 0, 0, 54, 60, 25, 6, 1, 0, 0, 0, 90, 204, 120, 36, 7, 1, 0, 0, 0, 90, 600, 540, 210, 49, 8, 1, 0, 0, 0, 0, 1440, 2220, 1170, 336, 64, 9, 1, 0, 0, 0, 0, 2520, 8100, 6120, 2226, 504, 81, 10, 1

Offset: 0

Paul Boddington, Nov 17 2003

			Array begins:
  1, 1, 1,  1,    1,     1,      1,      1,       1,       1,       1, ...
  0, 1, 2,  3,    4,     5,      6,      7,       8,       9,      10, ...
  0, 1, 4,  9,   16,    25,     36,     49,      64,      81,     100, ...
  0, 0, 6, 24,   60,   120,    210,    336,     504,     720,     990, ...
  0, 0, 6, 54,  204,   540,   1170,   2226,    3864,    6264,    9630, ...
  0, 0, 0, 90,  600,  2220,   6120,  14070,   28560,   52920,   91440, ...
  0, 0, 0, 90, 1440,  8100,  29520,  83790,  201600,  430920,  842400, ...
  0, 0, 0,  0, 2520, 25200, 128520, 463680, 1345680, 3356640, 7484400, ...
  ... - _Robert FERREOL_, Nov 03 2017

Dennis Walsh, Width-Restricted Finite Functions

T(1, k) = A001477(k); T(2, k) = A000290(k); T(3, k) = A007531(k); T(n, n) = A012244(n); T(n, n+1) = A036774(n); T(n, n+2) = A003692(n+1); T(2*n, n) = A000680(n); sum(T(n, k), n=0..2*k) = A003011(k); sum(T(r, n-r), r=0..n) = A089976(n).

See A141765 for an irregular triangle version : T(n,k)=A141765(k,n) for n <= 2k.

T:=(n,k)->add(n!*k!/(n-2*i)!/i!/(k-n+i)!/2^i,i=max(0,n-k)..n/2):
or
T:=proc(n,k) option remember :if n=0 then 1 elif n=1 then k elif k=0 then 0 else T(n, k-1)+n*T(n-1, k-1)+binomial(n,2)*T(n-2, k-1) fi end:
or
T:=(n,k)-> n!*coeff((1 + x + x^2/2)^k, x,n):
seq(seq(T(n-k,k),k=0..n),n=0..20);
# Robert FERREOL, Nov 07 2017

T[n_, k_] := Sum[n!*k!/(2^i*(n - 2 i)!*(k - n + i)!*i!), {i, Max[0, n - k], Floor[n/2]}];
Table[T[n-k , k], {n, 0, 11}, {k, 0, n}] // Flatten (* Jean-François Alcover, Dec 05 2017, after Robert FERREOL *)

from math import factorial as f
def T(n,k):
    return sum(f(n)*f(k)//f(n-2*i)//f(i)//f(k-n+i)//2**i for i in range(max(0,n-k),n//2+1))
[T(n-k,k) for n in range(21) for k in range(n+1)]
# Robert FERREOL, Oct 17 2017

T(n, k) = T(n, k-1) + n*T(n-1, k-1) + binomial(n, 2)*T(n-2, k-1) for n >= 2 and k >= 1.
T(n, k) = Sum_{i=max(0,n-k)..floor(n/2)} n!*k!/(2^i*(n-2*i)!*(k-n+i)!*i!). - Robert FERREOL, Oct 30 2017
T(n,k) = (-1)^n*n!*2^(-n/2)*GegenbauerC(n, -k, 1/sqrt(2)) for k >= n. - Robert Israel, Nov 08 2017
G.f.: Sum({n>=0} T(n,k)x^n)=n!(1 + x + x^2/2)^k. See Walsh link. - Robert FERREOL, Nov 14 2017

A141765 Triangle T, read by rows, such that row n equals column 0 of matrix power M^n where M is a triangular matrix defined by M(k+m,k) = binomial(k+m,k) for m=0..2 and zeros elsewhere. Width-2-restricted finite functions.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 4, 6, 6, 1, 3, 9, 24, 54, 90, 90, 1, 4, 16, 60, 204, 600, 1440, 2520, 2520, 1, 5, 25, 120, 540, 2220, 8100, 25200, 63000, 113400, 113400, 1, 6, 36, 210, 1170, 6120, 29520, 128520, 491400, 1587600, 4082400, 7484400, 7484400, 1, 7, 49, 336, 2226

Offset: 0

Paul D. Hanna, Jul 28 2008

T(k,n) is the number of distinct ways in which n labeled objects can be distributed in k labeled urns allowing at most 2 objects to fall in each urn. - N-E. Fahssi, Apr 22 2009

T(k,n) is the number of functions f:[n]->[k] such that the preimage set under f of any element of [k] has size 2 or less. - Dennis P. Walsh, Feb 15 2011

			This triangle T begins:
1;
1, 1, 1;
1, 2, 4, 6, 6;
1, 3, 9, 24, 54, 90, 90;
1, 4, 16, 60, 204, 600, 1440, 2520, 2520;
1, 5, 25, 120, 540, 2220, 8100, 25200, 63000, 113400, 113400;
1, 6, 36, 210, 1170, 6120, 29520, 128520, 491400, 1587600, 4082400, 7484400, 7484400;
1, 7, 49, 336, 2226, 14070, 83790, 463680, 2346120, 10636920, 42071400, 139708800, 366735600, 681080400, 681080400,
1, 8, 64, 504, 3864, 28560, 201600, 1345680, 8401680, 48444480, 254016000, 1187524800, 4819953600, 16345929600, 43589145600, 81729648000, 81729648000,
1, 9, 81, 720, 6264, 52920, 430920, 3356640, 24811920, 172504080, 1116536400, 6646147200, 35835307200, 171632260800, 711047937600, 2451889440000, 6620101488000, 12504636144000, 12504636144000,
...
Rows 6 and 8 appear in Park (2015). - _N. J. A. Sloane_, Jan 31 2016
Let M be the triangular matrix that begins:
  1;
  1,  1;
  1,  2,  1;
  0,  3,  3,  1;
  0,  0,  6,  4,  1;
  0,  0,  0, 10,  5,  1; ...
where M(k+m,k) = C(k+m,k) for m=0,1,2 and zeros elsewhere.
Illustrate that row n of T = column 0 of M^n for n >= 0 as follows.
The matrix square M^2 begins:
   1;
   2,  1;
   4,  4,  1;
   6, 12,  6,  1;
   6, 24, 24,  8,  1;
   0, 30, 60, 40, 10,  1; ...
with column 0 of M^2 forming row 2 of T.
The matrix cube M^3 begins:
   1;
   3,   1;
   9,   6,   1;
  24,  27,   9,   1;
  54,  96,  54,  12,   1;
  90, 270, 240,  90,  15,   1;
  90, 540, 810, 480, 135,  18,   1; ...
with column 0 of M^3 forming row 3 of T.
T(2,3)=6 because there are 6 ways to lodge 3 distinguishable balls, labeled by numbers 1,2 and 3, in 2 distinguishable boxes, each of which can hold at most 2 balls. - _N-E. Fahssi_, Apr 22 2009
T(5,8)=63000 because there are 63000 ways to assign 8 students to a dorm room when there are 5 different two-bed dorm rooms that are available. (See link for details of the count.) - _Dennis P. Walsh_, Feb 15 2011

Dennis Walsh, Width-restricted finite functions
Donghwi Park, Space-state complexity of Korean chess and Chinese chess, arXiv preprint arXiv:1507.06401, 2015

Cf. A003011 (row sums), A000680 (right border); diagonals: A012244, A036774, A003692.

seq(seq(n!*sum(binomial(k,j)*binomial(j,n-j)*2^(j-n),j=ceil(n/2)..k),n=0..2*k),k=1..10); # Dennis P. Walsh, Feb 15 2011

T[k_, n_] := If[n == 0, 1, n! Coefficient[(1 + x + x^2/2)^k, x^n]]; TableForm[Table[T[k, n], {k, 0, 10}, {n, 0, 2 k}]] (* N-E. Fahssi, Apr 22 2009 *)

{T(n,k)=local(M=matrix(n+1,n+1,n,k,if(n>=k,if(n-k<=2,binomial(n-1,k-1))))); if(k>2*n,0,(M^n)[k+1,1])}

T(k,n) = n!*Sum_{i=ceiling(n/2)..k} binomial(k,i)*binomial(i,n-i)*2^(i-n). - Dennis P. Walsh, Feb 15 2011
T(n,2*n) = (2n)!/2^n; thus the rightmost border of T equals A000680.
Main diagonal (central terms) equals A012244.
Other diagonals include A036774 and A003692.
Row sums of triangle T equals A003011, the number of permutations of up to n kinds of objects, where each kind of object can occur at most two times.
T(k,n) = n![x^n](1+x+x^2/2)^k. Double e.g.f.: Sum_{k,n} T(k,n)*(z^k/k!)*(x^n/n!) = exp(z(1+x+x^2/2)). - N-E. Fahssi, Apr 22 2009
T(j+k,n) = Sum_{i=0..n} binomial(n,i)*T(j,i)*T(k,n-i). - Dennis P. Walsh, Feb 15 2011

cp's OEIS Frontend

A005178 Number of domino tilings of 4 X (n-1) board.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

Formula

Extensions

A089975 Array read by ascending antidiagonals: T(n,k) is the number of n-letter words from a k-letter alphabet such that no letter appears more than twice.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A141765 Triangle T, read by rows, such that row n equals column 0 of matrix power M^n where M is a triangular matrix defined by M(k+m,k) = binomial(k+m,k) for m=0..2 and zeros elsewhere. Width-2-restricted finite functions.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula