1

You are given the multiset $\{1,2,2,3,3,3,\ldots\}$ with each type$(n)$ having $n$ elements.If you pick the first $k$ types, how many allowable arrangements are there using $k$ elements? For $k=5$ you could have $\{1,2,3,3,3\}$ or $\{2,3,4,4,4\}$ but not $\{1,1,2,3,5\}$ or $\{2,2,2,4,5\}$. Is there an easy way to answer this question? One way is to take $k^k$ and then subtract all unallowable arrangements, but is this any easier?

Martin Sleziak
  • 53,687
J. M. Bergot
  • 912
  • I thought the convention for subsets was to enclose them in { }. – J. M. Bergot Jul 27 '16 at 19:07
  • The braces were there, there were just no backslashes in front of them so they were taken as MathJax syntax. – Henrik supports the community Jul 27 '16 at 19:28
  • The question has been misunderstood: it does not ask for the allowable combinations with repetitions but for the number of ordered arrangements of them. Hence with allowable 2,2,3,3,3 one gets 5!/2!*3!=10 of them, as in 2,3,3,3,2 and 3,2,2,3,3. I hoped that mentioning k^k then removing the unallowable arrangements would give the meaning of the question. For k=1 to 5 I got for solution 1,3,19,176,2111. For k=3 you get 1,2,2 with 3 arrangements; 1,2,3 with 6; 1,3,3 with 3; 2,3,3 with 3, 2,3,3 with 3; 3,3,3 with 1 giving 3+6+3+3+3+1=19. – J. M. Bergot 1 min ago edit – J. M. Bergot Jul 29 '16 at 17:37
  • See A000707, which answers the question of how many submultisets are derived from 1,2,2,3,3,3... My question is to find the total number of arrangements (ordered multisets) ; I will demonstrate using k=3, having 6 multisets ('combinations with repetition' in the original question). Let '@m" mean 'has m ordered multisets'. The 6 multisets are 1,2,2 @3; 1,2,3 @6; 1,3,3 @3; 2,2,3 @3; 2,3,3 @3; 3,3,3 @1. Adding 3+6+3+3+3+1=19. For k=1 to 4 you get 1,3,19,175 ordered multisets. To insure the understanding of ordered multiset (arrangement) 1,2,2 has three: 1,2,2 and 2,1,2 and 2,2,1. – J. M. Bergot Aug 05 '16 at 18:01
  • One could extend this by considering progressive submultisets by taking the first m<=k and finding the sum of all arrangements. To demonstrate with k=3: m=1 means pick any one from 1,2,3 to give 1 @1; 2 @1; 3 @1 for a total of 3. For m=2 pick 1,2 @2; 2,2 @1; 1,3 @2; 3,3 @1; 2,2 @1; 2,3 @2; 3,3 @1 for a total of 10. Finally, take all 3, as in above comment of 19; now add 3+10+19=32. From k=1 to 4 the sequence is 1,2,32,284. – J. M. Bergot Aug 05 '16 at 18:38
  • Consider the question of the sum of the terms for the submultisets. For k=1 to 4 the sequence begins 1,7,42,234 or the sum of the terms of all ordered submultisets, which gives 1,10,126,1904. – J. M. Bergot Aug 06 '16 at 17:25
  • One could alter the original multiset 1,2,2,3,3,3...by considering triangular numbers, to give 1,1,2,3,1,2,3,4,5,6...or squares, to give 1,1,2,3,4,1,2,3,4,5,6,7,8,9. Ask the same questions as for the original. – J. M. Bergot Aug 06 '16 at 17:27
  • If you can clarify the question do so by editing it, then we can consider reopening it, just posting new comments won't help. – Henrik supports the community Aug 06 '16 at 17:27
  • I'll do it tomorrow, Aug 10. – J. M. Bergot Aug 09 '16 at 19:53

2 Answers2

1

Picking the first $k$ types, you get a subset of your multiset with length $\frac{k(k+1)}{2}$. For example, for $k=4$: $$ |\left\{1,2,2,3,3,3,4,4,4,4 \right\}| = \frac{4(5)}{2} = 10 $$ This is because the cardinality of the chosen subset with respect to $k$ is the $k$th triangular number, as you sum the numbers 1 through $k$.

You must choose $k$ elements of the subset, unless I'm misunderstanding something, and order does not matter, so the formula for the number of allowable arrangements using k elements is: $$ \binom {\dfrac{k(k+1)}{2}} {k} $$

Ali Abdulla
  • 59
1

We have by inspection that the generating function for these is

$$(1+x)(1+x+x^2)\times\cdots\times(1+x+\cdots+x^k)$$

and the desired value is thus given by

$$[x^k] \prod_{q=1}^k \frac{1-x^{q+1}}{1-x}.$$

This produces the sequence

$$1, 2, 6, 20, 71, 259, 961, 3606, 13640, 51909, \ldots$$

which is OEIS A000707 where we see that apparently no better closed form exists.

Marko Riedel
  • 61,317