Matematyka dyskretna (kombinatoryka i rekurencja) SesjaDepresja: 1. Ile jest możliwości wyboru 6 kart z talii 52 kart tak, aby karty były dokładnie w dokładnie trzech kolorach? 2. Ile jest możliwości ułożenia 10 ponumerowanych kul do 4 szuflad A,B,C,D, przy założeniu, że żadna szuflada nie może być pusta. 3. Niech a_n bezie liczbą rozwiązań równania: x₁ + 2*x₂ + 3*x₃ = n Znajdź rekurencyjny wzór na n−ty wtraz ciągu {a_n}^∞_n=0 4. Dany jest rekurencyjny ciąg: { 1 dla n = 0 a_n = { 4 dla n = 1 { 23 dla n = 3 { 5*a_n−1 + 3*a_n−2 − 9*a_n−3 dla n ≥ 3 Znajdź wzór jawny na n−ty wyraz ciągu.

Mariusz: 4. A(x)= ∑_n=0^∞a_nxⁿ ∑_n=3^∞a_nxⁿ=∑_n=3^∞5a_n−1xⁿ+∑_n=3^∞3a_n−2xⁿ−∑_{n =3}^∞9a_n−3xⁿ ∑_n=3^∞a_nxⁿ=5x(∑_n=3^∞a_n−1xⁿ⁻¹)+3x²(∑_n=3^∞a_n−2xⁿ⁻²) −9x³(∑_n=3^∞a_n−3xⁿ⁻³) ∑_n=0^∞a_nxⁿ−23x²−4x−1=5x(∑_n=2^∞a_nxⁿ)+3x²(∑_n=1^∞a_nxⁿ) −9x³(∑_n=0^∞a_nxⁿ) ∑_n=0^∞a_nxⁿ−23x²−4x−1=5x(∑_n=0^∞a_nxⁿ−4x−1)+3x²(∑_n=0^∞a_nxⁿ − 1) −9x³(∑_n=0^∞a_nxⁿ) A(x)−−23x²−4x−1=5x(A(x)−4x−1)+3x²(A(x)−1)−9x³A(x) A(x)−23x²−4x−1=5xA(x)−20x²−5x+3x²A(x)−3x²−9x³A(x) A(x)(1−5x−3x²+9x³)=−x+1

	−x+1
A(x)=
	1−5x−3x2+9x3

Mila: 2) liczba suriekcji: f: {x₁,x₂,...x₁₀→{A,B,C,D}

	4 j
L(10,4)=∑(j=0 do 4) (−1)j*		(4−j)n=

	4 0		4 1		4 2		4 3
=		*410−		((4−1)10+		*(4−2)10−		*(4−3)10=

=4¹⁰−4*3¹⁰+6*2¹⁰−4 Albo liczby Stirliga II rodzaju 4!*S₂(10,4)=4!*34105=818520 ======================

Mila: Dobrze zapisałeś treść (4) ?

PW: 1) metodą babci pod piecem (nie znam błyskotliwego wzoru). Mając wybrane 3 kolory rozwiązujemy zadanie "na sztuki", to jest uwzględniając tylko liczbę kart w poszczególnych kolorach, a nie ich moc. Niech xj oznacza liczbę kart w wybranych kolorach. x₁+x₂+x₃=6 Mamy następujące rozwiązania: (1) (1,1,4) − trzy możliwe permutacje (2) (1,2,3) − 6 możliwych permutacji (3) (2,2,2). Uwzględniając liczbę możliwych wyborów kart w poszczególnych kolorach otrzymamy liczbę rozwiązań:

	13 1		13 4
(1') n1=		2		.3

	13 1	13 2	13 3
(2') n2=				.6

	13 2
(3') n3=		3

Ponieważ wyboru 3 kolorów spośród 4 można dokonać na 4 sposoby, wszystkich wyborów jest 4(n₁+n₂+n₃). Z rachunkami słabo, ale spróbuję: n₁=13^2.715^.3 = 362 505 n₂=13^.78^.286^.6 = 1 740 024 n₃=78³ = 474 552 (4) 4(n₁+n₂+n₃) = 10 308 324. Dla porównania: liczba wszystkich wyborów 6 kart spośród 52 jest równa

	52 6
(5)		= 20 358 520,

a więc wynik (4) nie jest głupi − mniejszy od (5).

Pytający: 1. Z włączania i wyłączania wychodzi to samo, więc raczej dobrze, PW.

4 3		3 3	3*13 6		3 2	2*13 6		3 1	1*13 6
	(			−			+			)=10308324

https://www.wolframalpha.com/input/?i=binomial(4,3)*(sum+k%3D0..2+of+((-1)%5Ek*binomial(3,3-k)*binomial((3-k)*13,6))) 3. a_n // liczba rozwiązań całkowitych nieujemnych równania : x₁+2x₂+3x₃=n b_n // liczba rozwiązań całkowitych nieujemnych równania : x₁+2x₂=n c_n // liczba rozwiązań całkowitych nieujemnych równania : x₁=n Wtedy: c_n=1 dla n≥0 b₀=c₀=1 b₁=c₁=1 b_n=c_n+b_n−2=b_n−2+1 dla n≥2 ⇒

	2n+3+(−1)n
bn=		dla n≥0 // można wyprowadzić np. funkcjami tworzącymi
	4

albo prościej ([...] to podłoga):

	n
bn=[		]+1 dla n≥0 // co widać z równania x1+2x2=n; x2 przyjmuje wartości od 0 do [n/2]
	2

a₀=b₀=1 a₁=b₁=1 a₂=b₂=2

	2n+3+(−1)n		n
an=bn+an−3=an−3+		=an−3+[		]+1 dla n≥3
	4		2

Mariusz: Wielomian 1−5x−3x²+9x³ można dość łatwo rozłożyć korzystając z trygonometrii

	−x+1
A(x)=
	1−5x−3x2+9x3

Istnieje jakiś wzór na n. pochodną tej funkcji bez rozkładu na sumę ułamków prostych ?

Mila: Zadanie (1) liczyłam tak jak PW. Mariuszu wydaje mi się, że w (4) coś z treścią jest źle.