All Questions
Tagged with combinatorics number-theory
1,985
questions
2
votes
1
answer
73
views
optimal sandwiches in first $n$ positive integers
Consider an ordered permutation of $n$ integers $\lbrace a_1,a_2,\ldots,a_{n} \rbrace$. Define a sandwich to be a pair $(a_i,a_j)$ such that $a_i,a_j > a_{i+1},a_{i+2},\ldots,a_{j-1}$. Find the ...
- 109
3
votes
3
answers
161
views
If every real subseries whose set of indices has natural density zero converges, does the original series converge?
Proposition: Suppose $a_n\in\mathbb{R}\ \forall\ n\in\mathbb{N},\ $ and $\ \displaystyle\sum_{n\in A} a_n $
converges for every $A\subset \mathbb{N}$ with zero
natural density. Then does $\...
- 20.7k
2
votes
1
answer
102
views
Number of Ordered Factorisations [closed]
How many solutions does the following Diophantine equation ($\forall \, i$, $x_i \in \mathbb{N}$) have:
$$\prod_{i = 1}^n {x_i} = k$$
where $n$ and $k$ are natural numbers?
Assume you know the prime ...
- 124
1
vote
0
answers
64
views
How many permutations $\left(a_1,a_2,\dots,a_n \right)$ of $\left(1,2,\dots,n \right)$ such that...
Source
How many permutations $\left(a_1,a_2,\dots,a_n \right)$ of $\left(1,2,\dots,n \right)$ such that $$\left|a_{i+1} - a_i \right| \le 2, \ \forall i=1,2,\dots,n-1.$$
At first I thought this might ...
- 31
0
votes
1
answer
40
views
Proving an inequality involving factorials
In some certain exercise I am asked to show that $\forall n,k \in \mathbb{N},\frac{n^k}{k^k} \leq
{n\choose k}$.
I have bounded the left side by $\frac{n^k}{k^k} \leq \frac{n^k}{k!}$. When I computed ...
- 1,361
0
votes
2
answers
62
views
Finding the minimum value of K for non-repeated sums
Given a set $A$ containing 10 positive integers, with the largest element denoted as $K$, we calculate all possible sums of elements from set $A$, including sums of 2, 3, 4, and so on, up to all 10 ...
- 143
6
votes
0
answers
101
views
A Number-theoretic Generalization of the Union-closed Sets Conjecture
Denote $\mathbb{N}^*=\{1,2,3,...\}, \dot k = \{k,2k,3k,...\}, \mathbb{P}=\{2,3,5,7,11,..\}$ and write $M\leq \mathbb{N}^*$ to denote that $M$ is lcm-closed, i.e. $a,b\in M\Rightarrow \text{lcm}(a,b)\...
- 1,810
0
votes
0
answers
74
views
Möbius function for graphs??
I'm reading this post and I'm getting a little confused. I am trying to find a useful notion of the Mobius function for directed graphs and have had little success in my search. I don't know much ...
- 157
0
votes
1
answer
81
views
Question about element in $\{1,\cdots,n\}$ and its product with its permutation: $\sum_{j=1}^nj\sigma(j)$ for $\sigma \in S_n$ [closed]
Let $\sigma\in S_n$ for some $n\in \mathbb{N}$. I am interested in $\displaystyle \sum_{j=1}^nj\sigma(j)$. Can anyone help point me in a decent direction? If $\sigma = (1)$ in cycle notation, we ...
1
vote
1
answer
88
views
If $A \subseteq \mathbb{Z}/p\mathbb{Z}$, and $|A| > \frac{p}{3}$, then are there any nontrivial lower bounds for $|AA|$?
If $A \subseteq \mathbb{Z}/p\mathbb{Z}$, and $|A| > \frac{p}{3}$, then are there any nontrivial lower bounds for $|AA|$?
Where $AA=\{a_{1} \cdot a_2:a_1,a_2 \in A\}$, and $p$ is prime.
Writing out ...
- 196
4
votes
0
answers
251
views
Sum of even binomial coefficients modulo $p$, without complex numbers
Let $p$ be a prime where $-1$ is not a quadratic residue, (no solutions to $m^2 = -1$ in $p$).
I want to find an easily computable expression for
$$\sum_{k=0}^n {n \choose 2k} (-x)^k$$
modulo $p$. ...
- 4,284
2
votes
0
answers
99
views
Maximum size of multiset of integers without subset summing to zero.
Consider multisets of integers in the range $[-m,+m]$.
The sum of the elements is 0, but no strict non-empty sub-multiset has sum 0.
For example $\{+3, -1, -1, -1\}$ for $m \ge 3$.
The question I've ...
- 21
7
votes
2
answers
235
views
Approximation of gamma function via Riemann sums at integer points
I found something curious. We know that the gamma function is defined as
$$ \Gamma(n+1) := \int_{t=0}^\infty t^n \exp(-t) dt,$$
and it has the property that $\Gamma(n+1) = n!$ for non-negative integer ...
- 310
1
vote
0
answers
94
views
Find the value or prove that it's impossible [duplicate]
Let there be 4 integers $w,x,y,n$ belonging to $ℤ+$ such that $w,x,y \geq n$ and $n \gt 2$. Find the value of $w$ in terms of $x, y, n$ or prove that it's impossible if $ x \neq y $ and
$\frac{w!}{(w-...
- 119
2
votes
0
answers
66
views
Combinatorial explanation for an identity of the partition function
One can employ elementary methods to demonstrate that $p(n) \leq p(n-1) + p(n-2)$ for $n \geq 2$. Recently, I showed that if certain restrictions are imposed on the partitions, the inequality becomes ...
- 907
1
vote
3
answers
428
views
Grid filled with +1 or -1 is adjusted such that each cell is the product of its adjacent squares
In a 9x9 grid, we fill each square with either +1 or -1. We define an adjustment of the numbers in the grid as follows:
1. For each square, we calculate the product of its 4 adjacent squares (fewer ...
2
votes
0
answers
64
views
On the infinite Sum of Reciprocal Fibonacci Sequences
The question comes from On the Finite Sum of Reciprocal Fibonacci Sequences and On the finite sum of reciprocal Fibonacci sequences.
Althouth I cannot prove the identity $$\left\lfloor \left( \sum_{k=...
- 1,159
3
votes
1
answer
194
views
On the Finite Sum of Reciprocal Fibonacci Sequences
I want to check if $$\left \lfloor \left( \sum_{k=n}^{2n}{\dfrac{1}{F_{2k}}} \right) ^{-1} \right\rfloor =F_{2n-1}~~(n\ge 3)\qquad(*)$$ where $\lfloor x \rfloor$ is a floor function.
Fibonacci ...
- 1,159
4
votes
1
answer
135
views
Maximum number of n-tuples of equal sum
I'm interested in a general formula to calculate the maximum number of unique subsets from a set of distinct integers that sum to the same value.
For 2-tuples, given s > 1 distinct integers, there ...
- 43
0
votes
0
answers
66
views
Axiomatic books for combinatorics and number theory
I would like to know if there are any books on combinatorics and number theory that follow an axiomatic approach akin to that of Sierpinski's General Topology. I have found some books for both ...
- 1
0
votes
0
answers
21
views
Finding distinct value that makes up the Integer partition under multiple constraints.
I'm working on a problem that want me to solve for solutions given four equations that is equal to an integer,
For instance, consider the variables $a_1,a_2,\dots,a_m\in \mathbb{Z}_{\geq 0}$ $a_n\neq ...
- 1,071
1
vote
0
answers
23
views
When is the Frobenius number of a numerical semigroup larger than the maximum of the minimal generating set
Let $S$ be a numerical semigroup (https://en.m.wikipedia.org/wiki/Numerical_semigroup). Let $A$ be the minimal generating set for $S$. As standard, let $e(S)$, $m(S)$ and $F(S)$ stand respectively ...
- 65
0
votes
0
answers
44
views
How many musical notes does a scale need such that any integer intervals can be found in this scale?
We know that in the 12-tone equal temperament musical system, each octave is equally divided into 12 semitones. In a major scale, for example the C major scale, the notes are C, D, E, F, G, A, and B, ...
2
votes
0
answers
38
views
Constructing Disjoint Sets with Product Constraints in a Large Field" [closed]
Let $n$ be an integer. Let there be $n$ integer weights $w_1,w_2,\ldots,w_n$. Let there be a large field $\mathbb{F}$. We can assume that $n\ll|\mathbb{F}|$ and $\sum_{i\in {1,2,\ldots,n}} w_i \ll |\...
- 257
0
votes
0
answers
39
views
MacDonalds Hook content formula derivation
I was trying to understand the derivation of
$$
s_{\lambda}=a_{\lambda+\delta} / a_{\delta}=q^{n(\lambda)} \prod_{x \in \lambda} \frac{1-q^{n+c(x)}}{1-q^{h(x)}}
$$
as given in (https://math.berkeley....
1
vote
1
answer
77
views
Another formulation for Stirling numbers of the second kind
I find another formulation for Stirling numbers of the second kind:
Let $n\ge k\ge 1$. Denote by
$$\mathbb N_<^n := \{ \alpha = (\alpha_1,\cdots,\alpha_n): 0\le \alpha_1\le\cdots\le\alpha_n, \...
- 1,972
1
vote
0
answers
36
views
Proportion of a digit in an algebraic number's binary expansion
We know that
A real number is rational if and only if it's binary (or base $n$ expansion, for all $n$) is eventually periodic. Therefore, the proportion of each digit (0 or 1 in the binary case) is a ...
- 7,534
4
votes
0
answers
189
views
Subsets of $\mathbb{Z}$ satisfying the factorial property
Consider the subset $S \subseteq \mathbb{Z}$ given by:
$$S = \{ 2^i 3^j : i,j \ge 0 \}$$
Define the sequence $(a_k)$ to be the elements of $S$ in increasing order (with the standard order on $\mathbb{...
- 2,466
3
votes
0
answers
50
views
$\sum_{n=1}^m \frac{1}{n!} \sum_{\sum_{i=1}^n m_i = m, \\ m_i \in \mathbb N_+} \frac{1}{m_1\cdots m_n} = 1$? [duplicate]
I found an equation accidentally when doing my research about branching processes. I think it is correct but I don't know how to prove it:
\begin{equation}
\sum_{n=1}^m \frac{1}{n!} \sum_{\sum_{i=1}^n ...
- 1,972
0
votes
1
answer
54
views
On writing every integer from $(a-1)(b-1)$ onwards as a sum of two non-zero integers from the semigroup generated by $a,b$
Let $\mathbb N$ be the semigroup (even a monoid) of non-negative integers. Let $a<b$ be relatively prime integers such that $2< a$. Let $S :=\mathbb N a +\mathbb N b$ be the semigroup generated ...
- 65