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
Permutacje z warunkami
-
- 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
- arek1357
- Użytkownik
- Posty: 5747
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 526 razy
Permutacje z warunkami
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.
\(\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.
- arek1357
- Użytkownik
- Posty: 5747
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 526 razy
Re: Permutacje z warunkami
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ł...
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ł...
-- 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.
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
\(\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
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.