Formulas for different permutation/combination scenarios

Question

I was trying to develop formulas for different permutation/combination scenarios, but I could not sort out last three cases. Please check these following cases -

---

Unique items

1. Repetition: no

   • Permutation: $_nP_r$
   • Combination: $_nC_r$

2. Repetition: yes

   • Permutation: $n^r$
   • Combination: $_{n+r-1}C_r$ or $_{n+r-1}C_{n-1}$

---

Non-unique items

1. Repetition: no

   • Permutation: $\displaystyle \frac{n!}{k_1!k_2!\cdots k_n!}$, where $k_1,k_2,\dots k_n$ are numbers of non-unique items
   • Combination: ??

2. Repetition: yes

   • Permutation: ??
   • Combination: ??

Answer 1

Closely related with your question is a somewhat more general consideration of fundamental counting techniques called

The twelvefold way

R.P. Stanley presents in his classic Enumerative combinatorics vol. 1 in section 1.9 the so-called twelvefold way. He considers finite sets $N$ and $X$, with $|N|=n, |X|=x$ and counts the number of different functions $f:N\rightarrow X$ under different situations.

• Functions: $f$ may be arbitrary, injective or surjective giving three different possibilities.

• Sets: Elements of $N,X$ may be either distinguishable or indistinguishable resulting in four different possibilities.

Altogether we can consider $3\cdot 4=12$ different situations:

\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}\quad&{n\brace x}\quad\\ \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}\quad&p_x(n)\quad\\ \end{array}

with

$\qquad x^{\underline{n}}=x(x-1)\cdots(x-n+1)$ the falling factorial of $x$,

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

$\qquad \binom{x}{n}=\frac{x!}{n!(x-n)!}$ the binomial coefficient $x$ choose $n$,

$\qquad \left(\!\!{x\choose n}\!\!\right)=\binom{x+n-1}{n}$ the number of multisets $x$ multichoose $n$.

$\qquad {n\brace x}$ the Stirling numbers of second kind and

$\qquad p_x(n)$ the number of partitions of $n$ into $x$ parts.

A presentation in terms of urns and balls can be found here.

[2016-10-15] Add-on:

Some information regarding properties of functions and sets added due to a comment of OP.

A function $f:N\rightarrow X$ is said to be

• arbitrary or non-restrictive if there is no specific restriction given

• injective or one-to-one if each element of $X$ is the image of at most one element of $N$

• surjective or onto if each element of $X$ is the image of at least one element of $N$

Examples: Let's take a look at some functions with respect to these properties:

\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}

Balls and boxes

We think of $N=\{1,2,3\}$ as a set of balls and of $X=\{a,b,c,d\}$ as a set of boxes. A function $f:N\rightarrow X$ is considered as placing each ball into some box.

We consider four functions $j,k,l,m: N\rightarrow X$ by \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}

Four functions with distinguishable balls and boxes:

                                 

with balls indistinguishable:

                                 

with boxes indistinguishable:

                                 

with balls and boxes indistinguishable: