Correzione compito in classe

Considerato un particolare elemento X, l'insieme delle combinazioni con ripetizione degli n elementi 
presi k alla volta può essere suddiviso in due parti distinte:

quella delle combinazioni con ripetizione di n elementi k alla volta che non contengono l'elemento X,
cioè le combinazioni con ripetizione degli n-1 elementi diversi da X presi k alla volta;
quella delle combinazioni con ripetizione di n elementi k alla volta che contengono l'elemento X,
ciascuna con un X fisso seguito da k-1 elementi scelti ancora tra tutti, cioè le combinazioni con 
ripetizione degli stessi n elementi presi k-1 alla volta.

Indicato con CR(n,k) delle combinazioni con ripetizione di n elementi presi k alla volta, allora
	CR(n,k) = CR(n-1,k) + CR(n,k-1)
Poiché evidentemente 
	CR(1,k)=1   	per qualunque numero naturale k 
e 
	CR(n,1)=n	per qualunque numero naturale k
Si può allora calcolare valori di CR(n,k) come nel seguito a partire da una 
prima riga formata dai CR(1,k) e da una prima colonna formata dai CR(n,1)

	1	1	1	1	1	1	1	1
	2	1+2	1+3	1+4	1+5
	3	3+3	4+6	5+10	6+15
	4	6+4	10+10	15+20
	5	10+5=CR(5,2)			CR(5,6)
	6
ovvero
	1	1	1	1	1	1	1	1
	2	3	4	5	6	7
	3	6	10	15	21
	4	10	20	35
	5	15=CR(5,2)			CR(5,6)
	6
che è parte del triangolo di Pascal-Tartaglia
	1	1	1	1	1	1	1	1	1
	1	2	3	4	5	6	7
	1	3	6	10	15	21
	1	4	10	20	35
	1	5	15=C(6,2)			C(10,6)
	1	6
	1
con le righe messe in diagonale.

Come se gli n elementi fossero evidenziabili mediante k segni di spuntatura che indicano quante 
volte ripetere l'elemento. Ad esempio
	a Ö
	b ÖÖ
	c
	d ÖÖÖ
rappresenta la combinazione con ripetizione 
	abbddd
di a, b, c, d presi 6 alla volta.
Dunque contare quante combinazione con ripetizione di n elementi presi k alla volta equivale a contare 
in quanti modi diversi si possono inserire le k spuntature a fianco agli n elementi.
La prima spuntatura può essere attribuita a uno qualunque degli n elementi, in n modi diversi. 
La seconda spuntatura può essere attribuita a uno qualunque degli n-1 elementi non ancora evidenziati
e ancora a quello già evidenziato ma la seconda può essere inserita prima o dopo la precedente, in 
n-1+2=n+1 modi diversi. 
La terza spuntatura può essere attribuita: 
	a uno qualunque degli n-1 elementi non ancora evidenziati e ancora a quello già evidenziato ma 
		la terza spuntatura  può essere inserita prima, in mezzo o dopo le due già presenti, 
		in n-1+3 modi diversi;
	a uno qualunque degli n-2 elementi non ancora evidenziati e ancora a uno dei due già evidenziati ma 
		la terza spuntatura  può essere inserita prima, o dopo quella già presente, 
		in n-2+2·2 modi diversi;
in ogni caso in n+2 modi diversi. 
A ogni nuova spuntatura aumenta di un'unità il numero di possibilità.
In totale 
	n(n+1)(n+2) ... (n+k-1)
Tuttavia le spuntature sono identiche tra loro e quindi ognuna delle modalità descritta precedentemente
è ripetuta k! volte.
Ecco che infine il numero di ripetizione di n elementi presi k alla volta è
	n(n+1)(n+2) ... (n+k-1)/k!

Ad esempio si considerino le combinazioni con ripetizione di a, b, c, d presi 6 alla volta.
Mettiamo insieme i simboli
	a, b, c, d, 1, 2, 3, 4, 5.
Alcune combinazioni semplici di questi simboli, messe prima in ordine alfabetico le lettere
e poi in ordine crescente i numeri, sono
	a12345 ----> aaaaaa
	ab2345 ----> abbbbb
	ab1245 ----> aaabbb
	abc135 ----> aabbcc
	abcd14 ----> aabccd
	abcd35 ----> abccdd
	bd1235 ----> bbbbdd
	abd245 ----> abbddd

e a questi è possibile associare le combinazioni con ripetizione di a, b, c, d costruite con il seguente 
procedimento:
trascrivere come prima lettera della combinazione con ripetizione la prima lettera della combinazione semplice
passare al primo numero della combinazione semplice
ripetere
	se la posizione della combinazione con ripetizione indicata dal numero è già occupata da una lettera 
	allora
		ricopiare a fianco della combinazione con ripetizione tale lettera
	altrimenti
		trascrivere a fianco della combinazione con ripetizione la lettera seguente della combinazione semplice