

A188553


T(n,k) = Number of n X k binary arrays without the pattern 0 1 diagonally, vertically, antidiagonally or horizontally.


8



2, 3, 3, 4, 5, 4, 5, 8, 7, 5, 6, 12, 12, 9, 6, 7, 17, 20, 16, 11, 7, 8, 23, 32, 28, 20, 13, 8, 9, 30, 49, 48, 36, 24, 15, 9, 10, 38, 72, 80, 64, 44, 28, 17, 10, 11, 47, 102, 129, 112, 80, 52, 32, 19, 11, 12, 57, 140, 201, 192, 144, 96, 60, 36, 21, 12, 13, 68, 187, 303, 321, 256, 176
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

Also, T(n,k) is the number of words of length k, x(1)x(2)...x(k), on the alphabet {0,1,...,n}, such that, for i=2,...,k, x(i)=either x(i1) or x(i)=x(i1)1.
For the bijection between arrays and sequences, notice that the ith column consists of 1's and then 0's, and there are x(i)=0 to n of 1's.
(End)


LINKS



FORMULA

Empirical: T(n,k) = (n+1)*2^(k1) + (1k)*2^(k2) for k < n+3, and then the entire row n is a polynomial of degree n in k.
The above empirical formula is correct.
It can be proved that T(n,k) satisfies the recurrence
T(n,k) = Sum_{r=1..n+1} (1)^(r+1)*binomial(n+1,r)*T(n,kr)
with initial values
T(n,k) = Sum_{r=0..k1} (n+1r)*binomial(k1,r) for k = 1..n+1. (End)


EXAMPLE

Table starts
..2..3..4..5...6...7...8...9...10...11...12....13....14....15....16.....17
..3..5..8.12..17..23..30..38...47...57...68....80....93...107...122....138
..4..7.12.20..32..49..72.102..140..187..244...312...392...485...592....714
..5..9.16.28..48..80.129.201..303..443..630...874..1186..1578..2063...2655
..6.11.20.36..64.112.192.321..522..825.1268..1898..2772..3958..5536...7599
..7.13.24.44..80.144.256.448..769.1291.2116..3384..5282..8054.12012..17548
..8.15.28.52..96.176.320.576.1024.1793.3084..5200..8584.13866.21920..33932
..9.17.32.60.112.208.384.704.1280.2304.4097..7181.12381.20965.34831..56751
.10.19.36.68.128.240.448.832.1536.2816.5120..9217.16398.28779.49744..84575
.11.21.40.76.144.272.512.960.1792.3328.6144.11264.20481.36879.65658.115402
Some solutions for 5 X 3:
1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 1 1 0 1 1 1
1 1 1 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 1 1 1
1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0
Some solutions for T(5,3): By taking the sums of the columns in the above arrays we get 555, 100, 000, 543, 322, 432, 554.  Miquel A. Fiol, Feb 04 2024


MAPLE

T:= (n, k)> `if`(k<=n+1, (2*n+3k)*2^(k2), (n+1k)*binomial(k1, n) * add(binomial(n, j1)/(kj)*T(n, j)*(1)^(nj), j=1..n+1)): seq(seq(T(n, 1+dn), n=1..d), d=1..15); #Alois P. Heinz in the Sequence Fans Mailing List, Apr 04 2011 [We do not permit programs based on conjectures, but this program is now justified by Fiol's comment.  N. J. A. Sloane, Mar 09 2024]


CROSSREFS

Antidiagonal sums give A065220(n+5).


KEYWORD



AUTHOR



STATUS

approved



