Répondre

bridgslam · 23-08-2023 21:03:15

Bonsoir,

l'expression donnant le cardinal de la classe $C_p$ des permutations $\sigma$ ayant p indices pairs et (p-1) indices impairs tels que $\sigma(i) - i $ soit pair , donnée auparavant, se simplifie en fait agréablement en :

$ \boxed{ \large Card( C_p ) = p \{ \frac {n-1}{2}! \binom{\frac{n+1}{2} }{p}\}^2 }$ ( et en utilisant le symbole moins vétuste des combinaisons ).

Avec cette expresssion la vérification algébrique de $ n! = \sum_{p \in \{1,..., (n+1)/2\}} \; p [ \frac {n-1}{2}! \binom{\frac{n+1}{2} }{p}]^2$
peut s'envisager plus sereinement :-).

(en effet une preuve ensembliste simple sur un ensemble à n (impair) éléments presque :-) équitablement partagé en deux parties simplifie la partie sommatoire,
et tout se simplifie ensuite compte-tenu du coefficient fixe de la formule, cela donne bien,après deux lignes de calcul, n!)

On voit aussi arithmétiquement que le cardinal d'une classe rapporté au nombre p d'indices i impairs qui lui donne son nom est toujours un carré .
Notamment notre petite étude montre que pour tout n impair le nombre de permutations telles que i soit unique est un carré parfait (vu que p = 1).
Ce qu'on voyait déjà avec l'expression de u donnée dans un message antérieur.
Notre petite étude permet mieux d'en percevoir la raison...

Alain

bridgslam · 22-08-2023 16:44:29

Bonsoir,

J'ai disposé d'un peu de temps pour exprimer la taille des classes $C_p$ des permutations de $S_n$ , n impair, telles que
p indices impairs et (p-1) indices pairs vérifient la condition:

$Card ( C_p) = p!(p-1)! (C_{(n+1)/2}^p )^2(C_{(n-1)/2}^{p-1})^2 (( n+1)/2 - p )!^2$

les 120 permutations pour n=5 se répartissent alors en 36 ( indice unique, impair) , 72 ( trois indices, deux impairs et un pair ) ,12 ( cinq indices, trois impairs et deux pairs).

Vérifier dans le cas général que la somme des cardinaux $C_1, ..., C_{(n+1)/2} $ donne bien n! n'est pas forcément trivial.
Je n'ai pas essayé, n'étant pas vraiment fan (et même pas du tout) de ce genre de calcul.
Peut-être un logiciel de calcul formel le fait-il automatiquement d'ailleurs.

[ j'étais en phase d'investigation lorsque j'ai écrit ces remarques, en réalité- voir dernier message - tout s'arrange admirablement
et on a même avec cette nomenclature de bijections une application inattendue de la sommation des $ k\binom{n}{k}^2$
...
pas besoin de logiciel donc , a posteriori]

A.

bridgslam · 20-08-2023 09:53:53

Bonjour,

Enfin on peut classer toutes les permutations de $S_n$ (n impair) ainsi:

- celles de la classe $C_1$ ayant exactement 1 indice i impair et 0 indice pair répondant à la question (qu'on vient de dénombrer)
- celles de la classe $C_2$ ayant exactement 2 indices i impairs et 1 indice pair répondant à la question
- ....
- celles de la classe $C_{p+1}$ ayant exactement p+1 indices i impairs et p indices pairs répondant à la question
-....
- celles de la classe $C_{(n+1)/2}$ avec (n+1)/2 indices i impairs et (n-1)/2 indices pairs répondant à la question (par exemple l'identité)

Ainsi, par exemple, (encore avec n=7) :
1 2 3 4 5 6 7
5 6 7 1 2 3 4 est dans $C_2$

tandis que
1 2 3 4 5 6 7
1 2 3 4 5 6 7

et
1 2 3 4 5 6 7
3 6 5 4 7 2 1

sont dans $C_4$

On peut dénombrer chaque classe si on a un peu de courage (très faisable si on dispose d'un peu de temps).
$C_1$ occupe un peu plus du quart du total des 3 classes si n = 5, un peu plus du dixième du total des 4 classes si n = 7.

A.

bridgslam · 20-08-2023 00:07:05

Bonsoir ( bonjour plutôt),

Une petite investigation supplémentaire en terme de dénombrement permet de résumer le résultat suivant:

Soit n naturel et impair.
Pour toute permutation x de $S_n$ il existe i appartenant à {1,...,n} tel que $x_i - i$ soit pair.
Il y en a $u=\{(n-1)/2\}!^2(n+1)^2/4$ telles que i soit unique , i est alors impair.

n=1. u=1
n=3. u=4
n=5. u=36
n=7. u=576

...
il y a en fait une petite généralisation au fait que u est carré, si on s'intéresse aux autres permutations.

On peut s'amuser à les lister.
J'ai fait jusqu'à n=5...

Alain

bridgslam · 15-08-2023 18:32:20

Bonsoir,

Tout à fait.

A.

Abirmdr · 15-08-2023 16:30:48

bridgslam a écrit :

Bonsoir,
Je vous ai proposé 3 pistes différentes.
Posez $b_i = a_i - i$.
Supposer qu'ils sont tous impairs ...
Ensuite sommer les , exprimez cette somme et trouvez une contradiction.
Bon courage
A.

La somme ça va être nulle, n'est-ce pas ? Et le 0 est un nombre pair ? Donc une contradiction. C'est juste ??

bridgslam · 15-08-2023 16:24:48

Bonsoir,

Je vous ai proposé 3 pistes différentes.
Posez $b_i = a_i - i$.

Supposer qu'ils sont tous impairs ...
Ensuite sommer les , exprimez cette somme et trouvez une contradiction.

Bon courage
A.

Abirmdr · 15-08-2023 16:16:10

bridgslam a écrit :

Bonjour,
Si tous ces nombres étaient impairs, comme ils sont en nombre impair, leur somme serait ....
Or cette somme vaut ...
Donc...
A.

Bonjour bridgslam , pouvez vous m'expliquer plus , j'ai pas compris quel raisonnement vous avez utilisé ، et si c'est l'absurde , quels nombres vous avez posé impair ?

Merci d'avance.

Bernard-maths · 15-08-2023 16:13:10

Bonjour à tous !

A est l'ensemble des n premiers nombres entiers, et il y a (n-1)/2 nombres pairs, et (n-1)/2 + 1 nombres impairs. Donc un nombre impair de plus que de pairs ...

Or par bijection A est mis en relation avec lui-même ( les x_i étant 2 à 2 distincts).

Si on considère les nombres pairs, ils seront mis en relation avec (n-1)/2 nombres, et comme il y a 1 nombre impair de plus que les pairs, il restera au moins un nombre impair non mis en relation avec les nombres pairs.

DONC ... je vous laisse conclure ?

Bernard-maths

bridgslam · 15-08-2023 16:12:15

Et enfin en décomposant la bijection en produit de cycles, l'un des cycles est de longueur impaire
( longueur 1 en cas de pt fixe) et donc si deux éléments successifs du cycle sont toujours à distance impaire, le premier et le dernier on forcément même parité.
$x_1 x_2 ...... x_{2k+1}$
$ x_2 x_3..... x_1$

Cette dernière approche un peu plus constructive, permet de répertorier entre autres les bijections x telle que le i en question soit unique.
$E = \{ x \in S_n , \exists ! \; i \; x_i - i \; pair \}$

Par exemple si n = 7, il faut les chercher en tous cas parmi les permutations:

- possédant un 1-cycle unique (càd un point fixe et un seul) sans autre cycle d'ordre impair (donc de type (1,6) ou (1,2,4)
- possédant un 3-cycle unique sans autre cycle d'ordre impair (donc de type (3 , 2, 2) ou (3,4))
- possédant un 5-cycle unique sans autre cycle d'ordre impair (donc de type ( 5, 2) )
- les 7-cycles

bref parmi les permutations ayant un unique cycle d'ordre impair.

Ainsi, entre autres (encore avec n=7) sont dans E, avec des types différents:

1 2 3 4 5 6 7
4 5 2 3 1 7 6

1 2 3 4 5 6 7
4 7 1 3 6 5 2

1 2 3 4 5 6 7
4 5 1 3 6 7 2

1 2 3 4 5 6 7
4 5 2 1 6 3 7

En effet on a vu qu'un cycle de longueur impaire fournit (au moins) un i valable.
Le reste du travail à effectuer n'est pas vraiment automatique, mais cela circonscrit déjà la question en donnant un pseudo "gabarit" pour x.
Je ne me suis pas penché sur la question du dénombrement, mais je pense qu'un algorithme travaillant sur ces gabarits pourrait fournir E.

A.

bridgslam · 15-08-2023 15:20:30

Ou encore, sinon, par bijection les i pairs donneraient des $A_i$ impairs et vice versa, donc il y aurait autant de pairs que d'impairs dans A.

A.

bridgslam · 15-08-2023 14:43:08

Bonjour,

Si tous ces nombres étaient impairs, comme ils sont en nombre impair, leur somme serait ....
Or cette somme vaut ...
Donc...

A.

Abirmdr · 15-08-2023 13:21:20

Je suis en train de faire un exercice, aucunes idées et aucunes pistes pour le résoudre, donc ,l'énoncé dit :
Soit A={1,2,3,...,n} avec n entier naturel impair et soient x1,x2,....,xn des éléments de A distincts deux à deux,
Montrer qu'il existe i dans A tel que xi-i est pair .

Merci de votre aide, j'espère trouver des idées clairs et peut m'aider dans cet exo .

Forum de mathématiques - Bibm@th.net

Répondre

Résumé de la discussion (messages les plus récents en premier)

Pied de page des forums