This tag is for basic questions about the study of finite or countable discrete structures — specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions. ...

learn more… | top users | synonyms (5)

4
votes
1answer
44 views
+50

Steiner Triple Systems block clique

Given a Steiner Triple System (STS) of order $v$, one can build its graph in the following way: each vertex is a block, and two verticies are adjacent if their blocks have nonempty intersection. Thr ...
15
votes
1answer
277 views
+100

Maximizing curious symmetric function from simple combinatorics

A curious symmetric function crossed my way in some quantum mechanics calculations, and I'm interested its maximum value (for which I do have a conjecture). The problem There are $n$ different ...
2
votes
1answer
66 views
+100

A Law of Large Numbers Without Replacement

Let $(n_1,...,n_r)$ be $r$ positive integers, and let $n=n_1+...+n_r$. Fo each positive integer $m$ consider an urn containing $mn$ balls, of which $mn_1$ are of type 1,..., $mn_r$ of type r. For each ...
1
vote
1answer
43 views
+50

Question on data compression

Suppose we have some text as a series of a number of characters and a dictionary consisting of some words that are sub-strings of the text, $D=\{w_1,w_2,\dots,w_n\}$. The dictionary is rich enough so ...
1
vote
0answers
32 views
+50

Aumann-Shapley Uniformly Better Principle

Let $n_1,..,n_r$ be $r$ positive integers, and let $1 \leq k \leq n$, where $n=n_1+...+n_r$. Consider an urn containing $r$ different types of balls, $n_1$ balls of type 1, $n_2$ balls of type ...
1
vote
0answers
27 views
+50

Partition in graph connecting itself and other half

Let $G=(V,E)$ be a graph with $n$ vertices and minimum degree $\delta>10$. Prove that there is a partition of $V$ into two disjoint subsets $A$ and $B$ so that $|A|\leq ...