All Questions
Tagged with co.combinatorics nt.number-theory
1,338 questions
1
vote
0
answers
110
views
Generalized identity with Stirling numbers of the second kind and falling factorials
It is known that Striling numbers of the second kind satisfy the relation
$$
\sum\limits_{k=0}^{n}{n \brace k}(x)_k = x^n.
$$
where $(x)_n$ is the falling factorials such that
$$
(x)_n = x(x-1)(x-2)\...
- 175
37
votes
3
answers
2k
views
How to prove the identity $L(2,(\frac{\cdot}3))=\frac2{15}\sum\limits_{k=1}^\infty\frac{48^k}{k(2k-1)\binom{4k}{2k}\binom{2k}k}$?
For the Dirichlet character $\chi(a)=(\frac a3)$ (which is the Legendre symbol), we have
$$L(2,\chi)=\sum_{n=1}^\infty\frac{(\frac n3)}{n^2}=0.781302412896486296867187429624\ldots.$$
Note that this ...
- 215
2
votes
0
answers
110
views
+50
How to apply Pohlig Hellman using a very limited set of auxiliary inputs in that case?
So I was reading about Talotti, Paier, and Miculan - ECC’s Achilles’ Heel: Unveiling Weak Keys in Standardized Curves. The underlying idea is to lift the discrete logarithm problem to $\mathrm{prime}−...
- 87
21
votes
1
answer
738
views
Does $A-A=\mathbb Q$ hold for $A=\{x^4+y^4:\ x,y\in\mathbb Q\}$?
Let $A=\{x^4+y^4:\ x,y\in\mathbb Q\}$. Then
$$A-A:=\{a-b:\ a,b\in A\}=\{u^4+v^4-x^4-y^4:\ u,v,x,y\in\mathbb Q\}.$$
Motivated by Question 415482, here I ask the following question.
Question. Is it true ...
- 1,567
0
votes
1
answer
187
views
Matching bins up to shuffling II
Suppose a school purchases a set $\mathcal{S}$ of balls, say
$$\displaystyle \mathcal{S} = \{b_1, b_2, \cdots, b_n\}$$
with $n$ very large. The balls $b_j$ are pairwise distinct and have distinct ...
CommunityBot
- 1
2
votes
2
answers
496
views
Nested De Bruijn sequences
A binary De Bruijn sequence of index $n$ is a circular sequence $S=a_1 a_2 \dots a_{2^n},$ with $a_i \in \{0,1\},$ and such that each of the $2^n$ binary $n$-uples occurs exactly once in $S.$
Is ...
- 63.9k
0
votes
0
answers
137
views
State of the art on attempts to solve the elliptic curve discrete logarithm problem through transfering the problem to a weaker curve
Let an elliptic curve $E$, and 2 points on such curve $P$ and $O$ the methods I’m talking about consist in creating a weaker elliptic curve $F$ and mapping $P$ and $O$ to $F$ while successfully ...
- 87
1
vote
1
answer
186
views
Existence of Finite Amicable Groups
I'm interested in exploring the concept of "amicable groups" as follows:
Definition. Two finite groups $G$ and $H$ are called amicable groups if:
$G$ is the direct sum of proper subgroups ...
- 6,357
0
votes
1
answer
128
views
Closed form for $\sum\limits_{k=0}^{n} [\operatorname{wt}(k) = m]$ where $\operatorname{wt}(n)$ is the binary weight of $n$
Let $\operatorname{wt}(n)$ be A000120 (i.e., number of $1$'s in binary expansion of $n$).
Let $a(n,m)$ be the family of integer sequences such that
$$
a(n,m) = \sum\limits_{k=0}^{n} [\operatorname{wt}(...
- 7,226
8
votes
1
answer
668
views
Infinite series and sum of two squares
Consider the following infinite sequence $a(n)$ generated by
$$\sum_{n\geq0} a(n)q^n
=\frac{\sum_{k\geq0}F(2k+1)q^{\binom{k+1}2}}{\sum_{k\geq0} q^{\binom{k+1}2}}$$
where the $F(2k+1)$ are the odd ...
- 79.9k
0
votes
0
answers
85
views
How to prove the following equation (involving multiple binomial coefficients sum)?
I encountered the equation below, encountered a problem that has been bothering me for a long time
Does anyone have an idea how to prove it? I would be extremely grateful to you if you come up with an ...
- 41
3
votes
1
answer
192
views
Density of Pisot polynomials
Recall that a Pisot polynomial $P=x^n+ a_{n-1}x^{n-1}\ldots a_1$ has integer coefficients, a real root $x_1>1$ and all other roots $|x_i|<1$ for $1\leq i \leq n$. One key result is that $\{(...
- 1,043
4
votes
0
answers
81
views
Classification of nilpotent orbits over local fields (for type ABCD via partitions )
Let $\mathfrak g$ be a simple Lie algebra over a char $0$ local field $F$ (e.g. $F=\mathbb R$ or $F=\mathbb Q_p$) with its adjoint group $G$. Let $\mathcal N \subseteq \mathfrak g$ be its nilpotent ...
- 6,622
0
votes
0
answers
78
views
Solution modulo $9$ of certain linear equation implies triviality modulo $3$
Question: Let $k \geq 2$ and $r \geq 4$ be two natural numbers. We are given eight integers $\nu_{ij} \geq 0$ for every $1 \leq i \leq k$ and $1 \leq j \leq r$ such that the following two conditions ...
- 119
0
votes
1
answer
168
views
Partial sums of binomial coefficients and related family of polynomials
Let $a(n)$ be A302117. Here
$$
a(n) = 4(n-1)a(n-1) - \frac{1}{3}\prod\limits_{k=0}^{n-1}(2k-3), \\
a(0) = 0.
$$
Let
$$
T(n,k) = \sum\limits_{i=0}^{k} \binom{n}{i}.
$$
Let $P_n(z)$ be the family of ...
- 34.3k
1
vote
0
answers
57
views
Step back step forward algorithm for A108442
Let $a(n)$ be A108442. Here generating function is $\frac{1}{1-zA(z)}$ where
$$
A(z) = 1 + z(A(z))^2 + z(A(z))^3.
$$
Also
$$
a(n) = \sum\limits_{k=1}^{n}\frac{k}{2n-k}\sum\limits_{i=0}^{n-k} \binom{2n-...
- 4,928
2
votes
0
answers
182
views
Algorithm for $\frac{1}{1-x} = \sum\limits_{n=0}^{\infty}a(n)x^n\prod\limits_{k=1}^{n}\frac{1-kx}{1+kx}$
Let $a(n)$ be A208832. Here
$$
\frac{1}{1-x} = \sum\limits_{n=0}^{\infty}a(n)x^n\prod\limits_{k=1}^{n}\frac{1-kx}{1+kx}.
$$
Start with vector $\nu$ of fixed length $m$ with elements $\nu_i = 1$ (that ...
- 175
1
vote
0
answers
161
views
Efficient algorithm for A217061
Let $a(n)$ be A217061. Here
$$
a(n) = \sum\limits_{m=1}^{n}\frac{1}{(m-1)!}\sum\limits_{k=0}^{n-m}(n+k-1)!\sum\limits_{j=0}^{k}\frac{1}{(k-j)!}\sum\limits_{\ell=0}^{j}\frac{2^{\ell-j}(-1)^{\ell+j}s(n-...
- 4,928
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, ...
- 109k
2
votes
0
answers
67
views
$R$-recursion for A006351
Let $a(n)$ be A006351 (i.e., number of series-parallel networks with n labeled edges. Also called yoke-chains by Cayley and MacMahon). Here exponential generating function is $A(x)$ such that $B(x) = ...
- 175
3
votes
1
answer
855
views
Infinite dimensional lattice for integers and the Riemann hypothesis?
It is known that for each finite set of primes $p$ we have: $\log(p)$ are linear independent over the rational numbers.
We have $\log(ab) = \log(a)+\log(b)$ and $\log(n) = \sum_{p |n}v_p(n) \log(p)$.
...
CommunityBot
- 1
2
votes
0
answers
59
views
$R$-recursion for A338193
Let $a(n)$ be A338193. Here generating function is $A(x)$ such that
$$
A(x) = 1 + \int\frac{\left(\frac{x}{A(x)}\right)'}{\left(\frac{x}{(A(x))^2}\right)'} \, dx.
$$
Let
$$
R(n, q) = \begin{cases}
1 &...
- 4,928
10
votes
0
answers
287
views
Coefficients of polynomials vs trigonometric product
Let's consider the family of sequences of coefficients in the expansion
$$\prod_{i=0}^{n-1}(1+x^{3^i}+x^{3^{i+1}})=\sum_{k\geq0}a_n(k)\, x^k.$$
Remark. Evidently, the RHS is a finite sum.
Here is a ...
- 43.2k
2
votes
1
answer
221
views
A question on signed Stirling numbers of the first kind
Let $(x)_0=1$ and $(x)_n=x(x-1)\cdots(x-n+1)$ for $n=1,2,3,\ldots$. The signed Stirling numbers of the first kind, $s(n,k)$ with $n\ge k\ge0$, are defined by
$$(x)_n=\sum_{k=0}^ns(n,k)x^k.$$
Question. ...
- 7,226
2
votes
1
answer
431
views
Shadows of partitions of lcm
$\DeclareMathOperator\lcm{lcm}$Fix an integer $n\geq1$. Denote the least common multiple $L_n=\lcm(1,2,\dots,n)$.
QUESTION. Is the following true? For each integer partition $\lambda=(\lambda_1,\...
- 23.7k
1
vote
1
answer
92
views
Equivalence of sequences related to A033264
Let $a(n)$ be A033264 (i.e., number of blocks of $\{1,0\}$ in the binary expansion of $n$). Here
$$
a(4n) = a(4n+1) = a(2n), \\
a(4n+2) = a(n)+1, \\
a(4n+3) = a(n), \\
a(0) = 0.
$$
Let
$$
\ell(n) = \...
- 60.5k
7
votes
2
answers
603
views
Density version of the Erdős-Graham conjecture
In 2003 E. S. Croot [Ann. of Math. 157(2)(2003), 545-556] proved the Erdős-Graham Conjecture which states that if $\{2,3,\ldots\}$ is partitioned into finitely many subsets then one of the subsets ...
- 105k
23
votes
4
answers
2k
views
Identity for an infinite product
Here is an experimental "result" exhibiting the difference of two (formal) infinite products that "almost factorizes".
QUESTION. Is this true?
$$\prod_{n\geq1}(1+x^{2n-1})^{24} - \...
- 105k
1
vote
0
answers
89
views
Test for odd prime triples in a $2p-1$ progression
Let $a(n)$ be A057326 (i.e., first member of a prime triple in a $2p-1$ progression).
Let $b(n) = B$ after $n-1$ iterations where we start with $A=n, B=1$ and for $i$ from $1$ to $n-1$ simultaneously ...
- 4,928
5
votes
0
answers
185
views
Gaps in sumsets and difference sets
a) Let $S\subset \{1,2,\dotsc,N\}$ be a fairly thick set (with at least $N^{1-\epsilon}$ elements, say). Suppose that the intersection of, say,
$$3 S - 3 S = \{a_1+a_2+a_3-(a_4+a_5+a_6): a_1,\dotsc,...
CommunityBot
- 1
2
votes
0
answers
113
views
Numbers of positive terms in polynomials equal A069999
Let $a(n)$ be A069999 (i.e., number of possible dimensions for commutators of $n \times n$ matrices; it is independent of the field). OEIS states that no generating function is known.
Let $P(n,k)$ be ...
- 4,928
1
vote
1
answer
177
views
Algorithm for A127782
Let $a(n)$ be A127782 (i.e., an integer sequence with generating function $A(x)$ such that $A(x)=1+xA(x+x^2)$). Here
$$
a(n) = \sum\limits_{k=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor} \binom{n-k-1}{...
- 34.3k
1
vote
0
answers
82
views
Generating functions related to generating function of Catalan numbers
Let $C_n$ be A000108 (i.e., Catalan numbers). Here generating function is $C(x)$ such that
$$
C(x) = \frac{1-\sqrt{1-4x}}{2x}.
$$
Let $a(n)$ be an integer sequence with generating function $A(x)$ such ...
- 4,928
0
votes
0
answers
84
views
Generate two bijectively mapped sets subject to certain conditions on choice of elements
$\DeclareMathOperator\setsum{setsum}$Let there be two sets of numbers of size $n$ each given by $S_1, S_2$.
Let there be a one-to-one onto mapping $f: S_1 \rightarrow S_2$.
Let us denote the sum of ...
2
votes
1
answer
226
views
Expanders except for commutativity?
What would you call a graph that is an expander except for commutativity, in the following sense?
Say that, from every vertex, you have $d$ edges ($d$ large) labelled $x_1,\dotsc, x_d$. Say that your ...
- 148k
0
votes
0
answers
64
views
Algorithm and equivalent recursion for A258173 (related to Dyck paths)
Let $a(n)$ be A258173 i.e. sum over all Dyck paths of semilength $n$ of products over all peaks $p$ of $y_p$, where $y_p$ is the $y$-coordinate of peak $p$.
A Dyck path of semilength $n$ is a $(x,y)$-...
- 4,928
0
votes
0
answers
60
views
Algorithm for $q$-Bell numbers
Let $T(n,k)$ be A126347 (i.e., triangle, read by rows, with row polynomials $B(n, q)$). Here
$$
B(n, q) = \sum\limits_{k=0}^{n-1}\binom{n-1}{k}B(k, q)q^k, \\
B(0, q) = 1.
$$
Start with vector $\nu$ of ...
- 4,928
7
votes
0
answers
208
views
How biased is $(x_i x_j)_{i,j}$, $x_i\in \mathbb{F}_2$?
Let $N = \frac{n (n-1)}{2}$. Let $V$ be the $N$-dimensional vector space over $\mathbb{F}_2$ consisting of tuples $(x_{(i,j)})_{1\leq i <j \leq n}$, $x_{(i,j)}\in \mathbb{F}_2$. Let $S$ be the set ...
- 20.2k
-2
votes
1
answer
298
views
Is polynomial not bijective, on this finited field?
Let $(a,b,c) \in \mathbb F_p,p=2^{127}-1$ and $P(x)=x^{16}+ax^{11}+bx^{5}+c$.
Is it true that $P(x)$ not bijective on $\mathbb F_p$?
I have asked this question here (*), but no answer.
(*) : https://...
- 109k
3
votes
2
answers
257
views
On $\det[x+(\frac{i\pm j}p)]_{1\le i,j\le(p-1)/2}$ for primes $p\equiv 3\pmod 4$
I have made the followng conjecture on the basis of my computation.
Conjecture. For any prime $p\equiv3\pmod4$ with $p>3$, we have
$$\det\left[x+\left(\frac{i+j}p\right)\right]_{1\le i,j\le(p-1)/2}...
0
votes
1
answer
141
views
Property of composite numbers
Let $a(n)$ be the sequence of composite numbers (starting from $4$). Let
$$b(n)=a(n-1)a(n-2) \operatorname{mod} a(n)$$
Obviously, $b(1)=b(2)=0$.
I conjecture that with the only exception for the $b(3)=...
6
votes
0
answers
171
views
An inequality involving integer partitions
For integers $n\ge k\ge0$, let $p(n,k)$ denote the number of ways to write $n$ as a sum of $k$ positive integers (repetition allowed). For example, $p(6,3)=3$ since
$$6=1+1+4=1+2+3=2+2+2.$$
QUESTION. ...
- 15.6k
9
votes
0
answers
258
views
On a continued fraction and vector $\nu$ of length $n$
Please note that this question has been completely reworked in order not to overload it with unnecessary and useless information.
Let $f(n)$ be an arbitrary function with integer values.
Let $a(n)$ ...
- 4,928
2
votes
0
answers
51
views
Recursion for A129179 similar to recursion for Pascal's triangle
Let $T(n,k)$ be A129179 (i.e., triangle read by rows: $T(n, k)$ is the number of Schroeder paths of semilength $n$ such that the area between the $x$-axis and the path is $k$ ($n \geqslant 0, 0 \...
- 4,928
9
votes
1
answer
1k
views
0
votes
0
answers
169
views
On a property of prime numbers
Let $p_i$ be the $i^{\rm th}$ prime number (i.e. $p_1=2,\ p_2=3,\ p_3=5,\cdots$)
What is the function of number of combinations of $c_1,\cdots,c_n$ in terms of $n$ such that,
$$\sum_{i=1}^{n}c_ip_i\ =\...
- 4,746
2
votes
0
answers
121
views
Sequences of 1s in binary expression of powers of 3
Some properties of the binary expressions of $3^n$ are known, e.g. here was proven that the only periodic expression happens at $n=1$, or here it is shown that the number of $1$s in the expression ...
- 205
3
votes
0
answers
213
views
A family of polynomials related to integer partitions
For a positive integer $n$, let $p(n)$ be the number of partitions of $n$.
For $1\le k\le n$, let $p(n,k)$ denote the number of partitions of $n$ having exactly $k$ terms; in other words, $p(n,k)$ is ...
- 15.6k
0
votes
0
answers
121
views
Closed form of coefficients of a finite field polynomial
I want to find a valid polynomial for a finite field $\mathbb{Z}_p[x]_{f(x)}$ with $d=deg(f(x))$. For this definition to hold, it can be deduced that $p$ must be prime and the polynomial $f(x)$ ...
- 47
2
votes
0
answers
61
views
Algorithm for main diagonal of integer coefficients associated with Schroeder numbers
Let $T_q(n, k)$ be an integer table such that
$$T_q(n, k) = \begin{cases}
1 & \textrm{if } n = 0 \vee k = 0 \\
qT_q(n-1, n-1) + T_q(n, n-1) & \textrm{if } n = k > 0 \\
T_q(n, k-1) + T_q(n-1,...
- 7,226