Oral assez frustrant. J'ai pas eu beaucoup d'idée, et j'ai pas été performant au niveau des calculs et de l'intuition.
On pose f : N->R avec f (0)=0 et, pour n>0, f(n)=1+(Σ_{k=0}^{n}(k parmi n)f(k))/(2^n)
Que dire de f(n) asymptotiquement ?
J'ai vraiment pas brillé. D'abord j'ai voulu montrer que f (n)>=n avant de me rendre compte que c'est faux en général. Finalement j'ai montré que f (n)<=2n, et ensuite que pour tout alpha>0, il existe bêta tq f (n)<=alpha*n+bêta. Je pense que ça doit permettre de montrer que f (n)=o (n) mais j'ai la flemme d'y réfléchir. Ensuite il m'a fait intuiter que f (n) est de l'ordre de lnn, ce que j'ai essayé de quantifier un peu mais c'était pas glorieux. On a un peu utilisé des probas et Bienaymé-Tchebychev pour quantifier le fait que les coefficients binomiaux se resserrent autour de n/2, d'où f (n) environ égal à 1+f (n/2)
Le moment le plus rageant fut à la fin quand il m'a demandé de montrer que le rang est la taille de la plus grande sous matrice inversible. J'ai galéré et je suis même pas allé au bout, ce qui me gonfle parce que globalement je connais très bien les démos du cours.