Clustered k-Subsets

July 11, 2010 at 04:39 (algorithm, java, math.CO)

This post is mostly copied and pasted from my posts in this thread on MHF.

Problem statement: Let \displaystyle S_n = \{1,\ \dots\ ,n\} and let \displaystyle f(n,k,x) be the number of k-subsets of \displaystyle S_n such that when the elements are ordered from least to greatest, the absolute difference of any two adjacent elements is less than \displaystyle x. Find a formula or algorithm to determine \displaystyle f(n,k,x) for arbitrary \displaystyle n,k,x \in \mathbb{Z}, n\ge 0.

Read the rest of this entry »

Permalink Leave a Comment