Number of ways to compose a number such that there is a maximum pile size and for each pile size there are a finite number of valid piles of that size

35 Views Asked by At

So, I want to count all of the different ways that a number $n$ can be written as the sum of numbers that are less than or equal to $k$ where the order of the numbers matters. Now, this is just composition, which is not very hard to solve. However, in the problem I am working on, there are "duplicates" of the numbers. By this I mean, one of the ways of breaking $11$ down would be $1,3,3,4$ but also $1,3,3',4$ and $1,3',3,4$ etc. We assume the number of duplicates for a given $x$ is $f_x$. Now, the number of ways this can happen for a given partition is just the length of the partition divided by the product of the factorials of each number that a certain number and its equivalents appears, but I want to be able to manipulate this using summation and product notation (I'm fine with a summation over a partition or something) rather than having to use words or the $0$-indicator function or an Iverson Bracket or something. I've played around with it for a while, and I can get it in terms of those, but I don't know how to get it in a more nice and purely combinatorial way.

Also, sorry if this is really messily written, I'm not sure how to make myself more clear.

At the suggestion from @Karl I will give an example of what I mean here: Let's say we are looking at splitting up the number $4$ and there is $1$ way we can have the number $1$, $3$ ways of having the number $2$, $1$ way of having the number $3$, and $2$ ways of having the number $4$. The following is (hopefully) all of the valid ways: 1,1,1,1 | 2,1,1 | 1,2,1 | 1,1,2 | 2',1,1 | 1,2',1 | 1,1,2' | 2'',1,1 | 1,2'',1 | 1,1,2'' | 2,2 | 2,2' | 2,2'' | 2',2 | 2',2' | 2',2'' | 2'',2 | 2'',2' | 2'',2'' | 1,3 | 3,1 | 4 | 4'

1

There are 1 best solutions below

0
On BEST ANSWER

I think you can write your counting function as

$$c(n)=\displaystyle\sum_{x_1,\dots,x_n\in\Bbb Z_{\ge0}\\\sum_{i=1}^n ix_i=n}\binom{\sum_{i=1}^n x_i}{x_1,\dots,x_n}\prod_{i=1}^n w_i^{x_i}$$

where $w_i$ is the number of distinguishable versions of $i$ you have. The outer summation sums over partitions of $n$ (keeping track of how many parts of each size there are), the multinomial coefficient counts the ways of ordering the partition, and the product counts the ways of choosing versions. The $w_i$ can be set to zero, making your $k$ parameter redundant.