Filtriamo insieme

Calcolo combinatorio (disposizioni, permutazioni e combinazioni) e calcolo delle probabilità.

Filtriamo insieme

Messaggioda Rho33 » 21/04/2016, 13:53

Il valore della somma

$\displaystyle\sum_{i=0}^{33}\binom {99}{3i}$ può essere espresso nella forma $\dfrac {a^b+c}{d}$ . Trovare $a+b+c+d$


Bonus: Generalizzare con $n,k \in \mathbb{N}$ generici. Cioè, cosa posso dire del valore della somma:

$\displaystyle\sum_{i=0}^{n}\binom {n}{ki}$ con $n,k$ fissati ?



P.S. Per completezza $\displaystyle\binom {n}{k}=0$ per $k>n$

Hint per il bonus:
Testo nascosto:
Il problema è equivalente a trovare il numero di sottoinsiemi di $A= \{1,2,...,n \} $ il cui numero di elementi è divisibile per $k$
Ultima modifica di Rho33 il 26/04/2016, 18:02, modificato 1 volta in totale.
Rho33
 
Messaggi: 489
Iscritto il: 16/09/2014, 11:14

Re: Filtriamo insieme

Messaggioda carlotheboss » 21/04/2016, 16:02

O ho capito male il problema generale oppure è il numero di elementi del sottoinsieme ad essere divisibile per $k$ (e non la loro somma) perché sui casi piccoli non torna D:
Comunque il caso "piccolo" dovrebbe uscire $\dfrac{2^{99}-2}{3}$ per induzione (che non riesco a fare funzionare sul bonus)
Ultima modifica di carlotheboss il 21/04/2016, 16:24, modificato 3 volte in totale.
carlotheboss
 
Messaggi: 65
Iscritto il: 17/02/2016, 16:12

Re: Filtriamo insieme

Messaggioda carlotheboss » 21/04/2016, 16:21

carlotheboss ha scritto:O ho capito male il problema generale oppure è il numero di elementi del sottoinsieme ad essere divisibile per $k$ (e non la loro somma) perché sui casi piccoli non torna D:

Mi spiego meglio, ad esempio se scelgo $n = k = 4$ il problema mi chiede di calcolare $\binom{4}{0} + \binom{4}{4} = 2$ mentre se considero $A = \{1, 2, 3, 4\}$ posso scegliere 3 sottoinsiemi tali che la loro somma è divisibile per $4$ (cioé $k$): $\{4\}$, $\{1, 3\}$, $\{1, 3, 4\}$ (oppure 4 se considero l'insieme vuoto).
carlotheboss
 
Messaggi: 65
Iscritto il: 17/02/2016, 16:12

Re: Filtriamo insieme

Messaggioda mr96 » 21/04/2016, 17:11

L'hintone sta nel titolo, ma se non si conosce la teoria non aiuta molto...
mr96
 
Messaggi: 1486
Iscritto il: 11/02/2014, 20:37

Re: Filtriamo insieme

Messaggioda carlotheboss » 21/04/2016, 17:18

Purtroppo non penso di conoscerla essendo uno "nuovo", potresti dirmi di cosa si tratta precisamente?
carlotheboss
 
Messaggi: 65
Iscritto il: 17/02/2016, 16:12

Re: Filtriamo insieme

Messaggioda Rho33 » 26/04/2016, 17:51

Sì, ora edito, intendo il numero di elementi divisibile per $k$! Ok, il caso piccolo e semplice va bene, anche se, come suggerisce mr96, c'è una soluzione molto molto molto più figa che ovviamente si generalizza. Anche io ho scoperto sta cosa da poco, che ti pare! Comunque il problema lo lascio ancora per un po' in caso qualcuno sia interessato :lol:

Come hint 1:
Testo nascosto:
come si calcola la somma dei coefficienti di un polinomio ?


Hint 2:
Testo nascosto:
e la somma dei coefficienti di grado pari?


Hint 3:
Testo nascosto:
Ora la parte più difficile, trova la somma dei coefficienti con esponente multiplo di $3$ e generalizza.
Rho33
 
Messaggi: 489
Iscritto il: 16/09/2014, 11:14


Torna a Combinatoria e Probabilità

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite