Combinatorics: Trying to figure algorithm (about subsets)

Question

I'm trying to solve a problem on TopCoder. Basically what I need is algorithms for the following:

Let S = [1, 2, ..., n] be a sequence. Let m be less than n.

1) Find all subsequences of S of size m (which is easy - n^m).

2) Find all subsequences of S of size m where the elements are in nondecreasing order.

3) Find all subsequences of S of size m where the elements are not allowed to be repeated (which is also easy - (n!)/((n-m)!).

4) Find all subsequences of S of size m where the elements are in nondecreasing order and are not allowed to be repeated.

Still trying to find formula for parts 2 and 4. A little bit of help will be appreciated.

Thanks in advance.

EDIT:

Original problem:

https://docs.google.com/document/d/1X1VK8Vq2DlqMbZpXHGLoWv9ULfRLVoLtMTRRU5nh5qs/edit?usp=sharing

I'm confused about the use of the term "set" here. Sets tend to be unordered and to contain individual elements at most once, so I don't understand what question 2, 3 and 4 even mean. — Gian, Mar 21 '13 at 10:07
hmmm, my fault "set" in this problem is considered by the following properties: 1) [1, 2, 3] and [2, 1, 3] are different "sets" 2) [1, 1, 1] is a "set". bonus for the proper name of "set" :) — Kudayar Pirimbaev, Mar 21 '13 at 10:11
Your example suggest that `S` contains all the integers from `1..n` for some `n`. Is that intentional or accidental ? — High Performance Mark, Mar 21 '13 at 10:14
@HighPerformanceMark intentional. if you are interested in actual problem, here it is: https://docs.google.com/document/d/1X1VK8Vq2DlqMbZpXHGLoWv9ULfRLVoLtMTRRU5nh5qs/edit?usp=sharing — Kudayar Pirimbaev, Mar 21 '13 at 10:21

score 1 · Answer 1 · edited May 23 '17 at 12:21

to solve 4), note that w/o repetitions 'non-decreasing' means 'increasing'. partition the set of all sequences of length m built from S without repeating elements into equivalence classes defined by the set of elements occurring in the subsequence. within each equivalence class, there is exactly one increasing sequence (elements ordered by <). the size of each equivalence class is the number of permutations of the elements. the number of 4)-sequences therefore is (n!)/((n-m)! * m!) = n \choose m.

ad 2), model the sequence as a sequence of occurrence counts (including 0 for non-inclusion) for all elements in S. this can be written as a sequence of pairs (s_i, k_i), i=1..n; s_i \in S, k_i \in IN, \foreach p,q in {1..n}, p!=q: s_p != s_q of length exactly n. 'non-decreasing' implies a unique permissible ordering of the sequence given by arranging the elements according to increasing s_i. thus the only degree of freedom is the occurrence count which must obey the constraint of summing to m: sum_{i=1..n} k_i = m.

this problem is equivalent to partitions with (particular) restrictions and counting lattice paths. i don't think there is a closed formula for the number of n-tuples from IN^n meeting this condition.

however, there is a standard algorithm to enumerate all possibilities, eg. here

Combinatorics: Trying to figure algorithm (about subsets)

1 Answers1