This is for work, not school (and I’d rather not say anything else on that). I’ve got a multiset {(a[sub]i[/sub], n[sub]i[/sub]) | 1 < i < k}. I need to figure out a couple things:
The total number of subsets. I think this is 2^sum(n[sub]i[/sub] + 1, 1 < i < k) (not using the {sup}{/sup} tags because it’s too hard to read).
The number of subsets with at most one of each element. I think this product(n[sub]i[/sub] + 1, 1 < i < k).
Do these results seem right?
I might be missing something here. I wasn’t familiar with the term “multiset”, so I looked it up on www.mathworld.com . I’m reading your notation as a[sub]i[/sub] being an element of the multiset with multiplicity n[sub]i[/sub]. Is that correct? And a[sub]i[/sub] is distinct from a[sub]j[/sub] if and only if i and j are distinct.
Anyway, the way I’m reading it, I would think of {(a[sub]i[/sub], n[sub]i[/sub]) | 1 < i < k} as essentially being a set with N elements, where N is the sum of just the n[sub]i[/sub]'s (not the sum of n[sub]i[/sub]+1). So the total number of subsets would be 2[sup]N[/sup].
For the second part, since you have k distinct elements, I would think the number of subsets with at most one element would be 2[sup]k[/sup] (for each of the k elements, you have two choices–either include it or don’t).
My last sentence should read:
For the second part, since you have k distinct elements, I would think the number of subsets with at most one of each element would be 2[sup]k[/sup] (for each of the k elements, you have two choices–either include it or don’t).
I agree with Cabbage for (2); limiting the subset to contain at most one of each element means we can just think of the multiset as the k-element set {a[sub]i[/sub]}.
For (1), as I interpret it, a “subset” (sub-multiset?) is a set {(a[sub]i[/sub],m[sub]i[/sub]): 1 < i < k, 0 < m[sub]i[/sub] < n[sub]i[/sub]}; there are thus prod(n[sub]i[/sub]+1) such sub-multisets (the expression ultrafilter gave for (2)).
Yeah, now that I think about it, I agree with you on the first one, as well, Omphaloskeptic.
I was thinking of, for example, the multiset {1,1,1}. What I was originally thinking of would imply that the "1"s are distinct. So, for example, the subsets {1} and {1} could be distinct if in the first case we’re taking the 1 on the left, and in the second case we’re taking the 1 on the right (and we’d have a third distinct singleton set {1} by taking the 1 in the middle).
Of course, now that I think about it, I don’t think that’s the idea behind a multiset. A subset of {1,1,1} will simply have 0, 1, 2, or 3 "1"s, for a total of exactly four distinct subsets. In general, the number of subsets will be the product of (n[sub]i[/sub]+1), like you said.
Yeah, you guys are right, which means I’m using the wrong model for my problem. What I want is that any two elements of the set are distinguishable, but each one has a family associated with it. So let’s try this as counting subsets of the set A = A[sub]1[/sub] [symbol]È[/symbol] A[sub]2[/sub] [symbol]È[/symbol] … [symbol]È[/symbol] A[sub]k[/sub], where the A[sub]i[/sub] are pairwise disjoint, |A[sub]i[/sub]| = n[sub]i[/sub], and N = n[sub]1[/sub] + n[sub]2[/sub] + … n[sub]k[/sub].
Here there are 2[sup]N[/sup] possible subsets of A, which means I was over-counting earlier. As for subsets of A with at most one element from each A[sub]i[/sub], there are [symbol]P[/symbol][sub]1 < i < k[/sub](n[sub]i[/sub] + 1). How’s that look?
Looks good to me.