Combinaison et arrangement

[Sneeq]

Bonjour à tous!
Je cherche à résoudre un problème concernant les combinaisons et les arrangements. Le voici:
Je possède x objets que je dois ranger dans des boîtes ne pouvant contenir que 4 objets. Par contre je ne peux pas avoir 4 boîtes avec dans chacune un élément ( Il doit y avoir ⌊x / 4⌋ + 1 boîtes ). De plus, la position de chaque objet dans une boîte n'a pas d'importance.
Combien de possibilités donc quand j'ai x éléments?

Par exemple quand x≤4 : je n'ai qu'une possibilité
Quand x=5 : j'en possède 15 il me semble
Mais je n'ai pas trouvé de formule générale...

Merci d'avance pour vos réponses !

[anthony_unac]

Bonjour,
Si j'ai bien compris vous cherchez à la fois le nombre de boîtes dont on à besoin pour ranger les x objets ET le nombre de rangements possible ?
Pour le cas x=4 c'est trivial et une seule boite suffit à contenir les 4 objets donc 1 rangement possible.
Pour le cas x=5 vous aurez nécessairement besoin de deux boites dont une contenant un seul objet. Cet objet isolé peut être x_1 ou x_2 ou x_3 ou x_4 ou x_5 soit 5 possibilités (et non pas 15)

[GaBuZoMeu]

Les objets sont indistinguables, ou bien distingués (par exemple par un numéro) ?
Même question pour les boîtes ; les distingue-t-on ou pas ?

Par ailleurs pour le cas de 4 objets, quelque chose cloche : tu dis que le nombre de boîtes est égal à la partie entière du nombre d'objets divisé par 4, plus 1. Ça ferait donc 2 si le nombre d'objets est 4 ? Ou alors veux-tu dire plutôt que le nombre de boîtes est le plus petit entier supérieur ou égal au nombre de boîtes divisé par 4 ?

Bref, il faudrait mieux spécifier ton problème.

Pour le cas de 5 objets, supposant qu'il y a deux boîtes, la première peut contenir 1 ou 2 ou 3 ou 4 objets et la deuxième les autres. Si les objets ainsi que les boîtes sont numérotés, ça fait



Or tu dis trouver 15. Ça veut dire que tu comptes pour une seule possibilité le fait d'avoir les objets 1, 2 et 3 dans une boîte et les objets 4, 5 dans l'autre ?

Encore une fois, spécifie mieux ton problème.

[anthony_unac]

Par contre je ne peux pas avoir 4 boîtes avec dans chacune un élément ( Il doit y avoir ⌊x / 4⌋ + 1 boîtes ).

C'est exact si x n'est pas un multiple de 4 ! Par contre si x est un multiple de 4 il te faut x/4 boites tout bêtement

[Sneeq]

Bonjour,
Si j'ai bien compris vous cherchez à la fois le nombre de boîtes dont on à besoin pour ranger les x objets ET le nombre de rangements possible ?
Pour le cas x=4 c'est trivial et une seule boite suffit à contenir les 4 objets donc 1 rangement possible.
Pour le cas x=5 vous aurez nécessairement besoin de deux boites dont une contenant un seul objet. Cet objet isolé peut être x_1 ou x_2 ou x_3 ou x_4 ou x_5 soit 5 possibilités (et non pas 15)

Je ne recherche que le nombre de combinaisons possible. Pour le cas où x = 5, il y a en effet besoin de 2 boîtes. Le seul bémol est que les boîtes ne sont pas forcement pleines (mais en ayant le nombre minimum de boîtes).
Il peut y avoir 1 boite de 4 objets et 1 autre de 1 ; mais aussi une boîte de 3 objets et une autre de 2

Les objets sont indistinguables, ou bien distingués (par exemple par un numéro) ?
Même question pour les boîtes ; les distingue-t-on ou pas ?

Les objets sont bien distinguables mais pas les boîtes.

Par ailleurs pour le cas de 4 objets, quelque chose cloche : tu dis que le nombre de boîtes est égal à la partie entière du nombre d'objets divisé par 4, plus 1. Ça ferait donc 2 si le nombre d'objets est 4 ? Ou alors veux-tu dire plutôt que le nombre de boîtes est le plus petit entier supérieur ou égal au nombre de boîtes divisé par 4 ?

Je pense avoir trouvé la bonne formulation pour avoir le nombre de boîtes : ⌈(x-1) / 4⌉


Si vous avez d'autres points à éclaircir n'hésitez pas.
Merci d'avance

[GaBuZoMeu]

Je pense avoir trouvé la bonne formulation pour avoir le nombre de boîtes : ⌈(x-1) / 4⌉

Ben non, encore raté ! Ça donnerait une boîte pour x=5. Je t'ai pourtant donné explicitement la bonne formule !!

[lyceen95]

La formule générale va être compliquée :
4 objets = 1 seule solution
5 objets = 15 solutions
6 objets = 50 solutions
7 objets = 35 solutions
8 objets = 35 solutions
9 objets = 2949 solutions sous toutes réserves.
Visiblement, la formule générale va être assez compliquée ; Dès que le nombre d'objets est de la forme 4k+1, le nombre de combinaisons s'envole. Par contre, quand on passe de 4k+1 à 4k+2 , ou de 4k+2 à 4k+3, ou pire, de 4k+3 à 4k+4, le nombre de combinaisons n'augmente pas, voire il diminue.

[GaBuZoMeu]

Bon, donc, si je comprends bien, tu veux compter le nombre de partitions d'un ensemble à n (je préfère à x) éléments en un nombre de classes égal au plus petit entier supérieur ou égal à n/4, où chaque classe contient au plus 4 éléments.

Un petit programme python 3 pour compter ça :

ATTENTION ! ERREUR D'ÉCRITURE DU CODE, QUI DONNE DES RÉSULTATS ABERRANTS ! VOIR CORRECTION PLUS BAS.

Code: Tout sélectionner

from math import *

def rangements(n):
    q=n//4 ; r=n%4
    if r==0 :
        return factorial(n) // factorial(4)**q // factorial(q)
    if r==3 :
        return factorial(n) // factorial(4)**q // factorial(q)\
                             // factorial(3)
    if r==2 :
        p1= factorial(n) // factorial(4)**q // factorial(q) \
        // factorial(2)
        if q>0 :
            p2= factorial(n) // factorial(4)**(q-1) // factorial(q-1)\
            // factorial(3)^2 // factorial(2)
        else : p2=0
        return p1+p2
    if r==1 :
        p1= factorial(n) // factorial(4)**q // factorial(q)
        if q>0 :
            p2= factorial(n) // factorial(4)**(q-1) // factorial(q-1)\
            // factorial(3) // factorial(2)
        else : p2=0
        if q>1 :
            p3= factorial(n) // factorial(4)**(q-2) // factorial(q-2)\
            // factorial(3)^3 // factorial(3)
        else : p3=0
        return p1+p2+p3
       

et les premiers résultats obtenus :
pour n = 0 nombre de partitions = 1
pour n = 1 nombre de partitions = 1
pour n = 2 nombre de partitions = 1
pour n = 3 nombre de partitions = 1
pour n = 4 nombre de partitions = 1
pour n = 5 nombre de partitions = 15
pour n = 6 nombre de partitions = 136
pour n = 7 nombre de partitions = 35
pour n = 8 nombre de partitions = 35
pour n = 9 nombre de partitions = 62055
pour n = 10 nombre de partitions = 26776
pour n = 11 nombre de partitions = 5775
pour n = 12 nombre de partitions = 5775
pour n = 13 nombre de partitions = 43768725
pour n = 14 nombre de partitions = 13138126
pour n = 15 nombre de partitions = 2627625
pour n = 16 nombre de partitions = 2627625
pour n = 17 nombre de partitions = 51861434625
pour n = 18 nombre de partitions = 13266878626
pour n = 19 nombre de partitions = 2546168625
pour n = 20 nombre de partitions = 2546168625

Pas mal différent des résultats de lycéen95. À voir ...

[lyceen95]

Pour n=6, on a 2 boites.
1re configuration : 4 éléments dans une boite et 2 dans l'autre. Il y a 6*5/2=15 façons de choisir les 2 éléments de la 2ème boite.
2_ème configuration : 3 éléments dans chaque boite. On regarde la boite qui a l'élément n°1, il y a 5*4/2=10 façons de compléter cette boite.
Et donc 15+10 = 25 façons de disposer nos 6 objets dans 2 boites.

Je ne vois pas par quel raisonnement j'arrivais à 50 hier !

Je suis toujours sur l'énoncé : Les objets sont bien distinguables mais pas les boîtes.
Chaque boite contient au maximum 4 objets, et on prend le nombre minimum de boites correspondant à n.


Essayons de généraliser :

Pour n=4k
il y a solutions.


Pour n de la forme 4k+1
On a
- Soit k boites pleines et une boite avec 1 seul élément; possibilités.
- Soit k-1 boites pleines , une boite avec 3 éléments et 1 boite avec 2 éléments.
On a n*(n-1)*(n-2)*(n-3)*(n-4)/5! façons de choisir les 5 éléments à part, et on a 10 façons de répartir ces 5 éléments en une boite de 2 et une boite de 3. -->
- Soit k-2 boites pleines, et 3 boites de 3 éléments ( valable uniquement à partir de n=9)
On a n!(n-9)!/9! façons de choisir les 9 éléments en question.
Quand on a 9 éléments à répartir entre 3 boites, prenons l'élément de plus petit indice. il y a 8x7/2 façons de choisir les 2 Autres éléments qui seront dans sa boite.
Prenons ensuite l'élément de plus petit indice parmi les 6 éléments restants, il y a 5x4/2 façons de choisir les 2 éléments qui l'accompagnent.
donc


Pour n de la forme 4k+2, avec k>1,
On a
- soit k boites pleines et une boite avec 2 éléments : n*(n-1)/2 * (4k)! /(4!^k) /k!

- soit k-1 boites pleines et 2 boites avec 3 éléments.
On a n*(n-1)*(n-2)*(n-3)*(n-4)*(n-5)/6! façons de choisir les 6 éléments qui sont dans des boites de 3 éléments ; et on a 10 façons de dispatcher nos 6 éléments en 2 boites de 3. (Le même 10 que ci-dessus).

Donc solutions quand n=4k/2

Pour n de la forme 4k+3
Il y a une seule combinaison, k boites de 4 et une boite de 3
Nb solutions = n*(n-1)*(n-2)/6 * (4k!) /(4!)^k / k!


Pas sûr à 100%de tous ces calculs, puisque j'ai corrigé déjà 2 fois le principe. J'ai donc peut-être encore oublié un truc, jamais 2 sans 3.

[GaBuZoMeu]

Je corrige le code (l'erreur était d'avoir utilisé ^au lieu de ** pour des exponentiations :

Code: Tout sélectionner

from math import *

def rangements(n):
    q=n//4 ; r=n%4
    if r==0 :
        return factorial(n) // factorial(4)**q // factorial(q)
    if r==3 :
        return factorial(n) // factorial(4)**q //\
    factorial(q)// factorial(3)
    if r==2 :
        p1= factorial(n) // factorial(4)**q //\
        factorial(q) // factorial(2)
        if q>0 :
            p2= factorial(n) // factorial(4)**(q-1) //\
            factorial(q-1)// factorial(3)**2 // factorial(2)
        else : p2=0
        return p1+p2
    if r==1 :
        p1= factorial(n) // factorial(4)**q // factorial(q)
        if q>0 :
            p2= factorial(n) // factorial(4)**(q-1)//\
            factorial(q-1)// factorial(3) // factorial(2)
        else : p2=0
        if q>1 :
            p3= factorial(n) // factorial(4)**(q-2) //\
            factorial(q-2)// factorial(3)**3 // factorial(3)
        else : p3=0
        return p1+p2+p3

et maintenant les résultats sont plus raisonnables :
pour n = 0 nombre de partitions = 1
pour n = 1 nombre de partitions = 1
pour n = 2 nombre de partitions = 1
pour n = 3 nombre de partitions = 1
pour n = 4 nombre de partitions = 1
pour n = 5 nombre de partitions = 15
pour n = 6 nombre de partitions = 25
pour n = 7 nombre de partitions = 35
pour n = 8 nombre de partitions = 35
pour n = 9 nombre de partitions = 1855
pour n = 10 nombre de partitions = 3675
pour n = 11 nombre de partitions = 5775
pour n = 12 nombre de partitions = 5775
pour n = 13 nombre de partitions = 725725
pour n = 14 nombre de partitions = 1576575
pour n = 15 nombre de partitions = 2627625
pour n = 16 nombre de partitions = 2627625
pour n = 17 nombre de partitions = 640264625
pour n = 18 nombre de partitions = 1474097625
pour n = 19 nombre de partitions = 2546168625
pour n = 20 nombre de partitions = 2546168625

L'algorithme est toujours le même : pour n=4q+1 par exemple, il y a q+1 boîtes.
On considère les n! permutations des objets.
On met les 4 premiers dans une boîte, les 4 suivants dans une boîte, etc. et le dernier dans une boîte;
ou alors si q>0 on met, dans l'ordre de la permutation, q-1 fois 4 objets dans une boîte, puis 3 objets dans une boîte et les 2 derniers dans une boîte;
ou alors si q>1 on met, dans l'ordre de la permutation, q-2 fois 4 objets dans une boîte, puis trois fois 3 objets dans une boîte.
Pour chaque schéma de répartition on peut permuter les objets à l'intérieur de chaque boîte, et on peut permuter les boîtes ayant même nombre d'objets.

Maintenant je suis sûr de mon coup. Lycéen95, tu pourras comparer avec ce que tu trouves.

[fatal_error]

hi,

Je me corrige, ok pour moi pour n = 9 aussi
pour n=9
(C_9^4 * C_5^4)/2 = 315
C_9^4 * C_5^3 = 1260
(C_9^3 * C_6^3)/6 = 1680/6
tot: 1680

Une manière de visualiser:
placer les objets dans les boites (notés x). Les objets "manquants" sont représentés par 0
shifter les objets vers la droite
r est le nombre d'objets restant si toutes les boites sont pleines

r==1
[[xxxx],[xxxx],[x000]]
[[0xxx],[xxxx],[xx00]]*
[[00xx],[xxxx],[xxx0]]//pareil que [[0xxx],[xxxx],[xx00]]
[[000x],[xxxx],[xxxx]]//pareil que [[xxxx],[xxxx],[x000]]
*focus sur [xxxx],[xx00]: [[0xxx],[xxx0]]
n!/(4!)^(k-1) / (k-1)! / 1!
n!/(4!)^(k-2) / (k-2)! / 2! / 3!
n!/(4!)^(k-3) / (k-3)! / (3!)^3 /3!

r==2
[[xxxx],[xxxx],[xx00]]
[[0xxx],[xxxx],[xxx0]]
n!/(4!)^(k-1) / (k-1)! / 2!
n!/(4!)^(k-2) / (k-2)! / (3!)^2 / 2!

r==3
[[xxxx],[xxxx],[xxx0]]
n!/(4!)^(k-1) / (k-1)! / 3!

r==0
[[xxxx],[xxxx],[xxxx]]
n!/(4!)^k / k!

Code: Tout sélectionner

from math import factorial as f
def count(n):
  if n <= 4:
    return 1
  k = 1 + (n-1) // 4
  r = n % 4
  fn = f(n)
  f4 = f(4)
  p = lambda q: f4**q * f(q)

  if r == 0:
    return fn / p(k)
  if r == 3:
    return fn / p(k-1) / f(3)
  if r == 2:
    a = fn / p(k-1) / f(2)
    b = 0
    if k - 2 >= 0:
      b = fn / p(k-2) / f(3)**2 / f(2)
    return a + b
  if r == 1:
    a = fn / p(k-1) / f(1)
    b = 0
    c = 0
    if k - 2 >= 0:
      b = fn / p(k-2) / f(2) / f(3)
      if k - 3 >= 0:
        c = fn / p(k-3) / f(3)**3 / f(3)
    return a + b + c


for i in range(1, 15):
  print(i, count(i))


Code: Tout sélectionner

1 1
2 1
3 1
4 1
5 15.0
6 25.0
7 35.0
8 35.0
9 1855.0
10 3675.0
11 5775.0
12 5775.0
13 725725.0
14 1576575.0