zasada włączeń i wyłączeń - ciągi asdf: Ile jest różnych ciągów długości 2n takich, że każda liczba i ∈ {1, . . . , n} występuje dokładnie dwa razy, przy czym żadne dwa kolejne wyrazy nie są równe. Skorzystać z zasady włączeń i wyłączeń.

Adamm:

(2n)!		n 1	(2n−1)!
	− (			−
2n			2n−1

	n 2	(2n−2)!		n n
−			+ ... + (−1)n+1		n!)
		2n−2

asdf: Próbuję sobie to wyobrazić, jednak potrzebuję rozwinięcia poszczególnych składników Czy mógłbyś prosze opisać po krótce jak do tego doszedłeś?

asdf: podbij

jc: Wszystkich ciągów mamy (2n)!/2ⁿ. Po prostu rozkładasz liczby 1,1',2,2',...,n,n' na (2n)!, ale k i k' to to samo więc wszystko dzielisz przez 2ⁿ. Pomyśl teraz, że k liczb źle leży. Niech to będą ustalone liczby.

	(2n−k)!
Takich ciągów mamy		.
	2n−k

	n k
Ale k liczb możemy wybrać na		sposobów.

asdf: No tak, jakie to proste.... Dziekuję pięknie!

jc: Mamy jeszcze wzór rekurencyjny. x₁=0, x₂=1, x_n+1=(2n+1)x_n+x_n−1 dla n ≥ 1. Wynik zadania = x_n*n! x₃=5 x₄=7*5+1=36 a więc dla n=4 mamy 36*24 ciągów.

asdf: Jeszcze takie pytanie mi naszło podczas analizy tego: "Pomyśl teraz, że k liczb źle leży. Niech to będą ustalone liczby" dlaczego wybieramy k liczb z n wszystkich skoro mamy 2n wszystkich?

jc: Wybierasz liczby, nie miejsca. Masz n liczb, a każda z nich powtarza się dwa razy.

asdf: a z tym ze sie na przemian zamienia to + to − to z czego wynika?

asdf: znaczy... wiem, że tak jest w zasadzie włączeń i wyłączeń, jednak nie potrafie tego sobie wyobrazić na tym konkrentym przykładzie