n pracowników i k list obecności

SirPL · Post autor: **SirPL** » 11 lis 2014, o 22:11

Potrzebuję pomocy lub nakierowania na właściwe tory z następującym zadaniem:

Mamy \(\displaystyle{ n}\) pracowników i \(\displaystyle{ k}\) wejść. Przy każdym wejściu jest lista obecności na którą wpisuje się każdy wchodzący przez dane wejście pracownik. Każdy pracownik wpisuje się na dokładnie jedną listę. Na ile sposobów mogą być wypełnione listy obecności (zakładając, że rozróżniamy kolejność podpisów na każdej z list)?

Z góry dziękuję za pomoc i pozdrawiam.

arek1357 · Post autor: **arek1357** » 11 lis 2014, o 22:41

Nie wiem czy dobrze kumam ale chodzi o to , że mamy \(\displaystyle{ n}\) pracowników,
i każdy wybiera jedno z \(\displaystyle{ k}\) wejść czyli:

pierwsze wejście wybiera: \(\displaystyle{ n_{1}}\) pracowników

drugie wejście wybiera: \(\displaystyle{ n_{2}}\) pracowników

trzecie wejście wybiera: \(\displaystyle{ n_{3}}\) pracowników

...............................................................................

\(\displaystyle{ k}\)-te wejście wybiera: \(\displaystyle{ n_{k}}\) pracowników

Ponadto:

Przy każdym wejściu pracownicy się permutują na: \(\displaystyle{ n_{i}!}\)- sposobów

czyli wszystkich możliwości będzie:

\(\displaystyle{ \sum_{n_{1}+n_{2}+...+n_{k}=n}^{}n_{1}! \cdot n_{2}! \cdot ... \cdot n_{k}!}\)

\(\displaystyle{ 0 \le n_{i} \le n}\)

Nie wiem jak można to bardziej zwinąć.

SirPL · Post autor: **SirPL** » 12 lis 2014, o 00:56

Udało mi się samodzielnie rozwiązać to zadanie.

Do jego rozwiązania będziemy potrzebowali lematu:
Lemat: Liczba przedstawień liczby \(\displaystyle{ n}\) w postaci sumy \(\displaystyle{ k}\) liczb naturalnych (większych od zera) wynosi \(\displaystyle{ {n-1 \choose k-1}}\), jeśli przedstawienia różniące się kolejnością składników uważamy za różne. Twierdzenie to jest również znane jako problem Gwiazdek i Belek (ang. stars and bars)

Dowód lematu: (przez obrazek)
Przedstawmy liczbę \(\displaystyle{ n}\) jako \(\displaystyle{ n}\) elementów. W tym dowodzie przyjmijmy, że \(\displaystyle{ n=7}\).

★ ★ ★ ★ ★ ★ ★

Naszym celem jest podzielenie tych obiektów na \(\displaystyle{ k}\) grup. Będziemy to robić graficznie poprzez rysowanie pionowych belek. Zauważmy, że do podzielenia grupy na dwie podgrupy potrzebujemy użyć tylko jednej belki. Zatem do podzielenia grupy na \(\displaystyle{ k}\) podgrup użyjemy \(\displaystyle{ k-1}\) belek.

★ ★ ★|★ ★ ★|★

Chcemy wiedzieć na ile sposobów możemy wstawić \(\displaystyle{ k-1}\) belek. Ponieważ z założenia podgrupa nie może być pusta, zatem nie możemy wstawić belki przed pierwszym ani za ostatnim elementem, a także nie możemy wstawić dwóch belek bezpośrednio obok siebie. Zatem istnieje \(\displaystyle{ n-1}\) miejsc, gdzie można poprawnie wstawić belki: (oznaczone jako _ )

★_★_★_★_★_★_★

Z tego wynika, że sposobów na wstawienie \(\displaystyle{ k-1}\) belek w \(\displaystyle{ n-1}\) miejsc jest \(\displaystyle{ {n-1 \choose k-1} \blacksquare}\)

==========================================================

Przejdźmy do właściwego dowodu:
Będziemy dzielić pracowników na podgrupy i wybierać dla każdej podgrupy wejścia, z których korzystają.

Z lematu wiemy, że istnieje \(\displaystyle{ {n-1 \choose k-1}}\) sposobów na podział pracowników na \(\displaystyle{ k}\) podgrup. Będziemy rozważać kolejno podziały na \(\displaystyle{ i=1,2,3,...,k}\) podgrup.
Dla każdej z \(\displaystyle{ i}\) podgrup będziemy wybierać wejście, z którego korzystają. Wyboru takiego dokonamy na \(\displaystyle{ {k \choose i}}\) sposobów.
Aby rozróżnić kolejność osób wpisujących się na listę, dokonamy permutacji pracowników (na \(\displaystyle{ n!}\) sposobów).
Rozwiązaniem będzie suma wszystkich tych sposobów:

\(\displaystyle{ \sum_{i=1}^{n} {n-1 \choose i-1}{k \choose i}n!}\)

arek1357 · Post autor: **arek1357** » 12 lis 2014, o 06:39

Czyli jest założenie, że każda bramka jest niepusta
nie może tak być pracownicy dowolnie wybierają bramki.
Ja natomiast nie uwzględniłem, że pracownicy w końcu to też obiekty rozróżnialne!

pesel · Post autor: **pesel** » 12 lis 2014, o 06:51

.... co przy liczbie bramek większej od liczby pracowników nie będzie spełnione.

norwimaj · Post autor: **norwimaj** » 12 lis 2014, o 08:23

arek1357 pisze:Czyli jest założenie, że każda bramka jest niepusta
nie może tak być pracownicy dowolnie wybierają bramki.

Rozwiązanie podane przez SirPL też dopuszcza puste listy. Może mylące jest to, że w lemacie napisał literę \(\displaystyle{ k,}\) a nie \(\displaystyle{ i,}\) ale jak się przeczyta ze zrozumieniem, to nie ma problemu.

SirPL pisze: Dla każdej z \(\displaystyle{ i}\) podgrup będziemy wybierać wejście, z którego korzystają. Wyboru takiego dokonamy na \(\displaystyle{ {k \choose i}}\) sposobów.

Prościej by było od razu dopuścić, że niektóre składniki mogą być puste. Wtedy otrzymamy wynik w krótszej postaci:

\(\displaystyle{ \binom{n+k-1}n\cdot n!}\)

arek1357 · Post autor: **arek1357** » 12 lis 2014, o 08:25

No dokładnie udało mi się dojść do tego samego wzorku
I to naprawdę działa dobrze

SirPL · Post autor: **SirPL** » 12 lis 2014, o 08:57

Jak zostało powiedziane wyżej, zakładam, że mogą być puste bramki.
Zauważcie, że w każdej iteracji sumy wybieram ile stworzę grup, a co za tym idzie, z ilu bramek będę korzystał (i zakładam, że listy przy wszystkich innych bramkach będą puste). I tak od jednej do \(\displaystyle{ k}\) (wszystkich) bramek. Nie wiem, czy to tłumaczenie nie zaciemnia mojego toku myślenia jeszcze bardziej.

arek1357 · Post autor: **arek1357** » 12 lis 2014, o 11:22

Ja ostatecznie oparłem się na moim wejściowym wzorku sumacyjnym tylko dopuszczam wszystkie możliwości a jest ich:

\(\displaystyle{ k^n}\)

\(\displaystyle{ \sum_{}^{} \frac{n!}{n_{1}! \cdot n_{2}! \cdot ... \cdot n_{k}! } \cdot n_{1}! \cdot n_{2}! \cdot ... \cdot n_{k}!}\)

a możliwości jest teraz: \(\displaystyle{ {n+k-1 \choose n}}\) przez kltóre przemnażamy a pod sumą się poskraca