Prostokąt łaciński

Greenek · Post autor: **Greenek** » 11 cze 2008, o 18:33

Witam
Mam problem z dwoma zadaniami z prostokątów łacińskich.

1. Na ile różnych sposobów można rozszerzyć poniższy prostokąt łaciński 2 x 5 do kwadratu łacińskiego 5 x 5:

\(\displaystyle{ {{1 \ 2 \ 3 \ 4 \ 5} \choose {5 \ 3 \ 1 \ 2 \ 4}}}\)

2. Udowodnić, że jeśli m < n, to prostokąt łaciński o wymiarach m x n można rozszerzyć do prostokąta łacińskiego o wymiarach (m + 1) x n na co najmniej (n − m)!.

W pierwszym próbowałem wykombinować coś z permutacji, ale chyba nie tędy droga A na drugie nie mam w ogóle pomysłu.

Lukasz_C747 · Post autor: **Lukasz_C747** » 11 cze 2008, o 21:40

Nie ten dział, o raczej matematyka dyskretna.

Ad.2
Krótko mówiąc dopisujemy kolejny wiersz do macierzy. W pierwszej kolumnie tego rzędu możemy liczbę wpisać na (n-m) sposobów, bo mamy n liczb, ale m wykorzystaliśmy w poprzednich wierszach tej kolumny. W każdej kolejnej kolumnie mamy o 1 możliwość mniej (bo dodatkowo uwzględniamy liczby użyte w tym wierszu). Stąd dostajemy odpowiedź.

Ad.1
Korzystamy z zadania 2 Nie wydze szybszej i przyjemniejszej metody

Greenek · Post autor: **Greenek** » 12 cze 2008, o 12:26

Ale jak mam np. prostokąt 2x5 i chcę dodać jeden wiersz, to w pierwszej kolumnie mam (5-2), w drugiej (5-3), w trzeciej (5-4) i co dalej?