[seqfan] Guess the Recurrence, k-minimums of an array

[Ron Hardin]

Consider a 0..m random array of n+k-1 elements.  Form an n-element array by 
taking the minimum of k consecutive elements from the first array.  How many 
such n-element arrays are there?  T(n,k,m)

Preliminary answers from quick surveys of m=1,2,3, with recurrences for columns 
k=2..7

Is there a pattern for m=2,3 that parellels m=1?

m=1
T(n,k)=Number of n element 0..1 arrays with each element the minimum of k 
adjacent elements of a random 0..1 array of n+k-1 elements
Table starts
....2....2...2...2..2..2..2..2..2..2..2.2.2.2
....4....4...4...4..4..4..4..4..4..4..4.4.4..
....8....7...7...7..7..7..7..7..7..7..7.7....
...16...12..11..11.11.11.11.11.11.11.11......
...32...21..17..16.16.16.16.16.16.16.........
...64...37..27..23.22.22.22.22.22............
..128...65..44..34.30.29.29.29...............
..256..114..72..52.42.38.37..................
..512..200.117..81.61.51.....................
.1024..351.189.126.91........................
.2048..616.305.194...........................
.4096.1081.493...............................
Empirical: a(n)=2*a(n-1)-a(n-2)+a(n-3)
Empirical: a(n)=2*a(n-1)-a(n-2)+a(n-4)
Empirical: a(n)=2*a(n-1)-a(n-2)+a(n-5)
Empirical: a(n)=2*a(n-1)-a(n-2)+a(n-6)
Empirical: a(n)=2*a(n-1)-a(n-2)+a(n-7)
[note column 1 could then be written in the same pattern 
a(n)=2*a(n-1)-a(n-2)+a(n-2)]

m=2
T(n,k)=Number of n element 0..2 arrays with each element the minimum of k 
adjacent elements of a random 0..2 array of n+k-1 elements
Table starts
......3.....3.....3....3....3...3...3...3...3..3..3..3.3.3
......9.....9.....9....9....9...9...9...9...9..9..9..9.9..
.....27....22....22...22...22..22..22..22..22.22.22.22....
.....81....51....46...46...46..46..46..46..46.46.46.......
....243...121....91...86...86..86..86..86..86.86..........
....729...292...183..153..148.148.148.148.148.............
...2187...704...383..274..244.239.239.239.................
...6561..1691...819..511..402.372.367.....................
..19683..4059..1749..993..685.576.........................
..59049..9749..3699.1966.1223.............................
.177147.23422..7772.3880..................................
.531441.56268.16316.......................................
Empirical: a(n)=3*a(n-1)-3*a(n-2)+4*a(n-3)-a(n-4)+a(n-5)
Empirical: a(n)=3*a(n-1)-3*a(n-2)+a(n-3)+3*a(n-4)-a(n-5)+a(n-6)+a(n-7)
Empirical: a(n)=3*a(n-1)-3*a(n-2)+a(n-3)+3*a(n-5)-a(n-6)+a(n-7)+a(n-8)+a(n-9)
Empirical: 
a(n)=3*a(n-1)-3*a(n-2)+a(n-3)+3*a(n-6)-a(n-7)+a(n-8)+a(n-9)+a(n-10)+a(n-11)
Empirical: 
a(n)=3*a(n-1)-3*a(n-2)+a(n-3)+3*a(n-7)-a(n-8)+a(n-9)+a(n-10)+a(n-11)+a(n-12)+a(n-13)

Empirical: 
a(n)=3*a(n-1)-3*a(n-2)+a(n-3)+3*a(n-8)-a(n-9)+a(n-10)+a(n-11)+a(n-12)+a(n-13)+a(n-14)+a(n-15)


m=3
T(n,k)=Number of n element 0..3 arrays with each element the minimum of k 
adjacent elements of a random 0..3 array of n+k-1 elements
Table starts
........4......4......4.....4....4....4....4....4...4...4...4..4..4.4
.......16.....16.....16....16...16...16...16...16..16..16..16.16.16..
.......64.....50.....50....50...50...50...50...50..50..50..50.50.....
......256....144....130...130..130..130..130..130.130.130.130........
.....1024....422....310...296..296..296..296..296.296.296............
.....4096...1268....736...624..610..610..610..610.610................
....16384...3823...1821..1289.1177.1163.1163.1163....................
....65536..11472...4673..2741.2209.2097.2083.........................
...262144..34350..12107..6134.4202.3670..............................
..1048576.102896..31103.14269.8366...................................
..4194304.308419..79039.33577........................................
.16777216.924532.199819..............................................
Empirical: a(n)=4*a(n-1)-6*a(n-2)+10*a(n-3)-5*a(n-4)+6*a(n-5)-a(n-6)+a(n-7)
Empirical: 
a(n)=4*a(n-1)-6*a(n-2)+4*a(n-3)+5*a(n-4)-4*a(n-5)+6*a(n-6)+4*a(n-7)+2*a(n-9)+a(n-10)

Empirical: 
a(n)=4*a(n-1)-6*a(n-2)+4*a(n-3)-a(n-4)+6*a(n-5)-4*a(n-6)+6*a(n-7)+4*a(n-8)+5*a(n-9)+a(n-10)+3*a(n-11)+2*a(n-12)+a(n-13)

Empirical: 
a(n)=4*a(n-1)-6*a(n-2)+4*a(n-3)-a(n-4)+6*a(n-6)-4*a(n-7)+6*a(n-8)+4*a(n-9)+5*a(n-10)+6*a(n-11)+2*a(n-12)+4*a(n-13)+3*a(n-14)+2*a(n-15)+a(n-16)

Empirical: 
a(n)=4*a(n-1)-6*a(n-2)+4*a(n-3)-a(n-4)+6*a(n-7)-4*a(n-8)+6*a(n-9)+4*a(n-10)+5*a(n-11)+6*a(n-12)+7*a(n-13)+3*a(n-14)+5*a(n-15)+4*a(n-16)+3*a(n-17)+2*a(n-18)+a(n-19)

Empirical: 
a(n)=4*a(n-1)-6*a(n-2)+4*a(n-3)-a(n-4)+6*a(n-8)-4*a(n-9)+6*a(n-10)+4*a(n-11)+5*a(n-12)+6*a(n-13)+7*a(n-14)+8*a(n-15)+4*a(n-16)+6*a(n-17)+5*a(n-18)+4*a(n-19)+3*a(n-20)+2*a(n-21)+a(n-22)



 rhhardin at mindspring.com
rhhardin at att.net (either)