NWD, dwie funkcje

[killerone]

Witam, jestem nowy na forum.

Mam problem z kilkoma zadaniami z mat. dyskretnej

1. Obliczyć \(\displaystyle{ NWD (3211,7163)}\)
2. Obliczyc \(\displaystyle{ P(11,7)}\) i wyznaczyć \(\displaystyle{ S(7,4)}\)

Na razie te dwa, będę wdzięczny za pomoc

pzdr

[blost]

slyszales o czyms takim jak algorytm euklidesa ? dzieki temu zrobisz 1.
nie wiem co oznaczaja funkcje P i S
jakbys mogl napisac to moze latwiej byloby pomoc.

[jarek001]

Co do pierwszego to jak coś to będzie szło tak
\(\displaystyle{ NWD(3211,7163)}\)
\(\displaystyle{ 7163 = 2*3211 + 741}\)
\(\displaystyle{ 3211 = 4*741 + 247}\)
\(\displaystyle{ 741 = 3*247 + 0}\)
Czyli w tym przypadku \(\displaystyle{ NWD =247}\)

a w drugim wydaje mi się, że może mu chodzić o liczbę Stirlinga
czyli o ten wzór
\(\displaystyle{ S(n,k) = S(n-1,k-1) + k*S(n-1,k)}\)
a tutaj założenia:
\(\displaystyle{ S(n,k) = 0 \ , \ gdy \ k>n \vee k=1}\)
\(\displaystyle{ S(n,k) = 1 \ , \ gdy \ n=k}\)

ale nie jestem pewny czy w ogóle o to chodzi

[killerone]

Co do pierwszego to jak coś to będzie szło tak
\(\displaystyle{ NWD(3211,7163)}\)
\(\displaystyle{ 7163 = 2*3211 + 741}\)
\(\displaystyle{ 3211 = 4*741 + 247}\)
\(\displaystyle{ 741 = 3*247 + 0}\)
Czyli w tym przypadku \(\displaystyle{ NWD =247}\)

a w drugim wydaje mi się, że może mu chodzić o liczbę Stirlinga
czyli o ten wzór
\(\displaystyle{ S(n,k) = S(n-1,k-1) + k*S(n-1,k)}\)
a tutaj założenia:
\(\displaystyle{ S(n,k) = 0 \ , \ gdy \ k>n \vee k=1}\)
\(\displaystyle{ S(n,k) = 1 \ , \ gdy \ n=k}\)

ale nie jestem pewny czy w ogóle o to chodzi

dokładnie o to chodziło, dzięki wielkie

[jarek001]

Nie ma problemu, tylko przydałoby się aby ktoś lepszy jeszcze to sprawdził

[killerone]

Próbuje rozwiazac nastepny przykład

\(\displaystyle{ NWD(5166,2499)}\)
\(\displaystyle{ 5166 = 2*2499 + 168}\)
\(\displaystyle{ 2499 = 14*168 + 147}\)

Natomiast w drugim

\(\displaystyle{ S(7,3)=S(6,2)+3*S(6,3)}\)


i co dalej?

I jeszcze takie zadanie

Ile jest liczb, mniejszych lub równich od 130 względnie pierszych ze 130?-- 13 wrz 2009, o 16:31 --w tym pierwszym wyszło mi ze NWD to 21, mógłby ktos to sprawdzić i zobzcyc drugie zadanie?

[BSP]

Dla liczb Stirlinga II rodzaju zachodzi własnoś:

\(\displaystyle{ S(n,k)=\frac{1}{k!} \sum_{i=0}^{k}(-1)^i{k\choose i}(k-i)^n}\)

Czyli otrzymujemy coś takiego:

\(\displaystyle{ S(7,4)=\frac{1}{4!} \sum_{i=0}^{4}(-1)^i{4\choose i}(4-i)^7 = \frac{1}{24}(4^7-4*3^7+6*2^7-4)=350}\)

\(\displaystyle{ S(7,4) = 350}\)

Pozdrawiam

PS. Jeżeli potrzebujesz więcej własności liczb Stirlinga zajrzyj tutaj: ... dKind.html