Exo sympa

[kazeriahm]

salut, voici un exo dont je trouve la résolution jolie :

(u_n) est définie par u0=1 et pour tout n,


exprimer u_n en fonction de n

[fahr451]

méthode importante

prendre la série f génératrice formelle ( peu importe le rayon ici R >0)

le produit de convolution (ou de cauchy) donne
f^2 (x) = (f(x) -1) /x résoudre l'équation du second degré en ne gardant que la bonne solution f(0) = 1 >0

et développer la racine carrée en série entière

identifier les coeffs

[Joker62]

Ah ça va loin là :^)
Moi j'étais parti sur

avec
J'partais sur de l'algèbre linéaire en fait...

[alben]

Ah ça va loin là :^)
J'partais sur de l'algèbre linéaire en fait...

Non, ce que tu écris ne correspond à la définition de la suite (tu as une somme de carrés)
Sinon c'est effectivement très joli

[Joker62]

Ah ouai y'a pas de transposé j'viens de faire tilt. désolé

J'vais suivre les lignes de fahr pour voir

[Bouchra]

Ah tiens, sympa cet exo en effet. On l'a fait en exercice avec la méthode proposée par fahr451.

Juste pour dire ce que représente u_n ,
soit l'application :
G*G -> G
(x,y) |-> x.y
où G stable par ., et . loi non associative.
Soient x_0,...x_n n+1 éléments de G, u_n est le nombre de façons de composer selon la loi . les n+1 éléments.
Ou encore c'est le nombre de façons d'arranger n parenthèses.

Et voici un très bon cours sur les fonctions génératrices :
http://www.math.upenn.edu/~wilf/DownldGF.html
(Cet exo y figure en plus !)

[kazeriahm]

ca n'a meme pas tenu une demi heure :ptdr:

[fahr451]

Juste pour dire ce que représente u_n ,
Ou encore c'est le nombre de façons d'arranger n parenthèses.

judicieuse remarque (je n'avais pas tilté )


soit u(n) le nombre (dit de catalan) de façons de parenthéser une expression avec n parenthèses
une parenthèse = ( )

règle = ne pas fermer strictement plus de parenthèses qu'on en a ouvert

modélisation possible


dessiner un carré n x n quadrillé avec des petits carrés 1 x 1

une ouverture = déplacement d'une unité vers la droite

une fermeture = déplacement d'une unité vers le haut
on part du sommet en bas à gauche on arrive après 2n déplacements au sommet en haut à droite

une façon = un chemin
la règle impose = le chemin doit rester sous (sens large) la diagonale

question (pas si simple): établir la relation de récurrence proposée par kazeriahm

[yos]

??

[alben]

??

C'est aussi ce que j'ai trouvé en suivant pas à pas la démarche de Fahr

[fahr451]

oui c'est le n ième nombre de catalan

établir la relation de récurrence en partant à l'envers est intéressant également.

[Bouchra]

...
question (pas si simple): établir la relation de récurrence proposée par kazeriahm

Pour la relation avec les parenthèses, je l'ai vue dans le site que j'ai donné. Je connaissais juste en terme de composition mais c'est vrai que ça revient au même.
Je cite : (en anglais ...)

Example 3.
In order to highlight the strengths of ordinary vs. exponential generating
functions, let’s do a problem where the form of the convolution of
sequences that occurs suggests the ops form of generating function. We will
count the ways of arranging n pairs of parentheses, each pair consisting of a
left and a right parenthesis, into a legal string. A legal string of parentheses
is one with the property that, as we scan the string from left to right we
never will have seen more right parentheses than left.
There are exactly 5 legal strings of 3 pairs of parentheses, namely:
((())); (()()); (())(); ()()(); ()(()).[RIGHT](2.3.6)[/RIGHT]
Let f(n) be the number of legal strings of n pairs of parentheses (f(0) = 1),
for n 0.
With each legal string we associate a unique nonnegative integer k, as
follows: as we scan the string from left to right, certainly after we have
seen all n pairs of parentheses, the number of lefts will equal the number of
rights. However, these two numbers may be equal even earlier than that.
In the last string in (2.3.6), for instance, after just k = 1 pairs have been
scanned, we find that all parentheses that have been opened have also been
closed. In general, for any legal string, the integer k that we associate with
it is the smallest positive integer such that the first 2k characters of the
string do themselves form a legal string. The values of k that are associated
with each of the strings in (2.3.6) are 3, 3, 2, 1, 1. We will say that a legal
string of 2n parentheses is primitive if it has k = n. The first two strings
in (2.3.6) are primitive.
How many legal strings of 2n parentheses will have a given value of k?
Let w be such a string. The first 2k characters of w are a primitive string,
and the last 2n 2k characters of w are an arbitrary legal string. There
are exactly f(n;)k) ways to choose the last 2n;)2k characters, but in how
many ways can we choose the first 2k? That is, how many primitive strings
of length 2k are there?

Lemma 2.3.1. If k 1 and g(k) is the number of primitive legal strings,
and f(k) is the number of all legal strings of 2k parentheses, then
[CENTER]g(k) = f(k 1).[/CENTER]

Proof. Given any legal string of k;)1 pairs of parentheses, make a primitive
one of length 2k by adding an initial left parenthesis and a terminal right
parenthesis to it. Conversely, given a primitive string of length 2k, if its
initial left and terminal right parentheses are deleted, what remains is an
arbitrary legal string of length 2k 2. Hence there are as many primitive
strings of length 2k as there are all legal strings of length 2k 2, i.e., there
are f(k 1) of them.

Hence the number of legal strings of length 2n that have a given value
of k is f(k 1)f(n;)k). Since every legal string has a unique value of k, it
must be that
f(n) = f(k 1)f(n k) (; f(0) = 1) [RIGHT](2.3.7)[/RIGHT]
with the convention that f = 0 at all negative arguments.

Avec ta modélisation, c'est vrai que ce n'est pas évident de voir la relation de récurrence. Je vais y réfléchir.

Sinon en posant :
pour ,
On obtient pour :


Il est peut-être plus facile de voir que composer n éléments revient à composer k éléments et n-k éléments, k variant de 1 à n-1.