Parzysta ilość litery w słowie

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
michals95
Użytkownik
Użytkownik
Posty: 32
Rejestracja: 15 sty 2015, o 22:38
Płeć: Mężczyzna
Lokalizacja: W-wa
Podziękował: 5 razy
Pomógł: 1 raz

Parzysta ilość litery w słowie

Post autor: michals95 »

Niech \(\displaystyle{ n, m \in N}\) będą liczbami dodatnimi. Niech \(\displaystyle{ A={a_{1}, a_{2}, ... a_{m}}}\) będzie \(\displaystyle{ m}\)-elementowym zbiorem liter. Wykaż, że słów o długości \(\displaystyle{ n}\) zbudowanych z liter z \(\displaystyle{ A}\), w których litera \(\displaystyle{ a_{1}}\) występuje parzystą ilość razy jest dokładnie \(\displaystyle{ \frac{m^{n}+(m-2)^{n}}{2}}\). Myślałem sporo nad tym zadaniem, jednak bez efektów.
vicossess
Użytkownik
Użytkownik
Posty: 45
Rejestracja: 28 wrz 2015, o 20:47
Płeć: Mężczyzna
Podziękował: 8 razy
Pomógł: 4 razy

Parzysta ilość litery w słowie

Post autor: vicossess »

Mój pomysł jest taki: najpierw pozliczać ile jest takich wyrazów, gdy \(\displaystyle{ a_1}\) nie stoi na żadnym miejscu, na dwóch, na czterech etc.
Później trochę poprzekształcać wykorzystując wzór na sumę/różnicę n-tych potęg. Poniżej rozwiązanie, trochę pisane na szybko i niedopracowane, ale mam nadzieję, że poprawne
Ukryta treść:    
ODPOWIEDZ