szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Kobieta Offline
PostNapisane: 19 kwi 2016, o 13:40 
Użytkownik

Posty: 24
Lokalizacja: warszawa
Proszę o pomoc w rozwiązaniu zadania:

Ile jest słów długości n składających się wyłącznie z liter ze zbioru: \{a,b,c,d,e,f,g,h,i,j\}, zbudowanych za pomocą liter a, b oraz zbitek pozostałych: cc, dd, ee, ff, gg, hh, ii, jj?
Góra
Mężczyzna Offline
PostNapisane: 20 kwi 2016, o 11:24 
Użytkownik
Avatar użytkownika

Posty: 3490
Lokalizacja: blisko
Ja to zadanie tak rozumiem ile jest ciągów o długości n typu:

| _..... gdzie:

| oznacza którąś z literek: a lub b

a _ oznacza którąś z dwójek: cc, dd, ee,..., jj

I chodzi o kombinacje kreseczek pionowych i poziomych tak aby długość ciągu była n.

Ciąg spełniający te warunki oznaczmy przez S(n).

I np:

S(1)=2, spełniają: a, b

S(2)=12 spełniają takie układy jak:

aa
bb
ab
ba
cc
dd
ee
ff
gg
hh
ii
jj

Czyli układy typu:

|| , _

dlaS(3) mogą spełniać układy typu:

||| , |_ , _|

dla S(4) spełniają układy typu:

|||| , ||_ , _ _ oraz permutacje między nimi

pamiętamy, że kreseczka pionowa to literka a lub b a pozioma oznacza jedną z ośmiu dwójeczek.


I ogólny wzorek:


S(n)= \sum_{i=0}^{\left[  \frac{n}{2} \right] }2^{n+i} \frac{(n-i)!}{(n-2i)!i!}

Wzór jest łączeniem wariacji i permutacji z powtórzeniem!


Jeżeli ktoś miałby wątpliwości skąd się wziął ten wzór niech pisze...

Podam schemat myślenia i analizy jak doszedłem do tego wzorku.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Przełamanie kija o długości 4 m na 3 części  Krysewski  3
 40 znaków i słowa 10-znakowe.  Bordeux  2
 Ciągi niemalejące długości 7  bitel1993  13
 [Teoria liczb] Uporządkowane sumy ustalonej długości.  emme3663  3
 Skojarzenia w grafie, minimalizacja sumy długości karawędzi.  e715489  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl