Věta o Davidově hvězdě

The Davidova věta je matematický výsledek poskytující dvě identity týkající se binomických koeficientů , uspořádaných v Pascalově trojúhelníku ve formě dvou vnořených trojúhelníků.

První identita

Státy

Na GCDs těchto kombinační číslo se nacházejí ve vrcholech dvou trojúhelníků s Davidovou hvězdou v Pascalova trojúhelníku jsou stejné:

{\ displaystyle {\ begin {aligned} & {\ text {PGCD}} {\ biggl (} {\ binom {n-1} {k-1}}, {\ binom {n} {k + 1}}, {\ binom {n + 1} {k}} {\ biggr)} \\ [8pt] = {} & {\ text {PGCD}} {\ biggl (} {\ binom {n-1} {k}} , {\ binom {n} {k-1}}, {\ binom {n + 1} {k + 1}} {\ biggr)} \ end {zarovnáno}}}

Historický

Tuto identitu předpokládali Henry W. Gould v roce 1971, což prokázali Hoggatt a Hillman v roce 1972, poté Singmaster v roce 1973 a Hitotumatu a Sato v roce 1975.

Příklady

Pro n = 9, k = 3 nebo n = 9, k = 6 je číslo 84 postupně obklopeno čísly 28, 56, 126, 210, 120, 36. Vezmeme-li každý druhý člen, získáme: GCD (28 , 126, 120) = 2 = GCD (56, 210, 36) (viz opak).

Podobně je předchozí člen 36 obklopen prvky 8, 28, 84, 120, 45, 9 a při každém dalším členu získáme: GCD (8, 84, 45) = 1 = GCD (28, 120, 9).

Demonstrace Hitotumatu a Sato

Vzorec:

${\ displaystyle {\ begin {bmatrix} {\ binom {n-1} {k-1}} \\ {\ binom {n} {k + 1}} \\ {\ binom {n + 1} {k} } \ end {bmatrix}} = {\ begin {bmatrix} k + 1 & kn-1 & -n-1 \\ - k & nk + 1 & n \\ k + 1 & kn & -n \ end {bmatrix }} {\ begin {bmatrix} {\ binom {n + 1} {k + 1}} \\ {\ binom {n} {k-1}} \\ {\ binom {n-1} {k}} \ end {bmatrix}}}$

a inverzní vzorec:

${\ displaystyle {\ begin {bmatrix} {\ binom {n + 1} {k + 1}} \\ {\ binom {n} {k-1}} \\ {\ binom {n-1} {k} } \ end {bmatrix}} = {\ begin {bmatrix} -n & -k & nk + 1 \\ n & k + 1 & kn \\ - n-1 & -k-1 & nk + 1 \ end { bmatrix}} {\ begin {bmatrix} {\ binom {n-1} {k-1}} \\ {\ binom {n} {k + 1}} \\ {\ binom {n + 1} {k} } \ end {bmatrix}}}$

ukazují, že každý prvek trojúhelníku je úplnou lineární kombinací prvků druhého trojúhelníku, což znamená, že dělitele společné pro prvky trojúhelníku jsou dělitele společné pro prvky druhého trojúhelníku a naopak. To dokazuje rovnost GCD.

Zobecnění

Singmaster dokončil tuto identitu tím, že ukázal, že výše uvedené GCD jsou také stejné . ${\ displaystyle {\ text {PGCD}} {\ biggl (} {n-1 \ zvolit k-2}, {n-1 \ zvolit k-1}, {n-1 \ zvolit k}, {n-1 \ zvolte k + 1} {\ biggr)}}$

Ve výše uvedeném příkladu pro prvek 84 tedy máme také GCD {8, 28, 56, 70} = 2.

Tyto vazby přetrvávají i pro větší hvězdy . Například,

{\ displaystyle {\ begin {aligned} & {\ text {PGCD}} {\ biggl (} {\ binom {n-2} {k-2}}, {\ binom {n-1} {k}}, {\ binom {n} {k + 2}}, {\ binom {n + 1} {k + 1}}, {\ binom {n + 2} {k}}, {\ binom {n} {k- 1}} {\ biggr)} \\ [8pt] = {} & {\ text {PGCD}} {\ biggl (} {\ binom {n-2} {k}}, {\ binom {n-1} {k-1}}, {\ binom {n} {k-2}}, {\ binom {n + 1} {k}}, {\ binom {n + 2} {k + 2}}, {\ binom {n} {k + 1}} {\ biggr)}. \ end {zarovnáno}}}

Druhá identita

Státy

Hoggatt a Hansell si v roce 1971 všimli, že dvě sady tří čísel Davidovy hvězdy mají stejné produkty:

${\ displaystyle {\ binom {n-1} {k-1}} {\ binom {n} {k + 1}} {\ binom {n + 1} {k}} = {\ binom {n-1} {k}} {\ binom {n} {k-1}} {\ binom {n + 1} {k + 1}}}$ .

Například opětovným pozorováním, že prvek 84 je postupně obklopen prvky 28, 56, 126, 210, 120, 36, a tím, že vezmeme každý druhý člen, máme: 28 × 126 × 120 = 2 6 × 3 3 × 5 × 7 2 = 56 × 210 × 36.

Tento výsledek je snadno dokázal tím, že píše každý binomickou koeficient v faktoriálního tvaru: . ${\ displaystyle {n \ zvolit k} = {\ frac {n!} {(nk)! k!}}}$

Existuje však kombinatorická demonstrace, méně jednoduchá:

Demonstrace

Dovolit je šest přirozených čísel ověřujících a . ${\ textový styl a, b, c, x, y, z}$ ${\ displaystyle x, y, z \ leqslant \ min (a, b, c)}$ ${\ displaystyle (ba, cb, ac) = (yz, zx, xy)}$

Počítáme počet způsobů, jak rozdělit šestidílnou sadu velikostí : $a + b + c$

$NA$ , velikost , velikost , velikost $X$ $B$ $y$ $VS$ $z$

$NA'$ , Size , , velikost , , velikost . ${\ displaystyle sekera}$ $B '$ ${\ displaystyle od}$ $VS '$ ${\ displaystyle cz}$

Začneme rozdělením set do tří částí, z příslušných velikostí , a . Existuje několik způsobů, jak toho dosáhnout. $na$ $b$ $vs.$ $NE$

Metoda 1:

řežeme pasový díl v : způsoby. $na$ ${\ displaystyle A \ sqcup A '}$ ${\ displaystyle {\ binom {a} {x}}}$

řežeme pasový díl v : způsoby. $b$ ${\ displaystyle B \ sqcup B '}$ ${\ displaystyle {\ binom {b} {y}}}$

řežeme pasový díl v : způsoby. $vs.$ ${\ displaystyle C \ sqcup C '}$ ${\ displaystyle {\ binom {c} {z}}}$

Celkem: způsoby. ${\ displaystyle N. {\ binom {a} {x}} {\ binom {b} {y}} {\ binom {c} {z}}}$

Metoda 2:

řezali jsme pasovou část v (autě ): způsoby. $na$ ${\ displaystyle C \ sqcup B '}$ ${\ displaystyle z + od = a}$ ${\ displaystyle {\ binom {a} {z}}}$

řezali jsme pasovou část v (autě ): způsoby. $b$ ${\ displaystyle A \ sqcup C '}$ ${\ displaystyle x + cz = b}$ ${\ displaystyle {\ binom {b} {x}}}$

řezali jsme pasovou část v (autě ): způsoby $vs.$ ${\ displaystyle B \ sqcup A '}$ ${\ displaystyle y + ax = c}$ ${\ displaystyle {\ binom {c} {y}}}$

Celkem: způsoby. ${\ displaystyle N. {\ binom {a} {z}} {\ binom {b} {x}} {\ binom {y} {z}}}$

Dostaneme . ${\ displaystyle {\ binom {a} {x}} {\ binom {b} {y}} {\ binom {c} {z}} = {\ binom {a} {z}} {\ binom {b} {x}} {\ binom {c} {y}}}$

Pózujeme nyní a ověřujeme to . ${\ displaystyle (a, b, c) = (n-1, n, n + 1)}$ ${\ displaystyle (x, y, z) = (k-1, k + 1, k)}$ ${\ displaystyle (ba, cb, ac) = (1,1, -2) = (yz, zx, xy)}$

Dedukujeme totožnost Davidovy hvězdy . ${\ displaystyle {\ binom {n-1} {k-1}} {\ binom {n} {k + 1}} {\ binom {n + 1} {k}} = {\ binom {n-1} {k}} {\ binom {n} {k-1}} {\ binom {n + 1} {k + 1}}}$

Tato demonstrace je překladem / adaptací publikace zveřejněné na tomto webu .

Zobecnění

Můžeme nahradit tím , kde , což je posloupnost nenulových skutečností. ${n \ zvolte k}$ ${\ displaystyle {\ binom {n} {k}} _ {(a_ {n})} = {\ frac {f (n)} {f (nk) f (k)}}}$ ${\ displaystyle f (n) = \ coprod _ {k = 1} ^ {n} a_ {k}}$ $(rok)$

Zejména, pokud je Fibonacciho sekvence , je fibonomiální koeficient ; druhá Davidova věta je tedy platná ve fibonomiálním trojúhelníku. $(rok)$ $(F_ {n})$ ${\ displaystyle {\ binom {n} {k}} _ {(a_ {n})}}$ ${\ displaystyle {\ binom {n} {k}} _ {F}}$

Jestliže je q -analogue z n : , je koeficient dvojčlena Gauss ; druhá Davidova věta je tedy platná pro q -binomiální trojúhelník . $(rok)$ ${\ displaystyle [n] _ {q} = 1 + q + ... + q ^ {n-1}}$ ${\ displaystyle {\ binom {n} {k}} _ {(a_ {n})}}$ ${\ displaystyle {\ binom {n} {k}} _ {q}}$

Můžeme zobecnit na případ, kdy je libovolná posloupnost ve komutativní skupině označená násobením. Například ve skupině , viz následující A004247 z OEIS . $(rok)$ $({\ mathbb {Z}}, +)$ ${\ displaystyle {\ binom {n} {k}} _ {(n)} = k (nk)}$

Poznámky a odkazy

(fr) Tento článek je částečně nebo zcela převzat z článku anglické Wikipedie s názvem „ Davidova věta “ ( viz seznam autorů ) .

(in) HW Gould ,, „ Nová největší společná dělitelská vlastnost binomických koeficientů “ , Fibonacci Quarterly 10 ,1972, str. 579 - 584 ( číst online )
(in) Hillman, AP a Hoggatt, Jr., VE, „ „ Důkaz o Gouldově domněnce Pascal Hexagon. “ » , The Fibonacci Quarterly, sv. 10,6 ,1972, str. 565–568, 598 ( číst online )
(in) David Singmaster, „ „ Poznámky k binomickým koeficientům: IV-důkaz domněnky o Gouldovi na GCD trojitých dvou binomických koeficientů. “ " , The Fibonacci Quarterly 11.3 ,1973, str. 282-84
(in) Sin Hitotumatu a Daihachiro Sato, „ Davidova věta o hvězdě “ , Fibonacci Quarterly 13 ,1975, str. 70
Weisstein, Eric W. „Hvězda Davidovy věty.“ From MathWorld - A Wolfram Web Resource. http://mathworld.wolfram.com/StarofDavidTheorem.html
(in) VE Hoggatt W. HANSELL, „ THE HIDDEN SQUARES HEXAGON “ , Fibonacciho čtvrtletní let. 9 č. 2 ,1971, str. 120 133 ( číst online )

Externí odkaz

Vizualizace druhé věty o Davidově hvězdě .