All Questions
133
questions
1
vote
0
answers
39
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
339
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
244
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
159
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
208
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
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
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
445
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' \...
1
vote
1
answer
61
views
Prove or disprove the inequality that generalized the base cases
I have come across with a question that say prove or disprove the following:
$$\frac{(n_{1}+n_{2}+ \cdot \cdot \cdot n_{m})(n_{1}+n_{2}+ \cdot \cdot \cdot n_{m}-1)\cdot \cdot \cdot (n_{1}+n_{2}+ \cdot ...
0
votes
0
answers
51
views
Hybrid 'Discrete triangular number base' numbers
I'm trying to invent a new type of number who's digits are composed of hybrid 'Discrete Triangular Number Base' numbers (Which have two components; one in 'Discrete Triangular Number Base X and Base Y'...
3
votes
0
answers
161
views
Solve the equation with respect to $k_1,k_2\in \mathbb{Z}_{+}$
I am struggling with solving the following equation for positive integers $k_1$ and $k_2$ in terms of $n\in \mathbb{Z}_+$ and $i,j\in \mathbb{Z}_+$:
$$n-1=\sum_{i\le k_1,j\le k_2}\sum_{\text{gcd}(i,j)=...
6
votes
1
answer
178
views
Choosing elements from an abelian group $\mathbb{Z}_n$ that make the enumeration of partitions incomplete.
Take an abelian group $(\mathbb{Z}_n,+)$ and enumerate all partitions of two elements (i.e. $x=x_1+x_2$) of each element $\{0,1,...,n-1\}=\mathbb{Z}_n$. Take, for example, abelian groups $\mathbb{Z}_9$...
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, ...
3
votes
2
answers
194
views
OEIS entry - A316312 has a question: Is it true that if k is a term then 100 * k is a term? [closed]
Refer https://oeis.org/A316312 - the sequence in OEIS.
The sequence says
Numbers n such that sum of the digits of the numbers 1, 2, 3, ... up
to (n - 1) is divisible by n.
A few terms from the ...
0
votes
1
answer
287
views
Let X be a finite set with lXl=6. Then the number of equivalence relations on X such that each equivalence class has at least three elements in it is?
Let X be a finite set with |X| : 6. Then the number of equivalence relations on X
such that each equivalence class has at least three elements in it is:
(A) 10.
(B) 11.
(c) 20.
(D) 21.
My try
We know ...
3
votes
1
answer
272
views
Combinatorial Necklaces & Strips of $n$ Beads and $k$ Colours
Say I have $n$ indistinguishable beads and $k$ different colours. Suppose here and for the rest of the writeup that $k \mid n$ unless otherwise stated.
I want to colour all the $n$ beads using exactly ...
0
votes
1
answer
45
views
Number of ways $k$ identical objects can be distributed in $n$ different boxes [closed]
In how many ways $k$ identical objects can be distributed in $n$ different boxes so that for each $1 \leq i \leq n$ we have
$$ 2 x_i \leq k+1, $$
for all $1\leq i \leq n$. Roughly speaking, we don't ...
0
votes
2
answers
280
views
How many ordered pairs of integers $(a,b)$ are there such that $100≤a,b≤200$ and no carrying is required when calculating $a+b$?
How many ordered pairs of integers $(a,b)$ are there such that $100≤a,b≤200$ and no carrying is required when calculating $a+b$?
What I did was:
The number range was between 100 and 200 including them....
1
vote
1
answer
101
views
The number of points in diameters defined by a subdivided hexagon
Just as in the image, imagine that we have $n$ nested hexagons which have subdivided sides just as in the image i.e. the first inner hexagon has no subdivisions, it is just a regular hexagon, the ...
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},...
0
votes
1
answer
118
views
Alcuin's problem of inheritance.
A certain father died and left as an inheritance to his three sons $30$ glass flasks, of which $10$ were full of oil, another $10$ were half full, while another $10$ were empty. Divide the oil and ...
0
votes
1
answer
90
views
How many integers in the form $q^k$ mod by $p^d q$ for distinct prime $p$ and $q$?
Let $p$ and $q$ be distinct primes, and $d$ be a positive integer.
There are only finite many (at most $p^d q$) distinct integers in the form $q^k$ with non-negative integer $k$ mod by $p^d q$.
But ...
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 ...