szukanie zaawansowane
 [ Posty: 10 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 6 sty 2016, o 18:20 
Użytkownik

Posty: 1439
Lokalizacja: Warszawa
Pytanie nie jest z kombinatoryki, ale szeroko pojęta matematyka dyskretna wydała mi się najlepszą kategorią.

Zastanawiam się nad zagadnieniem maksymalnego współczynnika wielomianowego przy uogólnieniu dwumianu Newtona. Przykładowo: Dla jakich wartości 0\le k_1,k_2,k_3\le 12, gdzie k_1+k_2+k_3=12, współczynnik {12 \choose k_1,k_2,k_3} =\frac{12!}{k_1!\cdot k_2!\cdot k_3!} jest największy?
Jedyne, co udało mi się wymyślić, to wyznaczenie 13 kandydatów na ten współczynnik i porównanie ich. Ciekawe, że wynik jest dość zgodny z intuicją: k_1=k_2=k_3=4. Można by się ogólnie spodziewać, że takie współczynniki będą się maksymalizować przy możliwie równomiernym podziale na składniki. Nie widzę jednak narzędzi, którymi można by to sprawnie zbadać. Szczególnie w przypadku ogólnym: {n \choose k_1,k_2,\ldots,k_m}. Czy ktoś ma jakieś wiadomości na temat tego zagadnienia?
Góra
Mężczyzna Offline
PostNapisane: 6 sty 2016, o 20:05 
Użytkownik
Avatar użytkownika

Posty: 3469
Lokalizacja: blisko
Największy współczynnik jest przy:

x^4y^4z^4

a w przypadku ogólnym gdy różnica między:

dla każdego:

i,j:i \neq j.: |k_{i}-k_{j}|=0 \vee 1
Góra
Mężczyzna Offline
PostNapisane: 6 sty 2016, o 20:14 
Użytkownik

Posty: 1439
Lokalizacja: Warszawa
Bardzo fajnie, ale skąd to wiadomo?
Góra
Mężczyzna Offline
PostNapisane: 6 sty 2016, o 20:17 
Użytkownik
Avatar użytkownika

Posty: 3469
Lokalizacja: blisko
Hm sam nie wiem ale chyba nauczyłem się tego w szkole i przyjąłem jako prawdę objawioną od mojej pani.
Inaczej tego nie umiem nazwać.
Góra
Mężczyzna Offline
PostNapisane: 6 sty 2016, o 21:28 
Użytkownik

Posty: 1439
Lokalizacja: Warszawa
Wydaje mi się to dość nietrywialne. To jakaś gruba szkoła musiała być. Nawet o zwykłym dwumianie Newtona niewiele się mówi (jeśli już w ogóle), a co dopiero o wielomianie Newtona i własnościach jego współczynników.
Góra
Mężczyzna Offline
PostNapisane: 6 sty 2016, o 22:49 
Użytkownik
Avatar użytkownika

Posty: 3469
Lokalizacja: blisko
W sumie tak ale z drobną korektą gruba to była pani nasza "ot fszystkiego"

Ale jak widać Symbol Newtona po rozpisaniu wygląda jak piramida i zawsze widać, że maksymalne wartości są pośrodku, podobnie możesz sobie rozpisywać uogólniony symbol Newtona!
Góra
Mężczyzna Offline
PostNapisane: 6 sty 2016, o 23:09 
Użytkownik

Posty: 1439
Lokalizacja: Warszawa
OK, ale intuicję to ja miałem, zanim zacząłem cokolwiek liczyć ;) Stwierdzenie, że "mogę sobie rozpisać i zobaczyć" jest dość dalekie od matematycznej ścisłości. Akurat dla zwykłego symbolu Newtona łatwo jest wykazać, że największa wartość współczynnika jest "w środku".
Góra
Mężczyzna Online
PostNapisane: 6 sty 2016, o 23:31 
Użytkownik
Avatar użytkownika

Posty: 13142
Lokalizacja: Wrocław
Ja bym na to nie wpadł, ale możesz spojrzeć tutaj.
Za to nie mogę się dogrzebać do rozwiązania wspomnianego ogólniejszego zagadnienia, tj. maksymalizacji \frac{n!}{ \prod_{i=1}^{m} k_{i}!}, gdzie n=k_{1}+...+k_{m}. Ale pewnie nie umiem szukać.
Góra
Mężczyzna Online
PostNapisane: 7 sty 2016, o 07:17 
Użytkownik

Posty: 15818
Lokalizacja: Bydgoszcz
Uzasadnienie wynika z wypukłości funkcji \log\Gamma(x). Zachodzi k!=\Gamma(k+1).

Mamy
\log (k!l!m!)=\log\Gamma(k+1)+\log\Gamma(m+1)+\log\Gamma(m+1)\geq 3\log\Gamma\left(\frac{k+l+m}{3}+1\right)=3\log 4!

z równością gdy k=l=m=4.

Oczywiście gdy k+l+m nie dzieli sie na 3, największych wartości należy szukać w pobliżu

Podobnie postępuje się w przypadku większej ilości zmiennych.
Góra
Mężczyzna Offline
PostNapisane: 7 sty 2016, o 12:43 
Użytkownik

Posty: 1439
Lokalizacja: Warszawa
Wielkie dzięki! Dla trzech składników kombinowałem właśnie w takim kierunku jak w tym linku, ale zabrakło mi prostego pomysłu z porównaniem (k_1-1)!(k_2+1)! z k_1!k_2!. Czułem natomiast, że dla dowolnego rozbicia sprawa musi wymagać jakichś mocniejszych narzędzi. Bardzo dziękuję, a4karo! Wychodzi na to, że temat powinienem był zamieścić raczej w dziale "Analiza matematyczna" :).
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 10 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Podzielność współczynnika  Adam17632  4
 Wyznaczanie współczynnika wielomianu  luca1011  1
 Enumeratory - postać współczynnika przy x^k  MatXXX  2
 Algorytm RSA - obliczanie współczynnika d  Seahawk  1
 Rozpisywanie współczynnika dwumiennego  Adam17632  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl