Coefficienti binomiali.

Messaggioda karl » 20/03/2004, 16:56

Navigando sulla rete mi sono imbattuto in
questo problema:

<b>Trovare il numero M dei coefficienti dispari
nello sviluppo polinomiale di (x+1)^n
(n intero positivo)</b>

Personalmente sono riuscito a trovare solo qualche
(insoddisfacente) risultato parziale ,calcolato
piu' che altro in modo euristico.Per es. sembra
che nel caso di n=2^k (k>0) risulti costantemente M=2
ed altri casi che non ho provato fino in fondo.
Forse la mia strategia e' sbagliata:
volete provare voi a trovare una soluzione completa ?
karl.
karl
 

Messaggioda Pachito » 20/03/2004, 18:29

Auguri per i 500... <img src=icon_smile.gif border=0 align=middle>
Pachito
Junior Member
Junior Member
 
Messaggio: 120 di 488
Iscritto il: 11/02/2004, 12:30

Messaggioda karl » 20/03/2004, 18:57

Ringrazio sentitamente.
karl.
karl
 

Messaggioda Pachito » 20/03/2004, 19:00

Mi sembra difficile poter dare una risposta con un n generico...
Confermo che nel caso di n = 2^k risulti costantemente M=2 e aggiungerei banalmente M=n per n = 2^k - 1, M = 4 per n = 2^k + 1 e così via...
Pachito
Junior Member
Junior Member
 
Messaggio: 121 di 488
Iscritto il: 11/02/2004, 12:30

Messaggioda anonymous_af8479 » 21/03/2004, 11:39

Sono d'accordo, trovare una formula generale per n mi sembra arduo.

Per il momento mi accontento di un formula iterativa che ricostruisce il triangolo di Tartaglia a partire da n = 1 con la regola ovvia (P=pari, D=dispari) :

P + P = P
P + D = D
D + P = D
D + D = P

La formula può essere ottimizzata notando che si presentano tutti D quando n = 2^m-1 .

La formula è trasformabile in un semplicissimo programmino al computer per cui mi considero soddisfatto.

Naturalmente c'è di mezzo il "tempo macchina" che cresce al crescere di n , onde la soluzione non è il massimo dal punto di vista matematico, ma chi si accontenta ... gode.

Bye.

ps. poi l'analisi combinatoria non mi ha mai entusiasmato ...
anonymous_af8479
Advanced Member
Advanced Member
 
Messaggio: 62 di 2076
Iscritto il: 29/02/2004, 09:54

Messaggioda karl » 23/03/2004, 20:46

Andando piu' che altro ad intuito e senza pretese
di verita' matematica,sarei giunto a questa conclusione:
Sia M il numero dei coeff. dispari ,risulta che:

<b>
M=2^k
essendo k il numero degli addendi che figurano nella scomposizione
di n nella somma di potenze del 2
</b>

Faccio qualche esempio:
0)n=7
n=2^2+2^1+2^0,k=3--->M=2^3=8

1)n=9
n=2^3+2^0,k=2---->M=2^2=4

2)n=11
n=2^3+2^1+2^0,k=3---->M=2^3=8

3)n=16
n=2^4,k=1----->M=2^1=2

In maniera piu' "scientifica" si potrebbe dire che k corrisponde
al numero delle cifre "1" che compaiono nella rappresentazione
binaria del numero n.
Forse si puo' tentare una dimostrazione per induzione completa:
ma come?
karl.
karl
 

Messaggioda anonymous_af8479 » 23/03/2004, 21:47

Geniale karl !!!

Ho verificato la tua formula al computer fino a n = 22. Poi ho dei problemi strani di conversione tipi dati per cui devo rifare il programma.

Direi a questo punto che la formula richiede solo una verifica rigorosa.

Bye.

Modificato da - arriama il 23/03/2004 21:59:29

Modificato da - arriama il 23/03/2004 23:18:19
anonymous_af8479
Advanced Member
Advanced Member
 
Messaggio: 73 di 2076
Iscritto il: 29/02/2004, 09:54

Messaggioda anonymous_af8479 » 24/03/2004, 09:29

Il computer conferma !!!

Mi sono spinto fino a n = 500 (crepi l'avarizia !).

Per la dimostrazione pensavo che potrebbe entrarci il fatto che le regole di composizione dei Pari e Dispari :

P + P = P
P + D = D
D + P = D
D + D = P

sono analoghe alla regola della somma in binario :

0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 10

Però mi fermo qui ... preferisco le funzioni, integrali ecc.

Complimenti ancora per la brillante soluzione, karl.

Bye.
anonymous_af8479
Advanced Member
Advanced Member
 
Messaggio: 75 di 2076
Iscritto il: 29/02/2004, 09:54


Torna a Algebra, logica, teoria dei numeri e matematica discreta

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite