$r$-Permutations of $n$ things of $k_1,...,k_j$ kinds.

34 Views Asked by At

Given a multiset $\mathcal{M} := \{0^1,\ldots, 0^7,1^1,\ldots, 1^7, \cdots,9^1,\ldots, 9^7 \}$. i.e $10$ digits from $0$ to $9$, each present $7$ times such that $| \mathcal{M}| = 70$.

I want to count the number of $7$-Permutations of $\mathcal{M}$ such that any two permutations are indistinguishable, if they only differ by some exchange between digits of the same kind, for example $0^1 \ 1357 \ 0^6 \ 9$ and $0^6 \ 1357 \ 0^1 \ 9$ are just the same permutation $0135709$.

I tried using generating functions such that $$\bigg(1+t+\frac{t^2}{2!}+\frac{t^3}{3!}+\frac{t^4}{4!}+\frac{t^5}{5!}+\frac{t^6}{6!}+\frac{t^7}{7!}\bigg)^{10} = \sum_{r = 0}^{70} P(70,r) \ \frac{t^r}{r!}$$

After expanding, the coefficient of $t^7$ on the left is $\frac{125000}{63}$, so we get $P(70,r) = 7! \cdot \frac{125000}{63} = 10 \cdot 10^6$.

Did I count correctly? Thanks.

1

There are 1 best solutions below

4
On BEST ANSWER

You did indeed count correctly, and there is an easy check of the result $10^7$. Each seven-digit number, allowing leading zeroes, corresponds to a unique $7$-permutation of $\mathscr{M}$ when you don’t distinguish digits of the same type, and of course each such $7$-permutation of $\mathscr{M}$ corresponds to a unique seven-digit number when leading zeroes are allowed. There are $10^7$ seven-digit numbers, so there must be $10^7$ $7$-permutations of $\mathscr{M}$ when digits of the same type are not distinguished.