A et B ont le même nombre d'éléments.

Soit A l'ensemble des suites (a_n)_{n de 1 à 1996} d'entiers strictement positifs satisfaisant a_1 = 1 et a_{k+1} <= a_k + 1 pour k = 1, 2, ..., 1995.
Soit B l'ensemble des suites (b_n)_{n de 1 à 1996} d'entiers strictement positifs satisfaisant b_1 = 1 et b_k <= b_{k+1} <= k+1 pour k = 1, 2, ..., 1995.
Montrer que les ensembles A et B ont le même nombre d'éléments.

Bonjour,

Soit la fonction f qui transforme une suite a_n de A en la suite b_n = n+1-a_n.

a_1 = 1 ==> b_1 = 2-a_1 = 1
a_(k+1) <= a_k + 1 ==> a_k <= k ==> b_k > 0 ==> b_k est bien une suite d'entiers strictement positifs.
b_(k+1) - b_k = 1 + a_k - a_(k+1) >= 0 ==> b_k <= b_k+1

Pour s dans A, f(s) est donc dans B.
f est évidemment injective.

Enfin, pour une suite b_n de B, la suite n+1-b_n appartient à A :
b1 = 1 ==> a_1 = 1
b_k <= k ==> a_k > 0
a_k+1 - a_k = 1 + b_k - b_(k+1) <= 1

Donc f est une bijection de A dans B
Donc A et B sont équipotents.

CQFD

--
Patrick

Salut,

cool.

Ma solution faisait en fait la même chose mais d'une manière différente ^^

Dans les deux cas c'est le n-ième nombre de Catalan, et la différence entre A et B est un différent "encodage" du paysage.
Mais ça revient au même que ta bijection.