All Questions
Tagged with combinatorics algorithms
118
questions
1
vote
1
answer
65
views
Expected cost of algorithm based on hypergeometrical distribution
I am having an algorithm which cost I want to determine, but I am having trouble to do so. In order to do so, I tried to break it down to a well known scenario, to be able to communicate the issue:
...
- 1,131
1
vote
1
answer
1k
views
Number of permutations with constraints.
Hi so i was trying to solve this problem:
Given N, M where N is the number of numbers and M is the number of orders.
An order consits of a pair x y which says in the permutation x should be before y.
...
- 1,753
0
votes
1
answer
1k
views
Finding number of subarrays not including certain pairs
How many contiguous subarrays of an array exist such that they do not contain certain pairs of positions of the array?
For eg. if array ={11,22,33,45}
and if we do not want to include say position ...
- 133
0
votes
1
answer
136
views
Alternating Pair
I want to find the number of permutations of $1,2,\ldots,N$ having exactly $k$ triples satisfying the condition that either $n_{i-1}>n_i<n_{i+1}$ or $n_{i-1}<n_i>n_{i+1}.$
For example for ...
- 111
0
votes
1
answer
2k
views
Number of ways to win chocolate game
Alice and Bob are playing a game. They have N containers each having one or more chocolates. Containers are numbered from 1 to N, where ith container has A[i] number of chocolates.
The game goes like ...
- 311
0
votes
0
answers
109
views
Binary sequences of length $N$ including all numbers upto $N$ [duplicate]
Consider numbers $n$ and $N = 2^n$ and define a binary sequence $b = [b_0,\dots,b_{N-1}]$, $b_i \in \{0,1\}$, to be complete or to include all numbers upto $N$ when for each number $0 \leq i < N$ ...
- 18.2k
0
votes
1
answer
79
views
Maximizing sum of metric function on a set (Adaptation of Hungarian Algorithm)
Suppose I have a set of unique elements $A=\{a_1, a_2, ..., a_n\}$. Suppose I also have a metric function $f:A\times A \rightarrow R^+$. I want to choose $k$ elements from $A$ (i.e. $a_{i_1},a_{i_2}, ....
- 2,457
0
votes
0
answers
22
views
Minimizing the number of operations of subtracting one so as to get to $0$ [duplicate]
Hello Community! The above problem you see is a combinatorics problem, more like an algorithmic problem that I could not solve. :(
This problem requires that every child gets satisfied. In brief ...
- 779
0
votes
1
answer
82
views
Maximizing minimum of intersection size
Let $A=\{1,2,\dots,n\}$, and let $A_1,\dots,A_m$ be subsets of $A$ of the same size.
Let $k$ be a fixed positive integer.
We want to choose $B\subseteq A$ of size $k$ such that $\min(|A_1\cap B|,\dots,...
- 1,971
0
votes
0
answers
318
views
Searching a Young tableau for a collection of numbers
This question is a follow up on: Searching a Young tableau.
The previous question was "How many comparisons are needed to find an element $x$ in an $n \times n$ Young tableau of distinct elements (...
- 3,315
0
votes
2
answers
437
views
How should teams be paired for first round of Champions League?
In the draw for the round of 16 of the Champions League football tournament, the eight group winners are seeded, and the eight group runners-up are unseeded. The seeded teams are drawn against the ...
- 925
0
votes
1
answer
46
views
Positive bit count of the $S(n):=\sum_{i=1}^{n} 2^{(i-1)}$ always $n$?
From a discussion on a stack about the programing, I got the following mathematical Conjectures:
Conjectures:
Let n,m be positive integer, $S(n)$ and $CountPosbit(m)$ be as follows.
$S(n):=\sum_{i=1}...
- 665
0
votes
0
answers
59
views
A sequence in which the number of positive bits is always $k$.
Thanks to this stack , I got the following Conjectures.
My question is as follows;
My question:
(Q1)Are the followng conjectures (1) and (2) correct?
(Q2)If these are correct, please prove them.
The ...
- 665