Calcolo combinatorio

[David010]

Buon pomeriggio a tutti,
ho dei problemi a svolgere due esercizi in particolare di Calcolo Combinatorio, la stessa tipologia non sono riuscito a trovarla in altri topic ed eccomi qua, prima di postare il secondo vorrei sapere se nel primo qui di seguito ho ragionato bene oppure no.

Testo esercizio
1. Determinare il numero di terne che è possibile formare utilizzando una sola volta i numeri compresi tra 1 e 25 in modo tale
che la loro somma non sia 16.

Svolgimento
Primo dubbio, scrivendo "i numeri compresi tra 1 e 25" intende considerare anche gli estremi (ovvero 1 e 25) o solamente il range di numeri al loro interno (2-3-4-..-23-24)?
Non conoscendo nessuna formula e considerando gli estremi 1 e 25 mi sono messo a contare le terne (senza ripetizione e non contando l'ordine) che hanno somma uguale a 16 e sono:
1. $(1+2+13)$
2. $(1+3+12)$
3. $(1+4+11)$
4. $(1+5+10)$
5. $(1+6+9)$
6. $(1+7+8)$

Trovate queste terne ho utilizzato la teoria delle combinazioni semplici raggruppando i 25 numeri in gruppi di 3 e sottraendo a queste le combinazioni semplici di 13 numeri in gruppi di tre (che rappresenta le 6 triplette) con somma uguale a 16.

$C_{25,3} - C_{13,3}= ((25),(3))-((13),(3))= (25!)/(3!*(25-3)!)-(13!)/(3!*(13-3)!)= 2300-286= 2014$

Ditemi la vostra, grazie in anticipo a chi risponderà!

[Isaac888]

Ti manca $(2+3+11)$ per esempio... Non sono tutti quelli che hai trovato tu.
Intanto proverei ad utilizzare questi vincoli (senza perdita di generalità):

$x+y+z=16$
$x<y<z$
$x>0$
$z<14$

Poi noterei che $x$ non può essere troppo grande.
Magari potrebbe tornare utile osservare che $x=16-(y+z)$, dove $(y+z)$ è almeno $3$ ed è massimo $15$.
Il procedimento può essere iterato su $(y+z)$ e potresti ridurti a contare tutte le iterazioni. Magari potresti procedere dal basso verso l'alto nella conta. Cioè vedere chi può essere $(y+z)$ ad $x$ fissato. Questa è la mia idea.

Considera che $16:3$ è circa $5$, perciò se $x$ fosse più di $5$ cominceresti a ripetersi con le terne

[superpippone]

le terne che totalizzano 16, sono:
1) 1-2-13
2) 1-3-12
3) 1-4-11
4) 1-5-10
5) 1-6-9
6) 1-7-8
7) 2-3-11
8) 2-4-10
9) 2-5-9
10) 2-6-8
11) 3-4-9
12) 3-5-8
13) 3-6-7
14) 4-5-7

La soluzione è $2.300-14=2.286$

[David010]

Ringrazio entrambi per aver risposto, Isaac888 per le dritte che mi hai dato e superpippone per la scrittura di tutte le terne con la soluzione dell'esercizio.

Ora espongo il testo del secondo esercizio:
2. Determinare il numero di quaterne che è possibile formare utilizzando anche più di una volta i numeri compresi tra 1 e 10 in modo tale che la loro somma sia 21.

Svolgimento
Avendo visto la soluzione dell'esercizio precedente ho provato anche qui a scrivere le quaterne con somma uguale a 21, ragionando come segue:

$x+y+w+z= 21$
$x<y<w<z$
$x>0$

Osservando (come nel caso precedente) che $x=21-(y+w+z)$, dove $(y+w+z)$ è almeno $11$ ed è massimo $20$, ho iniziato quindi ad iterare con $x$ fissata e $y,w,z$ variabili. Sapendo che in questo caso i numeri possono ripetersi le combinazioni sono molte di più, sono arrivato a contarne $32$ dopo aver trovato le quaterne di numeri con $x=1$, $x=2$ e $x=3$ (quest'ultimo non concluso).

Sarebbe anche fattibile contarle tutte ma non in mancanza di tempo (l'esercizio è di un esame passato), esistono metodi di svolgimento migliori per quanto riguarda questa tipologia con ripetizioni?

[Isaac888]

Faccio un esempio:

$16=1+15$ dove $15=$

$2+13$
$3+12$
$...$
$7+8$

(mancante $1+14$)

Analogamente

$16=2+14$ dove $14=$

$3+11$
$...$
$6+9$

(mancanti $1+13$, $2+12$)

Sia $P_2(k)=#{(n,m)\in \mathbb{N}| n+m=k}$.
Il numero delle somme che fanno $16$, avendo notato che $x\leq 4$ (per motivi sopra spiegati) è:

$14=\sum_{i=1}^4(P_2(16-i)-i)$

Così il problema si riduce a calcolare una formula esplicita per $P_2(k)$. Lo stesso ragionamento può essere esteso a somme di più di 3 numeri (chiaramente ottenendo sommatorie miste in più di un indice).

PS: se qualcuno sa dirmi qualcosa in più sul $P_2(k)$ (magari con dimostrazione) gli sarei molto grato perché la cerco anche io da un po'un'espressione esplicita.
Per ora mi è ovvio solo che $P_2(k)\leq [\frac{k}{2}]$.

Sono arrivato a congetturare che $P_2(k)=[\frac{k}{2}]$ se $k$ è dispari, mentre è $\frac{k}{2}-1$ se $k$ è pari. Ditemi se non vi torna.

La cosa simpatica, se è vero quello che ho congetturato è che:

$P_3(k)=\sum_{i=1}^r(P_2(k-i)-i)$

dove $r$ si può calcolare facilmente. Credo che cambi di $1$ se $k$ è pari o dispari.