cp's OEIS Frontend

A089934 Table T(n,k) of the number of n X k matrices on {0,1} without adjacent 0's in any row or column.

%I A089934 #37 Jul 18 2025 09:33:41
%S A089934 2,3,3,5,7,5,8,17,17,8,13,41,63,41,13,21,99,227,227,99,21,34,239,827,
%T A089934 1234,827,239,34,55,577,2999,6743,6743,2999,577,55,89,1393,10897,
%U A089934 36787,55447,36787,10897,1393,89,144,3363,39561,200798,454385,454385,200798
%N A089934 Table T(n,k) of the number of n X k matrices on {0,1} without adjacent 0's in any row or column.
%C A089934 Recurrence orders are A089935. n X 1/1 X n patterns interpreted as binary values is A003714.
%C A089934 Number of independent vertex sets in the P_n X P_k grid graph. - _Andrew Howroyd_, Jun 06 2017
%C A089934 All columns (or rows) are linear recurrences with constant coefficients and order of the recurrence <= A001224(k+1). - _Andrew Howroyd_, Dec 24 2019
%C A089934 The enumeration of tiling "W-shaped" polyominoes in a (n+1) X (k+1) rectangle, whose shapes are (no flipping or rotating allowed):
%C A089934    ._. ._._.   ._._.     ._._.
%C A089934    |_| |_|_| ._|_|_|   ._|_|_|
%C A089934        |_|   |_|_|   ._|_|_|
%C A089934              |_|     |_|_|
%C A089934                      |_|       ... - _Liang Kai_, Apr 19 2025
%H A089934 Liang Kai, <a href="/A089934/b089934.txt">Antidiagonals n = 1..77, flattened</a> (antidiagonals n = 1..49 from Alois P. Heinz)
%H A089934 Kai Liang, <a href="https://arxiv.org/abs/2507.04007">Independent Set Enumeration and Estimation of Related Constants of Grid Graphs</a>, arXiv:2507.04007 [math.CO], 2025. See p. 4.
%H A089934 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/GridGraph.html">Grid Graph</a>
%H A089934 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/IndependentVertexSet.html">Independent Vertex Set</a>
%e A089934 Table starts:
%e A089934   ========================================================
%e A089934   n\k|  1   2     3      4       5        6          7
%e A089934   ---|----------------------------------------------------
%e A089934   1  |  2   3     5      8      13       21         34 ...
%e A089934   2  |  3   7    17     41      99      239        577 ...
%e A089934   3  |  5  17    63    227     827     2999      10897 ...
%e A089934   4  |  8  41   227   1234    6743    36787     200798 ...
%e A089934   5  | 13  99   827   6743   55447   454385    3729091 ...
%e A089934   6  | 21 239  2999  36787  454385  5598861   69050253 ...
%e A089934   7  | 34 577 10897 200798 3729091 69050253 1280128950 ...
%e A089934   ... - _Andrew Howroyd_, Jun 06 2017
%e A089934 a(2,2)=7:
%e A089934   11 11 11 10 10 01 01
%e A089934   11 10 01 11 01 11 10
%o A089934 (PARI)
%o A089934 step(v, S)={vector(#v, i, sum(j=1, #v, v[j]*!bitand(S[i], S[j])))}
%o A089934 mkS(k)={select(b->!bitand(b,b>>1), [0..2^k-1])}
%o A089934 T(n,k)={my(S=mkS(k), v=vector(#S, i, i==1)); for(n=1, n, v=step(v,S)); vecsum(v)} \\ _Andrew Howroyd_, Dec 24 2019
%Y A089934 T(n, 0) = T(0, m) = 1. Zero based table is A089980.
%Y A089934 Rows 1-7 are A000045, A001333, A051736, A051737, A089936, A089937, A089938.
%Y A089934 Main diagonal is A006506.
%Y A089934 Cf. A089935, A001224, A197054 (maximal independent sets), A218354, A003714.
%K A089934 nonn,tabl
%O A089934 1,1
%A A089934 _Marc LeBrun_, Nov 15 2003