Intereting Posts

Formulae of the Year 2016
The cardinality of the set of countably infinite subsets of an infinite set
how to integrate : $\int_{x^2}^{x^3}\frac{dt}{\sqrt{1+t^4}}$
Sufficient conditions for an entire functions to be constant
Why is $\mathbb{Z}, n\ge 3$ not a UFD?
Induction proof. Explain in detail why it’s incorrect
Proof of the universal property of the quotient topology
Vector bundle transitions and Čech cohomology
Diadics and tensors. The motivation for diadics. Nonionic form. Reddy's “Continuum Mechanics.”
Mid-point convexity does not imply convexity
Prove if $a\mid b$ and $b\mid a$, then $|a|=|b|$ , $a, b$ are integers.
About Math notation: the set of the $n^{th}$ natural numbers
Polynomial shift
Exterior derivative of a 2-form
Special case of the Hodge decomposition theorem

How can I find the number of $k$-permutations of $n$ objects, where there are $x$ types of objects, and $r_1, r_2, r_3, \cdots , r_x$ give the number of each type of object?

Example:

I have 20 letters from the alphabet. There are some duplicates – 4 of them are

a, 5 of them areb, 8 of them arec, and 3 ared. How many unique 15-letter permutations can I make?

- Covering with most possible equal size subsets having pairwise singleton intersections
- Number of permutations which fixes a certain number of point
- Probability of two events
- What is the number of ways to select ten distinct letters from the alphabet $\{a, b, c, \ldots, z\}$, if no two consecutive letters can be selected?
- There exists a vector $c\in C$ with $c\cdot b=1$
- Combinatorial interpretation of Fermat's Last Theorem

In the example:

$n = 20$

$k = 15$

$x = 4$

$r_1 = 4 \quad r_2 = 5 \quad r_3 = 8 \quad r_4 = 3$

Some background…

I was originally going to solve this problem in order to solve a simpler problem, but I managed to find a simpler solution to that problem instead. Now I’m still looking for the solution to this more general problem out of interest.

**Edit:**

I’ve done some more work on this problem but haven’t really come up with anything useful. Intuition tells me that as Douglas suggests below there will probably not be an easy solution. However, I haven’t been able to prove that for sure – does anyone else have any ideas?

**Edit:**

I’ve now re-asked this question (here) on MO.

- An extrasensory perception strategy :-)
- Combination Problem: Arranging letters of word DAUGHTER
- Proof that $a^b>b^a$ if $a<b$ are integers larger or equal to two and $(a,b)\neq (2,3),(2,4)$
- Combining kindergardeners in 'fair' cookie-baking groups. Kirkman's schoolgirl problem extended version
- Number of ways of choosing $m$ objects with replacement from $n$ objects
- Find combinations of N sets having no more than one item in common.
- Expected number of rolls
- Proving an Inequality Involving Integer Partitions
- A closed form for $T_N = 1 + \sum\limits_{k=0}^{N-2}{(N-1-k)T_k}$?
- Euler numbers grow $2\left(\frac{2}{ \pi }\right)^{2 n+1}$-times slower than the factorial?

There’s probably not going to be an easy way to do this… Consider two different examples of 15-letter “permutations”. Then the number of permutations with that multiset of digits depends on the proportions of the chosen digits.

If you really want to do this, you can sum $k!/(s(1)! s(2)! \cdots s(x)!)$ (called the mulitnomial coefficient) over all partitions of $s(1)+s(2)+ \cdots +s(x)=k$ [in this partition s(i) is allowed to be zero and order is important] such that $s(i) \leq r(i)$ for all i. The part s(i) says you have s(i) copies of the i-th letter. The number of permutations with s(i) i-th letters is given as above, by the Orbit Stabiliser Theorem.

Although, this is only one step better than the caveman’s counting formula: sum_P 1 where P is the set of permutations you want to count. I.e. just count them one-by-one.

EDIT: While I’m making a few touch-ups, here’s GAP code that implements the above formula.

```
NrPermIdent:=function(k,T)
local PSet,x;
x:=Size(T);
PSet:=Filtered(OrderedPartitions(k+x,x)-1,p->ForAll([1..x],i->p[i]<=T[i]));
return Sum(PSet,p->Factorial(k)/Product(p,i->Factorial(i)));
end;;
```

where T is a list of bounds and k is the number of terms in the partition.

For example:

```
gap> NrPermIdent(15,[4,5,8,3]);
187957770
```

As another indication that finding a simple formula for these numbers is not going to be easy, observe that NrPermIdent(n,[n,k]) is equal to $\sum_{0 \leq i \leq k} {n \choose k}$ (which is considered a difficult sum to find — see: https://mathoverflow.net/questions/17202/). I remember reading somewhere (most likely in A=B) that you can prove there is no “closed-form” solution for this.

There are 20!/4!5!8!3! arrangements of the 20 alphabets. Consider the action of $S_5$ on the arrangements by permuting the last 5 digits. You want to compute the number of orbits. You can then try to do it by Burnside’s formula. It is not difficult to do it at least for this case, since if a permutation of $S_5$ fixes an arrangement, it means that each cycle of the permutation corresponds to a color.

For the general case, I suspect that Polya’s enumeration theorem can do it, though I’m not certain.

- Convergence tests for improper multiple integrals
- Do we gain anything interesting if the stabilizer subgroup of a point is normal?
- Evaluate $\sum \sqrt{n+1} – \sqrt n$
- Monkeys and Typewriters
- Axiomatic definition of sin and cos?
- Solve by induction: $n!>(n/e)^n$
- Questions about Combinatorial Proof of $\sum_{k = 0}^n {n \choose k}^2= {2n \choose n}$
- Proving that $\frac{e^x + e^{-x}}2 \le e^{x^2/2}$
- On a definition of manifold
- Trigonometric curiosity
- “Standard” ways of telling if an irreducible quartic polynomial has Galois group C_4?
- Tensor product in dual-space
- Help with epsilon delta definition
- How prove that $\frac{1}{\sin^2\frac{\pi}{2n}}+\frac{1}{\sin^2\frac{2\pi}{2n}}+\cdots+\frac{1}{\sin^2\frac{(n-1)\pi}{2n}} =\frac{2}{3}(n-1)(n+1)$
- Every Group is a Fundamental Group