[Jakim]

Podczas robienia przykładu z sortowaniem, musiałem się uporać z obliczaniem kombinacji. Otóż postanowiłem spisać wzór, dzięki któremu możemy obliczyć ilość tychże kombinacji.

Załóżmy, że mamy 2 liczby. Dozwolone kombinacje to:

1-2

Tylko jedna kombinacja. Ale teraz mamy 3 liczby. Dozwolone kombinacje to:

1-2
1-3
2-3

Niedużo, nie? Tylko 3. A co się dzieje przy 4 liczbach?

1-2
1-3
1-4
2-3
2-4
3-4

6 kombinacji. Już jest ich więcej. W liczenie kombinacji możemy oczywiście bawić się w nieskończoność. A jak powiemy, ile będzie kombinacji przy 20 liczbach? Pisanie nie wchodzi w rachubę . A to jest bardzo proste.

Przypomnijmy,

przy 2 liczbach była 1 kombinacja
przy 3 liczbach były 3 kombinacje
przy 4 liczbach było 6 kombinacji

Zauważacie pewną prawidłowość?

Zapiszmy to wzorem: c(x)=1+2+3+4...+x-1,
gdzie c jest liczbą tych liczb .

Sprawdźmy, czy się zgadza.

c(2)=1

Była jedna kombinacja, nieprawdaż?

c(3)=1+2

Ooo, też się zgadza .

c(4)=1+2+3

Patrzcie, też się zgadza!

Widzicie, to proste. Mam nadzieję, że zrozumieliście, jak się oblicza ilość kombinacji. Ale wróćmy do zadania. No kto powie, ile mamy kombinacji?

Okej. Ale załóżmy, że mamy 50 liczb. Dodawanie? Nieee, to nie wypali. Potrzebujemy następnego wzoru:

Mamy dodawanie: 1+2+3+4...+50

Czy da się go prościej przedstawić? Oczywiście.

((50+1)*50)/2

Sprawdźmy. Wyszło 1275? To dobrze. Przedstawmy teraz wzór z użyciem niewiadomej x, która oznacza najwyższą liczbę z kombinacji:

((x+1)*x)/2

Ale czy wzór jest poprawny? Możemy to sprawdzić na mniejszych liczbach.

1+2+3+4+5 = 15

A nowym wzorem?

((5+1)*5)/2

Też wyszło 15? To dobrze! Ale zamiast x trzeba teraz x-1. Czemu c-1 a nie zwykłe c? Przypomnijmy sobie stary wzór: c(x)=1+2+3+4...+x-1. Widzicie? Na końcu było x-1. Okej. Zapiszmy wzór z x-1.

c(x) = ((x-1)*x)/2

Ten wzór można skrócić do prostszej postaci.

c(x) = ((x^2-x)/2

Oto nasz Graal . Ale sprawdźmy, czy działa .

c(4) = (4^2-4 )/2
c(4) = (16-4)/2
c(4) = 12/2
c(4) = 6

Zgadza się? Tak! Teraz liczenie kombinacji to pestka! Ale mamy kolejny problem. Uwzględnijmy teraz powtórzenia cyfr:

1-1
2-2
3-3
...
x-x


Ile w takim razie kombinacji będzie przy 2 cyfrach, ile przy 3, a ile przy 4? Sprawdźmy. Przy dwóch cyfrach:

1-1
1-2
2-2


Trzy. A jak będzie z trójką liczb?

1-1
1-2
1-3
2-2
2-3
3-3

Sześć. No a przy 4?

1-1
1-2
1-3
1-4
2-2
2-3
2-4
3-3
3-4
4-4

Tym razem dziesięć. A jak to przedstawić wzorem? Dodajmy x do liczby kombinacji ze starego wzoru, gdzie x to była najwyższa wartość kombinacji.

c(x)=1+2+3...x

Działa? Testujmy.

c(2)=1+2
c(2)=3

c(3)=1+2+3
c(3)=6

c(4)=1+2+3+4
c(4)=10

Wszystko się zgadza. Jak to zapisać w nowym wzorze? Dodając x.

c(x) = ((x^2)-x)/2+x

I kolejny raz zmuszeni jesteśmy sprawdzać, czy działa .

c(2) = ((2^2)-2)/2+2
c(2) = (4-2)/2+2
c(2) = 2/2+2
c(2) = 1+2
c(2) = 3

c(3) = ((3^2)-3)/2+3
c(3) = (9-3)/2+3
c(3) = 6/2+3
c(3) = 3+3
c(3) = 6

c(4) = ((4^2)-4)/2+4
c(4) = (16-4)/2+4
c(4) = 12/2+4
c(4) = 6+4
c(4) = 10

Wszystko pinknie śmiga. Liczenie kombinacji to teraz pestka . Mam nadzieję, że wszystko zrozumieliście - postarałem się wszystko jak najjaśniej wyjaśnić . Przejrzyjcie tabelkę ze wzorami jeszcze raz:

//dla kombinacji bez powtórzeń

c(x) = ((x^2-x)/2

//dla kombinacji z powtórzeniami

c(x) = ((x^2)-x)/2+x

Pozdrawiam!

//Dodano:

można użyć silni (dzięki Broo za przypomnienie! ) i skorzystać ze wzoru:
n! / ( (n-k)! * k! )

[Tasmpol]

Jeżeli TGF oblicza silnie, to nie trzeba bawić się we wzory Chyba Advenced Math object ma funkcje obliczania silni. Tylko jak to będzie po angielsku?

[Jakim]

Ale zdaję mi się, że silnia polega na tym:
1*2*3*4*...*x
a nie na:
1+2+3+4...+x

[Tasmpol]

No tak. To silnia nie służy do obliczania ilości kobinacji danej liczby obiektów?
Przypomniało mi się, Factorial Object oblicza silnie.

[BROO]

Liczba różnych kombinacji k-elementowych bez powtórzeń (czyli te o które Ci chodzi) zbioru n-elementowego wynosi:

n! / ( (n-k)! * k! )

Możesz użyć Factorial Object do liczenia silnii.

[Jakim]

[Tasmpol]

Właściwie to nigdy nie miałem o silni na matematyce, ale dzisiaj akurat przeglądałem mały leksykonik matematyki i trafiłem na silnie. Ciekawy zbieg okoliczności, nie?

[k@rgul]

[NeTRaY]

poza tym wszystkim pierwszy sposob jest wielokrotnie szybszy od wyliczania tego z "oficjalnego wzoru"

[Fadex]

Nie wiem czy ktoś wie, ale podobnego sposobu używa się do obliczania ile dana figura ma przekątnych.
4 kąty-2 przekątne
5kątów-5 przekątnych
6kątów-9przekątnych
7kątów-14 przekątnych
Więc?
P liczba przekątnych
N liczba kątów
n ID cyfry

N zawiera Pn-1 + (Nn - 2) przekątnych niewiele kto to zrozumiał

PS: Jak ja uwielbiam algebrę

[Jakim]

Dodałem jeszcze dwa wzory pozwalające na obliczanie kombinacji z większą ilością liczb.