Inscription / Connexion Nouveau Sujet
Niveau première
Partager :

Suites numériques

Posté par
dnomirolf
08-05-23 à 19:09

Bonjour, j'ai un peu de mal sur cet exercice sur les suites... J'espère que vous pourrez m'aider à trouver mes erreurs !

Énoncé :

Dans tout ce problème, 𝑛 désigne un entier naturel supérieur ou égal à 3.
Un joueur dispose de 𝑛 cartes numérotées de 1 à 𝑛. Il les mélange puis note dans l'ordre la suite des numéros des cartes obtenue. On appelle liste la suite des numéros ainsi observés.
Le nombre 𝑛 sera appelé longueur de la liste.
Par exemple, avec 𝑛 = 8, une liste possible est 𝐿 = [2,5,7,6,1,8,4,3].
Avec une liste donnée, le joueur marque un point chaque fois que le numéro d'une carte est supérieur à celui de la carte précédente.
Par exemple avec la liste 𝐿 = [2,𝟓, 𝟕, 6,1,𝟖, 4,3], le joueur marque 3 points.
On appelle score le nombre de points marqués par le joueur. Le score précédent est donc 3. 1. Quelques exemples
a. Donner un autre exemple de liste de longueur 8 et de score 3.
b. Donner toutes les listes de longueur 3 possibles ainsi que les scores correspondants.
2. Écrire sur votre copie la syntaxe d'une fonction Python qui, prenant en argument une liste 𝐿 et sa longueur 𝑛, renvoie le score de la liste 𝐿.
On revient au cas général ainsi qu'à des considérations théoriques.
3. Démontrer que tout score est compris entre 0 et 𝑛 − 1. Donner une liste dont le score vaut 0 et une liste dont le score vaut 𝑛 − 1.
4. Soit 𝑘 un entier compris entre 1 et 𝑛 − 2.
a. Démontrer qu'il existe une liste de longueur 𝑛 et de score 𝑘.
b. Peut-on trouver deux listes de longueur 𝑛 et de score 𝑘 ? On note désormais 𝐿_𝑛(𝑠) le nombre de listes de longueur 𝑛 et de score 𝑠.
5. Déterminer 𝐿_𝑛(0) et 𝐿_𝑛(𝑛 − 1).
6. Une relation de récurrence
a. Déterminer 𝐿_3(0),𝐿_3(1) et 𝐿_3(2). Comment insérer dans la liste [3,1,2]la carte portant le numéro 4 pour obtenir une liste dont le score vaut encore 1 ?
b. Comment insérer dans la liste [3,2,1] la carte portant le numéro 4 pour obtenir une liste dont le score reste nul ?
c. Vérifier que 𝐿_4(1) = 2𝐿_3(1) + 3𝐿_3(0).
d. Montrer que pour tout entier naturel 𝑛 ≥ 3,
𝐿_𝑛+1(1) = 2𝐿_𝑛(1) + 𝑛𝐿_𝑛(0).
e. Pour tout 𝑛 et pour tout entier naturel 𝑘 non nul, exprimer 𝐿_𝑛+1(𝑘) à l'aide de 𝐿_𝑛(𝑘) et 𝐿_𝑛(𝑘 − 1).
f. Dresser un tableau des valeurs de 𝐿_𝑛(𝑘) pour 𝑛 ∈ {3,4, 5} et 𝑘 ∈ {0,1, 2,3, 4}.


Ma tentative:

1. a. Un autre exemple de liste ayant une longueur de 8 et un score de 3 serait [8,1,7,6,5,2,3,4].
b. Les différentes listes de longueur 3 possibles sont [1,2,3] avec un score de 2, [1,3,2], [2,1,3], [2,3,1], [3,1,2] avec un score de 1, [3,2,1] avec un score de 0.

2. Voici la syntaxe d'une fonction Python qui renvoie le score d'une liste L :

def calculer_score(L, n):
    score = 0
    for i in range(1, n):
        if L[i] > L[i-1]:
            score += 1
    return score

3. Soit L une liste de n éléments. Pour tout couple d'indices (i, j) avec i < j, on compare L[i] et L[j]. S'il y a inversion (c'est-à-dire si L[i] > L[j]), le score est incrémenté de 1.

Le score est donc le nombre d'inversions dans la liste L. Puisqu'il ne peut y avoir un nombre négatif d'inversions, on a immédiatement que le score est compris entre 0 et n-1.

Pour une liste L triée dans l'ordre croissant, il n'y a aucune inversion, donc le score est 0.

Pour une liste L triée dans l'ordre décroissant, chaque élément est plus grand que tous les éléments qui le suivent, donc il y a n-1 inversions et le score est n-1.

Ainsi, on peut prendre la liste triée [1,2,3,...,n] pour avoir un score de 0 et la liste triée en ordre décroissant [n, n-1, ..., 3, 2, 1] pour avoir un score de n-1.

4. a. On peut construire une liste de longueur n et de score k en plaçant les k premiers nombres dans l'ordre croissant, puis en plaçant les n et n-1 à la fin de la liste. La liste [1, 2, ..., k, n, n-1, ..., k+1] est de longueur n et de score k, donc il existe au moins une liste de longueur n et de score k pour tout k entre 1 et n-2.
b. On peut construire une deuxième liste de longueur n et de score k en plaçant les n et n-1 en début de liste, puis en plaçant les k premiers nombres dans l'ordre décroissant. La liste [n-1, n, k+1, k, ..., 2, 1] est de longueur n et de score k. Cette liste est différente de la liste construite en a, car les éléments sont placés dans un ordre différent. Ainsi, pour tout k entre 1 et n-2, on peut trouver au moins deux listes de longueur n et de score k.

5. Nous pouvons utiliser les résultats obtenus dans les questions précédentes pour déterminer 𝐿𝑛(0) et 𝐿𝑛(𝑛−1).

Pour 𝐿𝑛(0) : La liste [𝑛, 𝑛−1, …, 2, 1] est la seule liste de longueur n qui peut avoir un score de 0. Donc 𝐿𝑛(0) = 1.

Pour 𝐿𝑛(𝑛−1) : La liste [1, 2, ..., 𝑛] est la seule liste de longueur n qui peut avoir un score de 𝑛−1. Donc 𝐿𝑛(𝑛−1) = 1.

Ainsi, il existe une unique liste de longueur n et de score 0 ou 𝑛−1, respectivement.

6. a. En appliquant le résultat de la question 5 à 𝑛 = 3, on trouve que 𝐿3(0) = 𝐿3(2) = 1 car il n'y a qu'une seule liste de longueur 3 qui est triée par ordre décroissant ([3,2,1]) et qu'une seule liste de longueur 3 qui est triée par ordre croissant ([1,2,3]).

Les listes de longueur 3 sont [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2] et [3,2,1]. On remarque que la liste [3,1,2] a un score de 1.

Pour insérer la carte portant le numéro 4 dans la liste [3,1,2] tout en maintenant un score de 1, on peut obtenir les listes [4,3,1,2] et [3,1,4,2].

b. Pour insérer la carte portant le numéro 4 dans la liste [3,2,1] de sorte que le score reste nul, il faut l'insérer à l'une des deux extrémités de la liste. Ainsi, on peut obtenir la liste [4,3,2,1] ou la liste [3,2,1,4], qui ont toutes deux un score de zéro car dans le premier cas toutes les cartes sont dans l'ordre décroissant, et dans le second cas, le 4 est à la fin de la liste et les autres cartes sont dans l'ordre décroissant.

c. Pour toute liste de longueur 4 et de score 1, on doit insérer le nombre 4 dans une liste de longueur 3 et de score 0 ou 1. En effet, si on insère 4 à la liste [1, 2, 3], on obtient une liste de score au moins 2. Ainsi, pour chaque liste de longueur 3 et score 1, il y a deux possibilités d'insérer le nombre 4 pour obtenir une liste de longueur 4 et de score 1. Cela donne donc 2 × 𝐿3(1) telles listes possibles. De plus, il y a 3 possibilités d'insérer le nombre 4 à la liste [1, 2, 3] pour obtenir une liste de longueur 4 et de score 1. Cela ajoute donc 3 × 𝐿3(0) listes possibles. Ainsi, on a:

𝐿4(1) = 2𝐿3(1) + 3𝐿3(0)

Il suffit donc de calculer 𝐿3(0) et 𝐿3(1) à partir des réponses trouvées à la question 5:

𝐿3(0) = 𝐿3(2) = 1
𝐿3(1) = 4

Donc, 𝐿4(1) = 2𝐿3(1) + 3𝐿3(0) = 2×4 + 3×1 = 11

d. La méthode de construction des listes de longueur 𝑛+1 et score 1 à partir de listes de longueur 𝑛 et score 0 ou 1 est similaire à la question précédente. On insère le numéro 𝑛+1 dans une liste de longueur 𝑛 et score 0 ou 1.

On remarque d'abord que la position 1 ne rapporte pas de point. Dans une liste de longueur 𝑛 et score 1, on peut insérer le numéro 𝑛+1 soit au tout début (en position 1), soit juste avant le numéro marquant l'unique point (position au moins 2). Ces deux positions sont distinctes et ce sont les seules possibles, ce qui fait 2𝐿𝑛(1) listes de ce type.

Dans une liste de longueur 𝑛 et de score 0, on peut insérer le numéro 𝑛+1 n'importe où sauf au tout début, la liste obtenue rapportera bien 1 point. Il y a donc 𝑛 positions possibles pour le numéro 𝑛+1, ce qui fait 𝑛𝐿𝑛(0) listes de ce type.

Enfin, insérer 𝑛+1 à une liste de longueur 𝑛 et de score supérieur ou égal à 2 donnera une liste de score supérieur ou égal à 2: en effet, si on l'insère en queue, cela augmentera le score d'une unité, et sinon, cela conservera le score initial.

On en déduit que le nombre de listes de longueur 𝑛+1 et score 1 est donné par 𝐿𝑛+1(1) = 2𝐿𝑛(1) + 𝑛𝐿𝑛(0).

e. Pour insérer le numéro n° (𝑛 + 1) dans une liste de longueur 𝑛+1 et de score 𝑘, on peut soit l'insérer en position 1 ou juste avant le numéro marquant le 𝑘-ième point (position au moins 2). Si on insère le n° (𝑛 + 1) en position 1, alors la liste restante doit être de longueur 𝑛 et de score 𝑘-1, car on ne peut pas avoir deux points consécutifs. Sinon, la liste restante doit être de longueur 𝑛 et de score 𝑘.

Ainsi, le nombre de listes de longueur 𝑛+1 et de score 𝑘 obtenues en insérant le n° (𝑛 + 1) dans une liste de longueur 𝑛 et de score 𝑘 est (𝑘 + 1) 𝐿𝑛(𝑘) pour l'insertion en position 1 ou juste avant le numéro marquant le 𝑘-ième point.

Le nombre de listes de longueur 𝑛+1 et de score 𝑘 obtenues en insérant le n° (𝑛 + 1) dans une liste de longueur 𝑛 et de score 𝑘-1 est (𝑛 + 1 − 𝑘) 𝐿𝑛(𝑘−1), car il y a 𝑛 + 1 positions possibles pour insérer le n° (𝑛 + 1), mais 𝑘 positions qui augmentent le score à 𝑘.

Enfin, insérer 𝑛 + 1 dans une liste de score strictement inférieur à 𝑘-1 ou strictement supérieur à 𝑘 ne conduira jamais à une nouvelle liste de score 𝑘.

Ainsi, on a 𝐿𝑛+1(𝑘) = (𝑘 + 1)𝐿𝑛(𝑘) + (𝑛 + 1 − 𝑘)𝐿𝑛(𝑘 − 1).

f. Le tableau des valeurs de 𝐿𝑛(𝑘) pour 𝑛 ∈ (3, 4, 5) et 𝑘 ∈ (0, 1, 2, 3, 4) est le suivant :
n\k01234
3141
4111111
512666261


Merci d'avance pour votre aide!

Posté par
lake
re : Suites numériques 09-05-23 à 15:20

Bonjour,
Je n'ai pas tout vérifié : je me suis limité aux formules de récurrences finales et au tableau ; tout est correct.

Remarque que (ce n'est pas demandé) :

  L_n(1)=2^n-n-1
  L_n(2)=3^n-(n+1)2^n+\dfrac{n(n+1)}{2}

Il existe des formules analogues pour Ln(k) (les nombres Eulériens ici : )

Posté par
lake
re : Suites numériques 09-05-23 à 15:36

J'ajoute ce lien de l'OEIS où la suite A008292 correspond à ton tableau lu par lignes : .
Tu as bien travaillé !

Posté par
dnomirolf
re : Suites numériques 09-05-23 à 20:42

Merci beaucoup pour votre aide !

Posté par
dnomirolf
re : Suites numériques 11-05-23 à 17:18

Je pense m'être trompé à l'exercice 5...



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1674 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !