Scribd Logo
Importer

Bienvenue sur Scribd !

  • 39 vues

    DM 2

    Transféré par

    Mustapha Belmufti
    Ce document présente plusieurs exercices sur l'inversion de Pascal, les dérangements, et la transformation de Fourier discrète. Les exercices portent sur le calcul de formules et la démonstration de propriétés mathématiques.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd

    DM 2

    Transféré par

    Mustapha Belmufti
    39 vues2 pages
    Ce document présente plusieurs exercices sur l'inversion de Pascal, les dérangements, et la transformation de Fourier discrète. Les exercices portent sur le calcul de formules et la démonstration de propriétés mathématiques.

    Titre original

    DM-2

    Copyright

    © © All Rights Reserved

    Formats disponibles

    PDF, TXT ou lisez en ligne sur Scribd

    Avez-vous trouvé ce document utile ?

    Ce contenu est-il inapproprié ?

    Ce document présente plusieurs exercices sur l'inversion de Pascal, les dérangements, et la transformation de Fourier discrète. Les exercices portent sur le calcul de formules et la démonstration de propriétés mathématiques.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    39 vues2 pages

    DM 2

    Transféré par

    Mustapha Belmufti
    Ce document présente plusieurs exercices sur l'inversion de Pascal, les dérangements, et la transformation de Fourier discrète. Les exercices portent sur le calcul de formules et la démonstration de propriétés mathématiques.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    Vous êtes sur la page 1sur 2

    v MP2I

    MPSI 3 Devoir maison ESPRIT 2023-2024


    Prépa

    DM 2 - Inversion de Pascal et transformation de Fourier discrète

    Exercice 1. – Formule d’inversion de Pascal

    Ã ! suite de nombres. On définit sa transformée binomiale comme la suite ( f n )n∈N ,


    Soit (e n )n∈N une
    n n
    X
    avec f n = ek .
    k=0 k

    1. Soient 0 ≤ k ≤ n des entiers naturels. Calculer, selon les valeurs de k et de n, la quantité


    Ã !Ã !
    n−k
    q n n−q
    µ(k, n) =
    X
    (−1) .
    q=0 q k

    2. Soit (e n )n∈N une suite de nombres et soit ( f n )n∈N sa transformée binomiale. Montrer la
    formule d’inversion de Pascal :
    Ã !
    n
    n−p n
    ∀n ∈ N, e n =
    X
    (−1) fp .
    p=0 p

    Exercice 2. – Nombre de dérangements


    Soit E un ensemble. Une permutation de E est une fonction f : E → E tel que tout élément de E
    admet un unique antécédent par f :

    ∀y ∈ E , ∃!x ∈ E : f (x) = y.

    Une permutation de E est un dérangement si elle est sans point fixe :

    ∀x ∈ E , f (x) ̸= x.

    Pour tout n ∈ N∗ , on note D n le nombre de dérangements de l’ensemble ‚1, nƒ. On convient que
    D 0 = 1.

    1. On admet que ∀n ≥ 1, D n+1 = n(D n + D n−1 ). En déduire que

    ∀n ≥ 1, D n = nD n−1 + (−1)n .

    2. On note (Tn )n∈N la transformée binomiale de (D n )n∈N . Calculer les valeurs de D n et Tn pour
    n ∈ ‚0, 5ƒ.

    3. Conjecturer une formule pour Tn , puis la démontrer.

    4. En déduire une formule pour D n .

    5. (Bonus) Si les n passagers d’un avion s’assoient au hasard sur les n sièges, quelle est la
    probabilité qu’aucun ne soit à la place indiquée sur son billet ? Pour n = 500, on réalisera
    en Python1 une simulation de l’expérience et on comparera au résultat théorique.
    1
    On pourra utiliser la méthode shuffle du module random.

    1
    Exercice 3. – Transformation de Fourier discrète
    2i π
    Soit n ≥ 1 un entier. On note ω = e n et E = Cn . Un élément a de E a n composantes, notées
    a 0 , . . . , a n−1 . Soit a dans E . On définit F a ∈ E sa transformée de Fourier discrète par
    n−1
    ωk j a k .
    X
    ∀ j ∈ ‚0, n − 1ƒ, (F a) j =
    k=0

    ³ ´ n−1
    X −k j
    On définit aussi F a ∈ E par ∀ j ∈ ‚0, n − 1ƒ, F a = ω ak .
    j
    k=0
    On pourra librement utiliser l’inégalité triangulaire sur C :
    ¯Xn ¯ X n
    ∀z 1 , . . . , z n ∈ C, ¯ zk ¯ ≤ |z k |.
    ¯ ¯
    k=1 k=1

    n−1
    1. Soit p ∈ Z. Calculer ωkp .
    X
    k=0

    2. En déduire que, pour tout a ∈ E ,


    ³ ´
    F F a = F (F a) = na.

    n−1 n−1
    a k X k un polynôme, de coefficients a k ∈ C. Pour tout z ∈ C, on note P (z) = ak z k .
    X X
    Soit P =
    k=0 k=0
    On note n o
    M P = max |P (ωk )|, k ∈ ‚0, n − 1ƒ .

    3. Montrer que pour tout k ∈ ‚0, n − 1ƒ, |a k | ≤ M P .

    Si a, b ∈ E , le produit de convolution de a et b, noté a ⋆ b, est défini par


    n−1
    ∀k ∈ ‚0, n − 1ƒ, (a ⋆ b)k =
    X
    a j b k− j .
    j =0

    4. Montrer que
    ∀a, b ∈ E , ∀k ∈ ‚0, n − 1ƒ, F (a ⋆ b) k = (F a)k (F b)k .
    ¡ ¢

    5. En déduire – en limitant les calculs – que ⋆ est commutative et associative :

    ∀a, b, c ∈ E , a ⋆ b = b ⋆ a et (a ⋆ b) ⋆ c = a ⋆ (b ⋆ c).

    On considère p et ν deux éléments de E . On suppose que leurs composantes sont dans R+ et


    n−1 n−1
    νk = 1. Pour tout j ∈ N, on note p( j ) = ν ⋆ · · · ⋆ ν ⋆ p, avec j facteurs ν. On dit que
    X X
    que pk =
    ³ k=0
    ´ k=0 ³ ´
    (j)
    p( j ) converge si pour tout k ∈ ‚0, n − 1ƒ, les suites p k convergent.
    j ∈N j ∈N
    ³ ´
    6. Déterminer une condition nécessaire et suffisante sur F ν pour que p( j ) converge.
    j ∈N

    Vous aimerez peut-être aussi