20x20-sjakkbrett

[FredrikM]

Dette er egentlig et ProjectEuler-problem:

http://projecteuler.net/index.php?secti ... lems&id=15

Men det har en elegant matematisk løsning.

Finn en formel for [tex]n \times n[/tex]-sjakkbrett.

[Karl_Erik]

Det er klart at enhver vei fra øverste venstre til nederste hjørne består av 2n rette linjestykker, der eksakt n er vannrette og eksakt n er loddrette. Rekkefølgen på disse korresponderer unikt til forskjellige veier, så antallet mulige veier er lik antallet måter å arrangere disse n vannrette og n loddrette på. Dette svarer til å velge [tex]\left ( \stack {2n} n \right )[/tex] av dem til å være loddrette og så la resten være vannrette, så svaret er [tex]\left ( \stack {2n} n \right )[/tex].

Alternativt kan en løse denne ved å tenke litt som programmerere gjør med dynamisk programmering og bruke kjente kombinatoriske identiteter for å få det en vil ha.

[FredrikM]

Jeg løste den slik:

Jeg kodet en vei som en string av enere og nuller. (0 = ned, 1=høyre). Da skal vi ende opp med n nuller og n enere (vektor med 2n posisjoner), og disse kan selvsagt omstokkes så mye vi vil. Mao [tex]\frac{(2n)!}{n!^2}[/tex].

(men disse metodene er jo bare hverandre i forkledning)

[Magnus]

Var vel i abelfinalen et år..