Esercizi Calcolo Combinatorio

[nico88desmo]

Un saluto a tutti
E' da circa un anno che seguo questo forum ma solo da poco mi sono registrato...ora inizio con il mio primo post

Vengo subito al dunque: sto provando a fare un esercizio sul calcolo combinatorio. Il testo è il seguente:
Quanti numeri tra 0 e 10000 ci sono tali che la somma delle loro cifre sia
(a) minore o uguale a 7?
(b) uguale a 13?

I risultati che ottengo sono i seguenti: (ho utilizzato la forma eplicita del binomilae doppio $(((n),(k))) -> ((n+k-1),(k))
a) $2 + \sum_{i=1}^7 ((i+2-1),(i));$
b) $((13+4-1),(13)) - 4 \sum_{i=10}^13 ((13-i+3-1),(13-i));$

Il primo risultato lo ottengo sommando i 2 casi "00000" e "10000" insieme a tutti gli altri casi dove la somma delle cifre è 1,...,7;
Il secondo risultato lo ottengo calcolando il numero di soluzioni della seguente equazione:
$x_1+x_2+x_3+x_4 = 13
In seguito tolgo i casi in cui le 4 variabili assumono valori > 9 in modo di considerare le var. come cifre.

Purtroppo i risultati non coincidono con quelli indicati dal mio prof, che sono:
a) $((7+5-1),(7))+1;
b) $((13+4-1),(13))-4*((3+4-1),(3));$

Cos'è che sbaglio???

Ringrazio tutti per l'attenzione.

[adaBTTLS]

benvenuto nel forum.

provo ad esprimerti qualche mia perplessità:
ciò che non mi convince nelle tue formule è il fatto che rimane invariata, nelle sommatorie, la differenza tra i due termini dei coefficienti binomiali.
per quanto riguarda le formule del tuo prof., mi ricordano i multiinsiemi, ma così come sono non riesco ancora a "vederle" in questo tipo di esercizio, perché se le cifre le prendi nell'insieme degli interi da 1 a 7 in maniera arbitraria non verificano l'altra condizione (cioè che la somma è minore o uguale a 7)...
aiutami a capire come vanno interpretati quei coefficienti.... comunque il numero del prof. l'ho ricavato in maniera diretta (331): in base alla tua richiesta forse non ti interessa come l'ho ricavato in maniera diretta, ti scrivo però brevemente il calcolo finale che lascia, come hai fatto tu, i 2 numeri estremi 0 e 10000 a parte, e calcola gli altri in base al numero (da 1 a 4) di cifre diverse da zero: $2+4*7+6*21+4*35+1*35=331$ dove nei vari prodotti il primo fattore è il numero di modi di scegliere le k posizioni (su 4) occupate dalle cifre diverse da 0, ed il secondo è dato dalla somma dei numeri di modi di scrivere i numeri da 1 a 7 come somma di k numeri diversi da 0.
spero di non sbagliare, ma provo a riportare in formule, correggendo la tua formula (a)

Un saluto a tutti
E' da circa un anno che seguo questo forum ma solo da poco mi sono registrato...ora inizio con il mio primo post

Vengo subito al dunque: sto provando a fare un esercizio sul calcolo combinatorio. Il testo è il seguente:
Quanti numeri tra 0 e 10000 ci sono tali che la somma delle loro cifre sia
(a) minore o uguale a 7?
(b) uguale a 13?

I risultati che ottengo sono i seguenti: (ho utilizzato la forma eplicita del binomilae doppio $(((n),(k))) -> ((n+k-1),(k))
a) $2 + \sum_{i=1}^7 ((i+2-1),(i));$
b) $((13+4-1),(13)) - 4 \sum_{i=10}^13 ((13-i+3-1),(13-i));$

Il primo risultato lo ottengo sommando i 2 casi "00000" e "10000" insieme a tutti gli altri casi dove la somma delle cifre è 1,...,7;
Il secondo risultato lo ottengo calcolando il numero di soluzioni della seguente equazione:
$x_1+x_2+x_3+x_4 = 13
In seguito tolgo i casi in cui le 4 variabili assumono valori > 9 in modo di considerare le var. come cifre.

Purtroppo i risultati non coincidono con quelli indicati dal mio prof, che sono:
a) $((7+5-1),(7))+1;
b) $((13+4-1),(13))-4*((3+4-1),(3));$

Cos'è che sbaglio???

Ringrazio tutti per l'attenzione.

a) $2 + \sum_{k=1}^4 ((4),(k))*[\sum_{i=1}^7 ((i-1),(k-1))]$

per la (b) valgono le stesse osservazioni, ma non ho provato ancora a ricavarla. aspetto qualche delucidazione circa il metodo del tuo prof.
verifica inoltre che la formula scritta da me dia lo stesso risultato. se ti interessa come ho ricavato il valore numerico in maniera diretta fammi sapere.
ciao.

[nico88desmo]

benvenuto nel forum.

provo ad esprimerti qualche mia perplessità:
ciò che non mi convince nelle tue formule è il fatto che rimane invariata, nelle sommatorie, la differenza tra i due termini dei coefficienti binomiali.
per quanto riguarda le formule del tuo prof., mi ricordano i multiinsiemi, ma così come sono non riesco ancora a "vederle" in questo tipo di esercizio, perché se le cifre le prendi nell'insieme degli interi da 1 a 7 in maniera arbitraria non verificano l'altra condizione (cioè che la somma è minore o uguale a 7)...
aiutami a capire come vanno interpretati quei coefficienti.... comunque il numero del prof. l'ho ricavato in maniera diretta (331): in base alla tua richiesta forse non ti interessa come l'ho ricavato in maniera diretta, ti scrivo però brevemente il calcolo finale che lascia, come hai fatto tu, i 2 numeri estremi 0 e 10000 a parte, e calcola gli altri in base al numero (da 1 a 4) di cifre diverse da zero: $2+4*7+6*21+4*35+1*35=331$ dove nei vari prodotti il primo fattore è il numero di modi di scegliere le k posizioni (su 4) occupate dalle cifre diverse da 0, ed il secondo è dato dalla somma dei numeri di modi di scrivere i numeri da 1 a 7 come somma di k numeri diversi da 0.
spero di non sbagliare, ma provo a riportare in formule, correggendo la tua formula (a)

a) $2 + \sum_{k=1}^4 ((4),(k))*[\sum_{i=1}^7 ((i-1),(k-1))]$

per la (b) valgono le stesse osservazioni, ma non ho provato ancora a ricavarla. aspetto qualche delucidazione circa il metodo del tuo prof.
verifica inoltre che la formula scritta da me dia lo stesso risultato. se ti interessa come ho ricavato il valore numerico in maniera diretta fammi sapere.
ciao.

Grazie per la risposta prima di tutto .
Ho provato a controllare al risposta b) e il risultato finale coincide, quindi in teoria la mia logica per il calcolo dovrebbe andare bene.

Per la a) invece:
- quali sono i coefficenti che non riesci a interpretare?
- del tuo calcolo con le varie somme di prodotti, il primo numero di ciascuna somma ho capito come lo ricavi, ma il secondo? Mi potresti esplicitare il modo che hai trovato i vari '7', '21', '35'?

[adaBTTLS]

dal calcolo diretto:

1. una sola cifra diversa da zero: 4 possibili posizioni... 7 è in numero dei valori che può assume quell'unica cifra diversa da zero, cioè da 1 a 7 (banale).

2. due cifre diverse da 0, 6 possibili casi per scelgliere due delle quattro posizioni, 21 è il numero dei modi per ottenere come somma un numero compreso tra 2 e 7 (considerando che sono due cifre diverse da zero): 6+5+4+3+2+1 [7= 6+1, 5+2, ... ; 6= 5+1, 4+2, ... ; ..... ; 2= 1+1]

3. tre cifre diverse da zero in 3 delle 4 posizioni: come si possono scrivere i numeri da 3 a 7 come somma di tre numeri diversi da zero?
nella formula ho scritto la sommatoria perché se non ricordo male l'elemento della sommatoria viene da una regola del calcolo combinatorio: "il numero di composizioni di k in n parti è $((k-1), (n-1))$". però dal calcolo diretto (è l'unico caso interessante da esaminare nel dettaglio) scrivo (in ordine decrescente):

5+1+1, 4+2+1, 3+3+1, 3+2+2
4+1+1, 3+2+1, 2+2+2
3+1+1, 2+2+1
2+1+1
1+1+1

tra le somme scritte sopra, ci sono 2 "terne" costituite da 3 elementi diversi tra loro, 7 "terne" costituite da due elementi uguali ed uno diverso, 2 "terne" codtituite da tre elementi uguali. considerando dunque le varie permutazioni si ottiene:
2*6+7*3+2*1=12+21+2=35
tale numero va moltiplicato per 4, perché i tre posti su quattro si possono scegliere in 4 modi.

4. analogamente al caso precedente scrivo....
4+1+1+1, 3+2+1+1, 2+2+2+1
3+1+1+1, 2+2+1+1
2+1+1+1
1+1+1+1
e dunque, per ciascuna delle somme precedenti (con i dovuti coefficienti binomiali o multinomiali): in corrispondenza a ciascuna somma attribuisco il numero delle permutazioni:
4+12+4
4+6
4
1

di nuovo un totale di 35, che però questa volta va moltiplicato per 1, visto che si occupano tutti i 4 posti disponibili.

per quanto riguarda il secondo quesito, la scorsa notte dovrei aver commesso qualche errore di calcolo, perché mi pare che dal calcolo diretto ho ottenuto 408, mentre dalla verifica della formula verrebbe 480. quando mi rispondi per farmi sapere se sono stata chiara, mi dici anche il risultato esatto dell'ultimo quesito?
inoltre mi piacerebbe sapere come il prof lega i multiinsiemi con questi esercizi. puoi darmi qualche indicazione? grazie.

[nico88desmo]

Grazie di nuovo per la risposta.
Ora ho capito il tuo ragionamento, meglio di così non ti potevi spiegare.
Ho provato a pensarci un pò per trovare un ragionamento un pò più automatico senza considerare tutti i casi, e alla fine mi sono accorto che nella risposta a) del primo post, ho commesso un errore nel scrivere gli indici della sommatoria. Infatti il risultato sarebbe:
$1 + sum_{k=0}^7 ((k+4-1),(k)).
In pratica così facendo considero il caso '10000' e aggiungo tutti i casi in cui l'equazione $\x_1+x_2+x_3+x_4 = k$ con $k=1,...,7$
In questo modo ottengo i 331 casi.
Per la risposta b) invece, il risultato finale è 480.

edit: avevo sbagliato a scrivere l'indice di partenza della sommatoria

[adaBTTLS]

prego.
ho rifatto i conti per verificare che le sommatorie "dentro parentesi quadre" dànno effettivamente come risultati 7, 21, 35, 35 (senza quindi fare tutti i casi possibili), rimangono però comunque sommatorie..., come compaiono sommatorie anche nei tuoi primi tentativi postati.
come si può passare alla formula con due addendi?
cioè il risultato del tuo prof come si ottiene? che cosa c'è alla base della teoria?
non so se chiedo troppo, ma potresti darmi anche una semplice indicazione tipo "questa è la formula di base ... dove n rappresenta ... e k rappresenta ..." ovvero "si applica il teorema ......."
ciao e grazie.

P.S. aggiungo un'osservazione all'ultimo tuo post: se fai x1+x2+x3+x4=k con k tra 1 e 7 lo 0 non lo comprendi... come fai ad ottenere il risultato esatto?

[nico88desmo]

Il mio prof. parte nel contare le k-collezioni di $I_n$ (insieme numeri interi da 1 a n) con eventualmente elementi ripetuti;
Ciascuna k-collezione la puoi identificare come n-sequenza di (k1, k2,...,kn) dove k1+k2+...+kn = k e tutti >=0;
(k1 = numero di volte che c'è '1',
k2 = numero di volte che c'è '2',
...
kn = numero di volte che c'è 'n')

esempio
10-collezione di $I_4$ = {1,1,1,2,2,2,3,3,3,4} dove la 4-sequenza è (3,3,3,1) oppure
10-collezione di $I_4$ = {1,1,2,2,2,3,3,3,4,4} dove la 4-sequenza è (2,3,3,2) o anche
10-collezione di $I_4$ = {1,1,1,1,2,2,2,2,2,2} dove la 4-sequanza è (4,6,0,0)

Per sapere il numero di k-collezioni quindi basta calcolare il numero di soluzioni dell'equazione k1+k2+...+kn=k;
Questa equazione si può immaginare come un insieme di * e | (paragone del nostro prof per farci capire meglio l'argomento ) esempio.
***|***|***|* = 10
**|***|***|** = 10
****|****** = 10.

in tutto ci sono n+k-1 posizioni. ora basta scegliere le posizioni degli asterischi (k)
Di conseguenza il numero di soluzioni dell'equazione è pari a $((n+k-1),(k))$

Spero di essermi spiegato bene

[adaBTTLS]

grazie della spiegazione. è molto chiara e mi riconduce ai coefficienti multinsiemistici.
il mio problema è ricollegare alcune formule del mio vecchio testo di analisi combinatoria: lì per esempio trovo spiegate bene le formule che ho usato io nella risposta con la doppia sommatoria, ma per quanto riguarda quello che tu hai chiamato binomiale doppio c'è un "salto" tra quella che è la normale costruzione, semplice, e quello che possono essere le applicazioni.
purtoppo devo insistere per convincermi, nonostante il calcolo diretto abbia confermato la formula del tuo prof, che la risposta al quesito "quanti numeri da 0 a 9999 hanno la somma delle cifre <=7?" è "sono tanti quanti sono i 7-sottoinsiemi di un 11-insieme"....:
io mi chiedo: perché, dopo aver distribuito "7 biglie in 4 scatole (5?)" devo prenderle tutte (o almeno tre?)? c'è forse lo spazio riservato per lo zero che io non considero?
diciamo che sono riflessioni "ad alta voce".......... non vi voglio assillare più di tanto...
il secondo quesito, che la mia mente rifiuta di trattare prima che si capisca qualche altro aspetto del meccanismo, in realtà sembrerebbe più semplice, cioè più vicino al mio modo di pensare, però è trattato dal tuo prof con lo stesso meccanismo del precedente...

ancora grazie e a presto. ciao.

[nico88desmo]

Il risultato del mio prof. nemmeno io l'ho capito, quel '5' non riesco proprio a capire da dove viene fuori...purtroppo.

Grazie anche a te per le risposte. Ciao.