[wiskunde] Een som met binomiaalcoëfficienten
Moderators: ArcherBarry, Fuzzwood
- Berichten: 78
Een som met binomiaalco
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.
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.
- Berichten: 78
Re: Een som met binomiaalco
Excuus ik wist niet dat tex nog werkte:
Hoe laat ik zien dat:
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}\)
- Berichten: 10.179
Re: Een som met binomiaalco
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.
Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.
- Berichten: 78
Re: Een som met binomiaalco
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
In Cameron - Combinatorics propositie 16.3.4 staat het volgende:
Het complement van een
Er geldt:
Waar
Het bewijs vertelt vervolgens: neemt men een verzameling van
Zij
Uit het principe van inclusie exclusie volgt dat het aantal blokken dat geen van de
Dit bewijs staat ook in Wilson & Lint a Course in Combinatorics stelling 19.4:
Laat
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
Tel de paren
(Links tel je het aantal
Waar
Dit is dan inderdaad om te schrijven naar
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.
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]\sum_{I\subseteq\{1,..,t\}}(-1)^{|I|}|\mathscr{B}_I|=\sum_{s=0}^t(-1)^s{t\choose s}\lambda_s\)
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]\lambda {v-j \choose k} / {v-t \choose k-t}
\)
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.
- Berichten: 10.179
Re: Een som met binomiaalco
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.
Morgen zal ik eens een uitwerking proberen te geven. Ze lijkt me niet onoverkomelijk moeilijk.
Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.
- Berichten: 78
Re: Een som met binomiaalco
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 .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.
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 \sum_{i=0}^{j} -1 ^i {j\choose i}\lambda {v-i \choose t-i}/ {k-i \choose t-i}
\)
\(-1^j\)
).Tja, ik denk dat het hier mee zou moeten maar ik tast nog in het duister..
http://mathworld.wol...nomialSums.html
- Berichten: 78
Re: Een som met binomiaalco
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)!}\)