Wikipedia:Reference desk/Archives/Mathematics/2014 June 29

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

June 29

Natural combinatoric numberings

1. The k-selections (from an ordered set of size n) in lexicographic order have a very convenient representation in base n because there are $n^{k}$ of them.
2. The k-permutations similarly use the factorial number system because there are $(n)_{k}$ of them.
3. The combinations are harder because ${\binom {n}{k}}$ does not(?) have a simple expression as a product of integers, but they have something almost as convenient (and still lexicographic) from the Pascal's triangle identity ${\binom {n}{k}}={\binom {n-1}{k}}+{\binom {n-1}{k-1}}$: you assign the first ${\binom {n-1}{k}}$ indices to the combinations that involve the first element, and so recursively among the sets with and without it.
4. The multinomial selections may be treated by combining the combination technique with a mixed radix system based on ${\binom {n}{k_{1},k_{2},\ldots ,k_{m}}}={\binom {n}{k_{1}}}{\binom {n-k_{1}}{k_{2},\ldots ,k_{m}}}$.
5. The multinomials may easily be extended to the case where some subset of s elements are taken to be indistinguishable by dividing by $s!$ — or even $\prod _{i}s_{i}!$. (Not so for the k-permutations or combinations with $k<n$, since not all of the indistinguishable elements are involved in each pattern.)

Questions, with a mind to writing code to interconvert between (subsets of) these arrangements and their indices:

1. Is my statement about factoring ${\binom {n}{k}}$ correct? (Of course it has a factorization! I mean a convenient one for this purpose.) Is there a better ordering (lexicographic or no) for combinations?
2. What natural ordering/numbering is natural for the multinomials with indistinguishable sets? --Tardis (talk) 03:47, 29 June 2014 (UTC)

1. ${\binom {n}{k}}={\frac {n}{1}}\cdot {\frac {n-1}{2}}\cdots {\frac {n-(k-1)}{k}}$
2. Usually, some sort of lexicographical or antilexicographical order is used. — Arthur Rubin (talk) 15:08, 2 July 2014 (UTC)

1. That's not a useful factorization for this purpose: many of the terms are not integers.
2. How do you (efficiently/simply) compute the indices for such an order with (some) indistinguishable elements? --Tardis (talk) 06:35, 3 July 2014 (UTC)

1. ${\binom {n}{k}}=\prod _{p}p^{\mathrm {b} (p,n,k)}$, where b(p,n,k) is the number of "borrows" when subtracting k from n in base p. (Well, you wanted a factorization....)
2. The method varies. If you choose to order lexicographically by the sequence of which set each element is in, you can index by using:

   ${\binom {n}{k_{1},k_{2},\ldots ,k_{m}}}={\binom {n-1}{k_{1}-1,k_{2},\ldots ,k_{m}}}+{\binom {n}{k_{1},k_{2}-1,\ldots ,k_{m}}}+\cdots +{\binom {n-1}{k_{1},k_{2},\ldots ,k_{m}-1}}$.

   If you choose to order lexicographically by the first set, then you use:

   ${\binom {n}{k_{1},k_{2},\ldots ,k_{m}}}={\binom {n}{k_{1}}}{\binom {n-k_{1}}{k_{2},\ldots ,k_{m}}}$.

   If some elements are indistinguishable, you do the same thing, but specify that the "indistinguishable" elements are in order. Please give an example of what you are trying to do, and I'll see if I can find a simple counting method

— Arthur Rubin (talk) 07:17, 5 July 2014 (UTC)