De Forma cerrada Solución para la Permutación de la Tabla

Question

Por $N,n\in\mathbb N$ estoy buscando una fórmula que genera todos los $N\choose{n}$ combinaciones de la siguiente manera:

E. g. tome $N=3,n=1$. Luego hay ${3\choose1}=3$ combinaciones tales que

1| - + +
2| + - +
3| + + -

o $N=4,n=0$. Luego hay ${4\choose0}=1$ combinaciones tales que

1| + + + +

o $N=4,n=1$. Luego hay ${4\choose1}=4$ combinaciones tales que

1| - + + +
2| + - + +
3| + + - +
4| + + + -

o $N=4,n=2$. Luego hay ${4\choose2}=6$ combinaciones tales que

1| - - + +
2| - + - +
3| - + + -
4| + - - +
5| + - + -
6| + + - -

Por lo $n$ determina el número de - en cada combinación (cada una con $N$ elementos). El orden final de las combinaciones no importa (es decir, si - - + + o + - + - que viene primero es irrelevante).

Pero, ¿hay una fórmula para $f_{i,k,n,N}$ (tomando el valor $-1$ o $+1$) de tal manera que podamos obtener el conjunto de combinaciones:

$$\left\{(f_{i,k,n,N}\ \text{with}\ i=1,2,\ldots N)\in\mathbb \{-1,1\}^N \mathrel{\bigg|} k=1,2,\ldots, {N\choose n}\right\}$$

Perhaps something like $f_{i,k,n,N}=(-1)^{i+k+\ldots}$ ?

Answer 1

Deje $f_{i, k, n, N} = (-1)^{g(i, k, n, N)}$$g(i, k, n, N) \in \{\,0, 1\,\}$. Entonces podemos tomar $$g(1, k, n, N) = \left[k > \binom{N - 1}{n}\right],\\ g(2, k, n, N) = \left[k - g(1, k, n, N)\binom{N - 1}{n} > \binom{N - 2}{n - g(1, k, n, N)}\right]$$ y así sucesivamente: $$g(i, k, n, N) = \left[k - \sum_{j = 1}^{i - 1}g(j, k, n, N)\binom{N - j}{n - \sum_{\ell = 1}^{j - 1}g(\ell, k, n, N)} > \binom{N - i}{n - \sum_{\ell = 1}^{i - 1}g(\ell, k, n, N)}\right].$$ Esta fórmula es recursivo, pero esta recurrencia es en el interior de la $k$th combinación. La otra forma de escribir la misma es la siguiente: $$g(1, k, n, N) = \left[k > \binom{N - 1}{n}\right],\\ g(i, k, n, N) = g\a la izquierda(i - 1, k - g(1, k, n, N)\binom{N - 1}{n}, n - g(1, k, n, N), N - 1\right) \text{ para } 2 \le i \le n.$$ El sentido de esta relación es bastante sencillo: no nos tomamos el primer elemento de la primera $\binom{N - 1}{n}$ combinaciones y tomar en todos los demás. Luego seguimos para construir la parte restante de la combinación.

P. S. $[P]$ $1$ si $P$ es verdadera y $0$ lo contrario. Esto es bastante generalizada, Iverson notación.