Suite extraite...

[nodgim]

Je crois que ça marche quand même (de toute façon, la preuve vient d'un bouquin donc en principe il n'y a pas d'erreur :we: )

On suppose , puisqu'on peut considérer la plus grande sous-suite croissante commençant par , et y ajouter au début, ce qui fait une sous-suite croissante de longueur donc .
Le raisonnement est le même dans l'autre cas : si , alors .

Pour ton exemple, les couples sont (si je ne fais pas d'erreur):
(4,3)
(5,2)
(2,4)
(3,3)
(4,2)
(4,1)
(3,2)
(2,2)
(1,2)
(1,1)
donc les couples sont bien tous distincts.

Apparemment tu ne prends pas les suites en rétro, car pour 3 par exemple ce n'est pas (1,1)

[poiuytreza]

Oui, désolé si c'était pas clair, je prends uniquement les sous-suites dont le premier terme est et qui "restent dans l'ordre de la suite de départ".

[nodgim]

Oui, désolé si c'était pas clair, je prends uniquement les sous-suites dont le premier terme est et qui "restent dans l'ordre de la suite de départ".

D'accord, je l'ai bien compris comme ça.