Nombre de fonctions affines par morceaux >0

gnouk · May 2019

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 ??

Cidrolin · May 2019

S'agit-il de chemins restants au dessus de l'axe des $x$ ?

gerard0 · May 2019

La description y ressemble fortement, et on peut alors laisser tomber le 0 et commencer à (1,1), puis par un changement de repère, chercher le nombre de chemins qui restent positifs de 0 à 2n-1.

Cordialement.

gnouk · May 2019

Oui c'est tout à fait cela, j'ai pensé à ce changement de variable..;

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$.

gnouk · May 2019

J'ai fait un programme qui les comptent, cela donne la suite (en partant de $n=1$)

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..

lourrran · May 2019

Pour le cas n=2, je pense qu'l y a 2 chemins, (++ et +-) ; ce serait bien de clarifier les notations.

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...

gnouk · May 2019

En appelant $b_i(j)$ le nombre de chemins >0 à $i$ arêtes arrivant à $j$, on obtient, par examen des possibilités
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$

gnouk · May 2019

Je pars de $f(0)=0$, puis fatalement $f(1)=1$, $f(2)=2$, puis $f(3)= 1$ ou 3 au choix.. jusqu'à $f(2n)=2,4,.. 2n$

gnouk · May 2019

En fait $b_{2n}(2)=\frac 1 {n+1} C_{2n}^n$ est un nombre de Catalan 1,2,5,14,42.. correspondant à un nombre de parenthésages.. logique on monte et descend autant,
et les parenthèses fermantes sont après les ouvrantes..

Ma solution est un peu compliquée.. il y a sûrement plus simple.

Nombre de fonctions affines par morceaux >0

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 9