[seqfan] Max Locations after Smoothing - recurrences

Ron Hardin rhhardin at att.net
Wed Jan 23 16:00:44 CET 2013


Take a length-n array of values 0..k
Extend it left and right with zeros
Smooth the result with 1,1 weighting
Mark the locations of resulting maxima, putting the mark at the trailing edge of 
any plateau
Count the number of different mark arrays.

The recurrences below are particularly simple.

/tmp/cxw
T(n,k)=Number of binary arrays indicating the locations of trailing edge maxima 
of a random length-n 0..k array extended with zeros and convolved with 1,1

Table starts
.....2......2......2......2......2......2.....2.....2.....2.....2
.....3......3......3......3......3......3.....3.....3.....3.....3
.....4......4......4......4......4......4.....4.....4.....4.....4
.....6......7......7......7......7......7.....7.....7.....7.....7
.....9.....11.....11.....11.....11.....11....11....11....11....11
....13.....17.....18.....18.....18.....18....18....18....18....18
....19.....27.....29.....29.....29.....29....29....29....29....29
....28.....42.....46.....47.....47.....47....47....47....47....47
....41.....66.....74.....76.....76.....76....76....76....76....76
....60....104....118....122....123....123...123...123...123...123
....88....163....189....197....199....199...199...199...199...199
...129....256....303....317....321....322...322...322...322...322
...189....402....485....511....519....521...521...521...521...521
...277....631....777....824....838....842...843...843...843...843
...406....991...1244...1328...1354...1362..1364..1364..1364..1364
...595...1556...1992...2141...2188...2202..2206..2207..2207..2207
...872...2443...3190...3451...3535...3561..3569..3571..3571..3571
..1278...3836...5108...5563...5712...5759..5773..5777..5778..5778
..1873...6023...8180...8967...9229...9313..9339..9347..9349..9349
..2745...9457..13099..14454..14912..15061.15108.15122.15126.15127
..4023..14849..20976..23299..24094..24356.24440.24466.24474.24476
..5896..23315..33590..37556..38930..39388.39537.39584.39598......
..8641..36608..53789..60538..62901..63697.63959.64043............
.12664..57480..86135..97583.101632.103009........................
.18560..90252.137932.157297.164212...............................
.27201.141709.220877.253552......................................
.39865.222504.353701.............................................
.58425.349364....................................................
.85626...........................................................

Empirical for column k:
k=1: a(n)=a(n-1)+a(n-3)
k=2: a(n)=a(n-1)+a(n-3)+a(n-5)
k=3: a(n)=a(n-1)+a(n-3)+a(n-5)+a(n-7)
k=4: a(n)=a(n-1)+a(n-3)+a(n-5)+a(n-7)+a(n-9)
k=5: a(n)=a(n-1)+a(n-3)+a(n-5)+a(n-7)+a(n-9)+a(n-11)
k=6: a(n)=a(n-1)+a(n-3)+a(n-5)+a(n-7)+a(n-9)+a(n-11)+a(n-13)
k=7: a(n)=a(n-1)+a(n-3)+a(n-5)+a(n-7)+a(n-9)+a(n-11)+a(n-13)+a(n-15)

Some solutions for n=6 k=4, one leading extended zero position followed by 
filtered positions  

..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....0....0....0....0....0....0..
..0....0....1....0....1....0....1....0....1....0....0....1....0....1....0....0..
..0....0....0....1....0....0....0....1....0....0....0....0....0....0....1....1..
..0....1....1....0....0....1....0....0....1....0....0....0....1....0....0....0..
..0....0....0....0....0....0....0....0....0....1....0....0....0....1....1....0..
..0....1....0....0....1....0....0....1....1....0....1....0....0....0....0....0..
..1....0....0....1....0....1....1....0....0....0....0....0....0....0....0....0..

(Other convolution kernels don't seem to come out so simple.)

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




More information about the SeqFan mailing list