Znaleziono 150 wyników

autor: King James
2 paź 2011, o 23:43
Forum: Kółko matematyczne
Temat: [Ciągi] Ciekawe ciągi, XII WM
Odpowiedzi: 4
Odsłony: 1200

[Ciągi] Ciekawe ciągi, XII WM

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}|...
autor: King James
2 paź 2011, o 21:45
Forum: Sekcja studencka
Temat: Informatyki: Wrocław, Kraków [TCS]
Odpowiedzi: 4
Odsłony: 1560

Informatyki: Wrocław, Kraków [TCS]

Ponieważ studiuję Informatykę Analityczną, napisze tylko o niej. [quote="patry93"]czy da się znaleźć ludzi nie uczestniczących w przeszłości w OIach/OMach i jak sobie radzą; [/quote] 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...
autor: King James
18 wrz 2011, o 23:55
Forum: Kółko matematyczne
Temat: [Kombinatoryka] Tożsamość kombinatoryczna
Odpowiedzi: 2
Odsłony: 833

[Kombinatoryka] Tożsamość kombinatoryczna

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...
autor: King James
7 wrz 2011, o 10:33
Forum: Kombinatoryka i matematyka dyskretna
Temat: Macierz sąsiedztwa
Odpowiedzi: 1
Odsłony: 637

Macierz sąsiedztwa

Macierz sąsiedztwa jest zawsze wymiaru \(\displaystyle{ n}\) na \(\displaystyle{ n}\). Istnieje kilka innych reprezentacji grafu jako macierzy, podejrzewam, że chodzi o macierz incydencji, http://en.wikipedia.org/wiki/Incidence_matrix.
autor: King James
6 wrz 2011, o 16:09
Forum: Kombinatoryka i matematyka dyskretna
Temat: Tożsamość (współczynniki dwumianowe)
Odpowiedzi: 7
Odsłony: 875

Tożsamość (współczynniki dwumianowe)

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 ...
autor: King James
30 sie 2011, o 22:51
Forum: Algebra abstrakcyjna
Temat: Twierdzenie Gallai
Odpowiedzi: 1
Odsłony: 870

Twierdzenie Gallai

\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) ...
autor: King James
30 sie 2011, o 22:38
Forum: Kombinatoryka i matematyka dyskretna
Temat: Podaj zwarty wzór na sumę:
Odpowiedzi: 4
Odsłony: 557

Podaj zwarty wzór na sumę:

\(\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}\).
autor: King James
29 sie 2011, o 00:15
Forum: Kombinatoryka i matematyka dyskretna
Temat: Suma z dwumianem
Odpowiedzi: 1
Odsłony: 351

Suma z dwumianem

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...
autor: King James
28 sie 2011, o 18:23
Forum: Kółko matematyczne
Temat: [Kombinatoryka] Kombi ze zbiorem dominującym
Odpowiedzi: 2
Odsłony: 984

[Kombinatoryka] Kombi ze zbiorem dominującym

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...
autor: King James
28 sie 2011, o 16:46
Forum: Kombinatoryka i matematyka dyskretna
Temat: Wykładnicza funkcja tworząca liczb Bernoulliego
Odpowiedzi: 1
Odsłony: 559

Wykładnicza funkcja tworząca liczb Bernoulliego

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)...
autor: King James
7 sie 2011, o 12:02
Forum: Kółko matematyczne
Temat: [MIX][Kombinatoryka] Tożsamości kombinatoryczne
Odpowiedzi: 7
Odsłony: 2072

[MIX][Kombinatoryka] Tożsamości kombinatoryczne

\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...
autor: King James
31 mar 2011, o 03:17
Forum: Kombinatoryka i matematyka dyskretna
Temat: Grafy cykle nieparzyste
Odpowiedzi: 2
Odsłony: 1693

Grafy cykle nieparzyste

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...
autor: King James
1 sie 2010, o 01:22
Forum: Matura i rekrutacja na studia
Temat: Infa pytania o studia
Odpowiedzi: 14
Odsłony: 3167

Infa pytania o studia

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...
autor: King James
7 sty 2009, o 01:47
Forum: Liczby zespolone
Temat: rozwiązać równanie
Odpowiedzi: 2
Odsłony: 581

rozwiązać równanie

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.
autor: King James
6 sie 2008, o 13:53
Forum: Kółko matematyczne
Temat: [MIX][Teoria liczb] Mini-Mix
Odpowiedzi: 14
Odsłony: 1526

[MIX][Teoria liczb] Mini-Mix

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-...