Liczba permutacji zbioru

[stiifii]

Witam, mam problem z jednym zadaniem, a mianowicie:

Znajdź liczbę permutacji zbioru \(\displaystyle{ A=\left\{1,...,n\right\}}\) , gdzie liczby podzielne przez \(\displaystyle{ 5}\) nie są obok siebie.

Przychodzi mi do głowy kilka rozwiązań:
a. układam wszystkie liczby podzielne przez \(\displaystyle{ 5}\) : \(\displaystyle{ \left( \bigg\lfloor \frac{n}{5} \bigg\rfloor\right)! \cdot \left( n-\bigg\lfloor \frac{n}{5}\bigg\rfloor\right)!}\)
b. korzystając z zasady włączeń–wyłączeń:
\(\displaystyle{ A}\) – wszystkie możliwości; \(\displaystyle{ |A|=n!}\)
\(\displaystyle{ X_{i}}\) – i liczb podzielnych przez \(\displaystyle{ 5}\) jest obok siebie
\(\displaystyle{ X_{2} = \left( \bigg\lfloor \frac{n}{5} \bigg\rfloor\right) \cdot \left( \bigg\lfloor \frac{n}{5} \bigg\rfloor -1\right) \cdot \left( n-1\right)!}\)
\(\displaystyle{ X_{i} = \sum_{k=0}^{\lfloor \frac{n}{5} \rfloor} \left( -1\right)^{k+1} \left( \bigg\lfloor \frac{n}{5} \bigg\rfloor -k\right) \cdot \left( \bigg\lfloor \frac{n}{5} \bigg\rfloor -k-1)\right) \cdot \left( n-1-k\right)!}\)
I do \(\displaystyle{ A}\) dodajemy powyższą sumę.

[arek1357]

Twój wzór nie gra..

Powinno raczej być:

\(\displaystyle{ S=n!- \sum_{i=2}^{s}(-1)^i {s \choose i}(n-i+1)! \cdot i!}\)

Gdzie \(\displaystyle{ s}\) to ilość liczb podzielnych przez pięć...

Zauważ, że wzór ten jest uniwersalny działa na n - elementach oraz dowolnych s przedziałkach,
w ten sposób, że przedziałki nie stoją koło siebie, np:

masz trzy literki i trzy liczby:

\(\displaystyle{ a,b,c,1,2,3}\)

I teraz masz tak je ułożyć aby literki nie stały koło siebie, z doświadczenia masz:

\(\displaystyle{ a12b3c}\) - jest tu.: \(\displaystyle{ 3! \cdot 3!}\) - możliwości

\(\displaystyle{ a1b23c}\) - jest tu.: \(\displaystyle{ 3! \cdot 3!}\) - możliwości

\(\displaystyle{ 1a2b3c}\) - jest tu.: \(\displaystyle{ 3! \cdot 3!}\) - możliwości

\(\displaystyle{ a1b2c3}\) - jest tu.: \(\displaystyle{ 3! \cdot 3!}\) - możliwości

Razem:

\(\displaystyle{ 4 \cdot 36=144}\)

A teraz podłóżmy pod ten wzór:

\(\displaystyle{ n=6, s=3}\)

mamy:

\(\displaystyle{ 6!- \sum_{i=2}^{3}(-1)^i {3 \choose i}(6-i+1)! \cdot i!= 720- {3 \choose 2} \cdot 5! \cdot 2!+ {3 \choose 3} \cdot 4! \cdot 3!=}\)

\(\displaystyle{ =720-3 \cdot 120 \cdot 2+1 \cdot 24 \cdot 6=720-720+144=144}\)