All Questions
52 questions
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
21
votes
1
answer
1k
views
Permutations $\pi\in S_n$ with $\sum_{k=1}^n\frac1{k+\pi(k)}=1$
Let $S_n$ be the symmetric group of all the permutations of $\{1,\ldots,n\}$.
Motivated by Question 315568 (http://mathoverflow.net/questions/315568), here I pose the following question.
QUESTION: ...
- 15.6k
19
votes
1
answer
3k
views
A mysterious connection between primes and squares
Motivated by two previous questions of mine (cf. Primes arising from permutations and Primes arising from permutations (II)), here I ask a curious question which connects primes with squares.
...
- 15.6k
18
votes
2
answers
992
views
A conjecture harmonic numbers
I will outlay a few observations applying to the harmonic numbers that may be interesting to prove (if it hasn't already been proven).
From the Online Encyclopedia of Positive Integers we have:
$a(n)$ ...
- 181
12
votes
0
answers
643
views
Wilf's conjecture: complementary Bell numbers
The complementary Bell numbers or Uppuluri–Carpenter numbers, denoted $\tilde{B}_n$, can be delivered by
$$G(x):=\sum_{n\geq0}\tilde{B}_n\frac{x^n}{n!}=e^{1-e^x}.$$
Definition. Fix an integer $m\geq0$....
- 43.2k
10
votes
1
answer
694
views
Prime numbers from permutation
Let $P(n)$ of a sequence $s(1),s(2),s(3),...$ be obtained by leaving $s(1),...,s(n)$ fixed and reverse-cyclically permuting every $n$ consecutive terms thereafter; apply $P(2)$ to $1,2,3,...$ to get $...
- 4,938
8
votes
2
answers
2k
views
Distribution of distances in permutations
Let's consider all possible permutations of N numbers. Suppose for each permutation we calculate the sum of absolute differences between consecutive elements. Thus, for (1,2,3) one would have abs(1-2)+...
- 99
8
votes
1
answer
200
views
factorization of polynomials wrt the major index stat
Let $\mathfrak{S}_n$ be the permutation group on $\{1,\dots,n\}$. Given $\pi=\pi_1\pi_2\dots\pi_n\in\mathfrak{S}_n$, its major index statistic is denoted maj$(\pi)$. Define the polynomials
$$Q_{n,k}(x)...
- 43.2k
7
votes
1
answer
531
views
Primes arising from permutations
Recently, Paul Bradley proved in arXiv:1809.01012 that for any positive integer $n$ there is a permutation $\pi_n$ of $\{1,\ldots,n\}$ such that $k+\pi_n(k)$ is prime for every $k=1,\ldots,n$ (cf. ...
- 15.6k
7
votes
2
answers
1k
views
Numbers with all N-digit prefixes divisible by N
In base 10, the number 3816547290 contains every digit exactly once. When I take the first N digits, that substring is divisible by N. For example, 381 is divisible by 3, 38165 is divisible by 5, etc. ...
- 173
6
votes
2
answers
366
views
Provoking involutions further
Let $\mathfrak{S}_n$ denote the permutation group, and $I_0(n)=\sum_{j\geq0}\binom{n}{2j}\frac{(2j)!}{2^jj!}$ stand for involutions see A000085 for more interpretations. There is also these numbers $...
- 43.2k
6
votes
2
answers
395
views
On the parity of $|\{(j,k):\ 1\le j<k\le\frac{p-1}2\ \&\ \ j(j+1)\ \text{mod}\ p\,>\,k(k+1)\ \text{mod}\ p\}|$ with $p$ prime
Let $p=2n+1$ be an odd prime, and let $a_1<\ldots<a_{n}$ be all the quadratic residues mod $p$ among $1,\ldots,p-1$. For $a\in\mathbb Z$ let $\{a\}_p$ be the least nonnegative residue of $a$ ...
- 15.6k
5
votes
1
answer
270
views
Counting the number of permutations of $(1,\ldots,i,\ldots,j,\ldots,m)$, where $i < j$ and number of inversions is $k$
How can I prove the following:
$d^{ij}(m,k) > d^{ji}(m,k)$ for all $k < \frac{1}{2}\binom{m}{2},$
where $d^{ij}(m,k)$ denotes the number of permutations of $(1,\ldots,i,\ldots,j,\ldots,m)$ ...
- 85
5
votes
0
answers
175
views
A close cousin of involutions?
If $\mathfrak{S}_n$ denotes the permutation group on $n$ letters, then $Inv(n)=\{\pi: \pi^2=1\}\subset\mathfrak{S}_n$ is the set of involutions or
self-inverse permutations. The latter is enumerated ...
- 43.2k
4
votes
1
answer
330
views
Combinatorial Technique Needed
The following problem is likely too special for MO.
However I have no clue how to deal with it, so I'll just try. Nevertheless
it is a combinatorial problem and a discussion about general methods
in ...
- 2,074
4
votes
2
answers
210
views
permutations rescuing chain/product rules?
Let $\mathfrak{S}_n$ be the permutation group on $[n]$. Denote the cardinality of $\{\pi\in\mathfrak{S}_n: \pi^2=id\}$, the set of involutions, by $I(n)$.
It is well-known that these numbers have the ...
- 43.2k
4
votes
1
answer
139
views
A close reative of "Inflated" Eulerian polynomials
I came across this post Coefficients of the Inflated Eulerian Polynomial by AULI-GRAHAM-SAVAGE. In particular, the polynomials related to descents interested me
$$P_n(x)=\sum_{\pi\in\mathfrak{S}_n}x^{...
- 43.2k
4
votes
0
answers
167
views
Binary iterations, Fibonacci numbers and permutation of natural numbers
Let $\operatorname{wt}(n)$ be A000120, i.e. the number of $1$'s in binary expansion of $n$ (or the binary weight of $n$).
Also let's consider
$$\ell(n)=\left\lfloor\log_{2} n\right\rfloor$$
and
$$T(n,...
- 4,938
4
votes
0
answers
160
views
Is there a permutation $\pi\in S_n$ with $\sum\limits_{0<k<n}\frac1{\pi(k)^2-\pi(k+1)^2}=0$ for each $n>7$?
Let $S_n$ be the symmetric group of all permutations of $\{1,\ldots,n\}$.
QUESTION: Is it true that for each $n=8,9,\ldots$ we have
$$\sum_{0<k<n}\frac1{\pi(k)^2-\pi(k+1)^2}=0\tag{$*$}$$
for ...
- 15.6k
3
votes
1
answer
226
views
Sums over permutations relates to permutations?
Consider the permutation group $\mathfrak{S}_n$ on $n$ letters $\{1,2,\dots,n\}$. Let $\iota=(1,2,3,\dots,n)\in\mathfrak{S}_n$ be the identity permutation in a $1$-line notation. Given $\pi, \rho\in\...
- 43.2k
3
votes
4
answers
654
views
A generalization of Landau's function
For a given $n > 0$ Landau's function is defined as $$g(n) := \max\{ \operatorname{lcm}(n_1, \ldots, n_k) \mid n = n_1 + \ldots + n_k \mbox{ for some $k$}\},$$
the least common multiple of all ...
- 798
3
votes
0
answers
151
views
Combinatorial interpretation of inverse modulo $2$ binomial transform of A284005
My question is related to the following:
Sum with products turned into subsequences
We have an identity
$$a(n, -1) = \sum\limits_{j=0}^{2^{\operatorname{wt}(n)}-1}(-1)^{\operatorname{wt}(n)-\...
- 4,938
3
votes
0
answers
282
views
A new combinatorial problem for finite groups
In a recent preprint arXiv:1811.10503, I proved that if $a_1,\ldots,a_n$ are distinct elements of a torsion-free additive abelian group $G$, then there is a permutation $\pi\in S_n$ such that all ...
- 15.6k
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
3
votes
0
answers
131
views
Chen primes and permutations
In 1973 the Chinese mathematician J.-R. Chen proved that there are infinitely many primes $p$ such that $p+2$ is a product of at most two primes. Nowadays such primes $p$ are called Chen primes.
For $...
- 15.6k
3
votes
0
answers
293
views
Primes arising from permutations (II)
In Question 315259 (cf. Primes arising from permutations) I asked a question on primes arising from permutations which looks quite challenging.
Here I pose a new question in this direction which does ...
- 15.6k
2
votes
1
answer
176
views
special values of symmetric functions at powers of $\frac1j$
Let $e_n(x_1,x_2,x_3,\dots)$ denote the $n$-th elementary symmetric function in the infinite variables $x_1,x_2,x_3,\dots$.
Let $u$ and $v$ be the roots of $z^2-6z+1=0$.
Question. Let $x_j=\frac1{j^8}...
- 43.2k
2
votes
1
answer
426
views
Conjecture on A057030
Let $P(n)$ of a sequence $s(1),s(2),s(3),...$ be obtained by leaving $s(1),...,s(n-1)$ fixed and reversing every n consecutive terms thereafter; apply $P(2)$ to $1,2,3,...$ to get $PS(2)$, then apply $...
- 4,938
2
votes
2
answers
243
views
$n$-distant permutations more than not
Let $\mathfrak{S}_{2n}$ be the permutation group of the letters $[2n]=\{1,2,\dots,2n\}$. Call a permutation $\pi\in\mathfrak{S}_{2n}$ has an $n$-distant pair if there is some $j\in [2n-1]$ such that $\...
- 43.2k
2
votes
1
answer
364
views
Odd permutations $\tau\in S_n$ with $\sum_{k=1}^nk\tau(k)$ an odd square
For any positive integer $n$, as usual we let $S_n$ be the symmetric group of all the permutations of $\{1,\ldots,n\}$.
QUESTION: Is it true that for each integer $n>3$ there is an odd permutation ...
- 15.6k
2
votes
1
answer
433
views
On triangular numbers modulo primes
Let $p$ be an odd prime. For $a\in\mathbb Z$ let $\{a\}_p$ denote the least nonnegative residue of $a$ modulo $p$. The list $\{1^2\}_p,\ldots,\{((p-1)/2)^2\}_p$ is a permutation of all the quadratic ...
- 15.6k
2
votes
1
answer
172
views
Permutation and its binary analog
Let $f(n)$ be A000045(n), i.e., Fibonacci numbers: $f(n)=f(n-1)+f(n-2)$ for $n>1$ with $f(0)=0$ and $f(1)=1$.
Let $g(n)$ be A072649, i.e., $n$ occurs $f(n)$ times. The sequence begins with
$$1, 2, ...
- 4,938
2
votes
0
answers
91
views
Splitting natural numbers into subsets with sums equal to A066258
Let $F(n)$ be A000045 i.e. Fibonacci numbers. Here
$$
F(n) = F(n-1) + F(n-2), \\
F(0) = 0, F(1) = 1
$$
Let $a(n)$ be A066258 i.e.
$$
a(n) = F(n)^2F(n+1)
$$
Let $b(n)$ be A345253 i.e. maximal ...
- 4,938
2
votes
0
answers
90
views
Unexpected recursion for the A193231 (blue code of $n$)
Let $a(n)$ be A193231, blue code of $n$ i.e. self-inverse permutation of non-negative integers such that $a(n)<2^k$ iff $n<2^k$ and
$$
a(n\operatorname{XOR}k) = a(n) \operatorname{XOR} a(k)
$$
...
- 4,938
2
votes
0
answers
76
views
Uniqueness of the permutation
Let $f(n)$ be A000045(n), i.e., Fibonacci numbers: $f(n)=f(n-1)+f(n-2)$ for $n>1$ with $f(0)=0$ and $f(1)=1$.
Let $g(n)$ be A072649, i.e., $n$ occurs $f(n)$ times. The sequence begins with
$$1, 2, ...
- 4,938
2
votes
0
answers
71
views
Closed form for the number of permutations with a given excedance set
Let $q(n)$ be A007814, i.e., number of trailing zeros in the binary representation of $n$. Here
$$q(2n+1)=0, q(2n)=q(n)+1$$
Let $\operatorname{wt}(n)$ be A000120, i.e., number of $1$'s in binary ...
- 4,938
2
votes
0
answers
192
views
A conjecture on crossing numbers related to primes
For a permutation $\sigma\in S_n$, its crossing number $\text{cr}(\sigma)$ is the number of pairs $\{i,j\}$ with $i,j\in\{1,\ldots,n\}$ such that
$$i<j\le\sigma(i)<\sigma(j)\ \ \text{or}\ \ \...
- 15.6k
1
vote
1
answer
108
views
Property of some permutations of non-negative integers such that $a(n)<2^k$ iff $n<2^k$
Let
$$
\ell(n) = \left\lfloor\log_2 n\right\rfloor
$$
Let
$$
f(n) = 2^{\ell(n)}
$$
Let $q_1(n)$ and $q_2(n)$ be an arbitrary self-inverse permutations of non-negative integers (that is, $q_i(q_i(n)) ...
- 4,938
1
vote
1
answer
182
views
Derangements and unit fractions
Motivated by a recent question of Zhi-Wei Sun and its nice answer by Zhao Shen, here are two related questions.
Let $S_n$ be the group of permutations on $\{1, 2, \ldots, n\}$.
a. For each $n \ge ...
- 4,589
1
vote
0
answers
71
views
Slightly modified program for the A345253 such that specific partial sums equal A066258
Let $F(n)$ be A000045 i.e. Fibonacci numbers. Here
$$
F(n) = F(n-1) + F(n-2), \\
F(0) = 0, F(1) = 1
$$
Let $a(n)$ be A345253 i.e. maximal Fibonacci tree: arrangement of the positive integers as ...
- 4,938
1
vote
0
answers
109
views
Existence of binary permutations with a given property
Let
$$\ell(n)=\left\lfloor\log_2 n\right\rfloor$$
Let
$$f(n)=n-2^{\ell(n)}$$
Let $a(n)$ be a permutation of the nonnegative integers such that $a(0)=0$, $a(n)=n$ if $n$ is a power of $2$ and ...
- 4,938
1
vote
0
answers
81
views
Infiniteness of the pairs of sequences with a given conditions
Let
$$\varphi=\frac{1+\sqrt{5}}{2}$$
Let
$$a_1(n)=\left\lfloor n\varphi \right\rfloor, a_2(n)=n+a_1(n)$$
Let $\operatorname{tr}(n)$ be A007814, i.e., the number of trailing zeros in the binary ...
- 4,938
1
vote
0
answers
85
views
Permutation to get Stolarsky representation from lazy Fibonacci (dual Zeckendorf) representation
Let $a_1(n)$ be A200714, i.e., Stolarsky representation interpreted as binary to decimal integers. The sequence begins with
$$0, 1, 3, 2, 7, 5, 6, 15, 4, 11, 13, 14, 31, 10, 9, 23, 12, 27, 29$$
Let $...
- 4,938
1
vote
0
answers
46
views
Permutation of nonnegative integers applied to the numbers $n$ whose binary expansion does not begin with $11$
Let $\operatorname{wt}(n)$ is A000120, number of $1$'s in binary expansion of $n$ (or the binary weight of $n$) and
$$n=2^{b_1}(1+2^{b_2+1}(1+2^{b_3+1}(1+\cdots(1+2^{b_{\operatorname{wt}(n)-1}+1}(1+2^{...
- 4,938
0
votes
2
answers
295
views
Permutations of squares and finite fields
Let $S_n$ be the symmetric group of all permutations of $\{1,\ldots,n\}$, and let
$$S(n)=\bigg\{\sum_{k=1}^nk^2\pi(k)^2:\ \pi\in S_n\}.$$
Motivated by Question 316142 of mine, here I ask the following ...
- 15.6k
0
votes
1
answer
122
views
Permutation of the natural numbers from operation related to binary expansion of $n$
Let
$$
\ell(n) = \left\lfloor\log_2 n\right\rfloor
$$
Let $T(n,k)$ be a $(k+1)$-th bit from the right side in the binary expansion of $n$. Here
$$
T(n, k) = \left\lfloor\frac{n}{2^k}\right\rfloor \...
- 4,938
0
votes
0
answers
63
views
Pairs of permutations such that $p(n)<2^k$ iff $n<2^k$
Let $p(n)$ be an arbitrary permutation of natural numbers such that $p(n)<2^k$ iff $n<2^k$.
Let $q(n)$ be an inverse permutation of $p(n)$.
Let
$$
\ell(n)=\left\lfloor\log_2 n\right\rfloor
$$
...
- 4,938
0
votes
0
answers
61
views
Stolarsky array and Stolarsky representation
Let $T(n,k)$ be A035506, i.e., Stolarsky array read by antidiagonals. Here we consider that $T(n,k)=0$ for $n<1, k<1$.
Let $a(n)$ be A200714, i.e., Stolarsky representation interpreted as binary ...
- 4,938
0
votes
0
answers
94
views
Permutation using irreducible fractions
Let
$$f(n,k)=n\operatorname{mod} k, g(n,k)=\left\lfloor\frac{n}{k}\right\rfloor$$
Let $T(n,k)$ be A072030, i.e., array read by antidiagonals: $T(n,k)$ = number of steps in simple Euclidean algorithm ...
- 4,938
0
votes
0
answers
266
views
Is there a permutation $\tau\in S_n$ with $\tau(1)^{\tau(2)}+\cdots+\tau(n-1)^{\tau(n)}+\tau(n)^{\tau(1)}$ a square?
Let $n>1$ be an integer, and let $S_n$ be the symmetric group of all the permutatins of $\{1,\ldots,n\}$.
I'm curious whether there is a permutation $\tau\in S_n$ such that
$$\tau(1)^{\tau(2)}+\...
- 15.6k