[wiskunde] Een som met binomiaalcoëfficienten

Heidegger

Ik heb de volgende vraag (een achtergrond volgt erna):

Hoe laat ik zien dat:

λ * (v-j boven k) / (v-t boven k-t)

gelijk is aan

som van i=0 tot j [ -1 ^j * j boven i * λ (v-i boven t-i ) / (k-i boven t-i)]

Achtergrond: beiden zijn uitdrukkingen voor het aantal blokken in een t-(v,k,lambda) design (X, B) dat geen punten overeenkomt met een j-subset van X, J.

De eerste uitdrukking komt van een dubbeltelargument het tweede van het gebruik van het principe van inclusie exclusie. Dit is het enige wat ik me nog afvraag, hoe je ze omschrijft in elkaar.

Heidegger

Excuus ik wist niet dat tex nog werkte:

Hoe laat ik zien dat:

\(\lambda {v-j \choose k} / {v-t \choose k-t}\)

gelijk is aan

\(\sum_{i=0}^{j} -1 ^j {j\choose i}\lambda {v-i \choose t-i}/ {k-i \choose t-i}\)

Drieske

Het toeval wil dat ik denk te weten op welke oefening je doelt... Kun je ze eens volledig geven? Want ik zou niet weten waarom je, als de opgave inderdaad is wat ik denk, dat nodig hebt.

Heidegger

Ja hoor natuurlijk. Het gaat om het aantal blokken in een design dat een lege doorsnede heeft met een bepaalde deelverzameling van de puntenverzameling.

Het complement van een design

\((X,\mathscr{B})\)

is

\((X,\overline{\mathscr{B}})\)

met:[/size]

\(\overline{\mathscr{B}}=\{X\backslash B : B\in\mathscr{B}\}\)

[/size]

In Cameron - Combinatorics propositie 16.3.4 staat het volgende:

Het complement van een

\(t-(v,k,\lambda)\)

design is een

\(t-(v,v-k,\overline{\lambda})\)

design[/size]

Er geldt:

\(\overline{\lambda}=\sum_{s=0}^t(-1)^s{t \choose s}\lambda_s\)

[/size]

Waar

\(\lambda_s=\lambda{v-s\choose t-s}/{k-s\choose t-s}\)

(dit komt van het afgeleide design voor

\(s\leq t\)

[/size]

Het bewijs vertelt vervolgens: neemt men een verzameling van

\(t\)

punten,

\(x_1,x_2,...,x_t\)

dan is het aantal blokken in het complementaire design dat al deze punten bevat gelijk aan het aantal blokken in het originele design dat géén van de punten bevat. Vervolgens kan dit worden berekend met inclusie-exclusie:[/size]

Zij

\(\mathscr{B}_i\)

de verzameling blokken die

\(x_i\)

bevat en voor

\(I\subseteq\{1,...,t\}\)

[/size]

\(\mathscr{B}_I=\cap_{i\in I}\mathscr{B}_i\)

, dan is

\(\mathscr{B}_I\)

de verzameling blokken met alle

\(x_i\)

voor

\(i\in I\)

erin, dus hebben we

\(\mathscr{B}_I=\lambda_s\)

als

\(|I|=s\)

. [/size]

Uit het principe van inclusie exclusie volgt dat het aantal blokken dat geen van de

\(x_1,...,x_t\)

bevat gelijk is aan:

\(
\sum_{I\subseteq\{1,..,t\}}(-1)^{|I|}|\mathscr{B}_I|=\sum_{s=0}^t(-1)^s{t\choose s}\lambda_s\)

[/size]

Dit bewijs staat ook in Wilson & Lint a Course in Combinatorics stelling 19.4:

Laat

\(0\leq j \leq t\)

het aantal blokken in het

\(t-(v,k,\lambda)\)

design dat géén van de punten van een

\(j\)

-deelverzameling

\(J\)

van

\(X\)

bevat is gelijk aan:[/size]

En dan dezelfde uitdrukking en het zelfde bewijs, maar daaronder staat dat een sneller bewijs een dubbeltelargument is en wel deze:

(Het aantal blokken dat geen van de punten van een

\(j\)

-deelverzameling bevat noemen ze

\(b^j\)

)[/size]

Tel de paren

\((J,B)\)

met

\(J\)

een

\(j\)

-subset van

\(X\)

en

\(B\)

een blok zodanig dat

\(J\cap B=\emptyset\)

. Dit levert

\({v\choose j}b^j=b{v-k \choose j}\)

. [/size]

(Links tel je het aantal

\(j\)

-sets dat je kan vormen en vermenigvuldig je dit met de opties voor een niet-snijdend blok. Rechts tel je het aantal blokken dat je kunt kiezen en vermenigvuldig je met de opties voor een niet snijdende

\(j\)

-set.[/size]

Waar

\(b=\lambda {v\choose t}/{k\choose t}\)

het aantal blokken in het design.[/size]

Dit is dan inderdaad om te schrijven naar

\(
\lambda {v-j \choose k} / {v-t \choose k-t}
\)

, dat is me wel gelukt.[/size]

Maar goed, het bewijs met inclusie-exclusie en het bewijs met dubbel-tellen geven dezelfde uitdrukking, nu kan ik alleen niet algebraïsch zien dat deze twee gelijk zijn... dat zou ik graag willen zien.

Drieske

Hmm, ja, okee. Je hebt dus wel al gevonden wat ik in gedachten had

. Het was dus ook de opgave/het bewijs dat ik in gedachten had. Mijn idee was dan om te zeggen: je hebt nu op twee manieren die lambda' gevonden. Ze drukken hetzelfde uit en zijn dus gelijk. Maar je wilt inzien waarom ze dat zijn, dus dan is dat niet meteen een bevredigend antwoord... Heb je al technieken gezien om dergelijke sommen te berekenen?

Morgen zal ik eens een uitwerking proberen te geven. Ze lijkt me niet onoverkomelijk moeilijk.

Heidegger

Drieske schreef: ↑zo 24 jun 2012, 21:38
Hmm, ja, okee. Je hebt dus wel al gevonden wat ik in gedachten had . Het was dus ook de opgave/het bewijs dat ik in gedachten had. Mijn idee was dan om te zeggen: je hebt nu op twee manieren die lambda' gevonden. Ze drukken hetzelfde uit en zijn dus gelijk. Maar je wilt inzien waarom ze dat zijn, dus dan is dat niet meteen een bevredigend antwoord... Heb je al technieken gezien om dergelijke sommen te berekenen?

Morgen zal ik eens een uitwerking proberen te geven. Ze lijkt me niet onoverkomelijk moeilijk.

Precies, in principe is het al combinatorisch bewezen dat ze gelijk zijn, maar ik zou graag algebraïsch(?) zien waarom dit gelijk is. En het ziet er inderdaad niet onmogelijk uit, maar in alle eerlijkheid ben ik er al heel lang mee bezig en mij lukt het niet. Ik zie graag je denkwerk tegemoet, kan ik ook weer rustig slapen

.

Overigens moet de som zijn:

\(
\sum_{i=0}^{j} -1 ^i {j\choose i}\lambda {v-i \choose t-i}/ {k-i \choose t-i}
\)

(Er stond

\(-1^j\)

).

Tja, ik denk dat het hier mee zou moeten maar ik tast nog in het duister..

http://mathworld.wol...nomialSums.html

Heidegger

Met omschrijven blijft de volgende vraag over:

\(\frac{(v-j)!}{(v-j-k)!k!}=?=\sum_{i=0}^j-1^i\frac{j!(v-i)!}{i!(j-i)!(k-i)!}\)

Wetenschapsforum

Laatste berichten

Nieuwsberichten

[wiskunde] Een som met binomiaalcoëfficienten

Een som met binomiaalco

Re: Een som met binomiaalco

Re: Een som met binomiaalco

Re: Een som met binomiaalco

Re: Een som met binomiaalco

Re: Een som met binomiaalco

Re: Een som met binomiaalco