Kombinatoryka, rozróżnialność i nierozróżnialność

0

Cześć!
Mam takie zadanie:

  1. Dana jest liczba naturalna k ­ >= 4. Na ile sposobów można k + 1 zadań
    przydzielić k komputerom, tak by dokładnie jeden komputer był wolny,
    jeżeli
    a) zadania i komputery są rozróżnialne,
    b) komputery są rozróżnialne, a zadania nie,
    c) zadania są rozróżnialne, a komputery nie,
    d) ani zadania, ani komputery nie są rozróżnialne?

(BARDZO PROSZĘ NIC NIE PODPOWIADAĆ BO TO ZADANIE Z KONKURSU)

brakuje mi tutaj wiedzy, której nie potrafię znaleźć w internecie. Poszukiwania o kombinatoryce kończą się na permutacjach, Newtonie i wariacjach. Czy ktoś mógłby podesłać materiały wyjaśniające o obiektach rozróżnialnych i nierozróżnialnych wraz z odpowiednimi wzorami?

4

Znaczy… to nie jest jakoś specjalnie osobno omawiany temat czy coś… Raczej się nie doczeka osobnego rozdziału w książce ani nic takiego, podobnie jak nie znajdziesz osobnego rozdziału o dodawaniu, nie wiem, liczb parzystych i nieparzystych…

Tutaj cała idea tego zadania się sprowadza do tego, żeby wiedzieć, której metody użyć w każdej z tych sytuacji, więc właściwie nie sposób tutaj czegokolwiek doradzić bez rozwiązywania zadania jako takiego.

Jedyne co mi przychodzi do głowy, co nie jest rozwiązaniem, ale może być w jakiś sposób przydatne, jest prostsze zadanie, tylko policzone „ręcznie”: „ile jest możliwych rezultatów rzutu dwiema odróżnialnymi kośćmi sześciennymi, a ile nieodróżnialnymi?”

No to dla odróżnialnych sprawa prosta — sześć możliwości na jednej, sześć na drugiej, więc łącznie sześć razy sześć, czyli trzydzieści sześć. A dla nieodróżnialnych — też nie jest jakoś skomplikowanie. Mamy sześć wyników, gdzie na obu jest to samo, a z tych z różnymi ściankami na każdej z kości, jedynkę można sparować z pięcioma wartościami, dwójkę z czterema (bo z jedynką już liczyliśmy), trójkę z trzema, czwórkę z dwoma i piątkę z jedną (szóstką), więc łącznie sześć plus pięć plus cztery plus trzy plus dwa plus jeden, czyli dwadzieścia jeden.

Możesz znaleźć coś przydatnego pod hasłem „zasada włączeń i wyłączeń”, żeby nie liczyć aż tak bardzo „ręcznie”, ale ogólnie, tak jak pisałem, cała idea tego zadania się opiera na doborze i wymyśleniu odpowiednich wzorów, a nie wzięcia gotowych.

3

Poszukiwania o kombinatoryce kończą się na permutacjach, Newtonie i wariacjach

I dobrze bo nic więcej nie potrzeba. Potrzebne ci są tutaj tylko kombinacje i wariacje (które są niczym innym jak permutacjami kombinacji). Jeśli coś jest nierozróżnialne, to interesuje cię kombinacja, jeśli coś jest rozróżnialne to wariacja, bo wtedy kolejność ma znaczenie (np. wylosowanie 1, 2 to co innego niż 2, 1).
U ciebie masz do wykonania dwa działania -> najpierw "wybierasz zadania" a potem dla każdego takiego wyboru interesuje cię "przydzielenie komputera".

1 użytkowników online, w tym zalogowanych: 0, gości: 1