All Questions
Tagged with co.combinatorics nt.number-theory
229 questions
58
votes
3
answers
6k
views
Number of elements in the set $\{1,\cdots,n\}\cdot\{1,\cdots,n\}$
Let $A_n=\{a\cdot b : a,b \in \mathbb{N}, a,b\leq n\}$. Are there any estimates for $|A_n|$? Will it be $o(n^2)$?
- 897
35
votes
5
answers
4k
views
Cliques, Paley graphs and quadratic residues
A question I've thought about, on and off for a long time, is how to improve the best bounds that (seem to be) known for the clique numbers of Paley graphs.
If p=1 mod 4 is a prime, we can define the ...
- 703
81
votes
10
answers
9k
views
Existence of a zero-sum subset
Some time ago I heard this question and tried playing around with it. I've never succeeded to making actual progress. Here it goes:
Given a finite (nonempty) set of real numbers, $S=\{a_1,a_2,\dots, ...
- 85.6k
54
votes
2
answers
8k
views
Walsh Fourier transform of the Möbius function
This question is related to this previous question where I asked about ordinary Fourier coefficients.
Special case: is Möbius nearly orthogonal to Morse
August Ferdinand Möbius (November 17, 1790 – ...
46
votes
3
answers
3k
views
Does an existence of large cardinals have implications in number theory or combinatorics?
Does an existence of large cardinals have implications in more down-to-earth fields like number theory, finite combinatorics, graph theory, Ramsey theory or computability theory? Are there any ...
- 1,699
46
votes
5
answers
6k
views
Integer-valued factorial ratios
This historical question recalls
Pafnuty Chebyshev's estimates for the prime distribution function. In his derivation
Chebyshev used the factorial ratio sequence
$$
u_n=\frac{(30n)!n!}{(15n)!(10n)!(6n)...
- 13.5k
39
votes
5
answers
3k
views
Does there exist a comprehensive compilation of Erdos's open problems?
Fan Chung and Ron Graham's book Erdos on Graphs: His Legacy of Unsolved Problems (A. K. Peters, 1998) collects together all of Erdos's open problems in graph theory that they could find into a single ...
- 82.7k
27
votes
3
answers
2k
views
Kasteleyn's formula for domino tilings generalized?
It seems a marvel when a bunch of irrational numbers "conspire" to become rational, even better an integer. An elementary example is $\prod_{j=1}^n4\cos^2\left(\pi j/(2n+1)\right)=1$.
Kasteleyn's ...
- 43.2k
23
votes
5
answers
1k
views
Sequences with integral means
Let $S(n)$ be the sequence whose first element is $n$, and from then onward,
the next element is the smallest natural number ${\ge}1$ that ensures that the
mean of all the numbers in the sequence is ...
- 151k
20
votes
2
answers
1k
views
Euler numbers and permanent of matrices
Motivated by Question 402249 of Zhi-Wei Sun, I consider the permanent of matrices
$$e(n)=\mathrm{per}\left[\operatorname{sgn} \left(\tan\pi\frac{j+k}n \right)\right]_{1\le j,k\le n-1},$$
where $n$ is ...
- 884
17
votes
1
answer
502
views
Irreducibility of root-height generating polynomial
The height $ht(\alpha)$ of a positive root $\alpha$ in a (finite, crystallographic) root system $\Phi$ is $\sum_{i=1}^n c_i$ where $\alpha = \sum_{i=1}^n c_i \alpha_i$ is its decomposition as a sum of ...
- 2,753
3
votes
1
answer
193
views
Sequences that sums up to second differences of Bell and Catalan numbers
Let $f(n)$ be A007814, the exponent of the highest power of $2$ dividing $n$, a.k.a. the binary carry sequence, the ruler sequence, or the $2$-adic valuation of $n$.
Let $g(n)$ be A025480, $g(2n) = n$...
- 4,938
3
votes
1
answer
324
views
Sum with Stirling numbers of the second kind
Let $wt(n)$ be A000120, number of $1$'s in binary expansion of $n$ (or the binary weight of $n$)
and
$$n=2^{t_1}(1+2^{t_2+1}(1+\dots(1+2^{t_{wt(n)}+1}))\dots)$$
Then we have an integer sequence given ...
- 4,938
2
votes
1
answer
261
views
Sequence that sums up to INVERTi transform applied to the ordered Bell numbers
$\DeclareMathOperator\wt{wt}$Let $\wt(n)$ be A000120, number of $1$'s in binary expansion of $n$ (or the binary weight of $n$).
Let $f(n)$ be A007814, the exponent of the highest power of $2$ ...
- 4,938
2
votes
1
answer
183
views
Pair of recurrence relations with $a(2n+1)=a(2f(n))$
Let $f(n)$ be A053645, distance to largest power of $2$ less than or equal to $n$; write $n$ in binary, change the first digit to zero, and convert back to decimal.
Let $g(n)$ be A007814, the ...
- 4,938
106
votes
5
answers
10k
views
integral of a "sin-omial" coefficients=binomial
I find the following averaged-integral amusing and intriguing, to say the least. Is there any proof?
For any pair of integers $n\geq k\geq0$, we have
$$\frac1{\pi}\int_0^{\pi}\frac{\sin^n(x)}{\...
- 43.2k
67
votes
6
answers
7k
views
How to recognise that the polynomial method might work
A couple of days ago I was at a nice seminar given by Christian Reiher, during which he told us about a short proof of the following special case of a theorem of Olson.
Theorem. Let $(a_1,b_1),\dots,(...
- 29k
37
votes
2
answers
3k
views
A question on maps from $\mathbb{Z}/p\mathbb{Z}$ to itself
Let $p\geq 3$ be a prime number, and let $u:\mathbb{Z}/p\mathbb{Z}\to \mathbb{Z}/p\mathbb{Z}$ be a map such that, for all $l\in \mathbb{Z}/p\mathbb{Z}$,$l\neq 0$, the map $k\mapsto u(k+l)-u(k)$ is a ...
- 1,730
28
votes
5
answers
9k
views
Erdos Conjecture on arithmetic progressions
Introduction:
Let A be a subset of the naturals such that $\sum_{n\in A}\frac{1}{n}=\infty$. The Erdos Conjecture states that A must have arithmetic progressions of arbitrary length.
Question:
I ...
- 4,952
26
votes
2
answers
2k
views
Singmaster's conjecture
Has any work been done on Singmaster's conjecture since Singmaster's work?
The conjecture says there is a finite upper bound on how many times a number other than 1 can occur as a binomial ...
23
votes
4
answers
3k
views
Exhibit an explicit bijection between irreducible polynomials over finite fields and Lyndon words.
Let $q$ be a power of a prime. It's well-known that the function $B(n, q) = \frac{1}{n} \sum_{d | n} \mu \left( \frac{n}{d} \right) q^d$ counts both the number of irreducible polynomials of degree $n$...
- 118k
19
votes
3
answers
1k
views
The sum of integers being a bijection
What are the pairs $(P,Q)$ of subsets of $\mathbb N$ for which the map
\begin{eqnarray*}
P\times Q & \rightarrow & {\mathbb N} \\\\
(p,q) & \mapsto & p+q
\end{eqnarray*}
is a bijection ...
- 52.3k
16
votes
0
answers
454
views
A Product Related to Unrestricted Partitions
Start with the product for unrestricted partitions:
$(1+x+x^2+...)(1+x^2+x^4+...)(1+x^3+x^6+...)...$
Now replace some of the plus signs with minus signs and expand the product into a series. Is it ...
- 2,143
16
votes
4
answers
10k
views
Exact formulas for the partition function?
I am curious, what kind of exact formulas exist for the partition function $p(n)$?
I seem to remember an exact formula along the lines $p(n) = \sum_k f(n, k)$, where $f(n, k)$ was some extremely ...
- 7,337
12
votes
0
answers
558
views
Possible orders of products of 2 involutions which interchange disjoint residue classes of the integers
Definition / Question
Definition: Let $r(m)$ denote the residue class $r+m\mathbb{Z}$, where
$0 \leq r < m$.
Given disjoint residue classes $r_1(m_1)$ and $r_2(m_2)$, let the class transposition
$...
- 19.6k
11
votes
1
answer
772
views
2-adic Logarithm and Resistance of n-dimensional Cube
Resistance across opposite vertices of n-dimensional cube with each edge at one ohm resistance is
$$R_n=\sum_{k=0}^{n-1}\frac1{(n-k){n\choose k}}=\frac1n\sum_{k=0}^{n-1}\frac1{{n-1\choose k}}.$$
The ...
- 12.3k
7
votes
2
answers
428
views
Limit associated with complementary sequences
Define $A=(a_n)$ and $B=(b_n)$ as follows: $a_0=1$, $a_1=2$, $b_0=3$, $b_1=4$, and $$a_n=a_0b_{n-1}+a_1b_{n-2}$$ for $n \geq 2$, where $A$ and $B$ are increasing and every positive integer occurs ...
- 3,443
4
votes
2
answers
2k
views
Estimate on sum of squares of multinomial coefficients
I am interested in approximating the sum of the squares of the multinomial coefficients, i.e.
$a_\ell^p := \sum_{k_0+\ldots+k_p = \ell} (\frac{\ell!}{k_0! \ldots k_p!})^2$
or more general,
$a_\...
- 145
3
votes
1
answer
439
views
An identity for polynomials over partitions
Given an integer partition $\lambda=(\lambda_1,\dots,\lambda_{\ell(\lambda)})$ of $n$ where $\ell(\lambda)$ is the length of $\lambda$, associate its conjugate partition $\lambda'$. Denote by $\lambda'...
- 43.2k
3
votes
0
answers
193
views
A conjectural lower bound for $|\{\sum_{k=1}^nka_k:\ a_1,\ldots,a_n\ \text{are distinct elements of }\ A\}|$
Motivated by Question 315568 of mine, I'm interested in the set
$$S(n):=\bigg\{\sum_{k=1}^n k\pi(k):\ \pi\in S_n\bigg\}.$$
It is easy to see that
$$S(1)=\{1\},\ S(2)=\{4,5\}\ \text{and}\ S(3)=\{10,...
- 15.6k
1
vote
1
answer
225
views
Will this greedy algorithm always work?
Let p(n) be the number of unrestricted partitions of n. p(0) is taken to be 1.
Let set 1 and set 2 be two empty sets.
Here's an algorithm. Put p(n) into set 1. On each successive step, k=1,2,3,..., ...
- 2,143
113
votes
7
answers
8k
views
Is the set $ AA+A $ always at least as large as $ A+A $?
Let $A$ be a finite set of real numbers. Is it always the case that $|AA+A| \geq |A+A|$?
My first instinct is that this is obviously true, and there is a one-line proof which I am foolishly ...
- 1,498
57
votes
0
answers
3k
views
On the first sequence without triple in arithmetic progression
In this Numberphile video (from 3:36 to 7:41), Neil Sloane explains an amazing sequence:
It is the lexicographically first among the sequences of positive integers without triple in arithmetic ...
39
votes
5
answers
6k
views
Factorials in Pascal's triangle
I asked this question of Keith Conrad, and he suggested that I try posting here. One of my students observed that the only instances of factorials in the interior of Pascal's triangle are $\binom{4}{...
- 391
35
votes
6
answers
2k
views
Placing numbers $1,2,\ldots,n^3$ in a cube so that numbers of any two adjacent unit subcube are coprime
This is a question first I asked in SE but since there was no suggestion or solution, I decide to put it here.
Consider an $n\times n \times n$ Cube containing $n^3$ unit cubes. Is it possible to ...
- 353
26
votes
2
answers
1k
views
Partitions to different parts not exceeding $n$
Consider the polynomial $(1+x)(1+x^2)\dots (1+x^n)=1+x+\dots+x^{n(n+1)/2}$, which enumerates subj. How to prove that it's coefficients increase up to $x^{n(n+1)/4}$ (and hence decrease after this)? Or ...
- 109k
23
votes
3
answers
3k
views
How many different numbers can be obtained as product of first $n$ natural numbers?
Let m and n be natural numbers, and consider the set of all possible products of m (not necessarily distinct) elements from the set $\{1,2,\ldots,n\}$, that is consider the set
$\{1^{a_1} \cdot 2^{...
- 323
18
votes
1
answer
1k
views
When is $(q^k-1)/(q-1)$ a perfect square?
Let $q$ be a prime power and $k>1$ a positive integer. For what values of $k$ and $q$ is the number $(q^k-1)/(q-1)$ a perfect square, that is the square of another integer? Is the number of such ...
- 533
18
votes
1
answer
2k
views
A geometric series equalling a power of an integer
The following problem cropped up whilst considering generalised quadrangles with a product structure, and it boils down to a simple number theoretic problem. Let $s$ be an integer greater than 2 and ...
- 623
17
votes
3
answers
2k
views
When is the number of areas obtained by cutting a circle with $n$ chords a power of $2$?
Also posted on the Math Stackexchange: When is the number of areas obtained by cutting a circle with $n$ chords a power of $2$?
Introduction
Recently, a friend told me about the following ...
- 1,326
16
votes
2
answers
700
views
A tantalizing Gamma quotient to challenge the Rohrlich-Lang Conjecture
The Rohrlich-Lang Conjecture for polynomial relations in Gamma values predicts that all polynomial relations between Gamma values over $\mathbb Q$ come from the functional equations satisfied by the ...
- 13.4k
14
votes
7
answers
3k
views
A special type of generating function for Fibonacci
Notation. Let $[x^n]G(x)$ be the coefficient of $x^n$ in the Taylor series of $G(x)$.
Consider the sequence of central binomial coefficients $\binom{2n}n$. Then there two ways to recover them:
$$\...
- 43.2k
14
votes
2
answers
1k
views
$n!$ divides a product: Part I
Question. The following is always an integer. Is it not?
$$\frac{(2^n-1)(2^n-2)(2^n-4)(2^n-8)\cdots(2^n-2^{n-1})}{n!}.$$
John Shareshian has supplied a cute proof. I'm encouraged to ask:
...
- 43.2k
14
votes
1
answer
512
views
divisibility independence
The following is a standard combinatorics question:
Any set of $n+1$ numbers from $1, \dotsc, 2n$ contains a pair of
numbers $a, b$ where $a \left| b \right.$
The argument is by pigeonhole ...
- 96.4k
13
votes
2
answers
697
views
in search of a transformation between determinants
Motivated by this MO question. Consider the two matrices $A_n$ and $B_n$ with entries $\binom{2j}i$ and $\binom{n+1}{2j-i}$, respectively; for $1\leq i, \,j\leq n$.
I can show $\det A_n=\det B_n=2^{\...
- 43.2k
13
votes
7
answers
4k
views
Status of the Hadamard Circulant conjecture
The following feels like a community wiki question, so I do it here:
Recently we have heard of a new proof of the Circulant Hadamard conjecture of Ryser
(a long standing difficult conjecture):
...
11
votes
1
answer
330
views
a Hankel matrix of involution numbers
Let $I_k$ denote the enumeration of involutions among permutations in $\mathfrak{S}_k$. I always enjoy these numbers. Of course, here is yet another cute experimental finding for which I ask validity. ...
- 43.2k
11
votes
3
answers
1k
views
A problem on a specific integer partition
Let $n$ be a positive integer, we consider partitions of the following form :
$$n = d^{2}_{1} + d^{2}_{2} + ... + d^{2}_{r}$$ such that :
$d_{i}\vert n$
$1=d_{1}<d_{2} \le d_{3} \le ... \le d_{r}$...
9
votes
3
answers
629
views
Can select many disjoint pairs with prescribed differences from Z_n?
Suppose we have a sequence $d_i<2n$ for $i=1,\ldots,n$ and we want to select $n$ disjoint pairs from $Z_p$, $x_i,y_i$ such that $x_i-y_i=d_i \mod p$. Then how big $p$ has to be compared to $n$ to ...
- 18.8k
9
votes
2
answers
388
views
Every possible number of partitions by restricting parts?
Write $p(n)$ for the number of integer partitions of $n$. For $S \subseteq \{1, \ldots, n\}$, let $p_S(n)$ be the number of partitions of $n$ with all parts in $S$. So $p(n) = p_{\{1,\ldots,n\}}(n)$....
- 4,589