[gull] nombre de combinaisons pour deux mots binaires

[Yves Martin]

On Thu, 2015-09-10 at 20:13 +0200, amel kapetanovic wrote:
> Le 10. 09. 15 17:24, Michael Parchet a écrit :
> > C'est quoi un mot binaire 
> 
> Un mot binaire est une suite de bits, si c'est un mot de disons 3 bits, 
> cela pourrait être 001, 101, 000, 111, etc.
> 
> A disposition si besoin est, avec mes salutations,
> Amel

 Bonjour,

Jolie question. Désolé hier soir, j'ai préféré Person of Interest...

Soit l'ensemble des entiers naturels positifs codés sur x bits, nommé "x-bits" 
La taille de l'ensemble "x-bits" (nombre de mots de x bits) est: 2^x

Je considère qu'une multiplication A x B équivaut à B x A et qu'il ne faut pas les compter à
double.

Avec a < b
il s'agit donc de dénombrer le nombre de pairs non ordonnés possible en
prenant un élément de l'ensemble "a-bits" et un élément de l'ensemble "b-bits",
sachant que "a-bits" est inclus dans "b-bits".

Le nombre de pairs non ordonnés correspond à la somme des entiers compris
de l'intervalle [ (2^b - 2^a) .. 2^b ]

Sachant que la somme des entiers de l'intervalle [1..n] est n(n+1)/2

Le résultat est: (2^b + 1)*2^(b-1) - (2^(b-1) - 2^(a-1))*(2^b - 2^a + 1)


Mon résultat compte bien sûr les pairs correspondant
à "0 * x" et à "1 * x" 


Je suis convaincu que l'on peut exprimer cela en terme de combinatoires
comme la façon de préléver deux éléments non ordonnés dans un ensemble
"b-bits" de 2^b éléments et dans son sous-ensemble inclus "a-bits" de
2^a éléments (en utilisant les fameux C(k,n), A(k,n) et factorielle mais
je n'ai pas creusé plus - https://fr.wikipedia.org/wiki/Combinatoire)


Sinon la réponse de Tibor 2^(a+b) est juste, à condition de considérer
que A x B est différent de B x A.


Bonne fin de semaine
-- 
Yves Martin