subset calculation with intervals

[Cubist]

I finally worked it out again...

Brilliant! Thank you. I love the mapping of this problem to your string notation.

 

[Cubist]

I spotted a couple of typos, and if @Dr.Peterson agrees then perhaps a moderator can correct these in post#20 (and then delete this post)

Any one-pair subset of the n-element set will end either in "_" (in which case there are [imath]T_{n-1}[/imath] ways to make the rest, which must include one pair); or in "_x" ([imath]T_{n-2}[/imath] ways); or in "xx" ([imath]S_{n-3}[/imath] ways, which must not include a pair). So

"_xx" <------- I think there ought to be an underscore before xx

[math]S_n=T_{n-1}+T_{n-2}+S_{n-3}[/math]

LHS ought to be [imath]T_n[/imath] not [imath]S_n[/imath]
[math]T_n=T_{n-1}+T_{n-2}+S_{n-3}[/math]

 

[Dr.Peterson]

I spotted a couple of typos, and if @Dr.Peterson agrees then perhaps a moderator can correct these in post#20 (and then delete this post)


"_xx" <------- I think there ought to be an underscore before xx


LHS ought to be [imath]T_n[/imath] not [imath]S_n[/imath]
[math]T_n=T_{n-1}+T_{n-2}+S_{n-3}[/math]

Correct on both counts. I've been too busy to check everything carefully.

Now if you can work out a single recursion ... I haven't put any time into that.

 

[Cubist]

Now if you can work out a single recursion ... I haven't put any time into that.

I'll have a go

 

[Cubist]

A single recursion for U...
[math] U_n=2U_{(n-1)} + U_{(n-2)} - 2U_{(n-3)} - U_{(n-4)} \, \text{where} \, n\ge4 \\ U_0=1, U_1=2, U_2=4, U_3=7 [/math]
Found by solving this system of equations:-
41 = a + 4 *b + 7 *c + 13 *d + 23 *e
72 = a + 7 *b + 13 *c + 23 *d + 41 *e
126 = a + 13 *b + 23 *c + 41 *d + 72 *e
219 = a + 23 *b + 41 *c + 72 *d + 126 *e
379 = a + 41 *b + 72 *c + 126*d + 219 *e
which gives a=0, b=-1, c=-2, d=1, e=2.

I checked this recursion relation for all values of U up to U₂₀