Coefficients binomiaux

par **lapras** » 21 Fév 2010, 16:24

Bonjour,
Soit

un entier naturel.
serait il possible de trouver une approximation (asymptotique) du plus petit entier

tel que :

?

Merci de votre aide,
Lapras :happy2:

par **Ben314** » 21 Fév 2010, 16:41

Salut lapras,
Je suppose que tu as fait une faute de frappe et qu'il faut lire :

?
Si c'est le cas, tu peut déjà utiliser le fait que

qui se démontre trés simplement par récurrence sur m.

par **lapras** » 21 Fév 2010, 16:45

Oui j'ai réglé l'erreur de frappe.
Sinon merci pour l'identité je ne m'en souvenais plus...
Je vais voir ce que je peux faire à partir de là.

par **Ben314** » 21 Fév 2010, 18:03

Aprés moulte calculs (approximation des factorielles avec stirling) je te vendrais bien que m(n) est équivalent à

Peut être même qu'une "meilleure" approximation serait :

mais pas sûr que je n'ais pas négligé des choses...

par **lapras** » 21 Fév 2010, 18:33

Merci ! En tout cas pour les 60 1eres valeurs de m(n), je trouve bien un facteur 0.135... qui doit correspondre à ton 1/e² !
J'ai essayé avec stirling mais c'était assez hideux donc j'ai pas continué les calculs...

par **Ben314** » 21 Fév 2010, 18:38

lapras a écrit:...J'ai essayé avec stirling mais c'était assez hideux...

Tout à fait thierry, tout à fait...
Le plus gonflant au début, c'est que, tant que l'on a pas une petite idée de la valeur approximative de m, on ne sait pas trop qui négliger : j'était parti dans l'idée que m était approximativement un \lambda.n et j'ai mis un moment à voir que ça ne marchait pas...

par **lapras** » 21 Fév 2010, 18:48

Effectivement ! J'aurais du te donner la courbe m = f(n) tu aurais vu que c'était parabolique... Désolé.

par **Ben314** » 21 Fév 2010, 19:42

Aprés "réinjectationage" de la première approximation dans la formule, je raffine...

mais je ne suis pas sûr du troisième terme...

par **lapras** » 21 Fév 2010, 20:04

Je suppose que tu veux dire que
m(n) = 1/e²n² + ... + o(n) ?

par **Ben314** » 21 Fév 2010, 21:01

Aprés un autre "réinjectationage" sous maple, j'ai finalement :

mais je ne suis pas sûr à 100% du O(1)...

Edit : en testant sous maple avec n=10000, on trouve m=13553488 en prenant l'arrondi de la formule ci dessus et en calculant les coeffs. binomiaux et la factorielle, il s'avère que c'est exactement la bonne valeur (d'accord, c'est pas une preuve...)

par **lapras** » 23 Fév 2010, 19:09

Ok, merci !
Sinon si je remplace le n! par un (n-1)!, ca change beaucoup l'approximation ?

par **Ben314** » 23 Fév 2010, 20:58

Ben... Il me semble que tu as :

et qu'en développant, ça provoque bien quelque petites différences (évidement pas sur le premier terme)

par **lapras** » 23 Fév 2010, 21:57

Non en fait je voulais dire si je garde le meme membre de gauche mais que je change juste le n! de droite par un (n-1)! ?

par **Ben314** » 24 Fév 2010, 00:18

Bon, j'ai tout pommé les calculs que j'avais fait la dernière fois (et j'ai pas sauve lea feuille maple... :cry:

), je recommence...
En prenant

et avec Stirling,

devient :

et c'est cette formule que je passe à la "moulinette-des-réapproximations" :

1) comme n et p/n tendent vers +oo

tend vers 1 et

tend vers

donc

2) Dans la partie droite de

, je remplace p par

et je demande à maple l'approximation lorsque n->+oo

3) Je réinjecte cette approximation dans

....

Maple finit par "sortir" ça :

mais je ne sais pas si on peut avoir confiance dans les constantes et le o(1)...

par **lapras** » 24 Fév 2010, 00:26

D'apres maple p a l'air d'etre de la forme n²/e² + C*n + O(1) où C est une constante.

par **Ben314** » 24 Fév 2010, 01:11

lapras a écrit:D'apres maple p a l'air d'etre de la forme n²/e² + C*n + O(1) où C est une constante.

Oui, j'ai édité mon post précédent aprés calculs...

par **lapras** » 25 Fév 2010, 15:13

Sinon, toujours à propos de coefficients binomiaux,
est ce que quelqun connait une minoration (la meilleur possible) de :

en fonction de

,

et

?
(où les

naturels bien sur)

par **Ben314** » 25 Fév 2010, 15:26

Le i de

, c'est bien une constante ?
Si oui, j'intuiterais trés fort que le min est atteint pour le plus grand nombre possible de ak égaux à 0 ou à i.
Si, vu la somme S désiré, on peut les rendre tous égaux à 0 ou i [donc si i divise S] c'est clairement le minimum, sinon, je pense que l'on doit répartir le reste de S/i le plus équitablement possible : si r>i/2, prendre un ak de plus égal à i et diminuer tout les ak égaux à i et, si r<i, augmenter les ak égaux à 0.

par **lapras** » 25 Fév 2010, 15:28

Le i est bien une constante et la somme des alpha_k l'est aussi. Pardon j'ai oublié de préciser que les alpha_k était >= 1. Quel est ton "r" ?

par **Ben314** » 25 Fév 2010, 15:34

lapras a écrit:Le i est bien une constante et la somme des alpha_k l'est aussi. Pardon j'ai oublié de préciser que les alpha_k était >= 1.

Sa complique un peu, mais a mon avis, dans ce cas, il faut en prendre le plus possible égaux à i [en premier] puis à 1 ou i-1 [un peu moins bon] puis, de nouveau à regarder "ce qu'il reste"...

Par exemple, si S s'écrit ai+b avec a+b=n, il faut évidement prendre a fois i et b fois 1 pour les ak.
Cela montre que tu n'auras pas un lien "croissant" entre ta somme S et le min, mais un truc qui va dépendre des congruences de S modulo i ou i-1 ou ???

P.S. "mon" r désignait le reste de la division de la somme S des ak (connu) par i (connu lui aussi)

Coefficients binomiaux

Coefficients binomiaux

Qui est en ligne