| I believe I have the answer.
[1] Original problem: n(c, m), where
n > n <= n <= ... <= n .
1 2 3 c
Answer: n (c, m) = m * C (c + m - 2, c - 1) - C (c + m - 1, c),
where C (i, j) = number of ways to take a subset of j things from
a set of i things, i. e.
C (i, j) = i! / j! / (i - j)!
Approach: solve easier problems below
[2] o(c, m), where
n < n < n < ... < n .
1 2 3 c
[3] p(c, m), where
n <= n <= n <= ... <= n .
1 2 3 c
[4] (n + p)(c, m) -- essentially n is unrestricted.
1
Loved the problem. Thank you.
|
| FULLER EXPLANATION OF 258.1
[0] All functions below are talking about (ordered) c-tuples
(n1, n2, n3, ..., nc)
where each of the n's is in { 1, 2, 3, ..., m }
[1] Original problem:
n (c, m) = number of c-tuples such that
n1 > n2 <= n3 <= n4 <= ... <= nc
E.g. n (3, 3) = 8, because there are { 211, 212, 213, 311, 312, 313,
322, 323 }.
General answer will follow in [6].
[2] Easier problem:
o (c, m) = number of c-tuples such that
n1 < n2 < n3 < n4 < ... < nc
These c-tuples correspond 1-1 to the subsets of c things taken from
a set of m distinct things, or
C (m, c)
which is my notation for
m! / c! / (m - c)!
[3] Another easier problem:
p (c, m) = number of c-tuples such that
n1 <= n2 <= n3 <= n4 <= ... <= nc
These non-strictly-increasing c-tuples correspond 1-1 to the
strictly-increasing c-tuples
(n1 + 0) < (n2 + 1) < (n3 + 2) < (n4 + 3) < ... < (nc + c - 1)
which are taken from a larger set of values, namely:
{ 1, 2, 3, ..., m + c - 1 }
Thus,
p (c, m) = o (c, m + c - 1) = C (m + c - 1, c)
[4] Another easier problem:
q (c, m) = number of c-tuples such that
n1 is unrestricted (i. e. 1 <= n1 <= m), and
n2 <= n3 <= n4 <= ... <= nc
Since there are m choices for n1,
q (c, m) = m * p (c - 1, m) = m * C (m + c - 2, c - 1)
[5] Claim: n + p = q
Given n2 <= n3 <= n4 <= ... <= nc, either
n1 > n2 [that's n]
or
n1 <= n2 [that's p]
[6] Answer to original problem:
n (c, m) = q (c, m) - p (c, m) =
m * C (m + c - 2, c - 1) - C (m + c - 1, c)
E. g. n (3, 3) = 3 * C (4, 2) - C (5, 3)
= 3 * (4! / 2! / 2!) - (5! / 3! / 2!)
= 18 - 10
Sets: { 211, 212, 213, 311, 312, 313, 322, 323 } =
{ 111, 112, 113, 122, 123, 133, 211, 212, 213, 222, 223, 233,
311, 312, 313, 322, 323, 333 } -
{ 111, 112, 113, 122, 123, 133, 222, 223, 233, 333 }
|