szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 14 lis 2016, o 11:16 
Użytkownik
Avatar użytkownika

Posty: 3272
Lokalizacja: blisko
Ile jest niezależnych układów typu:

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:

aabcd - sytuacja niedozwolona

abacd - sytuacja dozwolona
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 14 lis 2016, o 11:23 
Użytkownik

Posty: 7361
Lokalizacja: Z Bielskia-Białej
Ile wartości mogą przyjąć wyrazy ciągu?
Góra
Mężczyzna Offline
PostNapisane: 14 lis 2016, o 12:27 
Użytkownik
Avatar użytkownika

Posty: 3272
Lokalizacja: blisko
Dobre pytanie ale tym się nie interesujemy bierzemy po prostu same literki typu:

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.
Góra
Mężczyzna Offline
PostNapisane: 24 sty 2018, o 11:24 
Użytkownik
Avatar użytkownika

Posty: 3272
Lokalizacja: blisko
Podbijam wyszło mi tak:

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

np:

n=1, k=2

mamy literki: a,b

układy sprzyjające to:

a,b

czyli:

a(1,2)=2

ogólnie:

a(1,k)=k

a(2,1)=0

a(2,2)=2

dla:

n=3, k=2

mamy takie układy:

aba,bab

dla:

n=3, k=3

aba,bab,aca,cac,bcb,cbc,abc,acb,bac,bca,cab,cba

mamy 12.

Ogólnie:

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

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

bo:

a(1,1)=1

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:
1
 pomógł:=pomógł+1


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

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

lub:

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 :

k>n, a(n,k)=0

dla:

k=n,a(n,n)=n!



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

Kod:
1
 pomógł:=pomógł+1


-- 25 stycznia 2018, 14:31 --

Teraz podkręcam temat:

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

np:

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:

aaaa,bb,cccc - mamy cztery literki a i c oraz dwie b,

mamy tu:

a_{1}=a ,s_{1}=4

a_{2}=b ,s_{2}=2

a_{3}=c ,s_{3}=4

n=10

dopuszczalne np.: jest takie ustawienie:

cabcacabac

niedopuszczalne np. jest:

aabcaccbac

I oczywiście wszystkie literki tym razem muszą być wykorzystane.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 4 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 permutacje z powtórzeniami  toomi  1
 permutacje, całkowitoliczbowe rozwiązania równania itp. - zadanie 2  andzia_92  0
 permutacje - zadanie 12  kropq  1
 permutacje - na ile sposobow...  bartek_siekiera  2
 Digrafy i permutacje  rra  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl