1
$\begingroup$

Background of my question is, that I would like to store flags indicating the relation between a pairs of non-adjacent edges of a graph (that relation could for example be, whether the edges cross, i.e. whether the pair of edges constitutes to a maximal matching of the sub-graph induced by the four adjacent vertices).
My idea is to first calculate the ordinal number $o(\{v_1,v_2,v_3,v_4\})$ corresponding to the set of the integer-labels of the adjacent vertices and from that calculate the the ordinal number of the pair of edges:
$$o(\{\{v_1,v_2\},\{v_3,v_4\}\}) := 3\times o(\{v_1,v_2,v_3,v_4\}))$$ $$o(\{\{v_1,v_3\},\{v_2,v_4\}\}) := 3\times o(\{v_1,v_2,v_3,v_4\}))+1$$ $$o(\{\{v_1,v_4\},\{v_2,v_3\}\}) := 3\times o(\{v_1,v_2,v_3,v_4\}))+2$$

Questions:

  • is there a general formula, that only depends on the cardinality $k$ and on the $k$ elements itself of a finite set of integers, which yields the ordinal number of that set in the lexicographically sorted sequence of integer-sets with k elements (for a specific $k$ the formula could be obtained by polynomial interpolation, but I want a formula that contains $k$ as a parameter)?

  • is there a compact notation for "integer sets of cardinality $k$" (for cartesian products there is the nice way of writing $\mathbb{N}^k$; I would like something analogous for sets instead of cartesian products)?

Being able to calculating the ordinal number of integer sets would to me be an important building block for calculating more elaborate ordinal numbers for use in graph theoretic algorithms, as indicated above.

$\endgroup$
  • 1
    $\begingroup$ See mathoverflow.net/questions/42344. For your second question, another common notation is $\binom{\mathbb{N}}{k}$. $\endgroup$ – Richard Stanley May 13 '14 at 18:35
  • $\begingroup$ @RichardStanley the mathoverflow question you mention, is confusing terms; what it actually is about, is the (at least for binary encoding) calculating the ordinal number of values with a given Hamming weight. The interpretation of the question for other numerical bases is however unclear to me; maybe its about calculating the the ordinal number of values that can be represented with a fixed number of non-zero digits. $\endgroup$ – Manfred Weis Jun 2 '14 at 6:08
1
$\begingroup$

Regarding the second question: $[\mathbb{N}]^k$ is common.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.