I think the following function will given you the number of the n^Total[f]
arrangements that result in the desired frequencies when looking at length of Total[f]
. (Your examples all had n == Total[f]
but as long as Length[f] <= n
, the formula should work.)
count[n_, f_] := Piecewise[
{{Binomial[n, Length[f]]*Multinomial[Sequence @@ f]*
Multinomial[Sequence @@ (Tally[f][[All, 2]])],
n \[Element] PositiveIntegers && f \[Element] PositiveIntegers && Length[f] <= n}}]
A working example is
count[5, {1, 2, 2}]
(* 900 *)
As a partial check here is some code that will generate all of the arrangements for specified values of n
and f
:
arrangements[n_, f_] := Module[{alpha, t},
(* Unique values *)
alpha = Alphabet[][[1 ;; n]];
(* Generate all possible tuples *)
t = Tuples[alpha, {Total[f]}];
(* Find frequencies of values *)
t = {#, Tally[#]} & /@ t;
(* Keep tuples with Length[f] (same number of unique value) *)
t = Select[t, Length[#[[2]]] == Length[f] &];
(* Get frequencies and sort from low to high frequency *)
t[[All, 2]] = (#[[2, All, 2]] // Sort) & /@ t;
(* Select tuples with same frequencies in f *)
t = Select[t, #[[2]] == f &][[All, 1]]
]
Matching the previous example:
arrangements[n, f] // Length
(* 900 *)
(This function should be used only for relatively small values of n
and f
.)
Rationale
For a specific set of values associated with the frequencies the number of arrangements is Multinomial[Sequence@@f]
if n = Length[f]
. For example, the number of arrangements with n = 3
and f={1,2,3}
with a
being associated with the frequency of 1, b
associated with the frequency of 2, and c
associated with the frequency of 3 is Multinomial[1,2,3]
which equals 60. But there are 3! different arrangements of assigning a
, b
, and c
to the frequencies. So the total number of arrangements with a
, b
, and c
with a frequency vector of {1,2,3}
is Multinomial[1,2,3]*3!
which equals 360.
But suppose the frequencies are {1,2,2}
. Here there are ties in the frequencies so that there aren’t 3! = 6 different assignments as assigning a
b
c
to the frequencies will result in the same arrangements as a
, c
, b
. Here we would multiply Multinomial[1,2,2]
by 3!/(2! 1!)
to obtain 90 arrangements.
To clarify this for when there are multiple ties in the frequencies suppose f
is {1,2,2,2,3,3,3,3}
and n=8
. We would multiply Multinomial[1,2,2,2,3,3,3,3]
by 8!/(1! 3! 4!) resulting in 3,285,168,606,720,000arrangements. That multiplier is just Multinomial[1,3,4]
.
Now suppose that n > Length[f]
. There are more arrangements to consider. As we are choosing Length[f]
values out of n
values, that can happen Binomial[n, Length[f]]
ways and we multiply by that value. Hence the form of the function count
shown above.