Matematyka dyskretna Michał: 1. a) Ile jest liczb całkowitych między 1000 a 9999, których suma cyfr wynosi dokładnie 9? b) Ile spośród zliczanych w części (a) ma wszystkie cyfry różne od 0? 2. Ile jest relacji równoważności w zbiorze {0, 1, 2, 3}? Ad 1) https://matematykaszkolna.pl/forum/355210.html − Nie do końca rozumiem dlaczego tak to ma być zrobione. Wiem jak działa rozmieszczanie przedmiotów w pudełkach, nie do końca rozumiem skąd bierze się odpowiednio 8 i 5 (zamiast 9) w podpunktach.

Mila: a) Pierwsza cyfra nie może by równa 0, jest większa lub równa 1. Stąd suma cyfr równa 8. b) wszystkie cyfry x_i≥1

Michał: Dziękuję bardzo.

	5!
A idąc dalej, jeśli np. pierwsza cyfra ma być większa lub równa 7 wówczas mam		=
	2! * 3!

10, czyli: 7011, 7101, 7110, 7002, 7020, 7200, 8001, 8010, 8100, 9000. Jak to przełożyć, aby dokładnie jedna cyfra (niezależnie od pozycji) być większa lub równa np. 7?

Mila: Suma cyfr 9? x₁+x₂+x₃+x₄=9 i x₁≥7 (x₁+7)+x₂+x₃+x₄=9 x₁+x₂+x₃+x₄=2 liczba rozwiązań w zbiorze liczb całkowitych nieujemnych jest równa:

2+4−1 4−1		5 3		1
	=		=		*5*4*3=10
				6

2) druga cyfra ma być większa lub równa 7 x₁+x₂+x₃+x₄=9 i x₁≥1 i x₂≥7 (x₁+1)+(x₂+7)+x₃+x₄=9 x₁+x₂+x₃+x₄=1

1+4−1 4−1		4 3
	=		=4

1701,1710,2700 ,1800

Michał: Rozumiem, teraz już rozumiem i bardzo dziękuję za pomoc. Miałabyś czas i pomysł na drugie zadanie?

Mila: Czas mam, ale nie pamiętam teorii, poczekaj na Pytającego, jak nie spojrzy to poczytam coś na ten temat.

Mila: Liczba relacji równoważności. Zastosujemy liczby Stirlinga II rodzaju (chyba) S(n,1)=1, S(n,n)=1, S(n,k)=k*S(n−1,k)+S(n−1,k−1) S(4,1)=1

	23−2		24−2
S(4,2)=2*S(3,2)+S(3,1)=2*		+1=6+1=7 albo od razu S(4,2)=		=7
	2		2

	23−2
S(4,3)=3*S(3,3)+S(3,2)=3*1+		=3+3=6
	2

S(4,4)=1 Liczba relacji: 1+7+6+1=15

	2n−2
S(n,2) liczba podziałów na 2 niepuste podzbiory =
	2

Masz może odpowiedzi do zadań?

Pytający: Wszystko dobrze, Milu. Liczba relacji równoważności w zbiorze = liczba podziałów tego zbioru na rozłączne podzbiory (te podzbiory odpowiadają klasom abstrakcji), czyli tutaj ∑_k=1⁴ S(4,k)=15. https://www.wolframalpha.com/input/?i=sum+k%3D1..4+stirlings2%5B4,k%5D

Mila: Dziękuję

Michał: Mam odpowiedzi: 15. https://puu.sh/xfYak/a312c05b06.png − tutaj rozszerzona odpowiedź z podręcznika do matematyki dyskretnej. Dziękuję wam obojgu za pomoc. Dobrej nocy.

Mila:

Mila: Teoria do 2 zadania. https://edu.pjwstk.edu.pl/wyklady/mad/scb/mad12/main12_p3.html

Michał: Dziękuję. Dziwne że takie zadanie wystąpiło, gdy nie było liczby Strilinga. Dzięki za teorie, ten wzór rekurencyjny na pewno się przyda.

Pytający: Ale zauważ, że w odpowiedzi z podręcznika nie ma mowy o liczbach Stirlinga. Dla n=4 można wszystkie 15 podziałów po prostu wypisać nie znając tych liczb. Zatem pewnie "nie musisz" ich znać.

Michał: Faktycznie. Jeśli dobrze spojrzałem to do końca książki nie pojawiają się liczby Strilinga, więc tym bardziej jestem wdzięczny za pokazanie tego sposobu.