kombinatoryka Maryla27: Ile jest wszystkich dwudziestocyfrowych liczb zapisanych z użyciem tylko cyfr {0,1,2,3,4} i w których suma cyfr jest równa 6. 1|11111 1|2111 1|221 1|41 2|1111 2|211 2|22 2|4 4|11 4|2 Muszę policzyć na piechotę. Czy to są wszystkie możliwości. Jak podstawiam n=20 i k=6 do wzoru na kombinacje z powtórzeniami to wychodzi, że czegoś tutaj brakuje. Proszę o pomoc.

Adamm: gdzie jest 3?

Maryla27: Przepraszam, zbiór {0,1,2,4} bez 3.

Adamm:

19 5		19 4		19 3		19 2		19 4		19 3		19 2		19 1		19 2
	+		*4+		*3+		*2+		+		*3+		+		+		+

	19 1
+		=37544

wygląda w porządku

Maryla27: Bardzo dziękuję.

Maryla27: n=20 k=6 Wzór na kombinacje z powtórzeniami do tego zadania jest inny niż

n+k−1 k−1

Jaki? Proszę o pomoc.

Maryla27: Ponawiam prośbę.

Maryla27: Nie mogę znaleźć wzoru, żeby wyszedł ten sam wynik. Męczę się z tym zadaniem od wczoraj.

Maryla27: To jaki jest ten wzór ?

Pytający:

	n+k−1 k		n+k−1 k−1
Wzór na kombinacje z powtórzeniami to		, a nie		.

https://pl.wikipedia.org/wiki/Kombinacja_z_powt%C3%B3rzeniami Gdybyś mogła użyć cyfr {0,1,2,3,4,5,6}, wtedy wystarczyłoby policzyć 5 elementową (bo ustawiasz jedynkę na pierwszej pozycji, aby nie było tam zera) kombinację z powtórzeniami ze zbioru 20 elementowego:

20+5−1 5		24 5
	=		.

Możesz jednak użyć tylko {0,1,2,4}, zatem używając na siłę kombinacji z powtórzeniami, można by policzyć to tak (acz bardziej intuicyjne jest rozwiązanie Adamma): Rozważmy 3 przypadki (gdzie pierwsza cyfra jest ustalona): 1) 1|x₁x₂...x₁₉ x₁+x₂+...+x₁₉=5, x_i∊{0,1,2,4}

19+5−1 5		19 1		19 1	18+2−1 2		23 5		19 2
	−		−			=		−19(1+		)

19+5−1 5
	− uwzględnia to trójkę i piątkę na różnych miejscach, więc trzeba odjąć te

przypadki

19 1
	− na tylu miejscach może być piątka (zera na 18 pozostałych)

19 1	18+2−1 2
		− na jednym miejscu trójka, na pozostałych 18 mamy (2 jedynki, 16 zer) lub

(1 dwójka,17 zer), czyli właśnie taka kombinacja z powtórzeniami 2) 2|x₁x₂...x₁₉ x₁+x₂+...+x₁₉=4, x_i∊{0,1,2,4}

19+4−1 4		19 1	18 1		22 4
	−			=		−19*18

19+4−1 4
	− uwzględnia przypadki z trójką, więc trzeba to odjąć

19 1	18 1
		− na tyle sposobów można ustawić trójkę i jedynkę

3) 4|x₁x₂...x₁₉ x₁+x₂+...+x₁₉=2, x_i∊{0,1,2,4}

19+2−1 2		20 2
	=		− tu niczego odejmować nie trzeba, możemy użyć {0,1,2}

Ostatecznie:

23 5		19 2		22 4		20 2
	−19(1+		)+		−19*18+		=37544

https://www.wolframalpha.com/input/?i=(23+choose+5)-19(1%2B(19+choose+2))%2B(22+choose+4)-19*18%2B(20+choose+2)

Maryla27: Doczekałam się Bardzo, bardzo dziękuję.

Pytający: Można też policzyć w ten sposób:

24 5		21 3		20 2
	−1−19−19−		−19*		+19=37544

https://www.wolframalpha.com/input/?i=(24+choose+5)-1-19-19-(21+choose+3)-19*(20+choose+2)%2B19

24 5
	// tyle mamy liczb dwudziestocyfrowych o sumie cyfr 6

−1 // przypadek 6*10¹⁹ (6 i 19 zer) −19 // na pierwszej pozycji piątka, na jednej z pozostałych 19 pozycji jedynka −19 // na pierwszej pozycji jedynka, na jednej z pozostałych 19 pozycji piątka

	21 3
−		// na pierwszej pozycji trójka, suma pozostałych 19 cyfr równa 3

	20 2
−19*		// na jednej z 19 pozycji (poza pierwszą) trójka, na pierwszej co najmniej 1, więc

na pozostałe 19 pozycji (poza tą z trójką) dorzucamy "dwa oczka" +19 // w obu powyższych wyrażeniach odjęliśmy przypadki trójka na pierwszym miejscu i trójka na jednym z pozostałych, takich przypadków jest 19, więc dodajemy to, aby w ostatecznym rozrachunku było odjęte jednokrotnie

Pytający: I proszę bardzo.

Maryla27: Nareszcie coś mi się rozjaśnia w tym temacie. Cieszę się.