Dávid-csillag tétele

A Dávid-csillag tétel egy matematikai eredmény, amely két azonosságot ad a binomiális együtthatókkal kapcsolatban , Pascal háromszögében elrendezve két beágyazott háromszög alakjában.

Első identitás

Államok

A Pascal-háromszögben lévő Dávid - csillag két háromszögének csúcsán elhelyezkedő binomiális együtthatók GCD- je egyenlő:

{\ displaystyle {\ begin {aligned} & {\ text {PGCD}} {\ biggl (} {\ binom {n-1} {k-1}}, {\ binom {n} {k + 1}}, {\ binom {n + 1} {k}} {\ biggr)} \\ [8pt] = {} és {\ text {PGCD}} {\ biggl (} {\ binom {n-1} {k}} , {\ binom {n} {k-1}}, {\ binom {n + 1} {k + 1}} {\ biggr)} \ end {igazítva}}}

Történelmi

Ezt az identitást Henry W. Gould sejtette 1971-ben, Hoggatt és Hillman 1972-ben, majd Singmaster 1973-ban, Hitotumatu és Sato pedig 1975-ben mutatta be.

Példák

Az n = 9, k = 3, vagy n = 9, k = 6, a szám 84 körül egymás után a számok 28, 56, 126, 210, 120, 36. A figyelembe minden más távon, kapjuk: GCD (28 , 126, 120) = 2 = GCD (56, 210, 36) (lásd az ellenkezőjét).

Hasonlóképpen, az előző 36 kifejezést a 8, 28, 84, 120, 45, 9 elemek veszik körül, és minden más tagot megkapva: GCD (8, 84, 45) = 1 = GCD (28, 120, 9.)

Hitotumatu és Sato bemutatása

A képlet :

${\ 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}}}$

és a fordított képlet:

${\ 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}}}$

mutassuk meg, hogy egy háromszög minden eleme a másik háromszög elemeinek teljes lineáris kombinációja, ami azt jelenti, hogy a háromszög elemeinél közös osztók, a másik háromszög elemeinél közös osztók, és fordítva. Ez bizonyítja a GCD-k egyenlőségét.

Általánosítások

A Singmaster kiegészítette ezt az identitást azzal, hogy megmutatta, hogy a fenti GCD-k is megegyeznek . ${\ displaystyle {\ text {PGCD}} {\ biggl (} {n-1 \ select k-2}, {n-1 \ select k-1}, {n-1 \ select k}, {n-1 \ válassza a k + 1} {\ biggr)}} lehetőséget$

Így a 84. elemre vonatkozó fenti példában GCD-vel is rendelkezünk {8, 28, 56, 70} = 2.

Ezek a kapcsolatok a nagyobb csillagok esetében is fennállnak . Például,

{\ 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] = {} és {\ 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 {igazítva}}}

Második identitás

Államok

Hoggatt és Hansell 1971-ben észrevették, hogy a Dávid-csillag három számának két halmaza egyenlő termékekkel rendelkezik:

${\ 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}}}$ .

Például azzal, hogy ismét megfigyeljük, hogy a 84 elemet egymás után veszik körül a 28, 56, 126, 210, 120, 36 elemek, és minden más kifejezést figyelembe véve: 28 × 126 × 120 = 2 6 × 3 3 × 5 × 7 2 = 56 × 210 × 36.

Ez az eredmény könnyen bizonyítható írásával minden binomiális együttható faktoriális formában: . ${\ displaystyle {n \ select k} = {\ frac {n!} {(nk)! k!}}}$

Van azonban egy kombinatorikus bemutató, kevésbé egyszerű:

Demonstráció

Legyen hat természetes szám igazoló és . ${\ textstyle a, b, c, x, y, z}$ ${\ displaystyle x, y, z \ leqslant \ min (a, b, c)}$ ${\ displaystyle (ba, cb, ac) = (yz, zx, xy)}$

Számoljuk meg, hány módon lehet particionálni egy hatrészes méretkészletet : $a + b + c$

$NÁL NÉL$ , méret , méret , méret $x$ $B$ $y$ $VS$ $z$

$NÁL NÉL'$ , Méret , , méret , , méret . ${\ displaystyle ax}$ $B '$ ${\ displaystyle by}$ $VS ”$ ${\ displaystyle cz}$

Kezdjük azzal, hogy a készletet három részre osztjuk, a megfelelő méretre , és . Ennek számos módja van. $nál nél$ $b$ $vs.$ $NEM$

1. módszer:

vágjuk a derékrész a : módokon. $nál nél$ ${\ displaystyle A \ sqcup A '}$ ${\ displaystyle {\ binom {a} {x}}}$

vágjuk a derékrész a : módokon. $b$ ${\ displaystyle B \ sqcup B '}$ ${\ displaystyle {\ binom {b} {y}}}$

vágjuk a derékrész a : módokon. $vs.$ ${\ displaystyle C \ sqcup C '}$ ${\ displaystyle {\ binom {c} {z}}}$

Összesen: utak. ${\ displaystyle N. {\ binom {a} {x}} {\ binom {b} {y}} {\ binom {c} {z}}}$

2. módszer:

vágjuk a derékrész az (autó ): módokon. $nál nél$ ${\ displaystyle C \ sqcup B '}$ ${\ displaystyle z + by = a}$ ${\ displaystyle {\ binom {a} {z}}}$

vágjuk a derékrész az (autó ): módokon. $b$ ${\ displaystyle A \ sqcup C '}$ ${\ displaystyle x + cz = b}$ ${\ displaystyle {\ binom {b} {x}}}$

vágjuk a derékrész az (autó ): módokon $vs.$ ${\ displaystyle B \ sqcup A '}$ ${\ displaystyle y + ax = c}$ ${\ displaystyle {\ binom {c} {y}}}$

Összesen: utak. ${\ displaystyle N. {\ binom {a} {z}} {\ binom {b} {x}} {\ binom {y} {z}}}$

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

Pózol most és ezt ellenőrizzük . ${\ 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)}$

Dávid csillagának kilétére következtetünk . ${\ 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}}}$

Ez a bemutató az ezen az oldalon közzétett fordítás / adaptáció .

Általánosítás

Mi lehet cserélni az adott , hogy egy sorozat nem nulla valós számok. ${n \ k kiválasztása}$ ${\ displaystyle {\ binom {n} {k}} _ {(a_ {n})} = {\ frac {f (n)} {f (nk) f (k)}}}$ ${\ displaystyle f (n) = \ coprod _ {k = 1} ^ {n} a_ {k}}$ $(év)$

Különösen, ha a Fibonacci-szekvencia , akkor a fibonómiai együttható ; a Dávid-csillag második tétele tehát érvényes a fibonómiai háromszögben. $(év)$ $(F_ {n})$ ${\ displaystyle {\ binom {n} {k}} _ {(a_ {n})}}$ ${\ displaystyle {\ binom {n} {k}} _ {F}}$

Ha a q -analogue az n : , a binomiális együttható Gauss ; a Dávid-csillag második tétele tehát érvényes a q- binomiális háromszögben . $(év)$ ${\ displaystyle [n] _ {q} = 1 + q + ... + q ^ {n-1}}$ ${\ displaystyle {\ binom {n} {k}} _ {(a_ {n})}}$ ${\ displaystyle {\ binom {n} {k}} _ {q}}$

Általánosíthatunk arra az esetre, amikor a kommutatív csoport bármely szekvenciája szorzással jelölve van. Például, a csoport , lásd a következő A004247 a OEIS-ben . $(év)$ $({\ mathbb {Z}}, +)$ ${\ displaystyle {\ binom {n} {k}} _ {(n)} = k (nk)}$

Megjegyzések és hivatkozások

(fr) Ez a cikk részben vagy egészben az angol Wikipedia " Dávid-csillag tétele " című cikkéből származik ( lásd a szerzők felsorolását ) .

(in) HW Gould ,, " A binomiális együtthatók új legnagyobb közös osztó tulajdonsága " , Fibonacci Quarterly 10 ,1972, P. 579 - 584 ( online olvasás )
(in) Hillman, AP és Hoggatt, Jr., VE, " " Bizonyíték Gould Pascal Hexagon sejtéséről ". » , The Fibonacci Quarterly, 1. évf. 10.6 ,1972, P. 565–568, 598 ( online olvasás )
(in) David Singmaster, " " Megjegyzések a binomiális együtthatókról: Gould sejtésének IV-igazolása a bináris együtthatók háromszorosának GCD- jéről . " " , The Fibonacci Quarterly 11.3 ,1973, P. 282-84
(in) Sin Hitotumatu és Daihachiro Sato, " Dávid csillag tétel " , Fibonacci Quarterly 13 ,1975, P. 70
Weisstein, Eric W. "Dávid csillagának tétel". From MathWorld - Egy Wolfram webes erőforrás. http://mathworld.wolfram.com/StarofDavidTheorem.html
(in) VE Hoggatt W. HANSELL, " A REJTETT TÉREK HEXAGON " , Fibonacci negyedéves járat. 9 n ° 2 ,1971, P. 120 133 ( online olvasás )

Külső hivatkozás

A Dávid-csillag második tételének vizualizálása .