permutacje(variacje) z powtorzeniami + ograniczenie

[baniel]

Dla dobrego zrozumienia podam na przykładzie:

- mam zbiór liczb: 1,2,3,4,5
- chcę obliczyć ilość 7 elementowych permutacji(wariacji) z powtórzeniami
- ograniczenie: każda z liczb musi wystąpić przynajmniej jeden raz...

Próbowałem tak:
- wariacje z powtórzeniami - W(n,k) - no ale tutaj jest możliwe np. coś takiego (1,1,1,1,1,1,1), czyli nie występują wszystkie liczby
- permutacje z powtórzeniami - jest wzor... ale liczy się to tak, że we wzorze trzeba podać, które liczby mają się powtarzać.... czyli bym musiał po kolei robić, że najpierw powtarzają się jedynki, później dwójki i tak dalej i tak dalej....ehhh

Proszę o pomoc.... może jest jakis wzór??

Korekta ortograficzna
max

[max]

- permutacje z powtórzeniami - jest wzor... ale liczy się to tak, że we wzorze trzeba podać, które liczby mają się powtarzać.... czyli bym musiał po kolei robić, że najpierw powtarzają się jedynki, później dwójki i tak dalej i tak dalej....ehhh

W czym problem?
Możemy podzielić zbiór wszystkich wariacji z powtórzeniami na takie, w których powtarza się trzykrotnie tylko jedna liczba (możemy ją wybrać na 5 sposobów) i takie, w których powtarzają się dwukrotnie dwie liczby (możemy je wybrać na \(\displaystyle{ {5\choose 2}}\) sposobów)
\(\displaystyle{ 5\cdot \frac{7!}{3!} + {5\choose 2}\cdot \frac{7!}{2!\cdot 2!}}\)

[baniel]

nie no to ja to wiem, chodzi mi o rozwiazanie ogolne, bo np dla zbioru 50 elementowego , bede chial zrobic permutacje 200 elementowe a tego na kartce szybko nie policze... tym sposobem

Edit: z tymi liczbami troche przesadzilem(200 i 50), no ale dajmy ze zbior jest 5 elementowy a permutacja 9 elementowa.... i sam widzisz jak wiele przypadkow dochodzi...

Edit2: widze ze ktos mi bledy poprawia... przepraszam ale nie mam polskich znakow(English version of Windows:D)

[max]

Niech:
\(\displaystyle{ k}\) - liczba elementów zbioru, do którego należą wyrazy ciągu
\(\displaystyle{ n}\) - liczba wyrazów ciągu
\(\displaystyle{ l_{1}, \ldots, l_{k}}\) - wymagana minimalna liczba wystąpień w ciągu różnych elementów zbioru
\(\displaystyle{ m = n - (l_{1}+ \ldots + l_{k}) qslant 0}\)
Wtedy liczba możliwych ciągów z ograniczeniami co do liczb wystąpień odpowiednich elementów zbioru wyniesie:
\(\displaystyle{ \sum_{i_{1} + \ldots + i_{k} = m}{n\choose {l_{1} + i_{1}, \ldots, l_{k} + i_{k}}}}\)
gdzie:
\(\displaystyle{ {a\choose {b_{1}, \ldots, b_{q}}} = \frac{a!}{b_{1}!\cdot \ldots b_{q}!}, \quad a,q, b_{1}, \ldots, b_{q} \mathbb{N}}\)
W podanych przez Ciebie przykładach jest:
\(\displaystyle{ l_{1} = \ldots = l_{k} = 1\\
m = n - k}\)
I otrzymujemy nieco prostszy wzór:
\(\displaystyle{ \sum_{i_{1} + \ldots + i_{k} = m}{n\choose {1 + i_{1}, \ldots, 1 + i_{k}}}}\)
ale nie wiem czy to się da jakoś zwinąć...

[jovante]

Wtedy liczba możliwych ciągów z ograniczeniami co do liczb wystąpień odpowiednich elementów zbioru wyniesie:
\(\displaystyle{ \sum_{i_{1} + \ldots + i_{k} = m}{m\choose {i_{1},\ldots, i_{k}}}{n\choose {l_{1} + i_{1}, \ldots, l_{k} + i_{k}}}}\)

A nie powinno być?
\(\displaystyle{ \sum_{i_{1} + \ldots + i_{k} = m}{n\choose {l_{1} + i_{1}, \ldots, l_{k} + i_{k}}}}\)

Liczba składników takiej sumy to:
\(\displaystyle{ {m+k-1\choose m}}\)

[max]

Racja.. jakoś niepotrzebnie zamieszałem, sam już nie wiem dlaczego

A korzystając z zasady włączeń i wyłączeń otrzymujemy inny wzór:
\(\displaystyle{ k^{n} - k\cdot (k - 1)^{n} + {k\choose 2}(k - 2)^{n} - {k\choose 3}(k - 3)^{n} +\ldots + (-1)^{n}{k\choose k}(k - k)^{n} =\\
= \sum_{i = 0}^{k - 1}(-1)^{i}{k\choose i}(k - i)^{n}}\)
w przypadku szczególnym:
\(\displaystyle{ l_{1} = \ldots = l_{k} = 1}\)
W przypadku bardzo ogólnym można wyprowadzić wzór analogiczny, ale wygląda on raczej nieciekawie...