El Números catalanes tienen fama de aparecer en todas partes, pero la ocurrencia descrita a continuación, en el análisis de un algoritmo (incorrecto), sigue siendo un misterio para mí, y tengo curiosidad por encontrar una explicación.
Para situaciones en las que un algoritmo de ordenación en tiempo cuadrático es suficientemente rápido, suelo utilizar lo siguiente:
//Given array a[1], ... a[n]
for i = 1 to n:
for j = i+1 to n:
if a[i] > a[j]:
swap(a[i],a[j])Se parece a la ordenación por burbujas, pero se acerca más a la ordenación por selección. Es fácil ver por qué funciona: en cada iteración del bucle exterior, a[i] se establece como el elemento más pequeño de a[i…n] .
En un concurso de programación hace muchos años, uno de los problemas se reducía esencialmente a la ordenación:
Dada una lista de valores distintos $W_1, W_2, \dots, W_n$ , encontrar los índices cuando se ordena en orden ascendente. En otras palabras, encontrar la permutación $(S_1, S_2, \dots, S_n)$ para lo cual $W_{S_1} < W_{S_2} < \dots < W_{S_n}$ .
Se trata simplemente de operar sobre los índices y no sobre el array directamente, por lo que el código correcto sería:
//Given arrays S[1], ..., S[n] (initially S[i]=i i) and W[1], ..., W[n]
for i = 1 to n:
for j = i+1 to n:
if W[S[i]] > W[S[j]]:
swap(S[i],S[j])Pero en el fragor del concurso, en su lugar codifiqué un programa que lo hacía, incorrectamente:
for i = 1 to n:
for j = i+1 to n:
if W[i] > W[j]:
swap(S[i],S[j])Me di cuenta del error una vez finalizado el concurso, y más tarde, mientras esperaba los resultados, con desesperado optimismo intenté calcular las probabilidades de que, para algunas entradas, mi programa diera accidentalmente la respuesta correcta de todos modos. En concreto, conté el número de permutaciones de una lista arbitraria $W_1, \dots, W_n$ con valores distintos (ya que sólo su pedir no sus valores reales) para los que el algoritmo incorrecto anterior da la respuesta correcta, para cada n:
n Number of "lucky" permutations
0 1
1 1
2 2
3 5
4 14
5 42
6 132
7 429
8 1430
9 4862
10 16796
11 58786
12 208012¡Estos son los números catalanes! ¿Pero por qué? He intentado probarlo de vez en cuando en mi tiempo libre, pero nunca lo he conseguido.
Lo que he probado:
-
El (pseudo)algoritmo puede representarse en una notación más formal como el producto de todas las inversiones en una permutación. Es decir, queremos demostrar que el número de permutaciones $\sigma \in S_n$ tal que $$\prod_{i=1}^{n}\prod_{\substack{j \in \left\{i+1,i+2,\ldots,n\right\}; \\ \sigma_i > \sigma_j}}(i,j) = \sigma^{-1}$$ (con la convención de que la multiplicación se hace de izquierda a derecha) es $C_n$ . Este cambio de notación no simplifica el problema.
-
He hojeado brevemente La famosa lista de problemas catalanes de Stanley pero esto no parece estar (directamente) en la lista. :-)
-
Algunos experimentos informáticos sugieren que las permutaciones afortunadas son las que evitan el patrón 312, cuyo número parece ser el de los números catalanes. Pero no tengo ni idea de cómo probar esto, y puede que no sea el mejor enfoque...
