# Tagged Questions

Questions related to combinatorics and discrete mathematical structures

27 views

23 views

### Finding a closed form for a discrete sum using generating functions

Consider this sum: for context sake, the summand appears in the counting of the possible ways to have one cigarette box empty and the other having left N cigarettes when both boxes start with N ...
43 views

### Shortest path in divisors graph

There is a graph with N vertices numbered from 1 to N. Edge between a and b exists if and only if a|b or b|a. If a|b then the weight of the edge is b/a. If b|a then the weight of the edge is a/b. ...
36 views

I have written a lambda calculus interpreter, and it seems to work. I cant find the combinator for something I want though. I want to be able to define an arbitrary number of mutually recursive ...
80 views

### Formulating shortest path as submodular minimization

I'm curious about the general question of whether any combinatorial optimization problem with polynomial time solution can necessarily be reformulated as minimizing a submodular function. The answer ...
27 views

### Best combination of elements with defined constraints

My goal is to find the best combination, or good approximation, of weighted elements with different constraints / relations, for example: B can only be there after A B have to be there after A B ...
93 views

### Is it feasible to generate every possible RGB image?

This topic is normally brought up in computer science as a demonstration of how to calculate permutations but it stops there since we usually end up calculating that there are more images of a decent ...
26 views

### Help coming up with a solution to a combinatorial problem

So here is the problem: Say I want to find the only possible combinations to find the sum of a specific number using only the numbers 1, 2, & 3 with a specific number of additions. I know this ...
236 views

### Number of finite strings over a countably infinite alphabet

If the alphabet is countably infinite, then is the number of finite-length strings over this alphabet countably or uncountably infinite?
89 views

### Counting the number of permutations of string with given repeated interwoven subsequence

Given string $S$ of length $n$, count the number of distinct permutations $P_n$ of a string of length $2n$ such that each of them contains $S$ twice as an interwoven subsequence. Example. $S=abc$. ...
### Number of words within Hamming distance $\delta$
This is a problem I'm having reading Arora & Barak's book, page 378-379. They define: For two words $x, y \in \{0, 1\}^m$, the fractional Hamming distance of $x$ and $y$ is equal to the ...
Given $n$ variables and a function $f$ such that $f(v) = N(v) + D(v)$, where $N$ and $D$ are the subfunctions of function $f$. Function $f$, can be considered as an oracle. Query: let $v \in P$, ...