Fórmulas para diferentes escenarios de permutación/combinación

Question

Estaba tratando de desarrollar fórmulas para diferentes escenarios de permutación/combinación, pero no pude resolver los últimos tres casos. Por favor, compruebe los siguientes casos -

---

Artículos únicos

1. Repetición: no

   • Permutación: $_nP_r$
   • Combinación: $_nC_r$

2. Repetición: sí

   • Permutación: $n^r$
   • Combinación: $_{n+r-1}C_r$ o $_{n+r-1}C_{n-1}$

---

Artículos no únicos

1. Repetición: no

   • Permutación: $\displaystyle \frac{n!}{k_1!k_2!\cdots k_n!}$ , donde $k_1,k_2,\dots k_n$ son números de elementos no únicos
   • Combinación: ??

2. Repetición: sí

   • Permutación: ??
   • Combinación: ??

Answer 1

En estrecha relación con su pregunta hay una consideración algo más general de las técnicas fundamentales de recuento llamadas

El camino de los doce

R.P. Stanley presenta en su clásico Combinatoria enumerativa vol. 1 en la sección 1.9 el llamado el camino de los doce . Considera conjuntos finitos $N$ y $X$ con $|N|=n, |X|=x$ y cuenta el número de funciones diferentes $f:N\rightarrow X$ en diferentes situaciones.

• Funciones: $f$ puede ser arbitraria, inyectiva o sobreyectiva dando tres posibilidades diferentes.

• Conjuntos: Elementos de $N,X$ pueden ser distinguibles o indistinguibles, lo que da lugar a cuatro posibilidades diferentes.

En conjunto podemos considerar $3\cdot 4=12$ diferentes situaciones:

\begin{array}{ll|ccc} \text{elements }N&\text{elements }X&\quad\text{any }f\quad&\quad\text{injective }f\quad&\quad\text{surjective } f\quad\\ \hline \text{dist.}&\text{dist.}&x^n\quad&\quad x^{\underline{n}}\quad&x!{n\brace x}\\ \text{indist.}&\text{dist.}&\left(\!\!{x\choose n}\!\!\right)\quad&\quad\binom{x}{n}\quad&\left(\!\!{x\choose n-x}\!\!\right)\quad\\ \text{dist.}&\text{indist.}&\sum_{j=0}^x{n\brace j}\quad&\quad\begin{matrix}1&\text{if }n\leq x\\0&\text{if }n>x\end{matrix} \N - Cuadrado&&nbspde la abrazadera x}\N-cuadrado. \text{indist.}&\text{indist.}&\sum_{j=0}^xp_j(n)\quad&\quad \begin{matrix}1&\text{if }n\leq x\\0&\text{if }n>x\end{matrix} \N - cuadrado&p_x(n)\N - cuadrado \fin{span} {array}

con

$\qquad x^{\underline{n}}=x(x-1)\cdots(x-n+1)$ el _factorial descendente_ de $x$ ,

$\qquad x!=x(x-1)\cdots 3\cdot2\cdot1$ el factorial de $x$ ,

$\qquad \binom{x}{n}=\frac{x!}{n!(x-n)!}$ el _coeficiente binomial_ $x$ elija $n$ ,

$\qquad \left(\!\!{x\choose n}\!\!\right)=\binom{x+n-1}{n}$ el número de _multisets_ $x$ multichoose $n$ .

$\qquad {n\brace x}$ el _Números Stirling de segundo tipo_ y

$\qquad p_x(n)$ el número de [particiones](https://en.wikipedia.org/wiki/Partition(numbertheory)) de $n$ en $x$ partes.

Se puede encontrar una presentación en términos de urnas y bolas aquí .

[2016-10-15] Complemento:

Se han añadido algunas informaciones sobre las propiedades de las funciones y los conjuntos gracias a un comentario de OP.

Una función $f:N\rightarrow X$ se dice que

• arbitrario o no restrictivo si no hay ninguna restricción específica

• _inyectiva_ o uno a uno si cada elemento de $X$ es la imagen de como máximo un elemento de $N$

• _surjective_ o en si cada elemento de $X$ es la imagen de al menos un elemento de $N$

Ejemplos: Veamos algunas funciones con respecto a estas propiedades:

\begin{array}{l|ccc} \text{function}&arbitrary&injective&surjective\\ \hline \\ f:\{1,2,3\}\rightarrow\{a,b,c,d\}&\mathbb{\color{blue}{\text{yes}}}&-&-\\ f(1)=f(2)=c,f(3)=a\\ \\ g:\{1,2,3\}\rightarrow\{a,b,c,d\}&\mathbb{\color{blue}{\text{yes}}}&\mathbb{\color{blue}{\text{yes}}}&-\\ g(1)=d,g(2)=c,g(3)=a\\ \\ h:\{1,2,3,4\}\rightarrow\{a,b,c\}&\mathbb{\color{blue}{\text{yes}}}&-&\mathbb{\color{blue}{\text{yes}}}\\ h(1)=h(4)=c,h(2)=a,h(3)=b\\ \\ i:\{1,2,3,4\}\rightarrow\{a,b,c,d\}&\mathbb{\color{blue}{\text{yes}}}&\mathbb{\color{blue}{\text{yes}}}&\mathbb{\color{blue}{\text{yes}}}\\ i(1)=d,i(2)=c,i(3)=a,i(4)=b\\ \end{array}

Bolas y cajas

Pensamos en $N=\{1,2,3\}$ como un conjunto de bolas y de $X=\{a,b,c,d\}$ como un conjunto de cajas. Una función $f:N\rightarrow X$ se considera la colocación de cada bola en alguna casilla.

Consideramos cuatro funciones $j,k,l,m: N\rightarrow X$ por \begin{array}{lclcllcl} j(1)&=&j(2)&=&a,&\qquad j(3)&=&b\\ k(1)&=&k(3)&=&a,&\qquad k(2)&=&b\\ l(1)&=&l(2)&=&b,&\qquad l(3)&=&d\\ m(2)&=&m(3)&=&b,&\qquad m(1)&=&c\\ \end{array}

Cuatro funciones con bolas y cajas distinguibles:

                                 

con bolas indistinguibles:

                                 

con cajas indistintas:

                                 

con bolas y cajas indistinguibles: