Ancora combinatoria Olimpiadi

[anto_zoolander]

we ho fatto i seguenti problemi, chiederei un parere, specialmente sul primo.

Sia $X$ un insieme di $n$ elementi e sia $P(X)$ l’insieme dei sottoinsiemi di $X$. Determinare

$sum_(AinP(X))|A|$

allora io ho cominciato ricordandomi che $|P(X)|=sum_{k=0}^{n}$\(\displaystyle \binom{n}{k} \)$=2^n$

dunque gli $AinP(X)$ sono esattamente $2^n$ ora faccio questa considerazione: sto sommando le cardinalità dei vari sottoinsiemi di $X$

$|P(X)|=sum_{k=0}^{n}$\(\displaystyle \binom{n}{k} \)$=1+$ \(\displaystyle \binom{n}{1} \) $+...+ 1$

ovvero $1$ sottoinsieme con $0$ elementi, \(\displaystyle \binom{n}{1} \) sottoinsiemi con $1$ elemento.. ecc.. fino all'unico insieme che ha tutti gli elementi.

dunque certamente considerato $|A|inP(X)$ deve essere $0leq|A|leqn$ inoltre noto ogni insieme sarà composto come:

- un insieme che ha cardinalità $0$
- \(\displaystyle \binom{n}{1} \) insiemi che hanno cardinalità $1$
- \(\displaystyle \binom{n}{2} \) insiemi che hanno cardinalità $2$
...

quindi arrivo al ragionamento che:

$sum_(AinP(X))|A|=0*1+$ \(\displaystyle 1\binom{n}{1} \)$+$ \(\displaystyle 2\binom{n}{2} \)$+...+$ \(\displaystyle (n-1)\binom{n}{n-1} \)$+n$

$sum_(AinP(X))|A|=sum_{k=1}^{n}k$\(\displaystyle \binom{n}{k} \)$=sum_{k=0}^{n}(n-k)$\(\displaystyle \binom{n}{k} \)

logicamente sono arrivato al fatto che il risultato debba essere $n2^(n-1)$ solo che non so come dimostrarlo.

--------------------------------

determinare quante sono le funzioni $f:{1,2,3,4,5}->{10,11,12}$ tali che $f(1)nef(2)$

Io ho cominciato calcolando $D'_(3,5)=3^5=243$ che sono tutte le funzioni possibili. Il motivo è basato sul fatto che se calcolassi $D'_(5,3)$ considererei anche le funzioni che sono del tipo:

$f(1)=10, f(1)=11, f(1)=12$ che appunto non sono funzioni

Dunque adesso considero proprio tutte le funzioni che hanno $f(1)=f(2)$

$D'_(3,4)=3^4=81$

ora procedo togliendo dalle funzioni totali, le funzioni che non soddisfano il requisito del problema.

$D'_(3,5)-D'_(3,4)=243-81=162$

Io non ci vedo nulla di malvagio, però non si sa mai

--------------------------------

la somma $sum_{k=0}^{2005}$\(\displaystyle \binom{2005}{k} \)$(-2)^k$

questo mi sembra abbastanza banale, lo riporto con l'uguaglianza:

$sum_{k=0}^{n}$\(\displaystyle \binom{n}{k} \)$a^(n-k)b^k=(a+b)^n$ con $a=1,b=-2$

$(1+(-2))^2005 => (-1)^2005=-1$

però mi sembra troppo facile

[orsoulx]

Gli ultimi due mi sembrano corretti. Per la dimostrazione del primo ci sono percorsi diversi. Uno, puramente combinatorio, potrebbe essere sfruttare la simmetria dei coefficienti binomiali, sommando a coppie, per $ n $ dispari è immediato, nel caso pari basta poco...

Ciao
B.

[anto_zoolander]

Cavolo vero! Non ci ho proprio pensato. Peró tornerei praticamente all'uguaglianza precedente.

Tu che approccio avresti utilizzato?

[orsoulx]

Dipende dal contesto. Forse quello, forse un altro più rapido che sfrutta lo sviluppo di $ (1+x)^n $, ma che richiede la conoscenza delle derivate (almeno di un polinomio).
Curioso eh!
Ciao
B.

[anto_zoolander]

"orsoulx":Dipende dal contesto. Forse quello, forse un altro più rapido che sfrutta lo sviluppo di $ (1+x)^n $, ma che richiede la conoscenza delle derivate (almeno di un polinomio).
Curioso eh!
Ciao
B.

Le conosco mi illustri un po' il ragionamento?

[orsoulx]

Derivi ambo i membri dello sviluppo di $ (1+x)^n $ e sostituisci $ x=1 $. Finito.
Ciao
B.

[anto_zoolander]

considerando che ero a questo punto:

$sum_(AinP(X))|A|=sum_{k=1}^{n}k$\(\displaystyle \binom{n}{k} \)$=sum_{k=0}^{n}(n-k)$\(\displaystyle \binom{n}{n-k} \)

Adesso ho ottenuto che tutte quelle sono uguali a:

$sum_{j=1}^{n}sum_{k=j}^{n}$\(\displaystyle \binom{n}{k} \)$=sum_{j=1}^{n}sum_{k=0}^{n-j}$\(\displaystyle \binom{n}{k} \)

[anto_zoolander]

Non riuscendo a proseguire con la sommatoria, uso il consiglio di @Orsoulx, che ho sviluppato così:

parto da $sum_{k=0}^{n}$\(\displaystyle \binom{n}{k} \)$x^k=(1+x)^n, n,kinNN, x inRR$

derivo ambo i membri rispetto alla variabile $x$ impunemente

$sum_{k=0}^{n}k$\(\displaystyle \binom{n}{k} \)$x^(k-1)=n(1+x)^(n-1)$

naturalmente il binomiale nella derivazione lo tratto come costante.
Adesso considero il caso $x=1$

$sum_{k=0}^{n}k$\(\displaystyle \binom{n}{k} \)$=n(2)^(n-1)$

dunque in virtù della catena di uguaglianze dovrà essere:


$sum_{AinP(X)}|A|=sum_{k=0}^{n}k$\(\displaystyle \binom{n}{k} \)$=sum_{j=1}^{n}sum_{k=j}^{n} $\( \displaystyle \binom{n}{k} \)$=n*2^(n-1)$

chiedo conferme

[anto_zoolander]

Vado aggiungendo quesiti qui, così faccio un post unico.
Se può far fastidio mettetemi al corrente

Questa stavolta l'ho presa da un torneo del MIT

un comitato di $5$ persone deve essere scelto da un gruppo di $9$. In quanti modi può essere scelto, se Biff e Jacob devono esservi compresi entrambi o essere entrambi esclusi, e Alice e Jane rifiutano di farne parte assieme?

Da notare come noi uomini siamo sempre fraterni e le donne no, pure nei problemi di combinatoria

Allora io ho suddiviso il problema in tre punti, di cui due ripetuti

- Biff e Jacob fanno parte assieme
- c'è Jane$dotvee$Alice

Dunque considero $2C_(5,2)=2*(5!)/(3!*2!)=20$

Ovvero ho escluso $4$ persone e $3$ posti dai totali. L'ho considerato due volte perché devo considerare le combinazioni se è presente Jane, e le combinazioni se è presente Alice.

- Buff e Jacob non ci sono
- c'è Jane$dotvee$Alice

Considero sempre $2C_(5,2)=20$

Per lo stesso ragionamento di prima, solo che Biff e Jacob non ci sono.

- considero l'assenza di tutti.

Ma l'assenza di tutti mi dona solo $5$ posti e quindi una sola combinazione.

$20+20+1=41$ sono le combinazioni totali.

---------------------------

Quante distinte stringhe di $5$ lettere dell'alfabeto inglese (con possibile ripetizione) contengono esattamente tre lettere distinte?

Suddiviso anche quì il problema in due step: intanto le coppie possono essere del tipo

$A A ABC$ oppure $A ABBC$ dunque ragioni così:

Calcolo le combinazioni $C_(26,3)=(26!)/(23!*3!)=26*25*4$ quindi sto inizialmente considerando che appunto ci siano solo $3$ elementi, visto che comunque gli elementi distinti saranno proprio $3$.

Ora considero i singoli pezzi:

$A A A B C$ considero le permutazioni $P_{5}^{(3)}=20$
Inoltre devo considerarlo per la possibilità di scegliere i $3$ elementi

Dunque $3*20=60$ ovvero ci sono $60$ possibili permutazioni.

$A ABBC$ considero le permutazioni $p_{5}^{(2,2)}=30$

Quì ci sono $3*30=90$ permutazioni di quella tipologia. Sommando ottengo $90+60=150$ permutazioni considerando entrambe le tipologie con cui si presenta la stringa.
ora per concludere moltiplico le combinazioni ottenute, per le possibili permutazioni della stringa stessa.

$150*26*25*4=390.000$

[orsoulx]

"anto_zoolander":chiedo conferme

Sì. La dimostrazione è corretta. 'Sento' una certa ritrosia nel derivare ambo i membri dell'uguaglianza iniziale, che è una identità.
L'altro metodo che ti avevo consigliato era il seguente.
$ \sum_{k=0}^n k ((n), (k))= \sum_{k=0}^n (n-k) ((n), (n-k))= \sum_{k=0}^n (n-k) ((n), (k)) $ da cui
$ \sum_{k=0}^n k ((n), (k))=1/2 \sum_{k=0}^n [k ((n), (k))+(n-k)((n),(k))]=1/2 \sum_{k=0}^n n ((n), (k))=n/2 \sum_{k=0}^n ((n), (k))=n/2 2^n=n2^(n-1) $
Ciao
B.

[anto_zoolander]

"orsoulx":[quote="anto_zoolander"]chiedo conferme

Sì. La dimostrazione è corretta. 'Sento' una certa ritrosia nel derivare ambo i membri dell'uguaglianza iniziale, che è una identità.
L'altro metodo che ti avevo consigliato era il seguente.
$ \sum_{k=0}^n k ((n), (k))= \sum_{k=0}^n (n-k) ((n), (n-k))= \sum_{k=0}^n (n-k) ((n), (k)) $ da cui
$ \sum_{k=0}^n k ((n), (k))=1/2 \sum_{k=0}^n [k ((n), (k))+(n-k)((n),(k))]=1/2 \sum_{k=0}^n n ((n), (k))=n/2 \sum_{k=0}^n ((n), (k))=n/2 2^n=n2^(n-1) $
Ciao
B.[/quote]

Grazie mille mi mancano le proprietà sui binomiali, che noia.

[axpgn]

Ma non dovresti pensare alla maturità? Almeno per un mese ...

[anto_zoolander]

Preferisco studiare un po' di più, che non studiare matematica