<jupyter_start><jupyter_text><img src="http://www.cerm.unifi.it/chianti/images/logo%20unifi_positivo.jpg"         alt="UniFI logo" style="float: left; width: 20%; height: 20%;"> <NAME>September {23, 26}, 2016: refactoring toward class-based codeSeptember 22, 2016: Quicksort theory, average casesAbstractIn this notebook we study two recurrence relations arising from the analysis of the `Quicksort` algorithm: numbers of checks and swaps are taken into account, in the average case. Such relations involve subterms where subscripts dependends on *one* dimension. They are a simple, but interesting, starting point to approach the general method of recurrence unfolding, an algorithmic/symbolical idea stretched further in other notebooks.<jupyter_code>%run "recurrences.py"
%run "sums.py"
%run "start_session.py"
from itertools import accumulate

def accumulating(acc, current): return Eq(acc.lhs + current.lhs, acc.rhs + current.rhs)<jupyter_output><empty_output><jupyter_text>A generalization using accumulation<jupyter_code>mapped = list(accumulate(mapped, accumulating))
mapped
clear_cache()
m,v,r = to_matrix_notation(mapped, f, [n-k for k in range(-2, 19)])
m,v,r
m_sym = m.subs(inverted_fibs, simultaneous=True)
m_sym[:,0] = m_sym[:,0].subs(f[2],f[1])
m_sym[1,2] = m_sym[1,2].subs(f[2],f[1])
m_sym
# the following cell produces an error due to ordering, while `m * v` doesn't.
#clear_cache()
#m_sym * v
to_matrix_notation(mapped, f, [n+k for k in range(-18, 3)])<jupyter_output><empty_output><jupyter_text>According to [A162741][oeis], we can generalize the pattern above:[oeis]:http://oeis.org/A162741<jupyter_code>i = symbols('i')
d = IndexedBase('d')
k_fn_gen = Eq((k+1)*f[n], Sum(d[k,2*k-i]*f[n-i], (i, 0, 2*k)))
d_triangle= {d[0,0]:1, d[n,2*n]:1, d[n,k]:d[n-1, k-1]+d[n-1,k]}
k_fn_gen, d_triangle
mapped = list(accumulate(mapped, accumulating))
mapped
# skip this cell to maintain math coerent version
def adjust(term):
    a_wild, b_wild = Wild('a', exclude=[f]), Wild('b')
    matched = term.match(a_wild*f[n+2] + b_wild)
    return -(matched[a_wild]-1)*f[n+2]

m = fix_combination(mapped,adjust, lambda v, side: Add(v, side))
mapped = list(m)
mapped
to_matrix_notation(mapped, f, [n-k for k in range(-2, 19)])
mapped = list(accumulate(mapped, accumulating))
mapped
to_matrix_notation(mapped, f, [n-k for k in range(-2, 19)])
mapped = list(accumulate(mapped, accumulating))
mapped
to_matrix_notation(mapped, f, [n-k for k in range(-2, 19)])
mapped = list(accumulate(mapped, accumulating))
mapped
to_matrix_notation(mapped, f, [n-k for k in range(-2, 19)])<jupyter_output><empty_output><jupyter_text>Unfolding a recurrence with generic coefficients<jupyter_code>s = IndexedBase('s')
a = IndexedBase('a')
swaps_recurrence = Eq(n*s[n],(n+1)*s[n-1]+a[n])
swaps_recurrence
boundary_conditions = {s[0]:Integer(0)}
swaps_recurrence_spec=dict(recurrence_eq=swaps_recurrence, indexed=s, 
                               index=n, terms_cache=boundary_conditions)
unfolded = do_unfolding_steps(swaps_recurrence_spec, 4)
recurrence_eq = project_recurrence_spec(unfolded, recurrence_eq=True)
recurrence_eq
factored_recurrence_eq = project_recurrence_spec(factor_rhs_unfolded_rec(unfolded), recurrence_eq=True)
factored_recurrence_eq
factored_recurrence_eq.rhs.collect(s[n-5]).collect(a[n-4])
factored_recurrence_eq.subs(n,5)
recurrence_eq.subs(n, 5)
def additional_term(n): return (2*Integer(n)-3)/6

as_dict = {a[n]:additional_term(n) for n in range(1,6)}

recurrence_eq.subs(n, 5).subs(as_dict)<jupyter_output><empty_output><jupyter_text>--- A curious relation about Fibonacci numbers, in matrix notation<jupyter_code>d = 10
m = Matrix(d,d, lambda i,j: binomial(n-i,j)*binomial(n-j,i))
m
f = IndexedBase('f')
fibs = [fibonacci(i) for i in range(50)]
mp = (ones(1,d)*m*ones(d,1))[0,0]
odd_fibs_eq = Eq(f[2*n+1], mp, evaluate=True)
odd_fibs_eq
(m*ones(d,1))<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.14866255144032922, 'fraction_numerical': 0.025977366255144033, 'mean_word_length': 6.969262295081967, 'pattern_counts': {'":': 0, '<': 23, '<?xml version=': 0, '>': 23, 'https://': 0, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '537966', 'license': 'Apache-2.0', 'n_tokens_mistral': 1605, 'n_tokens_neox': 1511, 'n_words': 330, 'path': 'notebooks/recurrences-unfolding.ipynb', 'repo_name': 'massimo-nocentini/Ph.D', 'size': '3899'}