Ile jest wielomianów ?
-
mol_ksiazkowy
- Użytkownik
- Posty: 13371
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3425 razy
- Pomógł: 809 razy
Ile jest wielomianów ?
Udowodnić, że jeśli \(\displaystyle{ m \geq n \geq 2}\) to ilość wielomianów stopnia \(\displaystyle{ 2n-1}\) o różnych współczynnikach ze zbioru \(\displaystyle{ \left\{ 1, ..., 2m \right\}}\) które są podzielne przez \(\displaystyle{ 1+x+...+x^{n-1}}\) jest równa \(\displaystyle{ 2^n n! \left( 4 {m+1 \choose n+1} - 3 {m \choose n} \right)}\)
Ostatnio zmieniony 15 cze 2016, o 22:29 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
Trol-24-11-2025
Re: Ile jest wielomianów ?
dla \(\displaystyle{ m=n}\) wzór jest ok
ale dla np:
\(\displaystyle{ m>n}\)
wydaje mi się, że coś się sypie np. dla: \(\displaystyle{ m=4, n=3}\) - (i to druga część wzoru ta z nawiasem), pierwsza jest ok...
przy wolnej chwili wykażę to...
najpierw niech: \(\displaystyle{ m=n}\)
weźmy wielomian stopnia: \(\displaystyle{ 2n-1}\)
\(\displaystyle{ w(x)= a_{0}+a_{1}x+a_{2}x^2+...+a_{2n-1}x^{2n-1} , a_{i}=1,2,3,...,2n }\)
pytanie brzmi ile jest tach \(\displaystyle{ w(x)}\), które dzielą się przez: \(\displaystyle{ 1+x+x^2+...+x^{n-1}}\)
przeprowadźmy działania : modulo \(\displaystyle{ 1+x+x^2+...+x^{n-1}=0}\)
\(\displaystyle{ x^{n-1}=-1-x-x^2-...-x^{n-2} }\)
\(\displaystyle{ x^n=1}\)
\(\displaystyle{ x^{n+1}=x}\)
\(\displaystyle{ x^{n+2}=x^2}\)
-
\(\displaystyle{ x^{2n-2}=x^{n-2}}\)
\(\displaystyle{ x^{2n-1}=-1-x-x^2-...-x^{n-2}}\)
podstawiając do \(\displaystyle{ w(x)}\) te równości modulo otrzymamy po uproszczeniu:
\(\displaystyle{ \left( a_{0}-a_{n-1}+a_{n}-a_{2n-1}\right) + \left( a_{1}-a_{n-1}+a_{n+1}-a_{2n-1}\right) x+...+ \left( a_{n-2}-a_{n-1}+a_{2n-2}-a_{2n-1}\right)x^{n-2}=0 }\)
żeby ten wielomian się zerował modulo musimy jego współczynniki przyrównać do zera i otrzymamy:
\(\displaystyle{ a_{0}+a_{n}=a_{n-1}+a_{2n-1}= \frac{2n(2n+1)}{2n}=2n+1 }\)
\(\displaystyle{ a_{1}+a_{n+1}=a_{n-1}+a_{2n-1} }\)
-
\(\displaystyle{ a_{n-2}+a_{2n-2}=a_{n-1}+a_{2n-1} }\)
taki ciąg równań lub inaczej:
\(\displaystyle{ a_{0}+a_{n}=a_{1}+a_{n+1}=...=a_{n-2}+a_{2n-2}=a_{n-1}+a_{2n-1}}\)
jak widać mamy \(\displaystyle{ n}\) równań dwuskładnikowych, składniki można między sobą permutować, oraz równania też, wszystkie liczby są różne, równań jest \(\displaystyle{ n}\) więc możliwości jest:
\(\displaystyle{ 2^n \cdot n!}\)
druga część wzoru to:
\(\displaystyle{ 4 {m+1 \choose n+1} -3 {m \choose n} , m=n}\)
więc będzie:
\(\displaystyle{ 4-3=1}\)
więc dla \(\displaystyle{ m=n}\) wzór jest:
\(\displaystyle{ 2^n \cdot n!}\)
i to jest ok, ale gdy:
\(\displaystyle{ m>n}\) tak gładko już nie jest...
-
więc mamy:
\(\displaystyle{ m>n}\)
i problem polega na tym ,żeby ze zbioru:
\(\displaystyle{ \left\{ 1,2,3,...,2m\right\} }\)
wybrać podzbiór:
\(\displaystyle{ x_{1}, x_{2},...,x_{2n}}\)
takich liczb gdzie:
\(\displaystyle{ x_{1}+x_{2}+...+x_{2n}=kn}\)
suma ta ma być podzielna przez \(\displaystyle{ n}\)
oraz:
\(\displaystyle{ x_{1}< x_{2}<...<x_{2n}}\)
najmniejsza i największa ta suma wynosi:
\(\displaystyle{ \min= 1+2+3+...+2n=n(2n+1)}\)
\(\displaystyle{ \max= (2m-2n+1) +(2m-2n+2)+...+2m=4mn-2n^2-n}\)
każda z nich dzieli się przez: \(\displaystyle{ n}\)
oczywiście między nimi jest cała masa sum też podzielnych przez \(\displaystyle{ n}\)
problem polega na tym, żeby je zliczyć...
\(\displaystyle{ x_{1}+x_{2}+...+x_{2n}=kn}\)
łatwo wyliczyć, że:
\(\displaystyle{ k=0,1,2,3,...,4m-4n}\)
problem też leży w tym, że dla określonego \(\displaystyle{ k}\) sum może być więcej niż jedna...
ale póki co wskaże ja to będzie np. dla:
\(\displaystyle{ m=4, n=3}\)
gdzie ze zbioru:
\(\displaystyle{ \left\{ 1,2,3,4,5,6,7,8\right\} }\)
wybieramy sześcioelementowy podzbiór ściśle rosnący, wypiszę wszystkie przypadki:
\(\displaystyle{ 1+2+3+4+5+6=21 }\)
\(\displaystyle{ 1+2+3+4+6+8=24 }\)
\(\displaystyle{ 1+2+3+5+6+7=24 }\)
\(\displaystyle{ 1+2+3+6+7+8=27}\)
\(\displaystyle{ 1+2+4+5+7+8=27}\)
\(\displaystyle{ 1+3+4+5+6+8=27}\)
\(\displaystyle{ 2+3+4+5+6+7=27}\)
\(\displaystyle{ 1+3+5+6+7+8=30}\)
\(\displaystyle{ 2+3+4+6+7+8=30}\)
\(\displaystyle{ 3+4+5+6+7+8=33}\)
razem: \(\displaystyle{ 10 }\)
najwięcej jest o sumie \(\displaystyle{ 27}\) bo aż \(\displaystyle{ 4}\), każda suma jest podzielna przez: \(\displaystyle{ n=3}\)
zgodnie z oczekiwaniami, a teraz dopasujmy drugą część wzoru dla: \(\displaystyle{ m=4, n=3}\)
wzór (2 część):
\(\displaystyle{ 4 \cdot {m+1 \choose n+1} -3 \cdot {m \choose n} =4 \cdot {5 \choose 4} -3 \cdot {4 \choose 3} }\)
\(\displaystyle{ 4 \cdot 5-3 \cdot 4=20-12=8}\)
coś brakuje więc wzór nie domaga...
postawmy problem tak:
mamy znaleźć ilość sum:
\(\displaystyle{ x_{1}+x_{2}+...+x_{2n}=kn }\)
\(\displaystyle{ x_{1}<x_{2}<...<x_{2n} }\)
\(\displaystyle{ k=0, 1, 2,..., 4m-4n}\)
najmniejsza z tych sum będzie:
\(\displaystyle{ \min=1+2+3+...+2n=2n^2+n}\)
\(\displaystyle{ \max=2m-2n+1, 2m-2n+2,...,2m=4mn-2n^2+n}\)
oraz wszystkie pomiędzy , każda suma ma dzielić się przez \(\displaystyle{ n}\), ale sum równych \(\displaystyle{ kn}\) może być więcej niż jedna...
startujemy zawsze z sumy najmniejszej dokładając kolejno: \(\displaystyle{ n, 2n, 3n,}\)....
pokaże to dla: \(\displaystyle{ m=4, n=3 }\) naszego
\(\displaystyle{ 1+2+3+4+5+6=21}\)
dokładamy trzy:
na dwa sposoby:
\(\displaystyle{ 3=2+1, 3=1+1+1}\)
\(\displaystyle{ 1+2+3+4+(5+1)+(6+2)=24}\)
\(\displaystyle{ 1+2+3+(4+1)+(5+1)+(6+1)=24}\)
potem dokładamy \(\displaystyle{ 6}\) analogicznie na sposobów:
\(\displaystyle{ 6=2+2+2 , 6=2+2+1+1, 6=2+1+1+1+1, 6=1+1+1+1+1+1}\)
jak widać dokładanie nie może u nas przekroczyć \(\displaystyle{ 8}\), a ilość dołożeń nie może być większa niż \(\displaystyle{ 6}\)
jak widać jest to zwykłe a właściwie niezwykłe partycjonowanie liczby z ograniczeniami...
uogólniając już nasze sumy możemy zmodulować najmniejszą sumą czyli:
\(\displaystyle{ 1+2+3+...+2n}\) dla większej prostoty i przejrzystości otrzymamy takie liczby do partycjonowania:
\(\displaystyle{ 0}\)
\(\displaystyle{ n}\)
\(\displaystyle{ 2n}\)
\(\displaystyle{ kn , k=0,1, 2, ..., 4m-4n}\)
będzie to partycja z ograniczeniami a mianowicie jej długość nie może przekroczyć \(\displaystyle{ 2n}\) a jej największy składnik nie może przekroczyć: \(\displaystyle{ 2m-2n}\)
będzie to:
\(\displaystyle{ p(kn, 2n, 2m-2n) , k=0, 1, 2,3,...}\)
przyjmijmy, że:
\(\displaystyle{ p(0, 2n, 2m-2n)=1}\) - żeby nie tracić zerowego składnika czyli (najmniejszej sumy)...
może jeszcze jakiś wzorek na tę partycję:
\(\displaystyle{ p(kn, 2n, 2m-2n) = \sum_{i=1}^{\min(kn,2m-2n)} p(kn-i,2n-1,i) }\)
prześledźmy jak ten wzór działa dla naszych: \(\displaystyle{ m=4,n=3}\)
gdzie wiemy, że ma wyjść: \(\displaystyle{ 10}\) możliwości:
\(\displaystyle{ k=0, 1, 2, 3, 4}\)
mamy obliczyć:
\(\displaystyle{ p(0,6,2)=1}\)
\(\displaystyle{ p(3, 6, 2)= \sum_{i=1}^{2} p(3-i,5,i)=p(2,5,1)+p(1,5,2)=1+1=2}\)
\(\displaystyle{ p(6, 6, 2)= \sum_{i=1}^{2} p(6-i,5,i)=p(5,5,1)+p(4,5,2)=1+ \sum_{i=1}^{2}p(4-i,4,i)=1+p(3,4,1)+p(2,4,2)=1+1+ \sum_{i=1}^{2}p(2-i,3,i)=2+p(1,3,1)+p(0,3,2)=2+1+1=4}\)
\(\displaystyle{ p(9,6,2)= \sum_{i=1}^{2}p(9-i,5,i)=p(8,5,1)+p(7,5,2)=0+ \sum_{i=1}^{2}p(7-i,4,i)=p(6,4,1)+p(5,4,2)=0+ \sum_{i=1}^{2}p(5-i,3,i)=p(4,3,1)+p(3,3,2)=0+ \sum_{i=1}^{2}p(3-i,2,i)=p(2,2,1)+p(1,2,2)=1+1=2}\)
\(\displaystyle{ p(12,6,2)=1}\)
bez rozpisywania widać, że będzie to jeden...
więc zliczając otrzymamy:
\(\displaystyle{ 1+2+4+2+1=10}\) - zgodnie z oczekiwaniami ( sumy jak widać są symetryczne)
więc nasz wzór na ilość wielomianów spełniających warunki zadania powinien wyglądać następująco:
\(\displaystyle{ a(m,n)=2^nn! \cdot \left[ \sum_{k=0}^{4m-4n}p(kn, 2n, 2m-2n) \right] }\)
dla: \(\displaystyle{ m=n}\) druga część wyniesie przyjmijmy:
\(\displaystyle{ \sum_{k=0}^{0}p(kn, 2n, 0)=p(0,2n,0)=1}\)
ale dla np:
\(\displaystyle{ m>n}\)
wydaje mi się, że coś się sypie np. dla: \(\displaystyle{ m=4, n=3}\) - (i to druga część wzoru ta z nawiasem), pierwsza jest ok...
przy wolnej chwili wykażę to...
najpierw niech: \(\displaystyle{ m=n}\)
weźmy wielomian stopnia: \(\displaystyle{ 2n-1}\)
\(\displaystyle{ w(x)= a_{0}+a_{1}x+a_{2}x^2+...+a_{2n-1}x^{2n-1} , a_{i}=1,2,3,...,2n }\)
pytanie brzmi ile jest tach \(\displaystyle{ w(x)}\), które dzielą się przez: \(\displaystyle{ 1+x+x^2+...+x^{n-1}}\)
przeprowadźmy działania : modulo \(\displaystyle{ 1+x+x^2+...+x^{n-1}=0}\)
\(\displaystyle{ x^{n-1}=-1-x-x^2-...-x^{n-2} }\)
\(\displaystyle{ x^n=1}\)
\(\displaystyle{ x^{n+1}=x}\)
\(\displaystyle{ x^{n+2}=x^2}\)
-
\(\displaystyle{ x^{2n-2}=x^{n-2}}\)
\(\displaystyle{ x^{2n-1}=-1-x-x^2-...-x^{n-2}}\)
podstawiając do \(\displaystyle{ w(x)}\) te równości modulo otrzymamy po uproszczeniu:
\(\displaystyle{ \left( a_{0}-a_{n-1}+a_{n}-a_{2n-1}\right) + \left( a_{1}-a_{n-1}+a_{n+1}-a_{2n-1}\right) x+...+ \left( a_{n-2}-a_{n-1}+a_{2n-2}-a_{2n-1}\right)x^{n-2}=0 }\)
żeby ten wielomian się zerował modulo musimy jego współczynniki przyrównać do zera i otrzymamy:
\(\displaystyle{ a_{0}+a_{n}=a_{n-1}+a_{2n-1}= \frac{2n(2n+1)}{2n}=2n+1 }\)
\(\displaystyle{ a_{1}+a_{n+1}=a_{n-1}+a_{2n-1} }\)
-
\(\displaystyle{ a_{n-2}+a_{2n-2}=a_{n-1}+a_{2n-1} }\)
taki ciąg równań lub inaczej:
\(\displaystyle{ a_{0}+a_{n}=a_{1}+a_{n+1}=...=a_{n-2}+a_{2n-2}=a_{n-1}+a_{2n-1}}\)
jak widać mamy \(\displaystyle{ n}\) równań dwuskładnikowych, składniki można między sobą permutować, oraz równania też, wszystkie liczby są różne, równań jest \(\displaystyle{ n}\) więc możliwości jest:
\(\displaystyle{ 2^n \cdot n!}\)
druga część wzoru to:
\(\displaystyle{ 4 {m+1 \choose n+1} -3 {m \choose n} , m=n}\)
więc będzie:
\(\displaystyle{ 4-3=1}\)
więc dla \(\displaystyle{ m=n}\) wzór jest:
\(\displaystyle{ 2^n \cdot n!}\)
i to jest ok, ale gdy:
\(\displaystyle{ m>n}\) tak gładko już nie jest...
-
więc mamy:
\(\displaystyle{ m>n}\)
i problem polega na tym ,żeby ze zbioru:
\(\displaystyle{ \left\{ 1,2,3,...,2m\right\} }\)
wybrać podzbiór:
\(\displaystyle{ x_{1}, x_{2},...,x_{2n}}\)
takich liczb gdzie:
\(\displaystyle{ x_{1}+x_{2}+...+x_{2n}=kn}\)
suma ta ma być podzielna przez \(\displaystyle{ n}\)
oraz:
\(\displaystyle{ x_{1}< x_{2}<...<x_{2n}}\)
najmniejsza i największa ta suma wynosi:
\(\displaystyle{ \min= 1+2+3+...+2n=n(2n+1)}\)
\(\displaystyle{ \max= (2m-2n+1) +(2m-2n+2)+...+2m=4mn-2n^2-n}\)
każda z nich dzieli się przez: \(\displaystyle{ n}\)
oczywiście między nimi jest cała masa sum też podzielnych przez \(\displaystyle{ n}\)
problem polega na tym, żeby je zliczyć...
\(\displaystyle{ x_{1}+x_{2}+...+x_{2n}=kn}\)
łatwo wyliczyć, że:
\(\displaystyle{ k=0,1,2,3,...,4m-4n}\)
problem też leży w tym, że dla określonego \(\displaystyle{ k}\) sum może być więcej niż jedna...
ale póki co wskaże ja to będzie np. dla:
\(\displaystyle{ m=4, n=3}\)
gdzie ze zbioru:
\(\displaystyle{ \left\{ 1,2,3,4,5,6,7,8\right\} }\)
wybieramy sześcioelementowy podzbiór ściśle rosnący, wypiszę wszystkie przypadki:
\(\displaystyle{ 1+2+3+4+5+6=21 }\)
\(\displaystyle{ 1+2+3+4+6+8=24 }\)
\(\displaystyle{ 1+2+3+5+6+7=24 }\)
\(\displaystyle{ 1+2+3+6+7+8=27}\)
\(\displaystyle{ 1+2+4+5+7+8=27}\)
\(\displaystyle{ 1+3+4+5+6+8=27}\)
\(\displaystyle{ 2+3+4+5+6+7=27}\)
\(\displaystyle{ 1+3+5+6+7+8=30}\)
\(\displaystyle{ 2+3+4+6+7+8=30}\)
\(\displaystyle{ 3+4+5+6+7+8=33}\)
razem: \(\displaystyle{ 10 }\)
najwięcej jest o sumie \(\displaystyle{ 27}\) bo aż \(\displaystyle{ 4}\), każda suma jest podzielna przez: \(\displaystyle{ n=3}\)
zgodnie z oczekiwaniami, a teraz dopasujmy drugą część wzoru dla: \(\displaystyle{ m=4, n=3}\)
wzór (2 część):
\(\displaystyle{ 4 \cdot {m+1 \choose n+1} -3 \cdot {m \choose n} =4 \cdot {5 \choose 4} -3 \cdot {4 \choose 3} }\)
\(\displaystyle{ 4 \cdot 5-3 \cdot 4=20-12=8}\)
coś brakuje więc wzór nie domaga...
postawmy problem tak:
mamy znaleźć ilość sum:
\(\displaystyle{ x_{1}+x_{2}+...+x_{2n}=kn }\)
\(\displaystyle{ x_{1}<x_{2}<...<x_{2n} }\)
\(\displaystyle{ k=0, 1, 2,..., 4m-4n}\)
najmniejsza z tych sum będzie:
\(\displaystyle{ \min=1+2+3+...+2n=2n^2+n}\)
\(\displaystyle{ \max=2m-2n+1, 2m-2n+2,...,2m=4mn-2n^2+n}\)
oraz wszystkie pomiędzy , każda suma ma dzielić się przez \(\displaystyle{ n}\), ale sum równych \(\displaystyle{ kn}\) może być więcej niż jedna...
startujemy zawsze z sumy najmniejszej dokładając kolejno: \(\displaystyle{ n, 2n, 3n,}\)....
pokaże to dla: \(\displaystyle{ m=4, n=3 }\) naszego
\(\displaystyle{ 1+2+3+4+5+6=21}\)
dokładamy trzy:
na dwa sposoby:
\(\displaystyle{ 3=2+1, 3=1+1+1}\)
\(\displaystyle{ 1+2+3+4+(5+1)+(6+2)=24}\)
\(\displaystyle{ 1+2+3+(4+1)+(5+1)+(6+1)=24}\)
potem dokładamy \(\displaystyle{ 6}\) analogicznie na sposobów:
\(\displaystyle{ 6=2+2+2 , 6=2+2+1+1, 6=2+1+1+1+1, 6=1+1+1+1+1+1}\)
jak widać dokładanie nie może u nas przekroczyć \(\displaystyle{ 8}\), a ilość dołożeń nie może być większa niż \(\displaystyle{ 6}\)
jak widać jest to zwykłe a właściwie niezwykłe partycjonowanie liczby z ograniczeniami...
uogólniając już nasze sumy możemy zmodulować najmniejszą sumą czyli:
\(\displaystyle{ 1+2+3+...+2n}\) dla większej prostoty i przejrzystości otrzymamy takie liczby do partycjonowania:
\(\displaystyle{ 0}\)
\(\displaystyle{ n}\)
\(\displaystyle{ 2n}\)
\(\displaystyle{ kn , k=0,1, 2, ..., 4m-4n}\)
będzie to partycja z ograniczeniami a mianowicie jej długość nie może przekroczyć \(\displaystyle{ 2n}\) a jej największy składnik nie może przekroczyć: \(\displaystyle{ 2m-2n}\)
będzie to:
\(\displaystyle{ p(kn, 2n, 2m-2n) , k=0, 1, 2,3,...}\)
przyjmijmy, że:
\(\displaystyle{ p(0, 2n, 2m-2n)=1}\) - żeby nie tracić zerowego składnika czyli (najmniejszej sumy)...
może jeszcze jakiś wzorek na tę partycję:
\(\displaystyle{ p(kn, 2n, 2m-2n) = \sum_{i=1}^{\min(kn,2m-2n)} p(kn-i,2n-1,i) }\)
prześledźmy jak ten wzór działa dla naszych: \(\displaystyle{ m=4,n=3}\)
gdzie wiemy, że ma wyjść: \(\displaystyle{ 10}\) możliwości:
\(\displaystyle{ k=0, 1, 2, 3, 4}\)
mamy obliczyć:
\(\displaystyle{ p(0,6,2)=1}\)
\(\displaystyle{ p(3, 6, 2)= \sum_{i=1}^{2} p(3-i,5,i)=p(2,5,1)+p(1,5,2)=1+1=2}\)
\(\displaystyle{ p(6, 6, 2)= \sum_{i=1}^{2} p(6-i,5,i)=p(5,5,1)+p(4,5,2)=1+ \sum_{i=1}^{2}p(4-i,4,i)=1+p(3,4,1)+p(2,4,2)=1+1+ \sum_{i=1}^{2}p(2-i,3,i)=2+p(1,3,1)+p(0,3,2)=2+1+1=4}\)
\(\displaystyle{ p(9,6,2)= \sum_{i=1}^{2}p(9-i,5,i)=p(8,5,1)+p(7,5,2)=0+ \sum_{i=1}^{2}p(7-i,4,i)=p(6,4,1)+p(5,4,2)=0+ \sum_{i=1}^{2}p(5-i,3,i)=p(4,3,1)+p(3,3,2)=0+ \sum_{i=1}^{2}p(3-i,2,i)=p(2,2,1)+p(1,2,2)=1+1=2}\)
\(\displaystyle{ p(12,6,2)=1}\)
bez rozpisywania widać, że będzie to jeden...
więc zliczając otrzymamy:
\(\displaystyle{ 1+2+4+2+1=10}\) - zgodnie z oczekiwaniami ( sumy jak widać są symetryczne)
więc nasz wzór na ilość wielomianów spełniających warunki zadania powinien wyglądać następująco:
\(\displaystyle{ a(m,n)=2^nn! \cdot \left[ \sum_{k=0}^{4m-4n}p(kn, 2n, 2m-2n) \right] }\)
dla: \(\displaystyle{ m=n}\) druga część wyniesie przyjmijmy:
\(\displaystyle{ \sum_{k=0}^{0}p(kn, 2n, 0)=p(0,2n,0)=1}\)