Nombre de fonctions affines par morceaux >0
Bonjour
Je bute sur un problème simple en apparence, sans doute classique.. j'ai essayé de raisonner par récurrence, par complémentaire.. mais je suis bloqué à chaque fois.
Je considère les $4^n$ fonctions de ${0,1,\ldots,2n}$ dans $\mathbb{N}$, telles que $f(0)=0$, continues et affines par morceaux avec des pentes valant toujours 1 ou -1.
Combien d'entre elles restent strictement positives au delà de 1 ??
Je bute sur un problème simple en apparence, sans doute classique.. j'ai essayé de raisonner par récurrence, par complémentaire.. mais je suis bloqué à chaque fois.
Je considère les $4^n$ fonctions de ${0,1,\ldots,2n}$ dans $\mathbb{N}$, telles que $f(0)=0$, continues et affines par morceaux avec des pentes valant toujours 1 ou -1.
Combien d'entre elles restent strictement positives au delà de 1 ??
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Cordialement.
Auparavant, en me disant que le nombre de chemins >0 ou <0 était le même, j'avais essayé de calculer le nombre de fonctions s'annulant au moins une fois entre 1 et 2n, en considérant la première annulation, mais je ne n'y suis pas arrivé.
Bref, en retranchant 1 à $y$ et $x$, on cherche le nombre de chemins partant de (0,0) et ne passant jamais strictement en dessous de l'axe des $x$.
1,1,2,3,6,10,20,35,70,126,252,462,924,1716,3432
Je comprends bien pourquoi $a_{2n+1}=2a_{2n}$, puisque pour raison de parité, $f(2n)$ vaut au moins 2, donc la valeur de $f(2n+1)$ n'intervient pas. La suite des $a_{2n}$ semble être les coefficients binomiaux $C_{2n-1}^n$.. Il ne reste plus qu'à l'expliquer..
On voit parfois ce problème avec cette formulation : Une caissière (cinéma par exemple) n'a rien en caisse à l'ouverture. L'entrée coûte 5€, et les consommateurs ont tous soit un billet de 5€, soit un billet de 10€. Etudier les différentes configurations...
aux relations de récurrence
$b_{2n}(2n)=1$ pour tout $n \geq 1$
$b_{2n+2}(2k)=b_{2n}(2k-2)+2b_{2n}(2k)+b_{2n}(2k+2)$ pour tous $n$ et $k$
On peut remplir ainsi une sorte de triangle de Pascal, et la somme des termes d'une ligne donne $a_{2n}$
En sommant les relations, on aboutit donc à $a_{2n+2}=4a_{2n}-b_{2n}(2)$
J'ai avancé mais il manque encore quelque chose pour prouver $a_{2n}=C_{2n-1}^n$
et les parenthèses fermantes sont après les ouvrantes..
Ma solution est un peu compliquée.. il y a sûrement plus simple.