Las siguientes son definiciones comunes de coeficientes binomiales .
- Un coeficiente binomial C(n, k) se puede definir como el coeficiente de X^k en la expansión de (1 + X)^n.
- Un coeficiente binomial C(n, k) también da el número de formas, sin tener en cuenta el orden, en que pueden elegirse k objetos entre n objetos; más formalmente, el número de subconjuntos de k elementos (o k combinaciones) de un conjunto de n elementos.
Dados dos números n y r, encuentre el valor de n C r
Ejemplos:
Input : n = 5, r = 2 Output : 10 The value of 5C2 is 10 Input : n = 3, r = 1 Output : 3
La idea se basa simplemente en la siguiente fórmula.
n C r = (n!) / (r! * (nr)!)
C
#include <stdio.h> int factorial(int n) { if(n == 0) return 1; int factorial = 1; for (int i = 2; i <= n; i++) factorial = factorial * i; return factorial; } int nCr(int n, int r) { return factorial(n) / (factorial(r) * factorial(n - r)); } int main() { int n = 5, r = 3; printf("%d", nCr(n, r)); return 0; } // This code was contributed by Omkar Prabhune
C++
// CPP program To calculate The Value Of nCr #include <bits/stdc++.h> using namespace std; int fact(int n); int nCr(int n, int r) { return fact(n) / (fact(r) * fact(n - r)); } // Returns factorial of n int fact(int n) { if(n==0) return 1; int res = 1; for (int i = 2; i <= n; i++) res = res * i; return res; } // Driver code int main() { int n = 5, r = 3; cout << nCr(n, r); return 0; }
Java
// Java program To calculate // The Value Of nCr class GFG { static int nCr(int n, int r) { return fact(n) / (fact(r) * fact(n - r)); } // Returns factorial of n static int fact(int n) { if(n==0) return 1; int res = 1; for (int i = 2; i <= n; i++) res = res * i; return res; } // Driver code public static void main(String[] args) { int n = 5, r = 3; System.out.println(nCr(n, r)); } } // This code is Contributed by // Smitha Dinesh Semwal.
Python 3
# Python 3 program To calculate # The Value Of nCr def nCr(n, r): return (fact(n) / (fact(r) * fact(n - r))) # Returns factorial of n def fact(n): if n == 0: return 1 res = 1 for i in range(2, n+1): res = res * i return res # Driver code n = 5 r = 3 print(int(nCr(n, r))) # This code is contributed # by Smitha
C#
// C# program To calculate // The Value Of nCr using System; class GFG { static int nCr(int n, int r) { return fact(n) / (fact(r) * fact(n - r)); } // Returns factorial of n static int fact(int n) { if(n==0) return 1; int res = 1; for (int i = 2; i <= n; i++) res = res * i; return res; } // Driver code public static void Main() { int n = 5, r = 3; Console.Write(nCr(n, r)); } } // This code is Contributed by nitin mittal.
PHP
<?php // PHP program To calculate // the Value Of nCr function nCr( $n, $r) { return fact($n) / (fact($r) * fact($n - $r)); } // Returns factorial of n function fact( $n) { if($n == 0) return 1; $res = 1; for ( $i = 2; $i <= $n; $i++) $res = $res * $i; return $res; } // Driver code $n = 5; $r = 3; echo nCr($n, $r); // This code is contributed by vt_m. ?>
Javascript
<script> // Javascript program To calculate The Value Of nCr function nCr(n, r) { return fact(n) / (fact(r) * fact(n - r)); } // Returns factorial of n function fact(n) { if(n==0) return 1; var res = 1; for (var i = 2; i <= n; i++) res = res * i; return res; } // Driver code var n = 5, r = 3; document.write(nCr(n, r)); </script>
Producción:
10
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)
Soluciones Más Eficientes:
Programación Dinámica | Conjunto 9 (Coeficiente binomial)
Espacio y tiempo eficiente Coeficiente binomial
Todos los artículos sobre Coeficiente binomial
Publicación traducida automáticamente
Artículo escrito por Kanishk_Verma y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA