# Tagged Questions

73 views

### Theoretical computer science text for mathematician

I am a high school student, I know some basic programming in java,python and visual basic. I love combinatorics and I have encountered various cases in which I have found some problems are really ...
30 views

### How do you find a minimum of a function with these tools?

Let's say I can define a group $G$ acting on a set of combinatorial objects $X$ and I have a function $f: X \to \Bbb{N}$ that I want to find a minimum of in $X$. Is there a polynomial time ...
33 views

### Application of Combinatorics, Logic and computability theory in physical science: Tiling of Wang Tile with proportionality

The original problem of Domino Tiling and Wang Tile has great theoretical interest on computability theory... However, the great emerging problem on application of Wang Tile in material science and ...
69 views

### The complexity of counting solutions to $x_1 + \dots + x_m = N$ in non-negative integers under constraints

Consider the equation $$x_1 + \dots + x_m = N$$ where $x_1,\dots,x_m \ge 0$ and under the additional constraints $x_k \le a_k$ for $k=1,2,\dots,m$. I'm interested in knowing whether the number of ...
678 views

### Why is Dantzig's solution to the knapsack problem only approximate

For a bunch of items with values $v_i$ and weights $w_i$, and with a total weight $W$ that our bag can carry, how do we achieve maximum total value without breaking the bag? Dantzig proposed that we ...
61 views

Given: $$X = \left\{ x_1, x_2, \ldots , x_n \right\}\text{ with }x_i \in \mathbb N\text{ and }1 \le x_i \le x_{i+1}$$ $$z \in \mathbb N$$ Wanted result: $$Y = \left\{ y_1, y_2, \ldots , y_n ... 2answers 103 views ### number of strictly increasing sequences of length K with elements from \{1, 2,\cdots,N\}? What is the number of strictly incremental sequences of length K with elements from \{1, 2,\cdots,N\} ? Is there any exact value? How about approximations? 0answers 18 views ### Reducing the complexity of a Combinatoric Equation Given the equation:$$ P = \sum\limits_{n=1}^{\lfloor {\frac{q}{2}} \rfloor} {\dbinom{2n-1}{\frac{W}{2t}+n-1}\frac{1}{2^{2n-1}}} $$Are there any algebraic tricks (or any others for that matter) ... 1answer 97 views ### Cover the n-sphere with sub-hemispherical caps Original Question (answered): Define a cap (x,Phi) to be the set of all points of the sphere that are within an angle Phi of the point x.  0 \le \phi < \frac{\pi}{2} . (define the angle ... 3answers 53 views ### Best Sum of Three Elements in a Sequence I encountered the following problem: Given an integer sequence \left(s_1,s_2,\dots,s_n\right) and an integer l, find$$\min\left|s_i+s_j+s_k-l\right|,$$where i\neq j\neq k\neq i, and return ... 0answers 16 views ### The k-th term in the graded lexicographical order is recursive I recently constructed a proof that a computable universal function exists for the class of polynomials of n-variables. To this end, I adopted the graded lexicographical monomial order. However, I ... 0answers 21 views ### Time complexity of combinatorial number? [duplicate] What is the time big-oh complexity of the following combinatorial number?$$\binom{h+m-1}{m-1}. where $h \gg m$. I guess that it is $O((h+m)^{m-1})$. Thank you very much.
In short: In how many ways can all $2^n$ subset sums of $n$ real numbers $a_1,\ldots, a_n$ be ordered? I am not concerned about the case in which different subsets sum to the same number; you may ...