Funkcje niemalejące

[author]

Przepraszam, ze tworze temat podobny do jakiegos wczesniejszego... ale jest problem.
Na pewnym egzaminie bylo zadanie:
Na ile sposobow da sie utworzyc 10 literowe slowo z liter a,b,c, tak zeby po zadnym c nie wystepowalo ani a ani b, i po b zeby nie wystepowalo a (jednym slowem alfabetycznie).
Mozna to skojarzyc liczba nie malejacych ciagow 10-elementowych o wyrazach ze zbioru 3 elementowego, albo liczba funkcji niemalejacych f:{1,2,...,10} -> {a,b,c}

No i wedlug mnie jest to:
\(\displaystyle{ {n+k-1\choose k}}\)
czyli \(\displaystyle{ {12\choose 3}}\)
a w zamieszczonych odpowiedziach jest \(\displaystyle{ {12\choose 2}}\) tylko nie wiem z jakiej paki.
Prosze o utwierdzenie mnie w prawidlowej odpowiedzi.

[półpasiec]

no dobra odpowiedzia nie jest twoja
najpierw zauwaz ze moze pewna litera nie wystapic, dlatego aby pozbyc sie tej niedogodnosci rozwazymy 13 elementow i kazda literka wystapi co najmniej jeden raz, odpowiadajaca sytuacje dla 10 elementow uzyskamy odejmujac po jednym
no to teraz musisz wstawic miedzy 13 elementow, czyli do 12 przerw miedzy elementami, dwie przegrodki
o o o|o o o o o|o o o o o
wiec 12 po 2 jest dobre

[author]

no wlasnie, otoz ten wzorek co podalem on jest na liczbe niemalejacych funkcji, zgadza sie? Czyli wliczone sa takie ciagi jak (a,a,a,a,a,a,a,a,a,a)
czy (a,a,a,a,a,a,a,a,a,b) i tu nie wystepuje raz ani b ani c. a w drugim c nie wystepuje.
Nie za bardzo kumam dlaczego ten przypadek nie jest tym z funkcjami niemalejacymi...
Czy ten wzor jest po prostu zly?

-edit-
aha... czyli hmm nie zrozumialem widocznie tresci zadania... ze tu musza byc uzyte wszystkie litery a, b, c... bardzo prosilbym Cie abys jeszcze mogl cos dokladniej te metode pudelkowa przyblizyc, dlaczego akurat jest tutaj 12 i dlaczego 2 przegrodki... daloby rade?

[półpasiec]

ten wzor co podales to jest ilosc kombinacji z powtorzeniami a nie zadnych funkcji niemalejacych, chociaz mogl pasowac w jakims zadaniu, zamiast sie sugerowac tym ze gdzies tam kiedys moze i wyszlo tym sposobem, przeczytaj dokladnie to co napisalem, to chyba sie jasne wszystko zrobi

[author]

ok, ale moglbys mi jeszcze dokladniej wyjasnic skad te 2 przegrodki i 13 badz 12 ?
(apropo edit postu wyzej). Bardzoooo dziekuje z gory!
p.s fakt, wole to zrozumiec, a nie wzorkami rzucac...

[ Dodano: Wto Sie 23, 2005 2:22 pm ]
hehe, wreszcie wiem dlaczego ten wzor co podalem niby nie pasowal... po prostu zle zrozumialem n i k. k to moc dziedziny a n to moc przeciwdziedziny i wtedy mamy:
k=10, n=3
\(\displaystyle{ {10+3-1\choose 10}={12\choose 10}={12\choose 2}}\)

Badz co badz... czekam na Twoja wersje, bo ona jest bardziej swojska.

[półpasiec]

masz 10 miejsc
o o o o o o o o o o
zauwaz ze wsadzenie dwoch przegrodek np tak
o o o o|o o o o|o o
oznacza ciag aaaabbbbcc ale przegrodki moga byc wsadzone obie miedzy dwa miejsca
o o o o o o||o o o o
i oznacza to ciag aaaaaacccc
wiemy ze jesli nie bedziemy liczyc takich ciagow gdzie cos sie nie pojawia to liczba naszych ciagow bedzie rowna \(\displaystyle{ C^2_9}\) bo w 9 przerw musimyy wsadzic dwie przegrodki
no ale musimy jeszcze liczyc te gdzie np b nie wystepuje to robimy takie cos
niech \(\displaystyle{ a_ib_jc_k}\) gdzie \(\displaystyle{ i+j+k=10}\)oznacza ze a pojawilo sie i razy, b j razy, c k razy oraz \(\displaystyle{ i,j,k q 0}\)
widzimy ze mozemy jednoznacznie okreslic pary \(\displaystyle{ a_ib_jc_k a_{i+1}b_{j+1}c_{k+1}}\) no musimy juz wczesniejsza metoda policzyc ciagi dlugosci 13 a przy tym kazda liczba wystapi co najmniej jeden raz

[author]

kurczee... WIELKIE DZIEKI!!! FAJNIE! DUŻE PIWO!!!!!!