All Questions
133
questions
0
votes
0
answers
33
views
Counting matrix paths for (n,m>2) matrices
Given a $n\times m$ matrix with $k$ elements inside it, I need to calculate the number of arrangements of those $k$ elements that form at least 1 path from the top to bottom matrix row composed of the ...
6
votes
0
answers
215
views
The sequence $0, 0, 1, 1, 3, 10, 52, 459, 1271, 10094, 63133,...$
Let $a_0$ be a permutation on $\{1, 2, ...,N\}$ (i.e. $a_0 \in S_N$) . For $n \geq 0$:
If $a_n(i+1) \geq a_n(i)$, then $a_{n+1}(i) = a_n(i+1) - a_n(i)$.
Otherwise, $a_{n+1}(i) = a_n(i+1) + a_n(i)$.
$...
0
votes
0
answers
73
views
Counting integers in the Thue-Morse sequence
Let's call the infinite Thue-Morse sequence $T$. Define $\delta (n)$ to be $1$ if the binary representation of $n$ appears in $T$ and $0$ otherwise. Let $$F(n)=\sum_{i=1}^n\delta(i)$$
$\delta(7)=0$ , $...
2
votes
0
answers
35
views
Linear extension of a divisors set
For a number $N$, let $S_N$ be its set of divisors, and let $C(N)$ be the number of arrangements of $S_N$ in which every divisor itself appears after all of its divisors.
$C(12)=5$, because of the ...
2
votes
1
answer
337
views
Behrend's construction on large 3-AP-free set
Theorem (Behrend's construction)
There exists a constant $C>0$ such that for every positive integer
$N$, there exists a $3$-AP-free $A\subseteq[N]$ with $|A|\geq
Ne^{-C\sqrt{\log N}}$.
Proof. Let $...
1
vote
1
answer
243
views
Farkas' lemma for variables in the natural numbers
A lot of questions regarding the Farkas' lemma has already been done here. Most of them seems to be related to consequences of the Farkas' lemma, for example, see [1, 2, 3]. This means that the ...
1
vote
1
answer
158
views
Deza-Frankl-Singhi theorem
Let $p$ be a prime number and $A$ b a system of $(2p-1)$ element subsets of of an $n$-element set such that no two sets in $A$ intersect in precisely $p-1$ elements. I would like to prove that
$$|A|\...
5
votes
1
answer
203
views
If you write down all the numbers from 1 to n, how many digits would you have written down?
I've seen the question for numbers like 50, 100 or 1000, but not for $n$. Although I found a formula that might be the answer, but I don't know the name of it or the proof for it. I couldn't find it ...
6
votes
0
answers
121
views
Count number of ways to distribute n distinct positive integers into $r$ identical bins such that the product of integers in each bin is $\le M$
Problem Statement:
We have $n$ distinct positive integers say $a_1,a_2....a_n$ and a given integer value $M$.
We have to count number of ways to distribute these integers to $r$ identical bins subject ...
2
votes
2
answers
109
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
vote
1
answer
54
views
Finsing the number of natural solutions for an inequality
Given a vector:
$$
\overrightarrow{r}=\begin{pmatrix}r_{1}\\
r_{2}\\
\vdots\\
r_{m}
\end{pmatrix}
$$
where $$ r_{j}\in\mathbb{R} $$
and given a real number $x$, determine the number of vectors with ...
0
votes
1
answer
61
views
How to find the number of options for choosing numbers from $a_1, a_2, a_3, ... a_n$ such that their sum was equal to $k$
Let our numbers $2, 5, 6, 7, 10, 15$ and $k = 15$. I need to find the number of possible options for choosing numbers that form a total of 15. It's $(5, 10), (2, 7 ,6), (15)$. So the answer is 3.
1
vote
0
answers
55
views
Recasting Algorithmic Information In Terms of Finite Directed _Cyclic_ Graphs?
Any bit-string {0,1}* can be produced by a finite directed cyclic graph, the nodes of which are n-input NOR functions, with at least two arcs directed away from the graph without a terminal connection ...
1
vote
1
answer
58
views
There is a subset $T \subset S$ with $|T| = k+1$ such that for every $a,b \in T$, the number $a^2-b^2$ is divisible by $10$.
Let $k \ge 1$ be an integer.
If $S$ is a set of positive integers with $|S| = N$, then there is a subset $T \subset S$ with $|T| = k+1$ such that for every $a,b \in T$, the number $a^2-b^2$ is ...
17
votes
1
answer
443
views
Sum of set of divisible integers
I have a positive integer $n$, and a multiset $S$ of positive integers. $S$ has $n$ elements. For all $s \in S$, $s$ is a divisor of $n$.
I believe that there must exist a subset (submultiset) $S' \...