# Tag Info

35

For counting many types of combinatorial objects, like trees in this case, there are powerful mathematical tools (the symbolic method) that allow you to mechnically derive such counts from a description how the combinatorial objects are constructed. This involves generating functions. An excellent reference is Analytic Combinatorics by the late Philipe ...

35

Converting Full History to Limited History This is a first step in solving recurrences where the value at any integer depends on the values at all smaller integers. Consider, for example, the recurrence $$T(n) = n + \frac{1}{n}\sum_{k=1}^n \big(T(k-1) + T(n-k)\big)$$ which arises in the analysis of randomized quicksort. (Here, $k$ is the rank of the ...

31

The are countably many computable functions: Each computable function has at least one algorithm. Each algorithm has a finite description using symbols from a finite set, e.g. finite binary strings using symbols $\{0,1\}$. The number of finite binary strings denoted by $\{0,1\}^*$ is countable (i.e. the same as the number of natural numbers $\mathsf{N}$). ...

28

Generating Functions $\newcommand{\nats}{\mathbb{N}}$ Every series of numbers corresponds to a generating function. It can often be comfortably obtained from a recurrence to have its coefficients -- the series' elements -- plucked. This answer includes the general ansatz with a complete example, a shortcut for a special case and some notes about using this ...

28

An algorithm is informally described as a finite sequence of written instructions for accomplishing some task. More formally, they're identified as Turing machines, though you could equally well describe them as computer programs. The precise formalism you use doesn't much matter but the fundamental point is that each algorithm can be written down as a ...

27

$k$-SUM can be solved more quickly as follows. For even $k$: Compute a sorted list $S$ of all sums of $k/2$ input elements. Check whether $S$ contains both some number $x$ and its negation $-x$. The algorithm runs in $O(n^{k/2}\log n)$ time. For odd $k$: Compute the sorted list $S$ of all sums of $(k-1)/2$ input elements. For each input element $a$, ...

26

I just did a quick animation to convince you. Yellow is one, blue is zero.

22

I did not find a closed form, but according to this entry in the Online Encyclopedia of Integer Sequences the sequence starts with 1, 1, 1, 2, 3, 8, 20, 80, 210, 896, 3360, 19200, 79200, 506880, 2745600, 21964800, 108108000, 820019200, 5227622400, 48881664000, 319258368000, ... You can find a not-so-nice recursion in the OEIS database. Basically the idea ...

21

Assume for contradiction that $P_{1} = \langle v_{0},\ldots,v_{k}\rangle$ and $P_{2} = \langle u_{0},\ldots,u_{k}\rangle$ are two paths in $G$ of length $k$ with no shared vertices. As $G$ is connected, there is a path $P'$ connecting $v_{i}$ to $u_{j}$ for some $i,j \in [1,k]$ such that $P'$ shares no vertices with $P_{1} \cup P_{2}$ other than $v_{i}$ and ...

21

Master Theorem The Master theorem gives asymptotics for the solutions of so-called divide & conquer recurrences, that is such that divide their parameter into proportionate chunks (instead of cutting away constants). They typically occur when analysing (recursive) divide & conquer algorithms, hence the name. The theorem is popular because it is ...

18

It's difficult to answer the question "how often". But as with all "underlying structures" the benefit comes from recognizing that the underlying problem one is trying to solve has a matroid (or greedoid) structure. It's not just matroid problems. The matroid intersection problem has a specific model (bipartite matching). Nick Harvey did his Ph.D thesis ...

18

Ok, A bit more detailed answer than in the comments. Choosing $k$ out of $n$ is done by ${n \choose k} = \frac{n!}{k!(n-k)!}$. So for things like the size of the pizza, where you have 4 options (and you need to choose one, coz pizza cannot be both medium and extra-large at the same times) you have only $4$ options. Indeed, ${4 \choose 1}=\frac{4!}{3!}=4$. ...

17

Guess & Prove Or how I like to call it, the "$\dots$ technique". It can be applied to all kinds of identities. The idea is simple: Guess the solution and prove its correctness. This is a popular method, arguably because it usually requires some creativity and/or experience (good for showing off) but few mechanics (looks elegant). The art here is to ...

15

No, unfortunately not. There are even infinite square-free words if your alphabet has at least three symbols. This apparently natural border (two-element alphabets have only finitely many square-free words) is observed in many places, for instance: $\{xyyz \mid x,y,z\in \Sigma^+\}$ is co-finite for $|\Sigma|\leq 2$ but not context-free for $\Sigma>2$. ...

15

The Akra-Bazzi method The Akra-Bazzi method gives asymptotics for recurrences of the form: $$T(x) = \sum_{1 \le i \le k} a_i T(b_i x + h_i(x)) + g(x) \quad \text{for x \ge x_0}$$ This covers the usual divide-and-conquer recurrences, but also cases in which the division is unequal. The "fudge terms" $h_i(x)$ can cater for divisions that don't come out ...

14

For your language, can you take $p_0(x) = 1/2$, $\lambda_0 = 1$, $p_1(x) = 1/2$, $\lambda_1 = -1$, and $p_i(x) = \lambda_i = 0$ for $i > 1$? The Wikipedia article doesn't say anything about the coefficients being either positive or integral. The sum for my choices is $\qquad \displaystyle 1/2 + 1/2(-1)^n = 1/2 (1 + (-1)^n)$ which seems to be 1 for ...

13

A coin system is canonical if the number of coins given in change by the greedy algorithm is optimal for all amounts. The paper D. Pearson. A Polynomial-time Algorithm for the Change-Making Problem. Operations Reseach Letters, 33(3):231-234, 2005 offers an $O(n^3)$ algorithm for deciding whether a coin system is canonical, where $n$ is the number of ...

13

If looking for the key 60 we reach a number $K$ less than 60, we go right (where the larger numbers are) and we never meet numbers less than $K$. That argument can be repeated, so the numbers 10, 20, 40, 50 must occur along the search in that order. Similarly, if looking for the key 60 we reach a number $K$ larger than 60, we go leftt (where the smaller ...

13

If we have a set of size $n$, you can represent an element of the set using $\lceil \lg n \rceil$ bits. You say that there are 2598960 possible 5-card hands. That means that a 5-card hand can be represented using just $\lceil \lg 2598960 \rceil = 22$ bits. 22 bits is significantly shorter than 30 bits. How does the representation work? There are various ...

12

A unipathic graph can have $\Theta(n^2)$ edges. There's a well-known kind of graph that's unipathic and has $n^2/4$ edges. (Follow-up question: is this ratio maximal? Probably not, but I don't have another example. This example is maximal in the sense that any one edge that you add between existing nodes will break the unipathic property.)

12

$d$-SUM requires time $n^{\Omega(d)}$ unless k-SAT can be solved in $2^{o(n)}$ time for any constant k. This was shown in a paper by Mihai Patrascu and Ryan Williams(1). In other words, assuming the exponential time hypothesis, your algorithm is optimal up to a constant factor in the exponent (a polynomial factor in $n$) (1) Mihai Patrascu and Ryan ...

11

Generating functions are useful when you're designing counting algorithms. That is, not only when you're looking for the number of objects having a certain property, but also when you're looking for a way to enumerate these objects (and, perhaps, generate an algorithm to count the objects). There is a very good presentation in chapter 7 of Concrete ...

11

@Patrick87 gives a great answer for your specific case, I thought I would give a tip of how to find $s_L(n)$ in the more general case of any language $L$ that can be represented by an irreducible DFA (i.e. if it is possible to get to any state from any state). Note that your language is of this type. Proof of theorem for irreducible DFAs Let $D$ be the ...

11

Summations Often one encounters a recurrence of the form $$T(n) = T(n-1) + f(n),$$ where $f(n)$ is monotone. In this case, we can expand $$T(n) = T(c) + \sum_{m=c+1}^n f(m),$$ and so given a starting value $T(c)$, in order to estimate $T(n)$ we need to estimate the sum $f(c+1) + \cdots + f(m)$. Non-decreasing $f(n)$ When $f(n)$ is monotone non-...

11

Nice idea! The problem seems to be in step $(b)$. Replacing $(X_1,B,X_2)$ in an $N$-path by $(X_1,X_2)$ gives an $\bar{N}$-path, but not every $\bar{N}$-path will contain $(X_1,X_2)$. So this is not a bijection. This only says $N(n) \leq \bar{N}(n)$. Or you can in fact show that $\bar{N}(n) = 3N(n)/2$, resulting in $N(n+1) = 3N^3$.

11

The block designs you want (for testing 3 things at a time, and covering all pairs) are called Steiner triple systems. There exists a Steiner triple system with $\frac{1}{3} {n \choose 2}$ triples whenever $n \equiv 1 \mathrm{\ or\ } 3$ mod $6$, and algorithms are known to construct these. See, for example, this MathOverflow question (with a link to working ...

11

This is a summary of the paper On the Number of Distinct Languages Accepted by Finite Automata with n States. The paper provides relatively easy, yet far from tight, lower and upper bounds on the number of distinct languages accepted by NFA's. Their discussion on the number of distinct DFA's is very insightful, so I will also include that part. The paper ...

11

I can offer an example for super-exponentially many shortest paths and super-polynomially many minimum cuts. An example for many shortest s-t-paths you probably came up with is the layer graph, similar to the one here. Turns out we can use the same idea here -- all we have to do is use many layers so that there are many minimum cuts, and fiddle with the ...

10

I suggest taking a look at the edit distance algorithm. Instead of just calculating the distance, you'll want to record your minimum weight path through the array and return that.

10

The basic idea is: Try out all cut positions as first choice, solve the respective parts recursively, add the cost and choose the minimum. In formula: \$\qquad \displaystyle \operatorname{mino}(s, C) = \begin{cases} |s| &, |C| = 1 \\ |s| + \min_{c \in C} \left[ \begin{align}&\operatorname{mino}(s_{1,c}, \{c' \in C \mid c' < c\})\ \\ +\...

Only top voted, non community-wiki answers of a minimum length are eligible