All Questions
23
questions
8
votes
0
answers
280
views
Count permutations with given longest increasing subsequence
Problem: Given $n \in \mathbb{Z}_+$ and a set $A \subset \{ 1,\ldots,n \}$ sorted in ascending order, find the number of permutations $\sigma \in S_n$ such that $A$ is a longest increasing subsequence ...
- 4,051
0
votes
0
answers
68
views
Finding the general formula for the last standing soldier
Suppose there are 'n' soldiers standing in a circle who have decided to kill each other (just because they don't want to surrender to the opposition).
Lets say they are denoted from a1 to an in the ...
- 1
2
votes
1
answer
57
views
Computing subset reciprocals, $\frac1{a+b}+\frac1{a+c}+\frac1{b+c}$
I'm interested in computing the sum
$$
H_k = \sum_{S\subseteq T, |S|=k} \frac{1}{\sum_{s\in S} s},
$$
where $T$ is some set of integers.
Obviously this can be done in $|T|^k$ time, enumerating all ...
- 4,854
1
vote
0
answers
49
views
An efficiently computable infinite binary sequence satisfying a stronger disjunctiveness property
Given a natural number $n > 1$ and an infinite binary sequence $B = b_0b_1b_2b_3\ldots$ (here $b_i$ denotes an $i$-th element of $B$), let $f_n(B)$ denote the following tuple of infinite binary ...
- 922
6
votes
1
answer
317
views
Math behind this SQL problem
I have the following 'sorted by row' lists (2nd column), in which every row produces an output (3rd column, and 4th column). This output has been found without using formulas and it represents a ...
- 121
7
votes
2
answers
126
views
A sum of partitions
A friend of mine presented a problem I found interesting:
Compute the following: $$\sum_{n=0}^\infty\left(\prod_{k=1}^j(1+x^k)\right)[x^{mn}]$$ where $P(x)[x^n]$ denotes the $x^n$ coefficient of $P$...
1
vote
1
answer
296
views
Why does searching for a non-cyclic de Bruijn sequence always give you a cyclic de Bruijn sequence
I am looking at some code to produce binary cyclic de Bruijn sequences. If $n$ is the length of the subsequence that should not be repeated more than once, it looks for a non-cyclic de Bruijn sequence ...
user35671
5
votes
3
answers
142
views
Summation Involving Product Of Two Identical Polynomials.
Recently I stuck, to a problem. However I rarely think that there is some proper formula for this problem, but here I am in search of algorithm's or theorem that relate to this problem or can solve ...
- 97
-1
votes
1
answer
68
views
Lights on game algorithm
When I was a young child I was on holiday with my mother with a dutch family.
One day Dick, the family man, handed me a wooden box with some switches and lights (maybe eight, but I'm not sure) and ...
- 99
0
votes
1
answer
171
views
n-th item of the series of strings from set of characters
Consider a set of Characters like S={ABCDEFGHIJKLMNOPQRSTUVWXYZ} where S is 26.
R=3, where R is length of every item of the series.
Total Output is $S^R$ = $26^3$ = 17576 where first item is AAA and ...
- 3
2
votes
1
answer
157
views
Minimally Good Sequences
Let $k$ be a fixed positive integer. Let a sequence of positive integers with odd sum $(a_1,\ldots,a_n)$ be called good if for all integers $1 \leq i \leq n$, we have $\sum_{j \neq i} a_j \geq k$
Now ...
- 605
1
vote
1
answer
55
views
What is the name of the transform which finds the number of ways to make partitions of the given sizes?
I'm looking for the name of a transform which takes a sequence giving the number of 'prime' elements of a given size to the number of ways to make a number out of a sum of 'prime' elements, up to ...
- 32.3k
0
votes
1
answer
1k
views
Complexity of subset-generation algorithm
I'm trying to calculate the computational complexity of an algorithm which generates the power set of a set of items.
The algorithm works using the recursive formula of the binomial coefficient
$$\...
- 175
3
votes
4
answers
2k
views
Generate all de Bruijn sequences
There are several methods to generate a de Bruijn sequence. Is there a general algorithm to create all unique (rotations are counted as the same) De Bruijn sequences for a binary alphabet of length $n$...
- 10.9k
2
votes
1
answer
133
views
Find different sequences of game to find winner
Alice and Bob are having a racing competition to see who is the best runner. They don't want to decide this in a single race, so they choose a number N which is the minimum number of points one of ...
- 272