cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-8 of 8 results.

A228285 T(n,k) = Number of n X k binary arrays with top left value 1 and no two ones adjacent horizontally, vertically or nw-se diagonally.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 3, 3, 3, 3, 5, 6, 13, 6, 5, 8, 13, 35, 35, 13, 8, 13, 28, 112, 133, 112, 28, 13, 21, 60, 337, 587, 587, 337, 60, 21, 34, 129, 1034, 2448, 3631, 2448, 1034, 129, 34, 55, 277, 3154, 10414, 21166, 21166, 10414, 3154, 277, 55, 89, 595, 9637, 44024, 126119
Offset: 1

Views

Author

R. H. Hardin, Aug 19 2013

Keywords

Examples

			Table starts
   1   1    2      3       5        8         13          21            34
   1   1    3      6      13       28         60         129           277
   2   3   13     35     112      337       1034        3154          9637
   3   6   35    133     587     2448      10414       44024        186414
   5  13  112    587    3631    21166     126119      745178       4416695
   8  28  337   2448   21166   172082    1428523    11771298      97268701
  13  60 1034  10414  126119  1428523   16566199   190540884    2197847780
  21 129 3154  44024  745178 11771298  190540884  3057290265   49208639399
  34 277 9637 186414 4416695 97268701 2197847780 49208639399 1105411581741
Some solutions for n=4, k=4:
  1 0 0 1   1 0 0 1   1 0 0 0   1 0 1 0   1 0 0 0
  0 0 0 0   0 0 0 0   0 0 0 0   0 0 0 0   0 0 0 0
  0 0 0 1   0 0 0 1   0 0 0 0   0 0 0 0   0 0 0 1
  0 0 1 0   0 1 0 0   0 1 0 1   1 0 1 0   1 0 0 0
		

Crossrefs

Column 1 is A000045.
Column 2 is A002478(n-1).
For columns 3 through 9 see A228278, A228279, A228280, A228281, A228282, A228283, A228284.
For the main diagonal (n X n matrices) see A228277.
If the requirement that the top corner is 1 is omitted we get A226444.
If the "nw-se" condition in the definition is changed to "ne-sw", we get A228476-A228482.
See also A228390 and A228506 for other variants.

Formula

Empirical for column k:
k=1: a(n) = a(n-1) + a(n-2).
k=2: a(n) = a(n-1) + 2*a(n-2) + a(n-3).
k=3: a(n) = a(n-1) + 5*a(n-2) + 4*a(n-3) - a(n-5) with g.f. x(2+x-x^3)/((1+x)(1-2x-3x^2-x^3+x^4)).
k=4: a(n) = a(n-1) +10*a(n-2) +15*a(n-3) +4*a(n-4) -6*a(n-5) -a(n-6) +3*a(n-7) -a(n-8) with g.f. x *(x-1) *(2*x^3 -5*x^2 -6*x -3) / ( 1 -x -10*x^2 -15*x^3 -4*x^4 +6*x^5 +x^6 -3*x^7 +x^8 ).
k=5: [order 13] - see A228280.
k=6: [order 21]
k=7: [order 34]
k=8: [order 55]
k=9: [order 89]
From Doron Zeilberger, Aug 19 2013 and Aug 22 2013: (Start)
Using the C-finite Ansatz one can show that the k-th column satisfies a recurrence of order F_{k+2} for all k. For k <= 11, this is the minimal order. The empirical g.f.'s given above are correct. For further g.f.'s and Maple code, see the links.
In more detail: Every k X n Hardin matrix can be viewed as a walk, of length n, on a graph with F_{k+2} vertices (labeled by the set of {0,1} vectors of length k that avoid two consecutive 1's, which is well known and fairly easy to see has cardinality F_{k+2}).
Then the computer constructs the adjacency matrix.
There is an edge between vertex v1 and vertex v2 only if it is NOT the case that there exists an i (1 <= i <= k) such that v1[i]=1 and v2[i]=1 AND it is not the case that there exists an i (1 <= i <= k-1) such that v1[i]=1 and v2[i+1]=1.
Let us call this matrix A(k).
Then the number of k X n Hardin matrices (without the restriction that the top-left entry is 1, A226444) is the sum of the entries (i,j) of A(k)^n, or equivalently (1,...., 1) A(k)^n (1, ...., 1)^T.
So
f_k(x) = Sum_{n>=0} a(n)*x^n
= (1,...., 1) Sum_{n>=0} A(k)^n*x^n (1, ...., 1)^T
= (1,...., 1) (I-A*x)^(-1)(1, ...., 1)^T
and Maple knows how to invert the symbolic matrix (I-A*x), and this explains why the characteristic polynomial is the symbol for the recurrence.
If we impose that restriction then the answer (A228285) is
[0-1-Vector with 1's for those whose first entry is 1] A(k)^n (1, ...., 1)^T.
(End)

Extensions

Edited by N. J. A. Sloane, Aug 22 2013
Minor corrections and further edits by M. F. Hasler, Apr 28 2014

A066864 Number of binary arrangements without adjacent 1's on n X n rhombic hexagonal grid.

Original entry on oeis.org

1, 2, 6, 42, 524, 13322, 647252, 61758332, 11435477118, 4129523869606, 2902264461628298, 3973109800760143708, 10590895512774862686570, 54979738656662942307796576, 555797909644630436677137498230, 10941698340065066230952215658836402, 419471520990343359533179780148504998680
Offset: 0

Views

Author

R. H. Hardin, Jan 25 2002

Keywords

Comments

Also the number of tilings of an (n+1) X (n+1) square using 1 X 1 squares and L-tiles. An L-tile is a 2 X 2 square with the upper right 1 X 1 subsquare removed and no rotations are allowed. a(2) = 6:
|||_| | ||| |||_| || || |||_| || ||
|||_| |_|_| | ||| ||__| || || | |_|
|||_| |||_| |_|_| |||_| ||__| |_|_| - Alois P. Heinz, Jun 06 2013

Examples

			Neighbors for n=4:
  o--o--o--o
  | /| /| /|
  |/ |/ |/ |
  o--o--o--o
  | /| /| /|
  |/ |/ |/ |
  o--o--o--o
  | /| /| /|
  |/ |/ |/ |
  o--o--o--o
		

References

  • Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 342-349.
  • J. Katzenelson and R. P. Kurshan, S/R: A Language for Specifying Protocols and Other Coordinating Processes, pp. 286-292 in Proc. IEEE Conf. Comput. Comm., 1986.

Crossrefs

Main diagonal of A219741 and A226444.

Programs

  • Maple
    a:= proc(n) option remember; local b; b:=
          proc(n, l) option remember; local k;
            if n<2 then 1
          elif min(l[])>0 then b(n-1, map(h->h-1, l))
          else for k while l[k]>0 do od; b(n, subsop(k=1, l))+
               `if`(n>1 and kAlois P. Heinz, Aug 26 2013
  • Mathematica
    $RecursionLimit = 1000; a[n0_] := a[n0] = Module[{b}, b[n_, l_List] := b[n, l] = Module[{k}, Which[n<2, 1, Min[l]>0, b[n-1, l-1], True, For[k = 1, l[[k]] > 0, k++]; b[n, ReplacePart[l, k -> 1]] + If[n>1 && k 2, k+1 -> 1}]], 0]]];  b[n0+1, Array[0&, n0+1]]]; Table[a[n], {n, 0, 15}] (* Jean-François Alcover, Feb 24 2015, after Alois P. Heinz *)

Formula

Limit_{n->oo} a(n)^(1/n^2) = 1.395485972... (see A085851).

Extensions

a(12)-a(21) from Vaclav Kotesovec, May 01 2012
a(0) and a(22) from Alois P. Heinz, Aug 26 2013
a(23) from Alois P. Heinz, Aug 28 2013
a(24) from Vaclav Kotesovec, Sep 19 2014
a(25) from Alois P. Heinz, Dec 03 2014
a(26)-a(28) from Vaclav Kotesovec, Aug 13 2016

A322494 Number A(n,k) of tilings of a k X n rectangle using V (2m+1)-ominoes (m >= 0) in standard orientation; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 3, 3, 1, 1, 1, 1, 5, 8, 5, 1, 1, 1, 1, 8, 18, 18, 8, 1, 1, 1, 1, 13, 44, 68, 44, 13, 1, 1, 1, 1, 21, 107, 233, 233, 107, 21, 1, 1, 1, 1, 34, 257, 838, 1262, 838, 257, 34, 1, 1, 1, 1, 55, 621, 2989, 6523, 6523, 2989, 621, 55, 1, 1
Offset: 0

Views

Author

Alois P. Heinz, Dec 12 2018

Keywords

Comments

The shapes of the tiles are:
._.
._. | |
._. | | | |
.. | |. | |.. | |.._.
|| |__| |___| |_____| ... .
.
The sequence of column k (or row k) satisfies a linear recurrence with constant coefficients of order 2^(k-1) for k>0.

Examples

			A(3,3) = 8:
  ._____.  ._____.  ._____.  ._____.  ._____.  ._____.  ._____.  ._____.
  |_|_|_|  | |_|_|  |_|_|_|  |_| |_|  |_|_|_|  |_| |_|  | |_|_|  | | |_|
  |_|_|_|  |___|_|  | |_|_|  |_|___|  |_| |_|  | |___|  | |_|_|  | |___|
  |_|_|_|  |_|_|_|  |___|_|  |_|_|_|  |_|___|  |___|_|  |_____|  |_____|.
.
Square array A(n,k) begins:
  1, 1,  1,   1,     1,      1,       1,        1,         1, ...
  1, 1,  1,   1,     1,      1,       1,        1,         1, ...
  1, 1,  2,   3,     5,      8,      13,       21,        34, ...
  1, 1,  3,   8,    18,     44,     107,      257,       621, ...
  1, 1,  5,  18,    68,    233,     838,     2989,     10687, ...
  1, 1,  8,  44,   233,   1262,    6523,    34468,    181615, ...
  1, 1, 13, 107,   838,   6523,   51420,   396500,   3086898, ...
  1, 1, 21, 257,  2989,  34468,  396500,  4577274,  52338705, ...
  1, 1, 34, 621, 10687, 181615, 3086898, 52338705, 888837716, ...
		

Crossrefs

Columns (or rows) k=0+1,2-10 give: A000012, A000045(n+1), A322496, A322497, A322498, A322499, A322500, A322501, A322502, A322503.
Main diagonal gives A322495.
Cf. A226444.

Programs

  • Maple
    b:= proc(n, l) option remember; local k, m, r;
          if n=0 or l=[] then 1
        elif min(l)>0 then (t-> b(n-t, map(h->h-t, l)))(min(l))
        elif l[-1]=n then b(n, subsop(-1=[][], l))
        else for k while l[k]>0 do od; r:= 0;
             for m from 0 while k+m<=nops(l) and l[k+m]=0 and n>m do
               r:= r+b(n, [l[1..k-1][], 1$m, m+1, l[k+m+1..nops(l)][]])
             od; r
          fi
        end:
    A:= (n, k)-> b(max(n, k), [0$min(n, k)]):
    seq(seq(A(n, d-n), n=0..d), d=0..14);
  • Mathematica
    b[n_, l_] := b[n, l] = Module[{k, m, r}, Which[n == 0 || l == {}, 1, Min[l] > 0, Function[t, b[n-t, l-t]][Min[l]], l[[-1]] == n, b[n, ReplacePart[ l, -1 -> Nothing]], True, For[k=1, l[[k]] > 0, k++]; r = 0; For[m=0, k+m <= Length[l] && l[[k+m]] == 0 && n>m, m++, r = r + b[n, Join[l[[1 ;; k-1]], Array[1&, m], {m+1}, l[[k+m+1 ;; Length[l]]]]]]; r]];
    A[n_, k_] := b[Max[n, k], Array[0&, Min[n, k]]];
    Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Dec 18 2018, after Alois P. Heinz *)

A228482 T(n,k)=Number of nXk binary arrays with top left value 1 and no two ones adjacent horizontally, vertically or antidiagonally.

Original entry on oeis.org

1, 1, 1, 2, 2, 2, 3, 4, 4, 3, 5, 9, 14, 9, 5, 8, 19, 41, 41, 19, 8, 13, 41, 127, 172, 127, 41, 13, 21, 88, 386, 728, 728, 386, 88, 21, 34, 189, 1181, 3084, 4354, 3084, 1181, 189, 34, 55, 406, 3605, 13050, 25699, 25699, 13050, 3605, 406, 55, 89, 872, 11013, 55252, 152373
Offset: 1

Views

Author

R. H. Hardin Aug 22 2013

Keywords

Comments

Table starts
..1...1.....2......3.......5.........8.........13..........21............34
..1...2.....4......9......19........41.........88.........189...........406
..2...4....14.....41.....127.......386.......1181........3605.........11013
..3...9....41....172.....728......3084......13050.......55252........233875
..5..19...127....728....4354.....25699.....152373......902042.......5342712
..8..41...386...3084...25699....211588....1748684....14433982.....119188751
.13..88..1181..13050..152373...1748684...20185842...232542935....2680777055
.21.189..3605..55252..902042..14433982..232542935..3737615288...60122232373
.34.406.11013.233875.5342712.119188751.2680777055.60122232373.1349721589622
Same recurrences as A228285 except in addition this smaller one for k=5

Examples

			Some solutions for n=4 k=4
..1..0..0..1....1..0..1..0....1..0..0..1....1..0..1..0....1..0..1..0
..0..0..0..0....0..0..0..1....0..1..0..0....0..0..0..0....0..0..0..0
..0..0..0..1....0..0..0..0....0..0..1..0....0..1..0..0....0..0..0..0
..0..0..0..0....0..1..0..0....0..0..0..1....0..0..1..0....1..0..0..0
		

Crossrefs

Column 1 is A000045
Column 2 is A078039(n-1).

Formula

Recurrences for column k:
k=1: a(n) = a(n-1) +a(n-2)
k=2: a(n) = a(n-1) +2*a(n-2) +a(n-3)
k=3: a(n) = a(n-1) +5*a(n-2) +4*a(n-3) -a(n-5)
k=4: a(n) = a(n-1) +10*a(n-2) +15*a(n-3) +4*a(n-4) -6*a(n-5) -a(n-6) +3*a(n-7) -a(n-8)
k=5: a(n) = 3*a(n-1) +15*a(n-2) +16*a(n-3) -11*a(n-4) -20*a(n-5) +19*a(n-6) -8*a(n-7) +a(n-9)
k=6: a(n) = a(n-1) +42*a(n-2) +147*a(n-3) +70*a(n-4) -478*a(n-5) -449*a(n-6) +1199*a(n-7) +732*a(n-8) -2727*a(n-9) +659*a(n-10) +3827*a(n-11) -5776*a(n-12) +3926*a(n-13) -1152*a(n-14) -148*a(n-15) +154*a(n-16) +32*a(n-17) -29*a(n-18) -6*a(n-19) +3*a(n-20) +a(n-21)
k=7: a(n) = a(n-1) +85*a(n-2) +432*a(n-3) +192*a(n-4) -3711*a(n-5) -5096*a(n-6) +21164*a(n-7) +27340*a(n-8) -112654*a(n-9) -37244*a(n-10) +477721*a(n-11) -464722*a(n-12) -897815*a(n-13) +3102284*a(n-14) -4149918*a(n-15) +2761082*a(n-16) -138325*a(n-17) -1353257*a(n-18) +942033*a(n-19) +64683*a(n-20) -365483*a(n-21) +80904*a(n-22) +92350*a(n-23) -27097*a(n-24) -23292*a(n-25) +2585*a(n-26) +5635*a(n-27) +1405*a(n-28) -561*a(n-29) -545*a(n-30) -173*a(n-31) -14*a(n-32) +5*a(n-33) +a(n-34)

A219741 T(n,k) = Unmatched value maps: number of nXk binary arrays indicating the locations of corresponding elements not equal to any horizontal, vertical or antidiagonal neighbor in a random 0..1 nXk array.

Original entry on oeis.org

1, 2, 2, 4, 6, 4, 7, 13, 13, 7, 12, 28, 42, 28, 12, 21, 60, 126, 126, 60, 21, 37, 129, 387, 524, 387, 129, 37, 65, 277, 1180, 2229, 2229, 1180, 277, 65, 114, 595, 3606, 9425, 13322, 9425, 3606, 595, 114, 200, 1278, 11012, 39905, 78661, 78661, 39905, 11012, 1278, 200
Offset: 1

Views

Author

R. H. Hardin, Nov 26 2012

Keywords

Comments

Table starts
...1.....2......4........7.........12...........21.............37
...2.....6.....13.......28.........60..........129............277
...4....13.....42......126........387.........1180...........3606
...7....28....126......524.......2229.........9425..........39905
..12....60....387.....2229......13322........78661.........466288
..21...129...1180.....9425......78661.......647252........5350080
..37...277...3606....39905.....466288......5350080.......61758332
..65...595..11012...168925....2760690.....44159095......711479843
.114..1278..33636...715072...16350693....364647622.....8201909757
.200..2745.102733..3027049...96830726...3010723330....94531063074
.351..5896.313781.12813931..573456240..24858935864..1089590912023
.616.12664.958384.54243509.3396136349.205253857220.12558669019786

Examples

			Some solutions for n=3 k=4
..0..0..0..0....1..0..0..1....0..0..1..0....0..0..1..0....0..0..0..1
..0..1..0..0....0..0..0..0....1..0..0..0....0..0..0..0....0..1..0..0
..0..0..0..0....0..1..0..1....0..0..0..1....1..0..0..1....0..0..0..0
		

Crossrefs

Column 1 is A005251(n+2).
Column 2 is A002478(n+1).
Column 3 is A105262(n+1) for n>1.
Main diagonal is A066864.
See A226444 for an array with very similar entries. - N. J. A. Sloane, Aug 22 2013

Formula

Zeilberger's Maple code (see links in A228285) would presumably give recurrences for the columns of this array. - N. J. A. Sloane, Aug 22 2013

A243608 Number T(n,k) of ways k L-tiles can be placed on an n X n square; triangle T(n,k), n>=0, 0<=k<=A229093(n), read by rows.

Original entry on oeis.org

1, 1, 1, 1, 1, 4, 1, 1, 9, 20, 11, 1, 1, 16, 87, 196, 176, 46, 2, 1, 25, 244, 1195, 3145, 4431, 3161, 1007, 111, 2, 1, 36, 545, 4544, 22969, 73098, 147502, 185744, 140288, 59140, 12313, 1046, 26, 1, 49, 1056, 13215, 106819, 587149, 2251309, 6082000, 11562155
Offset: 0

Views

Author

Alois P. Heinz, Jun 07 2014

Keywords

Comments

An L-tile is a 2 X 2 square with the upper right 1 X 1 subsquare removed and no rotations are allowed.

Examples

			T(3,1) = 4:
  ._____.   ._____.   ._____.   ._____.
  | |_|_|   |_|_|_|   |_| |_|   |_|_|_|
  |___|_|   | |_|_|   |_|___|   |_| |_|
  |_|_|_|   |___|_|   |_|_|_|   |_|___|
T(4,4) = 1:
  ._______.
  | |_| |_|
  |___|___|
  | |_| |_|
  |___|___|
T(5,6) = 2:
  ._________.   ._________.
  | |_|_| |_|   |_| |_| |_|
  |___| |___|   | |___|___|
  |_| |___|_|   |___|_| |_|
  | |___| |_|   | |_| |___|
  |___|_|___|   |___|___|_| .
Triangle T(n,k) begins:
  1;
  1;
  1,  1;
  1,  4,   1;
  1,  9,  20,   11,    1;
  1, 16,  87,  196,  176,   46,    2;
  1, 25, 244, 1195, 3145, 4431, 3161, 1007, 111, 2;
		

Crossrefs

Columns k=0-6 give: A000012, A000290(n-1) for n>0, A243645, A243646, A243647, A243648, A243649.
Row sums give main diagonal of A226444 or A066864(n-1) for n>0.

Programs

  • Maple
    b:= proc(n, l) option remember; local k;
          if n<2 then 1
        elif min(l[])>0 then b(n-1, map(h->h-1, l))
        else for k while l[k]>0 do od; expand(
             b(n, subsop(k=1, l))+ `if`(n>1 and k (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, [0$n])):
    seq(T(n), n=0..10);
  • Mathematica
    b[n_, l_] := b[n, l] = Module[{k}, Which[n<2, 1, Min[l]>0, b[n-1, l-1], True, For[k = 1, l[[k]] > 0, k++]; Expand[b[n, ReplacePart[l, k -> 1]] + If[n>1 && k 2, k+1 -> 1}]], 0]]]];
    T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][ b[n, Table[0, {n}]]];
    Table[T[n], {n, 0, 10}] // Flatten (* Jean-François Alcover, Apr 12 2017, translated from Maple *)

A226543 Number of tilings of a 9 X n rectangle using 1 X 1 squares and L-tiles.

Original entry on oeis.org

1, 1, 55, 595, 11012, 168925, 2760690, 44159095, 711479843, 11435477118, 183947396032, 2958142131138, 47575298963072, 765124447990418, 12305134306097753, 197897152964385186, 3182680323964197938, 51185438892782012288, 823189555932846017125
Offset: 0

Views

Author

Alois P. Heinz, Jun 10 2013

Keywords

Comments

An L-tile is a 2 X 2 square with the upper right 1 X 1 subsquare removed and no rotations are allowed.

Crossrefs

Column k=9 of A226444.

A226544 Number of tilings of a 10 X n rectangle using 1 X 1 squares and L-tiles.

Original entry on oeis.org

1, 1, 89, 1278, 33636, 715072, 16350693, 364647622, 8201909757, 183947396032, 4129523869606, 92675094208964, 2080048909984067, 46684042670495080, 1047776070980376086, 23516183336037445861, 527795545850035568780, 11845801476106616135344
Offset: 0

Views

Author

Alois P. Heinz, Jun 10 2013

Keywords

Comments

An L-tile is a 2 X 2 square with the upper right 1 X 1 subsquare removed and no rotations are allowed.

Crossrefs

Column k=10 of A226444.
Showing 1-8 of 8 results.