Dowód, że liczba jest całkowita

[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?

[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.

[mol_ksiazkowy]

I chcę pokazać, że ta liczba to jest liczba sposobów - czegoś.

A czy tak jest ...? np dla \(\displaystyle{ n=3}\) ?

[matinf]

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.

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.

[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.

[matinf]

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 ?

[Qń]

... ych_stopni

Q.

[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 ?