Función Combinatoria
La primera definición de esta función es
C(n,x) = n! / (n - x)! x! .... (n >= x )
Teniendo implementado la función factorial, una rápida solución para
esta ecuación, podría ser :
double combinatoria( int n , int x)
{
return factorial(n) / factorial(n - x) * factorial(x);
}
Pero si empezamos a ver el proceso de cálculo, podemos plantear otra solución.
Observemos que :
Tomando como referencia el ejemplo 2 , si se agrupan los términos de la división en pares, se tiene
D = { (9,4) (8,3) (7,2) (6,1) }
De aquí se observa que la diferencia entre (a,b) es igual a 5, que corresponde al
mayor entre x y n - x.
También se observa que el número de pares es igual a 4, que corresponde al
menor entre x y n - x.
diferencia (a,b) = mayor (x , n - x )
términos = menor (x , n - x)
Reordenando el conjunto :
D = { ( 6,1 ) ( 7,2 ) ( 8,3 ) ( 9,4 ) }
(6,1) = ( 1 + diferencia , 1 )
(7,2) = ( 2 + diferencia , 2 )
(8,3) = ( 3 + diferencia , 3 )
(9,4) = ( 4 + diferencia , 4 )
Algoritmo
Leer n , x
dif = mayor ( x , n - x)
term = menor ( x , n - x )
comb = 1
Para i = 1 hasta term hacer
comb = comb * ( ( i + dif ) / i )
fin para
class combinatoria
{
public static void main(String arg[ ])
{
System.out.println("C(5,3) : " + combinatoria(5,3));
System.out.println("C(6,3) : " + combinatoria(6,3));
System.out.println("C(8,5) : " + combinatoria(8,5));
System.out.println("C(9,4) : " + combinatoria(9,4));
System.out.println("C(2,1) : " + combinatoria(2,1));
}
public static long combinatoria(int n, int x )
{
int dif, term;
double comb = 1;
dif = Math.max(x , n - x);
term = Math.min(x , n - x);
for (int i = 1; i <= term ; i++)
{
comb *= (double) ( i + dif ) / i;
}
return (long) comb;
}
}
Bajar archivo
Salida a pantalla
*nota : La especificación del tipo en comb *= (double) .. , es fundamental para el proceso de cálculo.
