All Questions
Tagged with co.combinatorics nt.number-theory
1,338 questions
1
vote
0
answers
108
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)\...
- 4,928
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 ...
0
votes
1
answer
127
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}(...
- 4,928
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
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 ...
- 43.2k
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 ...
- 4,928
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 $\{(...
- 680
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
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
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 ...
- 4,928
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
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) = ...
- 4,928
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
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
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
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) = \...
- 4,928
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,\...
- 43.2k
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
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
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,...
- 20.2k
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 ...
- 20.2k
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://...
- 4,074
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}{...
- 4,928
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} - \...
- 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. ...
- 15.6k
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
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
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\ =\...
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
9
votes
1
answer
1k
views
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,...
- 4,928
7
votes
0
answers
166
views
Examples of finitary problems/theorems of high logical complexity? [duplicate]
Generally, number theoretic conjectures which are well-known and easy to explain are either obviously $\Pi^0_1$ or $\Pi^0_2$, which is to say, their truth can be decided by a single membership query ...
- 1,452
1
vote
0
answers
56
views
Find a set satisfying a specific condition
Let $S$ be a set of numbers of size $n$.
Let $M_S$ be the set of all multisets of size $n$ made of elements from $S$, with at least one element repeated. For example, if $S=\{1, 2, 3\}$, then $M_S = \{...
2
votes
0
answers
46
views
On A088352 as an antidiagonal sums of A129179
Let $a(n)$ be A088352. Here $a(n)$ is an integer sequence with generating function $A(x)$ such that
$$
A(x) = \cfrac{1}{1-x-\cfrac{x^2}{1-x^3-\cfrac{x^4}{1-x^5-\cfrac{x^6}{1-x^7-\cfrac{x^8}{\ddots}}}}}...
- 4,928
0
votes
0
answers
54
views
Functional equations with coupled arguments and additive sructure
Let $G$ be a locally compact abelian group and let $f: G \to \mathbb{R}^+$ be a continuous function satisfying the functional equation
$$f(x + \phi(y)) + f(y + \phi(x)) = 1 + f(x+y)$$
for all $x, y \...
2
votes
1
answer
310
views
Generating function for A300483 (related to Chebyshev polynomial of first kind)
Let $a(n)$ be A300483. Here
$$
a(n) = 2\int\limits_{t \geqslant 0}T_n\left(\frac{t+1}{2}\right)\exp(-t)\,dt.
$$
where $T_n(x)$ is $n$-th Chebyshev polynomial of first kind.
Let $b(n)$ be an integer ...
- 4,928
10
votes
1
answer
625
views
Generating function for A261041
Let $a(n)$ be A261041 (i.e., number of partitions of subsets of $\{1,2,\dotsc,n\}$, where consecutive integers are required to be in different parts).
Let $b(n)$ be an integer sequence with generating ...
- 4,928
3
votes
1
answer
178
views
Algorithm for the sum with binomial coefficients and Bell numbers
Let $a(n)$ be A000110 (i.e., Bell or exponential numbers: number of ways to partition a set of $n$ labeled elements).
Let $b(n)$ be A355247 (i.e., expansion of exponential generating function $\exp(2(\...
- 4,928
4
votes
1
answer
112
views
On a number of compositions of $n$ into positive triangular numbers
Let $a(n)$ be A023361 (i.e., number of compositions of $n$ into positive triangular numbers). Here
$$
a(n) = \sum\limits_{i \geqslant 1, \frac{i(i+1)}{2}\leqslant n} a(n-\frac{i(i+1)}{2}), \\
a(0) = 1....
- 4,928
1
vote
0
answers
121
views
Simple algorithm for A107670
Let $T(n, k)$ be A107670 (i.e., matrix square of triangle A107667). Here we define the triangular matrix $P$ by $P(n, k) = \frac{(n+1)^{2(n-k)}}{(n-k)!}$ for $0 \leqslant k \leqslant n$ and the ...
- 4,928
4
votes
1
answer
130
views
Intersecting algorithm for A065601
Let $a(n)$ be A065601 (i.e., number of Dyck paths of length $2n$ with exactly $1$ hill). Here
$$
a(n) = \frac{1}{2(n+1)}((3n-2)a(n-1) + 2(9n-19)a(n-2) + 4(2n-3)a(n-3)), \\
a(0) = a(2) = 0, a(1) = 1.
$$...
- 4,928