Lisäystavat

Tehtäväsi on selvittää, monessako eri järjestyksessä luvut $1 \dots n$ voidaan lisätä tyhjään binäärihakupuuhun siten, että puun korkeudesta tulee mahdollisimman pieni. Voit olettaa, että puussa on enintään 100 solmua.

Toteuta tiedostoon fillways.py funktio count, joka kertoo, monessako eri järjestyksessä luvut $1 \dots n$ voidaan lisätä binäärihakupuuhun halutulla tavalla.

def count(n):
    # TODO

if __name__ == "__main__":
    print(count(1)) # 1
    print(count(3)) # 2
    print(count(4)) # 16
    print(count(7)) # 80
    print(count(10)) # 253440
    print(count(31)) # 74836825861835980800000

Selitys: Jos $n = 3$, kelvollisia järjestyksiä ovat vain $[2,3,1]$ ja $[2,1,3]$.