Números de Stirling

En matemáticas, los números de Stirling resuelven algunos problemas del área de combinatoria. Su nombre se debe a James Stirling, quien los popularizó en el siglo XVIII. Existen dos diferentes conjuntos de números con este nombre: números de Stirling de primera especie y números de Stirling de segunda especie. Fueron descubiertos nuevamente por Masanobu Saka en 1782, quien les otorgó su relevancia en combinatoria en su libro Sanpo-Gakkai (El mar del aprendizaje matemático).[1]​[2]​

Notación

Existen diversas formas de denotar los números de Stirling. Los números de Stirling de primera especie se escriben con una s pequeña y los de segunda especie con una S grande (Abramowitz and Stegun usa una mayúscula o una S gótica). Las notaciones más comunes son:

  • Los números de Stirling de primera especie ordinarios (signados) se denotan como:

s ( n , k )  (con signo) {\displaystyle s(n,k){\text{ (con signo)}}\,}

  • Los números de Stirling de primera especie no signados se denotan como:

[ n k ] = c ( n , k ) = | s ( n , k ) |  (sin signo) {\displaystyle \left[{n \atop k}\right]=c(n,k)=|s(n,k)|{\text{ (sin signo)}}\,}

Los números de Stirling de segunda especie se denotan como:

{ n k } = S ( n , k ) = S n ( k ) . {\displaystyle \left\{{\begin{matrix}n\\k\end{matrix}}\right\}=S(n,k)=S_{n}^{(k)}.\,}

La notación usando llaves y corchetes, en analogía a los coeficientes binomiales, fue introducida en 1935 por Jovan Karamata y promocionada por Donald Knuth; referida a veces como la notación de Karamata.

Números de Stirling de primera especie

Artículo principal: Números de Stirling de primera especie

Los números de Stirling de primera especie son los coeficientes s(n,k) de la expansión:

( x ) n = ∑ k = 0 n s ( n , k ) x k {\displaystyle (x)_{n}=\sum _{k=0}^{n}s(n,k)x^{k}\,}

donde ( x ) n {\displaystyle (x)_{n}} (símbolo de Pochhammer) denota el factorial descendente,

( x ) n = x ( x − 1 ) ( x − 2 ) ⋯ ( x − n + 1 ) {\displaystyle (x)_{n}=x(x-1)(x-2)\cdots (x-n+1)\,}

Nótese que (x)0 = 1 porque es un producto vacío. En combinatoria también se usa la notación x n _ {\displaystyle x^{\underline {n\!}}} para el factorial descedente, y x n ¯ {\displaystyle x^{\overline {n\!}}} para el factorial ascendente.[3]​

Los números de Stirling de primera especie no signados:

c ( n , k ) = [ n k ] = | s ( n , k ) | = ( − 1 ) n − k s ( n , k ) {\displaystyle c(n,k)=\left[{n \atop k}\right]=|s(n,k)|=(-1)^{n-k}s(n,k)}

(con una "s" minúscula), cuenta el número de permutaciones de n elementos con k ciclos disjuntos. Las siguiente tabla muestra algunos pocos números de Stirling de primera especie:

    1     − 1     1     2 − 3     1     − 6 11 − 6     1     24 − 50 35 − 10     1     − 120 274 − 225 85 − 15     1     {\displaystyle {\begin{array}{ccccccccccc}&&&&&~~1~~&&&&&\\&&&&-1&&~~1~~&&&&\\&&&2&&-3&&~~1~~&&&\\&&-6&&11&&-6&&~~1~~&&\\&24&&-50&&35&&-10&&~~1~~&\\-120&&274&&-225&&85&&-15&&~~1~~\\\end{array}}}

donde

s ( n , k ) = s ( n − 1 , k − 1 ) + ( n − 1 ) s ( n − 1 , k ) {\displaystyle s(n,k)=s(n-1,k-1)+(n-1)s(n-1,k)}

Números de Stirling de segunda especie

El número de Stirling de segunda especie S ( n , k ) {\displaystyle S(n,k)} de formas de dividir un conjunto de n elementos en k partes:

S ( n , k ) = card ( { B |   card ( B ) = k ∧ B ⊂ N n } ) {\displaystyle S(n,k)={\text{card}}\left(\{B|\ {\text{card}}(B)=k\land B\subset \mathbb {N} _{n}\}\right)}

donde el conjunto N n = [ 1 , n ] ∩ N {\displaystyle \mathbb {N} _{n}=[1,n]\cap \mathbb {N} } es el conjunto de los primeros n enteros. Otra notación para los números de Stirling de segunda especie son:

{ n k } := S ( n , k ) {\displaystyle \left\{{\begin{matrix}n\\k\end{matrix}}\right\}:=S(n,k)}

A continuación se muestra una tabla de valores para los números de Stirling de segunda especie:

n \ k 0 1 2 3 4 5 6 7 8 9
0 1
1 0 1
2 0 1 1
3 0 1 3 1
4 0 1 7 6 1
5 0 1 15 25 10 1
6 0 1 31 90 65 15 1
7 0 1 63 301 350 140 21 1
8 0 1 127 966 1701 1050 266 28 1
9 0 1 255 3025 7770 6951 2646 462 36 1

donde:

S ( n , k ) = S ( n − 1 , k − 1 ) + k S ( n − 1 , k ) {\displaystyle S(n,k)=S(n-1,k-1)+kS(n-1,k)\,}

Fórmulas simétricas

Abramowitz y Stegun presentan las siguientes fórmulas simétricas que relacionan los número de Stirling de primera especie con los de segunda especie:

[ n k ] = ( − 1 ) n − k ∑ j = 0 n − k ( − 1 ) j ( n − 1 + j n − k + j ) ( 2 n − k n − k − j ) { n − k + j j } {\displaystyle \left[{n \atop k}\right]=(-1)^{n-k}\sum _{j=0}^{n-k}(-1)^{j}{n-1+j \choose n-k+j}{2n-k \choose n-k-j}\left\{{n-k+j \atop j}\right\}}

Y

{ n k } = ( − 1 ) n − k ∑ j = 0 n − k ( − 1 ) j ( n − 1 + j n − k + j ) ( 2 n − k n − k − j ) [ n − k + j j ] . {\displaystyle \left\{{n \atop k}\right\}=(-1)^{n-k}\sum _{j=0}^{n-k}(-1)^{j}{n-1+j \choose n-k+j}{2n-k \choose n-k-j}\left[{n-k+j \atop j}\right].}

Referencias

  1. ↑ Mansour y Schork, 2015, p. 4.
  2. ↑ Cuesta, J. A. (2019). Roma, ramo, amor: el arte de la combinatoria. Colección Grandes Ideas de las Matemáticas. 144 pp. Eslovenia: Emse Edapp/Prisanoticias Colecciones. ISBN 978-84-17506-93-3
  3. ↑ Aigner, Martin (2007). «Section 1.2 - Subsets and Binomial Coefficients». A Course In Enumeration. Springer. p. 561. ISBN 3-540-39032-4. 

Bibliografía

  • M. Abramowitz, I. Stegun (Eds.). Stirling Numbers of the First Kind., §24.1.3 in Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, 9th printing. New York: Dover, p. 824, 1972.
  • Milton Abramowitz and Irene A. Stegun, eds., Handbook of Mathematical Functions (with Formulas, Graphs and Mathematical Tables), U.S. Dept. of Commerce, National Bureau of Standards, Applied Math. Series 55, 1964, 1046 pages (9th Printing: November 1970) - Combinatorial Analysis, Table 24.4, Stirling Numbers of the Second Kind (author: Francis L. Miksa), p. 835.
  • D.E. Knuth, Two notes on notation Archivado el 6 de mayo de 2021 en Wayback Machine. (TeX source).
  • Louis Comtet, Valeur de s(n, k), Analyse combinatoire, Tome second (page 51), Presses universitaires de France, 1970.
  • Louis Comtet, Advanced Combinatorics: The Art of Finite and Infinite Expansions, Reidel Publishing Company, Dordrecht-Holland/Boston-U.S.A., 1974.
  • Stirling numbers of the first kind, s(n,k) en PlanetMath..
  • Stirling numbers of the second kind, S(n,k) en PlanetMath..
  • Neil J. A. Sloane, The On-Line Encyclopedia of Integer Sequences.
  • Francis L. Miksa (1901–1975), Stirling numbers of the first kind, "27 leaves reproduced from typewritten manuscript on deposit in the UMT File", Mathematical Tables and Other Aids to Computation, vol. 10, no. 53, January 1956, pp. 37–38 (Reviews and Descriptions of Tables and Books, 7[I]).
  • Dragoslav S. Mitrinović, Sur les nombres de Stirling de première espèce et les polynômes de Stirling, AMS 11B73_05A19, Publications de la Faculté d'Electrotechnique de l'Université de Belgrade, Série Mathématiques et Physique (ISSN 0522-8441), n.º 23, 1959 (5.V.1959), pp. 1–20.
  • Victor Adamchik, "On Stirling Numbers and Euler Sums Archivado el 16 de junio de 2009 en Wayback Machine.", Journal of Computational and Applied Mathematics 79 (1997) pp. 119–130.
  • Arthur T. Benjamin, Gregory O. Preston, Jennifer J. Quinn, A Stirling Encounter with Harmonic Numbers, (2002) Mathematics Magazine, 75 (2) pp 95–103.
  • J. M. Sixdeniers, K. A. Penson, A. I. Solomon, Extended Bell and Stirling Numbers From Hypergeometric Exponentiation (2001), Journal of Integer Sequences, 4, Article 01.1.4.
  • Hsien-Kuei Hwang (1995). «Asymptotic Expansions for the Stirling Numbers of the First Kind». Journal of Combinatorial Theory, Series A 71 (2): 343-351. doi:10.1016/0097-3165(95)90010-1. 
  • John J. O'Connor, Edmund F. Robertson, James Stirling (1692–1770), (September 1998).
Control de autoridades
  • Proyectos Wikimedia
  • Wd Datos: Q80918
  • Wd Datos: Q80918