zliczanie zbiorow i funkcji,dwu i multimiany - zadania

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Lios
Użytkownik
Użytkownik
Posty: 18
Rejestracja: 27 mar 2012, o 18:13
Płeć: Mężczyzna
Podziękował: 1 raz

zliczanie zbiorow i funkcji,dwu i multimiany - zadania

Post autor: Lios »

Prosze o podpowiedzi odnosnie ponizszych zadan,niektore z nich bede mial jutro na kolokwium ale z wiekszoscia nie potrafie sobie sam poradzic

1.
W poczekalni do lekarza, w rzędzie złożonym z \(\displaystyle{ n}\) krzeseł, siedzi \(\displaystyle{ k}\) pacjentów, w
ten sposób, że żadni dwaj nie znajdują się na sąsiednich krzesłach. Na ile różnych
sposobów pacjenci mogą być rozsadzeni?

2.

Podaj liczbę rozwiązań równania diofantycznego:

\(\displaystyle{ x_{1}+ x_{2} + x_{3} + ... + x_{10} = 150 , x_{i} \in P}\) (całkowite dodatnie)


3.
Ile jest rozłożeń ośmiu nieatakujących się wież na szachownicy \(\displaystyle{ 8x8}\)
takich,że żadna z wież nie leży na przekątnej \(\displaystyle{ a_{1} - h_{8}}\)


4.
Rozważmy prostokąty o wierzchołkach w punktach kratowych (o obu
współrzędnych całkowitych), zawarte w kwadracie wyznaczonym przez punkty \(\displaystyle{ (0,0) i (n,n)}\).Ile istnieje takich prostokatow?

Póki co zrobiłem 2 zadanie wyszło mi \(\displaystyle{ {149\choose 9}}\),to jest dobrze?

i mam pomysł na 3 zadanie ale nie jestem pewien,czy to bedzie 8 liczba Catalana pomnozona razy dwa? tzn liczba drog pod przekatna i liczba drog nad przekatna?

Bardzo prosze o podpowiedzi nie mam kompletnie pomyslu na zadanie 1 i 4,pozdrawiam
psotek
Użytkownik
Użytkownik
Posty: 3
Rejestracja: 8 kwie 2013, o 22:07
Płeć: Mężczyzna
Lokalizacja: warszawa

zliczanie zbiorow i funkcji,dwu i multimiany - zadania

Post autor: psotek »

w pierszym mi wychodzi
\(\displaystyle{ \sum_{i=0}^{n/2} {n \choose i}}\)
w drugim chyba jest jeszcze \(\displaystyle{ x_{i} \ge i}\)
wiec odpowiedzia jest 114 nie 149 .
Lios pisze:tak jest ten warunek zapomniałem dopisac czyli wtedy \(\displaystyle{ x_{i}= y_{i} + i}\)?
to jest P z uwzglednieniem 2 warunku ( to znaczy nie będziesz mógł mieć w \(\displaystyle{ x_{1}=1}\) )
pamietaj ze musimy miec liczby naturalne nie P wiec trzba jeszcze odjac 1.
w trzecim nie jestem pewien ale po usuniecu przekatnej mamy szachownice 7X8 lub 8X7 wiec robiac to jak krate ( jesli mozna ) mamy \(\displaystyle{ {8+7 \choose 8} lub {8+7 \choose 7}}\)

w czwartym wiem zeCHYBA wychodzi \(\displaystyle{ {n+1 \choose 2} ^{2}}\)ale niewiem jak to policzyc
jutro tez mam tego kolosa i próbuje coś ogarnąć xD

to sa tylko moje domysly
Ostatnio zmieniony 8 kwie 2013, o 22:50 przez psotek, łącznie zmieniany 10 razy.
Lios
Użytkownik
Użytkownik
Posty: 18
Rejestracja: 27 mar 2012, o 18:13
Płeć: Mężczyzna
Podziękował: 1 raz

zliczanie zbiorow i funkcji,dwu i multimiany - zadania

Post autor: Lios »

tak jest ten warunek zapomniałem dopisac czyli wtedy \(\displaystyle{ x_{i}= y_{i} + i}\)?

na pewno 114?

\(\displaystyle{ x_{i}= y_{i} + i}\)?

czyli

\(\displaystyle{ y_{1} + y_{2} + ... + y_{10} + 55 = 150}\)
\(\displaystyle{ y_{1} + y_{2} + ... + y_{10} = 95}\)

zatem \(\displaystyle{ {104\choose 9}}\) mi tak wyszło


a pozostałe zadania,mozna prosic o podpowiedz?
Awatar użytkownika
yorgin
Użytkownik
Użytkownik
Posty: 12762
Rejestracja: 14 paź 2006, o 12:09
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 17 razy
Pomógł: 3440 razy

zliczanie zbiorow i funkcji,dwu i multimiany - zadania

Post autor: yorgin »

1. psotek, co jeśli \(\displaystyle{ n}\) jest nieparzyste?

2. Lios, dobrze zrobione.

3. Szukamy tak naprawdę ilości permutacji bez punktu stałego, lub jeśli znacie wielomiany wieżowe, to można się nimi posłużyć. Liczb Catalana nie znam, więc nie potwierdzę ani zaprzeczę.

4. Domyślam się, że chodzi o prostokąty o bokach równoległych do boków kwadratu? To jest istotne założenie...

Każdy taki prostokąt jest wyznaczony przez dwa wierzchołki: lewy górny i prawy dolny.
psotek
Użytkownik
Użytkownik
Posty: 3
Rejestracja: 8 kwie 2013, o 22:07
Płeć: Mężczyzna
Lokalizacja: warszawa

zliczanie zbiorow i funkcji,dwu i multimiany - zadania

Post autor: psotek »

1. n/2 zaokrglone w dól dla nieparzystych
2. nie jest dobrze bo \(\displaystyle{ x_{1} \neq 1}\) a powinno
3. czyli trzecie mam zle?
Lios pisze: Bardzo prosze o podpowiedzi nie mam kompletnie pomyslu na zadanie 1 i 4,pozdrawiam
A reszte ogarniasz (5-12)?
yorgin pisze: 4. Domyślam się, że chodzi o prostokąty o bokach równoległych do boków kwadratu? To jest istotne założenie...
Mozna to zalorzyc bo one sa na KRACIE
Pokombinowałem troszke i wyszlo mi cos takiego
\(\displaystyle{ \sum_{i=0}^{n}[ \sum_{j=0}^{n}(n-j)(n-i) ]}\)

@down : to git xD
Ostatnio zmieniony 8 kwie 2013, o 23:14 przez psotek, łącznie zmieniany 5 razy.
Lios
Użytkownik
Użytkownik
Posty: 18
Rejestracja: 27 mar 2012, o 18:13
Płeć: Mężczyzna
Podziękował: 1 raz

zliczanie zbiorow i funkcji,dwu i multimiany - zadania

Post autor: Lios »

kolejne zadania są na funkcje tworzące i dalsze tematy ktorych jeszcze nie mielismy,nie bedzie ich na kolokwium jutro
psotek
Użytkownik
Użytkownik
Posty: 3
Rejestracja: 8 kwie 2013, o 22:07
Płeć: Mężczyzna
Lokalizacja: warszawa

zliczanie zbiorow i funkcji,dwu i multimiany - zadania

Post autor: psotek »

A co z tymi zadaniami co dal nam doktorant?
ODPOWIEDZ