S(r, n), representa el número de formas en que podemos organizar r objetos alrededor de círculos indistinguibles de longitud n, y cada círculo n debe tener al menos un objeto a su alrededor.
Ejemplos:
Input: r = 9, n = 2 Output: 109584 Input: r = 6, n = 3 Output: 225
Los casos especiales son:
- S(r, 0) = 0, trivial.
- ¡ S(r, 1) representa la permutación circular que es igual a (r – 1)!
- S(r, n) donde r = n, es igual a 1.
- S(r, r -1) = rC2
Una identidad importante de los números de Stirling que S(r, n) = S(r – 1, n – 1) + (r – 1) * S(r – 1, n)
Enfoque: Para simplificar, denote los r objetos distintos por 1, 2, …, r. Considere el objeto «1». En cualquier disposición de los objetos, ya sea
- “1” es el único objeto en un círculo o
- “1” se mezcla con otros en un círculo.
En el caso 1, hay s(r – 1, n – 1) formas de formar dichos arreglos. En el caso 2, en primer lugar, los r — 1 objetos 2, 3, …, r se colocan en n círculos de s(r — 1, n) formas; entonces “1” se puede colocar en uno de los r — 1 espacios distintos a la “derecha inmediata” de los r — 1 objetos distintos correspondientes. Por el principio de multiplicación, hay (r — 1)s(r — 1, n) maneras de formar tales arreglos en el caso 2. La identidad ahora se sigue de la definición de s(r, n) y el principio de adición.
Usando los valores iniciales S(0, 0) = 1, s(r, 0) = 0 para r > 1 y s(r, 1) = (r — 1)! para r > 1, y aplicando la identidad que demostramos, podemos obtener fácilmente el número de Stirling calculándolo de forma recursiva.
En el código, tenemos tres funciones que se utilizan para generar los números de Stirling, que son nCr(n, r), que es una función para calcular lo que llamamos (n – elegir – r), la cantidad de formas que podemos tomar r objetos a partir de n objetos sin la importancia de los ordenamientos. factorial (int n) se usa, como era de esperar, para calcular el factorial de un número n. La función número de Stirling (r, n) funciona recursivamente usando los cuatro casos base discutidos anteriormente y luego recursivamente usando la identidad que probamos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement above approach
#include <iostream>
using namespace std;
// Calculating factorial of an integer n.
long long factorial(int n)
{
// Our base cases of factorial 0! = 1! = 1
if (n == 0)
return 1;
// n can't be less than 0.
if (n < 0)
return -1;
long long res = 1;
for (int i = 2; i < n + 1; ++i)
res *= i;
return res;
}
// Function to compute the number of combination
// of r objects out of n objects.
int nCr(int n, int r)
{
// r cant be more than n so we'd like the
// program to crash if the user entered
// wrong input.
if (r > n)
return -1;
if (n == r)
return 1;
if (r == 0)
return 1;
// nCr(n, r) = nCr(n - 1, r - 1) + nCr(n - 1, r)
return nCr(n - 1, r - 1) + nCr(n - 1, r);
}
// Function to calculate the Stirling numbers.
// The base cases which were discussed above are handled
// to stop the recursive calls.
long long stirlingNumber(int r, int n)
{
// n can't be more than
// r, s(r, 0) = 0.
if (n > r)
return -1;
if (n == 0)
return 0;
if (r == n)
return 1;
if (n == 1)
return factorial(r - 1);
if (r - n == 1)
return nCr(r, 2);
else
return stirlingNumber(r - 1, n - 1)
+ (r - 1) * stirlingNumber(r - 1, n);
}
// Driver program
int main()
{
// Calculating the stirling number s(9, 2)
int r = 9, n = 2;
long long val = stirlingNumber(r, n);
if (val == -1)
cout << " No stirling number";
else
cout << "The Stirling Number s(" << r
<< ", " << n << ") is : " << val;
return 0;
}
Java
// Java program to implement
// above approach
import java.io.*;
class GFG
{
// Calculating factorial of
// an integer n.
static long factorial(int n)
{
// Our base cases of factorial
// 0! = 1! = 1
if (n == 0)
return 1;
// n can't be less than 0.
if (n < 0)
return -1;
long res = 1;
for (int i = 2; i < n + 1; ++i)
res *= i;
return res;
}
// Function to compute the number
// of combination of r objects
// out of n objects.
static int nCr(int n, int r)
{
// r cant be more than n so
// we'd like the program to
// crash if the user entered
// wrong input.
if (r > n)
return -1;
if (n == r)
return 1;
if (r == 0)
return 1;
return nCr(n - 1, r - 1) +
nCr(n - 1, r);
}
// Function to calculate the Stirling
// numbers. The base cases which were
// discussed above are handled to stop
// the recursive calls.
static long stirlingNumber(int r, int n)
{
// n can't be more than
// r, s(r, 0) = 0.
if (n > r)
return -1;
if (n == 0)
return 0;
if (r == n)
return 1;
if (n == 1)
return factorial(r - 1);
if (r - n == 1)
return nCr(r, 2);
else
return stirlingNumber(r - 1, n - 1) +
(r - 1) *
stirlingNumber(r - 1, n);
}
// Driver Code
public static void main (String[] args)
{
// Calculating the stirling number s(9, 2)
int r = 9, n = 2;
long val = stirlingNumber(r, n);
if (val == -1)
System.out.println(" No stirling number");
else
System.out.println( "The Stirling Number s(" +
r + ", " + n + ") is : " + val);
}
}
// This Code is Contributed by anuj_67
Python 3
# Python 3 program to implement above approach # Function to compute the number of combination # of r objects out of n objects. # nCr(n, n) = 1, nCr(n, 0) = 1, and these are # the base cases. def nCr(n, r): if(n == r): return 1 if(r == 0): return 1 # nCr(n, r) = nCr(n - 1, r - 1) + nCr(n - 1, r) return nCr(n - 1, r - 1) + nCr(n - 1, r) # This function is used to calculate the # factorial of a number n. def factorial(n): res = 1 # 1 ! = 0 ! = 1 if(n <= 1): return res for i in range(1, n + 1): res *= i return res # Main function to calculate the Stirling numbers. # the base cases which were discussed above are # handled to stop the recursive call, n can't be # more than r, s(r, 0) = 0. # s(r, r) = 1. s(r, 1) = (r - 1)!. # s(r, r - 1) = nCr(r, 2) # else as we proved, s(r, n) = s(r - 1, n - 1) # + (r - 1) * s(r - 1, n) def stirlingNumber(r, n): if(r == n): return 1 if(n == 0): return 0 if(n == r -1): return nCr(r, 2) if(r - n == 1): return factorial(r - 1) return (stirlingNumber(r - 1, n - 1) + (r - 1) * stirlingNumber(r - 1, n)) r, n = 9, 2 print(stirlingNumber(r, n))
C#
// C# program to implement
// above approach
using System;
class GFG
{
// Calculating factorial of
// an integer n.
static long factorial(int n)
{
// Our base cases of factorial
// 0! = 1! = 1
if (n == 0)
return 1;
// n can't be less than 0.
if (n < 0)
return -1;
long res = 1;
for (int i = 2; i < n + 1; ++i)
res *= i;
return res;
}
// Function to compute the number
// of combination of r objects
// out of n objects.
static int nCr(int n, int r)
{
// r cant be more than n so
// we'd like the program to
// crash if the user entered
// wrong input.
if (r > n)
return -1;
if (n == r)
return 1;
if (r == 0)
return 1;
return nCr(n - 1, r - 1) +
nCr(n - 1, r);
}
// Function to calculate the Stirling
// numbers. The base cases which were
// discussed above are handled to stop
// the recursive calls.
static long stirlingNumber(int r, int n)
{
// n can't be more than
// r, s(r, 0) = 0.
if (n > r)
return -1;
if (n == 0)
return 0;
if (r == n)
return 1;
if (n == 1)
return factorial(r - 1);
if (r - n == 1)
return nCr(r, 2);
else
return stirlingNumber(r - 1, n - 1) +
(r - 1) *
stirlingNumber(r - 1, n);
}
// Driver Code
public static void Main ()
{
// Calculating the stirling
// number s(9, 2)
int r = 9, n = 2;
long val = stirlingNumber(r, n);
if (val == -1)
Console.WriteLine(" No stirling number");
else
Console.WriteLine( "The Stirling Number s(" +
r + ", " + n + ") is : " + val);
}
}
// This code is contributed by inder_verma..
PHP
<?php
// PHP program to implement above approach
// Calculating factorial of an integer n.
function factorial($n)
{
// Our base cases of factorial 0! = 1! = 1
if ($n == 0)
return 1;
// n can't be less than 0.
if ($n < 0)
return -1;
$res = 1;
for ($i = 2; $i < $n + 1; ++$i)
$res *= $i;
return $res;
}
// Function to compute the number of combination
// of r objects out of n objects.
function nCr($n, $r)
{
// r cant be more than n so we'd like the
// program to crash if the user entered
// wrong input.
if ($r > $n)
return -1;
if ($n == $r)
return 1;
if ($r == 0)
return 1;
// nCr($n, $r) = nCr($n - 1, $r - 1) + nCr($n - 1, $r)
return nCr($n - 1, $r - 1) + nCr($n - 1, $r);
}
// Function to calculate the Stirling numbers.
// The base cases which were discussed above are handled
// to stop the recursive calls.
function stirlingNumber($r, $n)
{
// n can't be more than
// r, s(r, 0) = 0.
if ($n > $r)
return -1;
if ($n == 0)
return 0;
if ($r == $n)
return 1;
if ($n == 1)
return factorial($r - 1);
if ($r - $n == 1)
return nCr($r, 2);
else
return stirlingNumber($r - 1, $n - 1)
+ ($r - 1) * stirlingNumber($r - 1, $n);
}
// Calculating the stirling number s(9, 2)
$r = 9;
$n = 2;
$val = stirlingNumber($r, $n);
if ($val == -1)
echo " No stirling number";
else
echo "The Stirling Number s(", $r
,", " , $n , ") is : " , $val;
// This code is contributed by ANKITRAI1
?>
Javascript
<script>
// js program to implement above approach
// Calculating factorial of an integer n.
function factorial( n)
{
// Our base cases of factorial 0! = 1! = 1
if (n == 0)
return 1;
// n can't be less than 0.
if (n < 0)
return -1;
let res = 1;
for (let i = 2; i < n + 1; ++i)
res *= i;
return res;
}
// Function to compute the number of combination
// of r objects out of n objects.
function nCr(n, r)
{
// r cant be more than n so we'd like the
// program to crash if the user entered
// wrong input.
if (r > n)
return -1;
if (n == r)
return 1;
if (r == 0)
return 1;
// nCr(n, r) = nCr(n - 1, r - 1) + nCr(n - 1, r)
return nCr(n - 1, r - 1) + nCr(n - 1, r);
}
// Function to calculate the Stirling numbers.
// The base cases which were discussed above are handled
// to stop the recursive calls.
function stirlingNumber( r, n)
{
// n can't be more than
// r, s(r, 0) = 0.
if (n > r)
return -1;
if (n == 0)
return 0;
if (r == n)
return 1;
if (n == 1)
return factorial(r - 1);
if (r - n == 1)
return nCr(r, 2);
else
return stirlingNumber(r - 1, n - 1)
+ (r - 1) * stirlingNumber(r - 1, n);
}
// Driver program
// Calculating the stirling number s(9, 2)
let r = 9, n = 2;
let val = stirlingNumber(r, n);
if (val == -1)
document.write( " No stirling number");
else
document.write( "The Stirling Number s(", r
, ", " , n , ") is : " , val);
</script>
The Stirling Number s(9, 2) is : 109584
Nota: La solución anterior se puede optimizar mediante Programación Dinámica . Consulte, Números de campana (Número de formas de particionar un conjunto), por ejemplo.
Consulte los números de Stirling del primer tipo para obtener más información sobre los números de Stirling.
Publicación traducida automáticamente
Artículo escrito por MahmoudAbdAl-Ghany y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA