Intereting Posts

Let$\ p_n$ be the$\ n$-th prime. Is$\ \lim_{n\to\infty} \log \log n \prod_{i=1}^{\lfloor \log n \rfloor} \frac{p_i-1}{p_i}>0$?
Epsilon-delta proof
Proof that the largest eigenvalue of a stochastic matrix is 1
Calculate $\lim_{n\to\infty}(\sqrt{n^2+n}-n)$.
Prove $7$ divides $13^n- 6^n$ for any positive integer
How to find $\lim a_n$ if $ a_{n+1}=a_n+\frac{a_n-1}{n^2-1} $ for every $n\ge2$
Uses of the incidence matrix of a graph
system of differential linear equations $y'=\begin{pmatrix}1 & 1\\0 & 1\end{pmatrix}y$
Showing there exists infinite $n$ such that $n! + 1$ is divisible by atleast two distinct primes
Testing continuity of the function $f(x) = \lim\limits_{n \to \infty} \frac{x}{(2\sin{x})^{2n}+1} \ \text{for} \ x \in \mathbb{R}$
Distributions valued in Fréchet spaces
Does the derivative of a continuous function goes to zero if the function converges to it?
Number of zero digits in factorials
Giving meaning to $R$ (for example) via the evaluation homomorphism
Unitisation of $C^{*}$-algebras via double centralizers

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?

- Pile of $2000$ cards
- expected number of repeats in random strings from different sized alphabets
- A Proof of Correctness of Durstenfeld's Random Permutation Algorithm
- How many seven-digit numbers satisfy the following conditions?
- How many permutations of $\{1,2,…n\}$ derange the odd numbers?
- How many knight's tours are there?

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.

- Probability of a run of *k* or more of a subset of categories in *m* multinoulli trials?
- Probability of making it across a path of $n$ tiles through random walk
- How to rotate n individuals at a dinner party so that every guest meets every other guests
- How many different arrangements?
- upper bounding alternating binomial sums
- Putnam A-6: 1978: Upper bound on number of unit distances
- Painting a cube with 3 colors (each used for 2 faces).
- Uses of the incidence matrix of a graph
- Probability event with $70$% success rate occurs three consecutive times for sample size $n$
- Combinatorics for a 3-d rotating automaton

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.

- Applying equivalence of norms on $\mathbb R^n$ .
- Definition of the $\sec$ function
- A Challenge on linear functional and bounding property
- Subgroups of finitely generated groups are not necessarily finitely generated
- How can I get f(x) from its Maclaurin series?
- Orthonormal basis in $L^2(\Omega)$ for bounded $\Omega$
- If $f$ s discontinuous at $x_0$ but $g$ is continuous there, then $f+g$?
- Motivation behind topology
- Is the determinant differentiable?
- Probability that a vector in $\mathbb{Z}^n$ is primitive
- $\operatorname{tr}(AABABB) = \operatorname{tr}(AABBAB)$ for $2×2$ matrices
- Show that the spectrum of an operator on $\ell^2(\mathbb{N})$ is $\{0\}$.
- Proof for “Given any basis of a topological space, you can always find a subset of that basis which itself is a basis, and of minimum possible size.”
- What is $\int_0^1 \ln (1-x) \ln \left(\ln \left(\frac{1}{x}\right)\right) \, dx$?
- Why doesn't this work imply that there are countably many subsets of the naturals?