Ile jest permutacji...

[luk_rog]

Ile jest permutacji cyfr 0,...,9, w których pierwsza cyfra jest większa od 4 oraz trzecia jest mniejsza od 6? Jak zmieni się odpowiedź, jeśli oraz zastąpić przez bądź?

Czy poniższe rozumowanie jest poprawne?
Ogólnie na pierwszym miejscu mogą znajdować się cyfry od 5 do 9, na drugim od 0 do 9 wyłączając cyfrę z pierwszego miejsca, na trzecim cyfry od 0 do 5 ewentualnie wyłączając jedną lub dwie z poprzednich miejsc, na czwartym cyfry od 0 do 9 wyłączając trzy z poprzednich miejsc itd.
Jeśli na pierwszym miejscu pojawi się cyfra różna od 5 a na drugim miejscu cyfra większa od 5, to na trzecim miejscu mamy do wyboru sześć cyfr a na pozostałych miejscach cyfry od 0 do odpowiednio wyłączając cyfry z poprzednich miejsc. W tym przypadku permutacji tych jest \(\displaystyle{ 4 \cdot 4 \cdot 6 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}\).
Jeśli na pierwszym miejscu pojawi się cyfra 5 (która może się pojawić również na trzecim miejscu) a na drugim miejscu cyfra większa od 5, to na trzecim miejscu mamy do wyboru pięć cyfr a na pozostałych miejscach j. w. W tym przypadku permutacji tych jest \(\displaystyle{ 4 \cdot 5 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}\).
Jeśli na pierwszym miejscu pojawi się cyfra 5 (która może się pojawić również na trzecim miejscu) a na drugim miejscu cyfra mniejsza od 4 (która również może pojawić się na trzecim miejscu), to na trzecim miejscu mamy do wyboru cztery cyfry a na pozostałych miejscach j. w. W tym przypadku permutacji tych jest \(\displaystyle{ 4 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}\).
Zatem ostateczna odpowiedź brzmi
\(\displaystyle{ 4 \cdot 4 \cdot 6 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 + 4 \cdot 5 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 + 4 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}\)
Odpowiedź na drugą część zadania analogicznie.

[mat_61]

Mocno to skomplikowałeś (nawet nie chce mi się szczegółowo analizować czy jest poprawnie, ale na pierwszy rzut oka wydaje mi się, że nie).

1) Pierwsza cyfra 5, trzecia spośród {0;1;2;3;4}, pozostałe dowolne z 8 pozostałych cyfr, czyli:

\(\displaystyle{ 1 \cdot 5 \cdot 8!}\)

2) Pierwsza cyfra spośród {6;7;8;9}, trzecia spośród {0;1;2;3;4;5}, pozostałe dowolne z 8 pozostałych cyfr, czyli:

\(\displaystyle{ 4 \cdot 6 \cdot 8!}\)

Teraz wystarczy dodać te wartości.

-- 4 sty 2011, o 23:21 --

Odpowiedź na drugą część zadania analogicznie.

Nie wiem co rozumiesz pod pojęciem analogicznie, ale bądź jest przeciwieństwem (negacją) oraz.

\(\displaystyle{ \neg (p \wedge q) \Leftrightarrow (p|q)}\)

Tym samym od wszystkich możliwych permutacji wystarczy odjąć te obliczone powyżej.

[luk_rog]

W swoich obliczeniach nie uwzględniasz drugiego miejsca, czy to znaczy że nie trzeba go uwzględniać? Po mojemu jest tak:
Niech C1, C2, C3 oznaczają cyfry odpowiednio na pierwszym, drugim i trzecim miejscu. Ogólnie \(\displaystyle{ C1 \in \left\{ 5,6,7,8,9\right\} , C3 \in \left\{ 0,1,2,3,4,5\right\}}\).
1) \(\displaystyle{ C1 \in \left\{ 6,7,8,9\right\}, C2 \in \left\{ 6,7,8,9\right\} \setminus \left\{ C1\right\}, C3 \in \left\{ 0,1,2,3,4,5\right\}}\), czyli \(\displaystyle{ 4 \cdot 3 \cdot 6 \cdot 7!}\)
2) \(\displaystyle{ C1=5, C2 \in \left\{ 6,7,8,9\right\}, C3 \in \left\{ 0,1,2,3,4\right\}}\), czyli \(\displaystyle{ 1 \cdot 4 \cdot 5 \cdot 7!}\)
3) \(\displaystyle{ C1=5, C2 \in \left\{ 0,1,2,3,4\right\}, C3 \in \left\{ 0,1,2,3,4\right\} \setminus \left\{ C2\right\}}\), czyli \(\displaystyle{ 1 \cdot 5 \cdot 4 \cdot 7!}\)
Wyniki dodać i to jest odpowiedź.
Co do drugiej części zadania wiem o co chodzi, tylko źle to sformułowałem.

[mat_61]

W swoich obliczeniach nie uwzględniasz drugiego miejsca, czy to znaczy że nie trzeba go uwzględniać?

Ależ oczywiście, że uwzględniam wszystkie miejsca. Przecież dla cyfry na drugim miejscu nie ma żadnych warunków. W związku z tym można potocznie powiedzieć, że wybieram cyfrę dla I miejsca, następnie cyfrę dla III miejsca (obydwie wg określonych w zadaniu warunków) a następnie pozostałe osiem cyfr rozmieszczam dowolnie na pozostałych ośmiu miejscach tzn. II, IV, V itd.

Kolejność rozpatrywanych miejsc nie ma w permutacji żadnego znaczenia jeżeli nie ma postawionych szczególnych warunków dla konkretnych miejsc.

Zobacz taki przykład:

Ile można ułożyć 3-cyfrowych liczb parzystych o nie powtarzających się cyfrach ze zbioru \(\displaystyle{ \left\{ 1;2;3;4;5;6;8\right\}}\)

Można to zrobić wg Twojej propozycji tak (rozpatrując wybór od pierwszej cyfry):

- na pierwszym miejscu cyfra nieparzysta, na drugim nieparzysta, na trzecim parzysta: \(\displaystyle{ 3 \cdot 2 \cdot 4=24}\) możliwości

- na pierwszym miejscu cyfra nieparzysta, na drugim parzysta, na trzecim parzysta: \(\displaystyle{ 3 \cdot 4 \cdot 3=36}\) możliwości

- na pierwszym miejscu cyfra parzysta, na drugim nieparzysta, na trzecim parzysta: \(\displaystyle{ 4 \cdot 3 \cdot 3=36}\) możliwości

- na pierwszym miejscu cyfra parzysta, na drugim parzysta, na trzecim parzysta: \(\displaystyle{ 4 \cdot 3 \cdot 2=24}\) możliwości

Razem 120 możliwości.

Ale można też wybierać od ostatniej cyfry:

- na ostatnim miejscu parzysta, na drugim dowolna, na trzecim dowolna: \(\displaystyle{ 4 \cdot 6 \cdot 5=120}\)

Obydwa sposoby są oczywiście poprawne, ale różnica w ilości wykonywanych obliczeń znacząca.

W pierwszym przypadku dlatego jest ich tak dużo, że ilość możliwości wyboru trzeciej cyfry zależy od tego co wybrałeś wcześniej, dlatego też zawsze najlepiej najpierw dokonywać tych wyborów, które mają w zadaniu narzucone jakieś warunki.
Zauważ ile miałbyś pisania w twoim sposobie rozwiązania gdyby podany w zadaniu warunek nie dotyczył I i III miejsca ale np. IV i IX.

----------------------------------------------

Wracając do Twojego sposobu liczenia:

1) \(\displaystyle{ C1 \in \left\{ 6,7,8,9\right\}, C2 \in \left\{ 6,7,8,9\right\} \setminus \left\{ C1\right\}, C3 \in \left\{ 0,1,2,3,4,5\right\}}\), czyli \(\displaystyle{ 4 \cdot 3 \cdot 6 \cdot 7!}\)
2) \(\displaystyle{ C1=5, C2 \in \left\{ 6,7,8,9\right\}, C3 \in \left\{ 0,1,2,3,4\right\}}\), czyli \(\displaystyle{ 1 \cdot 4 \cdot 5 \cdot 7!}\)
3) \(\displaystyle{ C1=5, C2 \in \left\{ 0,1,2,3,4\right\}, C3 \in \left\{ 0,1,2,3,4\right\} \setminus \left\{ C2\right\}}\), czyli \(\displaystyle{ 1 \cdot 5 \cdot 4 \cdot 7!}\)

, to zapomniałeś o jednym przypadku:

1a) \(\displaystyle{ C1 \in \left\{ 6,7,8,9\right\}, C2 \in \left\{ 0;1;2;3;4;5\right\}, C3 \in \left\{ 0,1,2,3,4,5\right\} \setminus \left\{ C2\right\}}\), czyli \(\displaystyle{ 4 \cdot 6 \cdot 5 \cdot 7!}\)

[luk_rog]

Wszystko jasne. Co prawda z tego co widać w poprzednich postach nasze wyniki się nie zgadzają, ale pominąłem jeszcze jeden przypadek, ale dzięki Tobie uświadomiłem sobie, że istnieje. Dzięki!

[mat_61]

Właśnie równolegle z Twoim wpisem uzupełniłem swój post o ten brakujący przypadek w Twoim rozwiązaniu. Teraz porównując wyniki zobaczysz, że są takie same a jak widać różnica w ilości obliczeń jest znacząca (nie mówiąc o możliwości ewentualnej pomyłki).

[notokey]

Tym samym od wszystkich możliwych permutacji wystarczy odjąć te obliczone powyżej.

tzn. możesz napisać ile jest tych wszystkich możliwych permutacji. Mam już liczbę, ale chcę sobie sprawdzić, czy jest dobra.

[mat_61]

Moja uwaga:

Tym samym od wszystkich możliwych permutacji wystarczy odjąć te obliczone powyżej.

dotyczy oczywiście drugiego pytania.

Jak chcesz, żeby sprawdzić czy Twoja odpowiedź jest dobra to ją napisz i zaznacz którego pytania dotyczy.