Funkcje tworzące ktoś: Użyj funkcji tworzących, aby znaleźć liczbę wybrania 10 piłek z dużej sterty sterty na której są piłki czerwone, białe i niebieskie jeśli: a) wybieramy co najmniej 2 piłki samego koloru b) wybieramy co najmniej 2 piłki czerwonego koloru

Pytający:

	n+k k		1
// ∑n=0∞(		(ax)n)=
			(1−ax)k+1

b)

	x2
x2+x3+x4+...=		// czerwone
	1−x

	1
x0+x1+x2+x3+x4+...=		// białe
	1−x

	1
x0+x1+x2+x3+x4+...=		// niebieskie
	1−x

x2

1

1

x2

1

2

1

*

*

=

=

−

+

=

1−x

1−x

1−x

(1−x)3

1−x

(1−x)2

(1−x)3

	n+(2−1) (2−1)		n+(3−1) (3−1)
=∑n=0∞((1−2		+		)xn)

	(n+1)(n+2)		n(n−1)
bn=1−2(n+1)+		=
	2		2

b₁₀=45 a) Na pewno dobrze napisana treść?

Mila: Pytający można to obliczyć bez funkcji tworzących w taki sposób? x₁+x₂+x₃=10−2 x₁≥2⇔

8+3−1 3−1		10 2
	=

Pytający: Można, nawet tak jest chyba najprościej, Milu. I obliczenia dobre, ale wkradł Ci się błąd w zapisie, bo albo: x₁+x₂+x₃=10, x₁≥2 albo x₁+x₂+x₃=10−2, x₁≥0

Mila: Dziękuję bardzo, tak . Chciałam dwa w jednym Pozdrawiam.

ktoś: Zapomniałem to zajrzeć, bo inne przedmioty się pojawiły. W a) miało być a) wybieramy co najmniej 2 piłki z każdego koloru ( 2 czerwone, 2 niebieskie, 2 białe) Zaraz postaram się zrozumieć to co napisaliście odnośnie b)

ktoś: a) wybieramy co najmniej 2 piłki z każdego koloru (minimum 2 czerwone, minimum 2 niebieskie, minimum 2 białe) Pisząc precyzyjniej

ktoś: W b) nie do końca rozumiem czemu akurat takie obliczenia mamy. // czym tutaj dokładnie jest x? x²+x³+x⁴+ ... x⁰+x¹+x²+x³+x⁴+ ...

ktoś: W a) mi wyszło 201

Pytający: x jest zmienną funkcji tworzącej. Generalnie poczytaj, może rozjaśni: http://wazniak.mimuw.edu.pl/index.php?title=Matematyka_dyskretna_1/Wyk%C5%82ad_7:_Funkcje_tworz%C4%85ce

	x2
x2+x3+x4+... =		odpowiada ciągowi (0,0,1,1,1,1,...)
	1−x

n−ty wyraz tego ciągu (indeksując od zera) to liczba sposobów, na które można wybrać n piłek tak, aby co najmniej 2 były tego wybranego koloru (czerwonego), dlatego dwa pierwsze wyrazy są równe 0. Z definicji funkcji tworzącej n−ty wyraz tego ciągu to współczynnik przy xⁿ jego funkcji tworzącej.

	1
x0+x1+x2+x3+x4+... =		odpowiada ciągowi (1,1,1,1,1,1,...)
	1−x

n−ty wyraz tego ciągu (indeksując od zera) to liczba sposobów, na które można wybrać n piłek danego koloru (bez żadnych ograniczeń) Po wymnożeniu funkcji tworzących odpowiadających wyborom piłek poszczególnych kolorów, otrzymana funkcja tworząca odpowiada ciągowi, którego n−ty wyraz jest liczbą sposobów wyboru n piłek z uprzednio ustalonymi ograniczeniami na wybór piłek w poszczególnych kolorach. Czyli współczynnik przy x¹⁰ wypadkowej funkcji tworzącej to szukana liczba sposobów. a) Trochę inaczej zrobię w tym podpunkcie, będzie prościej: c_k // liczba sposobów, na które można wybrać k piłek czerwonych b_k // liczba sposobów, na które można wybrać k piłek białych n_k // liczba sposobów, na które można wybrać k piłek niebieskich Wtedy zgodnie z ograniczeniami dla tego podpunktu:

	⎧	0 dla k<2
ck=bk=nk=	⎩	1 dla k≥2

Wszystkie ciągi są takie same, mają tę samą funkcję tworzącą:

	x2
∑k=0∞(ckxk)=∑k=0∞(bkxk)=∑k=0∞(nkxk)=
	1−x

Zatem funkcja tworząca szukanego ciągu to:

	x2		1
(		)3=x6*		=
	1−x		(1−x)3

	k+2 2
=x6*∑k=0∞(		xk)=

	(k+1)(k+2)
=∑k=0∞(		xk+6)=
	2

	(k−5)(k−4)
=∑k=6∞(		xk)
	2

Stąd szukany ciąg to:

	⎧	0 dla k<6
dk=	⎩	(k−5)(k−4)/2 dla k≥6

I szukana odpowiedź to:

	(10−5)(10−4)
d10=		=15
	2

Co znacznie prościej policzyć z kombinacji z powtórzeniami (sposób Mili):

(10−3*2)+3−1 3−1		6 2
	=		=15

Mila: Zgodnie z poleceniem jest Twoje rozwiązanie. Z x⁶ pięknie to rozpisałeś, w (b) nie było tego problemu. Pozdrawiam Pytającego

Pytający: W (b) nie było tego problemu, ale również można było tak rozpisać, jest prościej:

x2		n+2 2		(n+1)(n+2)
	=x2∑n=0∞(		xn)=∑n=0∞(		xn+2)=
(1−x)3				2

	(n−1)n
=∑n=2∞(		xn)
	2

I dziękuję za to umilanie, Milu. I również pozdrawiam serdecznie!

Mila: