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?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Mężczyzna Online
PostNapisane: 20 kwi 2016, o 11:24 
Użytkownik
Avatar użytkownika

Posty: 3640
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 
 Ilosc ciągów długości 8 z liter a,b,c  anq_  2
 Bijekcja między ciągami binarnymi długości n, a podzbiorami  vishera  2
 W sześciokącie foremnym o boku długości 1 umieszczono 7 punk  czerwonepomidory  1
 Sześcioliterowe słowa  kenser  7
 Ile jest słów długości 4...  AdrianXIX  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl