Corso prime: Pb. 18.1

[a.matichecchia]

Salve, sono uno studente liceale, ho seguito la prima lezione del corso del prof. Callegari. E provando ad eseguire gli esercizi proposti ho trovato difficoltà nel problema numero 18:

18) Quante sono le funzioni crescenti (contando anche quelle che sono solo debolmente crescenti) da A={1,2,3,4,5} a B={1,2,3,4,5,6,7}.

Io ho provato a risolvere in questo modo:

calcolo prima le funzioni strettamente crescenti allora dati n,m ∈ A trovo f(n)=x e f(m)=y tali che n<m ⇒ f(n)<f(m)
e quindi scelti 5 numeri a caso dall'insieme B esiste solo un'insieme di funzioni strettamente crescenti, di conseguenza riformulo questa parte del problema: in quanti modi posso scegliere 5 numeri da B. Trovo che posso sceglierli in $ \frac{7!}{5! * 2!} $ quindi in 21 modi, di conseguenza ho 21 funzioni strettamente crescenti.

Passo a calcolare le funzioni debolmente crescenti ragionando in questo modo:
1) scelti 4 numeri da B ho 4 insiemi di funzioni debolmente crescenti, dato che ho $ \frac{7!}{4!*3!} = 35 $ modi per scegliere 4 numeri a caso da B
moltiplicando $ 35 *4 = 140 $ trovo tutte le funzioni debolmente crescenti che partono da A e arrivano a 4 elementi di B.

2) con lo stesso ragionamento per 3 numeri da B ho 10 funzioni, dati 35 modi per scegliere 3 numeri ho 350 funzioni.

3) per 2 numeri ho 4 funzioni, dati 21 modi per scegliere 2 numeri ho 84 funzioni.

4) per 1 numero ho 1 funzione, dati 7 modi per scegliere 1 numero ho 7 funzioni.

In totale sommando ho 602 funzioni strettamente e debolmente crescenti. Mentre il risultato ne prevede 492. Dov'è il mio errore?

[wall98]

Il risultato corretto è 462 vero?

In questo caso, se non sbaglio (non garantisco), è errato il punto 2 in quanto secondo me per raggiungere 3 numeri in B hai $\binom{4}{2}=6$ funzioni.

Se il risultato è giusto spiego perchè

[Enigmatico]

Che sognifica che scelti b numeri da B hai a funzioni?

[AlexThirty]

In questo caso, se non sbaglio (non garantisco), è errato il punto 2 in quanto secondo me per raggiungere 3 numeri in B hai $\binom{4}{2}=6$ funzioni.

Se il risultato è giusto spiego perchè

EDIT: mi sa che hai ragione e forse ho capito il tuo metodo, se hai voglia spiegalo.

[Ratman98]

Forse sbaglio , ma anch'io ne conto 462. Infatti le combinazioni con ripetizione di 5 elementi scelti tra i 7 del secondo insieme di numeri sono 462. E ad ognuna di queste combinazioni corrisponde esattamente una funzione strettamente o debolmente crescente( cioè tutte quelle che ci interessano).

[a.matichecchia]

Forse sbaglio , ma anch'io ne conto 462. Infatti le combinazioni con ripetizione di 5 elementi scelti tra i 7 del secondo insieme di numeri sono 462. E ad ognuna di queste combinazioni corrisponde esattamente una funzione strettamente o debolmente crescente( cioè tutte quelle che ci interessano).

E io non capisco: perchè contare le combinazioni con ripetizioni di 5 numeri scelti fra i 7? @Ratman98 puoi farmi qualche esempio di corrispondenza fra una combinazione e un'insieme di funzioni?

[Ratman98]

Ad esempio le combinazioni con ripetizione comprendono tutti i sottoinsiemi di 5 elementi del secondo insieme ed a ciascuno di essi corrisponde una funzione crescente. Ad esempio tra questi c'è $B=\{4,5,6,7,2\}$ al quale corrisponde la funzione strettamente crescente $f(1)=2$,$f(2)=4$, $f(3)=5$, $f(4)=6$, $f(5)=7$.Ma con le combinazioni con ripetizione ho anche contato insiemi di 5 elementi come $B=\{1,3,3,5,5\} $al quale corrisponde la funzione $f(1)=1$,$f(2)=3$,$f(3)=3$,$f(4)=5$,$f(5)=5$ che è debolmente crescente.Spero di essere stato chiaro .

[Enigmatico]

Rilancio la mia domanda: non ho capito come fai a determinare le funzioni diverse, mi potresti fare un esempio (a me vengono numeri diversi...)? Poi, non sono riuscito a trovare un modo furbo per trovarle, quindi le ho contate a mano, tu come hai fatto?

[a.matichecchia]

Ad esempio le combinazioni con ripetizione comprendono tutti i sottoinsiemi di 5 elementi del secondo insieme ed a ciascuno di essi corrisponde una funzione crescente. Ad esempio tra questi c'è $B=\{4,5,6,7,2\}$ al quale corrisponde la funzione strettamente crescente $f(1)=2$,$f(2)=4$, $f(3)=5$, $f(4)=6$, $f(5)=7$.Ma con le combinazioni con ripetizione ho anche contato insiemi di 5 elementi come $B=\{1,3,3,5,5\} $al quale corrisponde la funzione $f(1)=1$,$f(2)=3$,$f(3)=3$,$f(4)=5$,$f(5)=5$ che è debolmente crescente.Spero di essere stato chiaro .

Ho capito perfettamente e mi sempre il metodo più furbo e coerente per risolverlo. In pratica nel tuo metodo il problema viene riformulato in questo modo: in quanti modi posso scegliere 5 palline da 7 tipi, vero?. Solo che mi rimane un dubbio: dov'era la pecca nel mio ragionamento?

[a.matichecchia]

Rilancio la mia domanda: non ho capito come fai a determinare le funzioni diverse, mi potresti fare un esempio (a me vengono numeri diversi...)? Poi, non sono riuscito a trovare un modo furbo per trovarle, quindi le ho contate a mano, tu come hai fatto?

All'inizio le ho contate a mano. Cioè per 5 numeri distinti è ovvio che la funzione sia unica.

Per 3 numeri io prendo i 5 numeri numeri da A 1 x 2 x 3 x 4 x 5 dove ho messo la x per me c'è uno spazio.
E prendo i 3 numeri da B={1,2,3} il mio obbiettivo è mettere 2 separatori in 2 dei 4 spazi, in quanti modi posso farlo? Per ogni modo corrisponderà una funzione, ad esempio: 1 2 \ 3 4 \ 5 per me sarà $f(1)=1$,$f(2)=1$,$f(3)=2$,$f(4)=2$,$f(5)=3$ oppure
1 \ 2 3 4 \ 5 per me sarà $f(1)=1$,$f(2)=2$,$f(3)=2$,$f(4)=2$,$f(5)=3$
in quanti modi posso mettere 2 separatori in 4 spazi. In $ \frac{5!}{3! * 2!} $ cioè 10.

[AlexThirty]

Provo a dare una mia soluzione.

Potremmo usare la formula già pronta delle combinazioni di $ n $ elementi in $ k $ posti con possibile ripetizione come ha detto Ratman:
$ \binom{n+k-1}{k}=\frac{(7+5-1)!}{5!(7-1)!}=462 $
Ma così è troppo facile. Quindi proviamo a analizzare come ha fatto a.matichecchia

Per le funzioni strettamente crescenti vale quello che ha detto a.matichecchia
Sono quindi $ 21 $

Passiamo ora a quelle debolmente crescenti.

1) Caso 1: da B prendiamo 4 valori.
Questi 4 valori possono essere presi in $ \binom{7}{4}=35 $ modi. Ora pensiamo al numero che può ripetersi. Chiaramente avrò 4 casi possibili e non mi devo fare neanche tanti problemi riguardo alla sua posizione o da che $ f(x) $ deriva, tanto saranno sicuramente in ordine crescente. Quindi ho in tutto $ 140 $ casi

2) Caso 2: da B prendiamo 3 valori.
Questi 3 valori li prendo in $ \binom{7}{3}=35 $ modi. Ora vediamo quelli che si ripetono: sono tra questi 3 e ne prendo 2 (anche con possibile ripetizione), quindi ci sono (usiamo la formula) $ \binom{3+2-1}{2}=6 $ casi. Casi totali: $ 210 $.

3) Caso 3: da B prendiamo 2 valori.
Questi li scelgo in $ \binom{7}{2}=21 $ modi. Ne avanzano 3 che sono le ripetizioni da assegnare. Quindi ci sono (sempre con possibili ripetizioni) 2 numeri da assegnare in 3 posti $ \binom{2+3-1}{3}=4 $ casi. In tutto $ 84 $ casi.

4) Caso 4: da B prendiamo 1 valore.
Ci sono $ 7 $ casi.

In tutto i casi sono $ 21+140+210+84+7=462 $

La formula che ho citato all'inizio è molto bella da usare in questi casi ed è comodissima. IO ho cercato di darti una spiegazione più approfondita al tuo metodo, ma comunque l'ho usata. Ecco una breve dimostrazione.

Immagina di dover risolvere questo problema: dire quante sono le terne ordinate di numeri non negativi tali che $ a+b+c=n $ con $ n $ fissato.
Pensalo cosi, hai $ n $ blocchi in fila, e ne aggiungi due, ora tra questi $ n+2 $ blocchi ne devi togliere due tra di essi, in modo tale che si creino tre "segmenti" di blocchi intervallati da spazi vuoti (un segmento può anche essere di zero blocchi). Così poi potremo dire che il primo segmento è $ a $, il secondo segmento è $ b $ e il terzo è $ c $. Questo funziona perchè togliendo due blocchi si ritorna ad averne $ n $, quindi se li contiamo siamo a posto; ma abbiamo ora una cosa molto comoda, cioè che li abbiamo divisi in 3 insiemi indipendenti, ma che possono anche avere lo stesso numero di blocchi (e qui ci risulta utile per il fatto della ripetizione).
Come li scelgo i due blocchi da togliere? Beh in $ \binom{n+2}{2} $ modi.
Ora torniamo a noi, questo poteva essere fatto con un qualsiasi numero $ k $ di interi la cui somma doveva dare $ n $. Ma il risultato è sempre lo stesso siccome aggiungeremo $ k-1 $ scatole, avremo cioè $ \binom{n+k-1}{k-1} $. Ma attenzione! Questi sono ordinati, ma noi li vogliamo non ordinati (l'ordine non conta) e la formula diventa $ \binom{n+k-1}{k} $ (in pratica si divide per k, anche se non so perché questo passaggio so fa così quindi se qualcuno di più esperto può aiutarmi lo ringrazio)
P.S. Questa dimostrazione non è mia ma di un mio amico e mi è stata detta tempo fa, un grazie a lui

[Ratman98]

Dopo essermi complimentato con AlexThirty per l'ottima formalizzazione ( dovresti aver capito dove sbagli) , sì ho proceduto similmente a come si fa quando ho 7 sette ceste con palline di colore differente per ogni cesta e voglio sapere in quanti modi posso scegliere 5 di esse. Che poi è la stessa cosa di quando voglio contare le n-uple di numeri interi non negativi la cui somma vale $k$, con $k$ positivo.
@AlexThirty sono combinazioni con ripetizione e non disposizioni. Giusto per essere pignolo .

[AlexThirty]

Ops corretto

[wall98]

EDIT: mi sa che hai ragione e forse ho capito il tuo metodo, se hai voglia spiegalo.

Il mio metodo è il tuo metodo
E non lo spiegherei meglio di quanto l'abbia spiegato tu


In ogni caso c'era comunque un modo ricorsivo, che unito alla soluzione che abbiamo dato (usando la formula delle combinazioni con ripetizione) dimostra che:

$\displaystyle \binom{n}{k}=\sum_{i=k-1}^{n-1} \binom{i}{k-1}$ (che poi questa identità si dovrebbe dimostrare in tanti modi)

[AlexThirty]

Quello si chiama teorema della mazza da hockey mi sembra, e si vede bene nel triangolo di tartaglia