Strona 1 z 1
Dowód, że liczba jest całkowita
: 14 lip 2014, o 14:36
autor: matinf
Witam,
Udowodnić, że \(\displaystyle{ \frac{(n^2)!}{(n!)^{n}}}\) jest całkowita.
I chcę pokazać, że ta liczba to jest liczba sposobów - czegoś. A czego to zaraz spróbuję napisać. No bo jeśli jest to faktycznie liczba sposobów, to musi być całkowita.
No więc tak. Wyobraźmy sobie, że mamy \(\displaystyle{ n^2}\) kulek.
Te kulki mają kolor. Niech będzie \(\displaystyle{ n}\) możliwych kolorów. Co więcej, jest dokładnie \(\displaystyle{ n}\) kulek, które mają ten sam kolor. Tzn, że nie ma tak, że jakiś kolor nie został użyty, nie ma tak, że jakiegoś koloru jest więcej - jest idealnie równo - każdy z \(\displaystyle{ n}\) kolorów "nosi" \(\displaystyle{ n}\) kulek.
Na ile sposobów można ustawić w rzędzie te kulki ?
Z racji że kolory się powtarzają to jest to:
\(\displaystyle{ \frac{(n^2)!}{(n!)^{n}}}\)
No czyli jest to liczba całkowita. Ma sens taki dowód. A może gdzieś się pomyliłem?
Dowód, że liczba jest całkowita
: 14 lip 2014, o 14:55
autor: przem_as
Na razie z tego co napisałeś kulki można ustawić na \(\displaystyle{ (n^2)!}\) sposobów i tyle. Napisz jak widzisz rolę tych kolorów.
Dowód, że liczba jest całkowita
: 14 lip 2014, o 15:19
autor: mol_ksiazkowy
I chcę pokazać, że ta liczba to jest liczba sposobów - czegoś.
A czy tak jest ...? np dla
\(\displaystyle{ n=3}\) ?
Dowód, że liczba jest całkowita
: 14 lip 2014, o 16:41
autor: matinf
przem_as pisze:Na razie z tego co napisałeś kulki można ustawić na \(\displaystyle{ (n^2)!}\) sposobów i tyle. Napisz jak widzisz rolę tych kolorów.
No chodzi o to, że te kolory sprawiają, że kulki o tych samych kolorach nie są rozróżnialne, a więc żeby dostać ilość rozstawień musimy podzielić przez to co napisałem w mianowniku.
mol_ksiazkowy pisze:I chcę pokazać, że ta liczba to jest liczba sposobów - czegoś.
A czy tak jest ...? np dla
\(\displaystyle{ n=3}\) ?
Tak, zgadza się - dla trójki jest ok.
Dowód, że liczba jest całkowita
: 14 lip 2014, o 16:51
autor: Qń
Idea trochę niezgrabnie opowiedziana, ale prawidłowa.
A prościej powiedzieć, że:
\(\displaystyle{ \frac{(n^2)!}{(n!)^{n}}= \binom{n^2}{\underbrace{n,n,\ldots n}_n}}\)
Q.
Dowód, że liczba jest całkowita
: 14 lip 2014, o 16:55
autor: matinf
Qń pisze:Idea trochę niezgrabnie opowiedziana, ale prawidłowa.
A prościej powiedzieć, że:
\(\displaystyle{ \frac{(n^2)!}{(n!)^{n}}= \binom{n^2}{\underbrace{n,n,\ldots n}_n}}\)
Q.
Ok.
Ale od razu zapytam. Co oznacza ta równość, którą napisałeś. Te duże nawiasy sugerują symbol Newtona, ale "u dołu" mamy przecinki. Co to znaczy ?
Dowód, że liczba jest całkowita
: 14 lip 2014, o 16:56
autor: Qń
... ych_stopni
Q.
Dowód, że liczba jest całkowita
: 15 lip 2014, o 00:28
autor: matinf
A takie coś:
\(\displaystyle{ \frac{(nk)!}{(n!)^k\cdot k!}}\)
Najpierw pokażę analogicznie jak wyżej, że całkowite jest:
\(\displaystyle{ \frac{(nk)!}{(n!)^k}}\)
Mamy \(\displaystyle{ nk}\) kulek, \(\displaystyle{ k}\) kolorów. Każdy z \(\displaystyle{ k}\) kolorów jest reprezentowany przez dokładnie \(\displaystyle{ n}\) kulek. Nieróżróżnialne są kulki tego samego koloru. Liczbą wszystkich permutacji tych kulek jest \(\displaystyle{ \frac{(nk)!}{(n!)^k}}\), a więc to jest całkowite.
Muszę jeszcze pokazać, że dzieli się ten ułamek: \(\displaystyle{ \frac{(nk)!}{(n!)^k}}\) przez \(\displaystyle{ k!}\)
W tym celu podzielę na klasy abstrakcji wszystkie te permutacje, które "wchodzą" w powyższy wynik.
Dwie permutacje (pierwsza i druga - tak nazywam je) będą w tej samej klasie abstrakcji jeśli istnieje taka permutacja \(\displaystyle{ (i_1, i_2,..., i_k)}\), że:
--> W pierwszej permutacji na pozycji \(\displaystyle{ p-tej}\) występuje kulka koloru \(\displaystyle{ k_1}\) to w drugiej permutacji na tej samej pozycji występuje kulka o kolorze \(\displaystyle{ i_1}\)
--> W pierwszej permutacji na pozycji \(\displaystyle{ r-tej}\) występuje kulka koloru \(\displaystyle{ k_2}\) to w drugiej permutacji na tej samej pozycji występuje kulka koloru \(\displaystyle{ i_1}\)
--> itd.
Istotne jest to, że każda z klas abstrakcji ma moc \(\displaystyle{ k!}\). Bo tak wiele można wskazać permutacji "kodującej" relację równoważności. A skoro tak, to liczba \(\displaystyle{ \frac{(nk)!}{(n!)^k}}\) daje się podzielić przez \(\displaystyle{ k!}\)
Ok ?