All Questions
103
questions
2
votes
2
answers
110
views
Counting integers $n \leq x$ such that $rad(n)=r$
Let $r$ be the largest square-free integer that divides $n$. Then $$r = \operatorname{rad}(n)=\prod_{\substack{p\mid n\\p\text{ prime}}}p$$ $r$ is called the "radical" of $n$, or the square-...
- 1,022
2
votes
1
answer
281
views
An efficient algorithm to generate a set of tuples satisfying a given upper bound for a distance between two arbitrary elements
Let $T_i^n$ denote a particular tuple of $n$ natural numbers (here $i < n!$ and we assume that the tuple contains all elements of the set $\{0, 1, \ldots, n-2, n-1\}$, i.e. there are no duplicates)....
- 922
0
votes
0
answers
32
views
Polynomial time "fairness" algorithm that assigns leaders for $m$ tasks amongst $n$ workers.
Suppose we have $n$ workers and $m$ tasks. Suppose each task has a workforce $S_i \subseteq \{1, 2, .., n\}$. Note that $S_i \cap S_j \neq \emptyset$ is possible (and expected).
Given this ...
- 11
0
votes
1
answer
250
views
How to find the average pairwise distance in G for a "flower" graph
I need to know how to compute the sum of the distances between all pairs of “pedal” nodes of the flower graph. And the sum of the distances between all pairs of “stalk” nodes
I know that the average ...
1
vote
1
answer
73
views
Trivial approximation ratio of $n/2$ for 2-Opt for TSP
I recently read that the 2-Opt algorithm for the TSP yielded an approximation ratio of $n/2$ by trivial reasons. However, there was neither proof nor further context provided and I am curious how this ...
- 177
1
vote
1
answer
163
views
Algorithms to check Pattern Avoidance Permutations
My question is the following: Given two permutations $\pi \in S_{n}$ and $\mu \in S_{k}$, decide whether $\pi$ is $\mu$-avoiding or not.
I think the formal definition is quite hard to write in the ...
- 108
1
vote
0
answers
205
views
Find the number of compatibility relations of [n] containing k maximal irredundant set C n,k
Let [n] denote the set of n elements {1, 2, ... , n}. A relation on the set [n] is a subset of the Cartesian product [n] × [n]. Equivalence relations are relations that satisfy self-reflexivity, ...
- 11
5
votes
0
answers
45
views
Number of lines of $3$ points in an arrangement of points and lines
It is well known that a finite set of $n$ points cannot form more than
$$\bigg\lfloor \frac{n(n-3)}{6} \bigg\rfloor+1 $$
lines that include $3$ points. Would this result still hold if we assume that ...
user920720
0
votes
0
answers
32
views
How to describe these combinatorial sets in general and prove their cardinality
The sets I am looking at are defined as follows: for $k=1$ the set is defined as:
$\Sigma_1:=\Big\{ \frac{1}{1},\frac{1}{3}\Big\}$
whereas for $k=2$ we have
$\Sigma_{2}:=\Big\{ \frac{1}{1},\frac{2}{1},...
user830143
0
votes
0
answers
15
views
How to simplify this combinatorial formula and solve the cardinality of the intersection? [duplicate]
Define two sets: $\Sigma_1$ and $\Sigma_2$ where we have that $a$ is odd (i.e. $a=2n+1$ for some $n\in \mathbb{N}$) and $b\in \mathbb{N}$,
$\Sigma_1 = \Big\{ \frac{2}{a},\frac{2}{a-2},\frac{2}{a-4},....
user830143
0
votes
0
answers
46
views
Computing the cardinality of a combinatorial set
Define two sets: $S_1$ and $S_2$ where we have that $a$ is an odd natural number and $b\in \mathbb{N}$,
$S_1 = \Big\{ \frac{2}{a},\frac{2}{a-2},\frac{2}{a-4},...,\frac{2}{a-(a-1)},$
$\frac{2+4}{a+2},\...
user830143
2
votes
0
answers
56
views
Unique number of combinations after $z$ steps of merging items by specific rules
I encountered an issue where I am trying to estimate the number of unique combinations:
There exists $N$ distinct molecules (or, for example, balls), where each molecule is labelled with some ...
- 21
1
vote
1
answer
46
views
A combinatorial formula for different sums $a\cdot( k_1+ k_2+...+k_{n-1})+k_n$
I am looking for a combinatorial rule for the following: let $n \in \mathbb{N}$ and $k_1,k_2,...,k_n \in \mathbb{N}$ (these are known). Since we know what the sum $\sum_{j=1}^{n}k_i$ is, let's say ...
user830143
0
votes
0
answers
43
views
All combinatorial derangements of $1,2,3 \cdots k$ with specified rules [duplicate]
Let's say that we have the points $\{1,2,3,...,k\}$. I am looking for all the ways to create a derangement of these points with the following rule:
we define a derangement as a permutation $\sigma$ ...
user830143
2
votes
0
answers
50
views
Enumerating separating subcollections of a set
Let $S$ be a (finite) set, and let $C \subseteq 2^S$ be a collection of subsets of $S$. We say that a subcollection $C' \subseteq C$ is separating if for any two elements of $S$ there exists a subset ...
- 11.2k