[seqfan] Simple empirical formulas, proof?

[Ron Hardin]

This turns up with a fairly obvious empirical formula (for rows), with the exception of the restriction on small k perhaps, see formulas.

Here every value 0..k has to appear in every k+2 consecutive terms (so there's one extra choice), and 0..k appear first in that order so as to avoid superfluous permutation counting.

It's also a nice example of unit coefficient recurrences.


/tmp/eik
T(n,k)=Number of length n+k+1 0..k arrays with every value 0..k appearing at least once in every consecutive k+2 elements, and new values 0..k introduced in order

Table starts
...3....6...10...15....21....28....36....45....55....66....78....91...105
...5...12...22...35....51....70....92...117...145...176...210...247...287
...8...22...43...71...106...148...197...253...316...386...463...547...638
..13...40...82..139...211...298...400...517...649...796...958..1135..1327
..21...74..157..271...416...592...799..1037..1306..1606..1937..2299..2692
..34..136..304..531...821..1174..1590..2069..2611..3216..3884..4615..5409
..55..250..586.1047..1626..2332..3165..4125..5212..6426..7767..9235.10830
..89..460.1129.2059..3231..4642..6308..8229.10405.12836.15522.18463.21659
.144..846.2176.4047..6411..9256.12587.16429.20782.25646.31021.36907.43304
.233.1556.4195.7955.12716.18442.25138.32821.41527.51256.62008.73783.86581

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

Empirical for column k:
k=1: a(n)=a(n-1)+a(n-2)
k=2: a(n)=a(n-1)+a(n-2)+a(n-3)
k=3: a(n)=a(n-1)+a(n-2)+a(n-3)+a(n-4)
k=4: a(n)=a(n-1)+a(n-2)+a(n-3)+a(n-4)+a(n-5)
k=5: a(n)=a(n-1)+a(n-2)+a(n-3)+a(n-4)+a(n-5)+a(n-6)
k=6: a(n)=a(n-1)+a(n-2)+a(n-3)+a(n-4)+a(n-5)+a(n-6)+a(n-7)
k=7: a(n)=a(n-1)+a(n-2)+a(n-3)+a(n-4)+a(n-5)+a(n-6)+a(n-7)+a(n-8)
k=8: a(n)=a(n-1)+a(n-2)+a(n-3)+a(n-4)+a(n-5)+a(n-6)+a(n-7)+a(n-8)+a(n-9)
k=9: a(n)=a(n-1)+a(n-2)+a(n-3)+a(n-4)+a(n-5)+a(n-6)+a(n-7)+a(n-8)+a(n-9)+a(n-10); and also :
k=9: a(n)=6*a(n-1)-13*a(n-2)+12*a(n-3)-4*a(n-4) for n>14
Empirical for row n:
n=1: a(n) = (1/2)*n^2 + (3/2)*n + 1
n=2: a(n) = (3/2)*n^2 + (5/2)*n + 1
n=3: a(n) = (7/2)*n^2 + (7/2)*n + 1
n=4: a(n) = (15/2)*n^2 + (9/2)*n + 1
n=5: a(n) = (31/2)*n^2 + (11/2)*n + 1 for n>1
n=6: a(n) = (63/2)*n^2 + (13/2)*n + 1 for n>2
n=7: a(n) = (127/2)*n^2 + (15/2)*n + 1 for n>3
n=8: a(n) = (255/2)*n^2 + (17/2)*n + 1 for n>4
n=9: a(n) = (511/2)*n^2 + (19/2)*n + 1 for n>5

Column 1 is A000045(n+3)
Column 2 is A196700(n+3)
Row 1 is A000217(n+1)
Row 2 is A000326(n+1)
Row 3 is A069099(n+1)
Row 4 is A220083

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