Matematyka.pl

1. Dany jest ciąg a_n taki, że \sum_{d|n}^{}a_d=2^n . Udowodnij, że n|a_n Uogólnijmy twierdzenie zamienijąc 2 na stałą k \geq 2 . Dany ciąg jest jednoznacznie wyznaczony, pokażemy, że a_n = p_n , gdzie p_n oznacza liczbę n -literowych słów pierwotnych nad alfabetem \mathcal{A} , gdzie |\mathcal{A}|...

Ponieważ studiuję Informatykę Analityczną, napisze tylko o niej. czy da się znaleźć ludzi nie uczestniczących w przeszłości w OIach/OMach i jak sobie radzą; Na moim roku, studia licencjackie skończyło 14 osób, w tym 7 osób z przeszłością olimpijską (finał OI lub OM), co nie jest absolutnie żadnym wy...

Dla wygody zamienimy n na n+1 , następnie k na n-k i podzielimy tożsamość przez 2 otrzymując \sum_{k=0}^{n} {n+k \choose n} 2^{n-k} = \frac{1}{2}2^{2n+1} Policzymy liczbę podzbiorów zbioru \{0,...,2n\} które zawierają co najmniej n+1 elementów (jest ich tyle samo co podzbiorów zawierających co najwy...

Macierz sąsiedztwa jest zawsze wymiaru \(\displaystyle{ n}\) na \(\displaystyle{ n}\). Istnieje kilka innych reprezentacji grafu jako macierzy, podejrzewam, że chodzi o macierz incydencji, .

Rozważmy X = \{0,...,n-1\} , niech \mathbf{P}_k(X) oznacza zbiór podzbiorów co najwyżej k elementowych zbioru X , niech \phi(j,Y) = |\{i \ | \ i > j, \ i \in Y\}| . Lewa strona równości jest równa |\mathbf{P}_k(X)| , spróbujemy podzielić podzbiory co najwyżej k elementowe zbioru X na pewne klasy, w ...

\nu(G)+\rho(G) = |V| Weźmy dowolne skojarzenie M realizujące \nu(G) , w celu otrzymania pokrycia krawędziowego dołóżmy do niego po jednej krawędzi sąsiedniej z każdym wierzchołkiem V-V(M) (nie ma wierzchołków izolowanych). Skonstruowane pokrycie jest wielkości |M|+(|V|-2|M|) = |V|-|M| \geq \rho(G) ...

\(\displaystyle{ \sum_{k=0}^{m}(-1)^k{n \choose k} {n \choose m-k} = \begin{cases} (-1)^{\frac{m}{2}}{n \choose \frac{m}{2}} \ \ \text{gdy} \ 2 \ | \ m \\ 0 \qquad \qquad \quad \text{gdy} \ 2 \not | \ m \end{cases}}\)

Rozważ współczynnik przy \(\displaystyle{ x^m}\) w splocie funkcji \(\displaystyle{ (1-x)^n}\) i \(\displaystyle{ (1+x)^n}\).

Idea w porządku, jednak jest trochę niedociągnięć, kulki powinny być rozróżnialne. \sum_{i=0}^n i^2 {n \choose i}^2 = n^2 {2n-2 \choose n-1} Rozważmy liczbę czwórek (X,Y,a,b) takich, że X \subset \{1,...,n\} , Y \subset \{n+1, ..., 2n\} , |X|+|Y|=n , a \in X , b \in \{n+1, ... , 2n\}-Y . Zinterpretu...

Niech G=(V,E) , ustalmy p \in (0,1) , wybierzmy losowo podzbiór wierzchołków V_1 \subset V , przy czym każdy wierzchołek z V wybieramy niezależnie z prawdopodobieństwem p . Chcemy do naszego V_1 dołożyć wierzchołki, które razem z V_1 będą tworzyły zbiór dominujący, niech więc V_2 będzie zbiorem wier...

Zwykły splot, przekształćmy rekurencję \sum_{i=0}^m {m \choose i} B_{m-i} = B_m + [m=1] B(z) = \sum_{m \geq 0} \frac{B_m z^m}{m!} B(z) + z = \sum_{m \geq 0} \sum_{i=0}^m {m \choose i} B_{m-i} \frac{z^m}{m!} = \sum_{m \geq 0} z^m \sum_{i=0}^m \frac{1}{i!} \cdot \frac{B_{m-i}}{(m-i)!} = e^z \cdot B(z)...

\sum_{i \geq 0} {i \choose m} x^i = \frac{x^m}{(1-x)^{m+1}} Kombinatorycznie można to pokazać licząc liczbę całkowitych nieujemnych rozwiązań równania x_1+...+x_{m+1} = i-m lub niekombinatorycznie rozwijając (1-x)^{\alpha} , dla \alpha=-m-1 albo wykorzystując f. tworzącą dwóch zmiennych indeksowany...

Alternatywne podejście. Możemy się ograniczyć do jednej spójnej składowej. Rozważmy drzewo rozpinające DFS grafu G ukorzenione w wierzchołku v . Przypiszmy każdemu wierzchołkowi jego głębokość w drzewie modulo 2 . Tak otrzymane kolorowanie jest poprawne, gdyż w przeciwnym razie gdyby dwa wierzchołki...

Jako student po 2 roku informatyki analitycznej dodam swoją opinię. Zgadzam się z Adamem Romanem, co do pracy w branży IT, raczej nikt nie wymyśla algorytmów, tylko przeważnie przechodzi przez proces zarządzania projektem. Algorytmika jest jednak istotna ponieważ, rozwija studentów, uczy nie tylko s...

Wskazówka :
\(\displaystyle{ (z+2)^n+(z-2)^n=0 \iff ft(\frac{z+2}{z-2}\right)^n=-1}\)

Swoją drogą w poleceniu oryginalnego zadania nie było sumy potęg tylko różnica.

8. Niech p to liczba pierwsza >3. i weźmy wielomian p(x)=(x-1)(x-2)....(x-(p-1)) . Wykaż, że p^2 | p^\prime(0) . p'(x)=\left(\prod_{i=1}^{p-1}(x-i)\right)'=\sum_{j=1}^{p-1}\prod_{i=1 \atop i\neq j }^{p-1}(x-i)=\sum_{j=1}^{p-1}\frac{1}{x-j}\prod_{i=1}^{p-1}(x-i) p'(0)=-\sum_{j=1}^{p-1}\frac{(-1)^{p-...