All Questions
28
questions with no upvoted or accepted answers
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)$.
$...
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 ...
5
votes
0
answers
278
views
Expected Value for the Number of Parts of a Partition of n
Given a positive integer $n$, I want to know the expected value for the number of parts of a random partition of $n$.
I am aware that a similar question has been asked already: Expected number of ...
5
votes
1
answer
205
views
Find the number of sets of cardinality $m$ that are subsets of $\{1,\cdots,n\}$ such that the sum of the elements of the subset is divisible by $k$.
For specific cases with small numbers, this works out fairly easily using straightforward enumeration and modular arithmetic. However, my question is: how do we solve this problem in general?
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)=...
3
votes
0
answers
43
views
Finite generation of a subset of an algebraic structure.
Consider the set $\mathbb{N}^n$ of $n$ tuples of positive integers, with the following partially defined "operations" $\oplus_i$.
This operation takes in two vectors $A=(a_1,..a_i,...a_n)$, $B=(b_1,.....
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
0
answers
25
views
Number of $k$-sets in $[n]$ so that any two of them share at most 2 elements?
Let $[n]$ be $\{1,2,\dots,n\}$. Let
\begin{align}T_\ell:=\Big|\Big\{&\{K_1,\dots,K_m\} \text{ is "maximal"}:\\ &\text{each $K_i$ is a $k$-subset of $[n]$, and $|K_i\cap K_j|\le \ell$ for all $...
2
votes
0
answers
379
views
What is the probability that two random vectors in $\mathbb{Z}_n^k$ have dot product $z$?
In particular, I'm considering the set
$S(n, k, z) = \{(x, y) \in (\mathbb{Z}_n^k)^2 \mid \langle x, y \rangle = z\}$
which contains, for any $n, k, z$ each pair of vectors $(x, y) \in (\mathbb{Z}_n^...
2
votes
1
answer
521
views
Optimization and Postage Stamp Problem
(1)
Given the set U = {1, 2, 3, ..., 98, 99, 100} of Natural numbers, find the smallest subset S contained in U that:
For every element v belonging to U, there are a, b elements of S, not ...
2
votes
0
answers
285
views
Van der Waerden type numbers (for geometric progressions)
Van der Waerden theorem is true also for geometric progressions.
Is there anything interesting in van der Waerden type numbers $ W'(r,k) $ derived from this version? ($ W'(r,k) $ is such that if the ...
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 ...
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
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, ...
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 ...