Permutacje z warunkami

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Permutacje z warunkami

Post autor: arek1357 »

Ile jest niezależnych układów typu:

\(\displaystyle{ a_{1} \neq a_{2} \neq ... \neq a_{n}}\)

wychodzą mi tu permutacje z powtórzeniami i ograniczeniami takimi, że w układzie nie może koło siebie być dwie równe liczby np:

\(\displaystyle{ aabcd}\) - sytuacja niedozwolona

\(\displaystyle{ abacd}\) - sytuacja dozwolona
Kartezjusz
Użytkownik
Użytkownik
Posty: 7330
Rejestracja: 14 lut 2008, o 08:31
Płeć: Mężczyzna
Lokalizacja: Z Bielskia-Białej
Podziękował: 6 razy
Pomógł: 961 razy

Permutacje z warunkami

Post autor: Kartezjusz »

Ile wartości mogą przyjąć wyrazy ciągu?
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Permutacje z warunkami

Post autor: arek1357 »

Dobre pytanie ale tym się nie interesujemy bierzemy po prostu same literki typu:

\(\displaystyle{ abab,...}\)

i nie ważne ile ta literka wyniesie dla nas istotne jest aby literki między sobą były równe lub różne-- 17 listopada 2016, 15:12 --Wyszła mi dziwna cząstkowa rekurencja.
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Re: Permutacje z warunkami

Post autor: arek1357 »

Podbijam wyszło mi tak:

Niech \(\displaystyle{ a(n,k)}\) - ilość takich układów o długości n i ilości liter k.

np:

\(\displaystyle{ n=1, k=2}\)

mamy literki: \(\displaystyle{ a,b}\)

układy sprzyjające to:

\(\displaystyle{ a,b}\)

czyli:

\(\displaystyle{ a(1,2)=2}\)

ogólnie:

\(\displaystyle{ a(1,k)=k}\)

\(\displaystyle{ a(2,1)=0}\)

\(\displaystyle{ a(2,2)=2}\)

dla:

\(\displaystyle{ n=3, k=2}\)

mamy takie układy:

\(\displaystyle{ aba,bab}\)

dla:

\(\displaystyle{ n=3, k=3}\)

\(\displaystyle{ aba,bab,aca,cac,bcb,cbc,abc,acb,bac,bca,cab,cba}\)

mamy 12.

Ogólnie:

\(\displaystyle{ a(n+1,k)=a(n,k) \cdot (k-1)}\)

Teraz proponuję znaleźć wzór jawny tej rekurencji co jest bardzo łatwe...

bo:

\(\displaystyle{ a(1,1)=1}\)

\(\displaystyle{ a(n,k)=k \cdot (k-1)^{n-1},n>1,k \ge 1}\)

Wzór na układ o długości n w których żadna literka nie ma identycznego sąsiada...


Przyznaję sobie punkt pomógł...

Kod: Zaznacz cały

 pomógł:=pomógł+1
Natomiast jeżeli chcemy, żeby każda literka była użyta chociaż raz otrzymamy wzór:

\(\displaystyle{ b(n,k)= \sum_{i=1}^{k-1}(-1)^i {k \choose k-i} a(n,k-i)}\)

lub:

\(\displaystyle{ b(n,k)= \sum_{i=1}^{k-1}(-1)^i {k \choose i} a(n,k-i)= \sum_{i=0}^{k-1}(-1)^i {k \choose i}(k-i)(k-i-1)^{n-i}}\)

Teraz może ktoś to ładnie zwinie...,

dla :

\(\displaystyle{ k>n, a(n,k)=0}\)

dla:

\(\displaystyle{ k=n,a(n,n)=n!}\)



Przyznaję sobie następny punkt pomógł...

Kod: Zaznacz cały

 pomógł:=pomógł+1
-- 25 stycznia 2018, 14:31 --Teraz podkręcam temat:

niech jednakowych literek będzie jakaś tam ilość:

np:

\(\displaystyle{ a_{i} - s_{i}, i=1,...,r}\)

n - ilość wszystkich elementów...


Zadanie:

Ile jest takich permutacji, że żadne identyczne nie stoją koło siebie, np:

\(\displaystyle{ aaaa,bb,cccc}\) - mamy cztery literki a i c oraz dwie b,

mamy tu:

\(\displaystyle{ a_{1}=a ,s_{1}=4}\)

\(\displaystyle{ a_{2}=b ,s_{2}=2}\)

\(\displaystyle{ a_{3}=c ,s_{3}=4}\)

\(\displaystyle{ n=10}\)

dopuszczalne np.: jest takie ustawienie:

\(\displaystyle{ cabcacabac}\)

niedopuszczalne np. jest:

\(\displaystyle{ aabcaccbac}\)

I oczywiście wszystkie literki tym razem muszą być wykorzystane.
ODPOWIEDZ