On the monotonic sequences

Tiberiu Popoviciu
(original), Mathematical Analysis, monotonicity, paper

Abstract

Authors

T. Popoviciu

Keywords

?

Paper coordinates

T. Popoviciu, Despre şirurile monotone, Pozitiva, 1 (1940), pp. 41-45 (in Romanian).

PDF

https://ictp.acad.ro/wp-content/uploads/2025/11/1940-b-Popoviciu-Pozitiva-Despre-sirurile-monotone.pdf

About this paper

Journal
Publisher Name
DOI
Print ISSN
Online ISSN

[MR0019133]

google scholar link

??

1940-b-Popoviciu-Positive-On-Monotone-Sequences
Original text
Rate this translation
Your feedback will be used to help improve Google Translate

About monotonic sequences

by Tiberiu Popoviciu
There exists a natural number N n N n N_(n)\mathrm{N}_{\mathrm{n}}Nnsuch that of any sequence of real numbers having at least N n N n N_(n)\mathrm{N}_{\mathrm{n}}NnIn terms, we can extract at least one monotonic byteline sequence of n n nnnterms but, we can construct a sequence having N n − 1 N n − 1 N_(n)-1\mathrm{N}_{\mathrm{n}}-1Nn−1terms of which no partial sequence of n n nnnThe term is not monotonic. It can be shown that N 3 = 5 N 3 = 5 N_(3)=5\mathrm{N}_{3}=5N3=5And ( n − 1 ) 2 < N ⩽ 5 6 n ( n − 1 ) 2 < N ⩽ 5 6 n (n-1)^(2) < N <= (5)/(6)n(\mathrm{n}-1)^{2}<\mathrm{N} \leqslant \frac{5}{6} n(n−1)2<N⩽56n! The exact value of N n N n N_(n)\mathrm{N}_{\mathrm{n}}Nnremains to be found (equal, most likely, to ( n − 1 ) 2 + 1 ( n − 1 ) 2 + 1 (n-1)^(2)+1(n-1)^{2}+1(n−1)2+1 ).
  1. Let's consider a finite string
    (1)
c 1 , c 2 , c 3 , … c m c 1 , c 2 , c 3 , … c m c_(1),c_(2),c_(3),dotsc_(m)c_{1}, c_{2}, c_{3}, \ldots c_{m}c1,c2,c3,…cm
of m m mmmreal numbers. If all the differences
D C i = C i + 1 − C i , i = 1 , 2 , … , m − 1 D C i = C i + 1 − C i , i = 1 , 2 , … , m − 1 Delta_(C_(i))=C_(i)+1-C_(i)quad,quad i=1,2,dots,m-1\Delta_{C_{i}}=C_{i}+1-C_{i} \quad, \quad i=1,2, \ldots, m-1DCi=Ci+1−Ci,i=1,2,…,m−1
are of the same sign or zero, the sequence (1) is said to be monotone. More precisely, the sequence (1) is said to be increasing, non-decreasing, constant, non-increasing or decreasing, as we have
D C 1 > , ⩾ , = , ⩽ resp. < 0 , i = 1 , 2 , … , m − 1 D C 1 > , ⩾ , = , ⩽  resp.  < 0 , i = 1 , 2 , … , m − 1 DeltaC_(1) > , >= ,=, <= " resp. " < 0,quadi=1,2,dots,m-1\Delta \mathrm{C}_{1}>, \geqslant,=, \leqslant \text { resp. }<0, \quad \mathrm{i}=1,2, \ldots, \mathrm{~m}-1DC1>,⩾,=,⩽ resp. <0,i=1,2,…, m−1
Obviously, increasing and constant sequences are special cases of non-decreasing sequences. If the sequence (1) is increasing, non-decreasing, etc., the sequence of opposites
− c 1 , − c 2 , … , − c m − c 1 , − c 2 , … , − c m -c_(1),-c_(2),dots,-c_(m)-\mathrm{c}_{1},-\mathrm{c}_{2}, \ldots,-\mathrm{c}_{\mathrm{m}}−c1,−c2,…,−cm
is resp. decreasing, non-increasing, etc. and vice versa. We can therefore take as a type of monotone sequence, the decreasing sequence.
2. Given the natural numbers i 1 < i 2 < … < i k ≤ m i 1 < i 2 < … < i k ≤ m i_(1) < i_(2) < dots < i_(k) <= m\mathrm{i}_{1}<\mathrm{i}_{2}<\ldots<\mathrm{i}_{\mathrm{k}} \leq \mathrm{m}i1<i2<…<ik≤m; string
c i 1 , c i 2 , … , c i k c i 1 , c i 2 , … , c i k c_(i_(1)),c_(i_(2)),dots,c_(i_(k))c_{i_{1}}, c_{i_{2}}, \ldots, c_{i_{k}}ci1,ci2,…,cik
is called a partial string of (1). It is clear that a string (1) with m m mmmterms
has ( m k ) ( m k ) ((m)/(k))\binom{m}{k}(mk)partial strings with k k kkkterms and in total 2 m − 1 2 m − 1 2^(m)-12^{m}-12m−1partial strings with any number of terms (each term c i c i c_(i)c_{\mathrm{i}}ci(it forces itself to create a partial string).
We have the almost obvious property.
Theorem 1. If the sequence (I) is increasing, non-decreasing, etc. any partial sequence (having at least 2 terms) is also increasing, non-decreasing, etc.
The converse of the theorem is trivial. The definition itself tells us that for the sequence (1) to be increasing, non-decreasing, etc., it is necessary and sufficient that the partial sequences
c i , c i + 1 , i = 1 , 2 , … m − 1 c i , c i + 1 , i = 1 , 2 , … m − 1 c_(i),c_(i+1),quad i=1,2,dotsm-1\mathrm{c}_{\mathrm{i}}, \mathrm{c}_{\mathrm{i}+1}, \quad i=1,2, \ldots \mathrm{~m}-1ci,ci+1,i=1,2,… m−1
to be increasing, non-decreasing, etc.
If we consider monotony without specifying its meaning, we arrive at the following
Theorem 2. The necessary and sufficient condition for the sequence (1) to be monotone is that all partial sequences of three terms are monotone.
For the partial string c j , c j , c k , i < j < k c j , c j , c k , i < j < k c_(j),c_(j),c_(k),i < j < kc_{\mathrm{j}}, c_{\mathrm{j}}, c_{\mathrm{k}}, i<j<kcj,cj,ck,i<j<k, the necessary and sufficient condition for monotonicity is
(2)
( c i − c i ) ( c k − c i ) > 0 c i − c i c k − c i > 0 (c_(i)-c_(i))(c_(k)-c_(i)) > 0\left(c_{i}-c_{i}\right)\left(c_{k}-c_{i}\right)>0(ci−ci)(ck−ci)>0
Let us now prove Theorem 2. The condyle is obviously necessary by Theorem 1. Let us prove that it is also sufficient. Suppose that (2) is satisfied, whatever i ∠ j ∠ k ≤ m i ∠ j ∠ k ≤ m i/_j/_k <= mi \angle j \angle k \leq mi∠j∠k≤mIf the sequence (1) were not monotone, the sequence of differences
(3)
D C 1 , D C 2 , … , D C m − 1 D C 1 , D C 2 , … , D C m − 1 DeltaC_(1),DeltaC_(2),dots,Delta_(C_(m-1))\Delta \mathrm{C}_{1}, \Delta \mathrm{C}_{2}, \ldots, \Delta_{\mathrm{C}_{\mathrm{m}-1}}DC1,DC2,…,DCm−1
would have at least two non-zero terms with opposite signs. Let D c r D c r Deltac_(r)\Delta c_{r}Dcrfirst term ≠ 0 ≠ 0 !=0\neq 0≠0in (3) and D c s , s > r D c s , s > r Deltac_(s),s > r\Delta c_{s}, s>rDcs,s>rfirst term ≠ 0 ≠ 0 !=0\neq 0≠0and of opposite sign to D c r D c r Deltac_(r)\Delta c_{r}Dcrin (3). We have D c r D c s < 0 D c r D c s < 0 Deltac_(r)Deltac_(s) < 0\Delta c_{r} \Delta c_{s}<0DcrDcs<0, and through its construction s s sss
D C s D C i ⩽ 0 , i = r + 1 , r + 2 , … , s − 1 D C s D C i ⩽ 0 , i = r + 1 , r + 2 , … , s − 1 Delta_(C_(s))Delta_(C_(i)) <= 0quad,quadi=r+1,r+2,dots,s-1\Delta_{\mathrm{C}_{\mathrm{s}}} \Delta_{\mathrm{C}_{\mathrm{i}}} \leqslant 0 \quad, \quad \mathrm{i}=\mathrm{r}+1, \mathrm{r}+2, \ldots, \mathrm{~s}-1DCsDCi⩽0,i=r+1,r+2,…, s−1
school s > r + 1 s > r + 1 s > r+1s>r+1s>r+1If
​ s = r + 1 s = r + 1 s=r+1s=r+1s=r+1, we have
D C r D C s = ( C r + 1 − C r ) ( C r + 2 − C r + 1 ) < 0 D C r D C s = C r + 1 − C r C r + 2 − C r + 1 < 0 DeltaC_(r)DeltaC_(s)=(C_(r+1)-C_(r))(C_(r+2)-C_(r+1)) < 0\Delta \mathrm{C}_{\mathrm{r}} \Delta \mathrm{C}_{\mathrm{s}}=\left(\mathrm{C}_{\mathrm{r}+1}-\mathrm{C}_{\mathrm{r}}\right)\left(\mathrm{C}_{\mathrm{r}+2}-\mathrm{C}_{\mathrm{r}+1}\right)<0DCrDCs=(Cr+1−Cr)(Cr+2−Cr+1)<0
which contradicts (2).
If s > r + 1 s > r + 1 s > r+1s>r+1s>r+1, we have
D C s ( D r + D C r + 1 + … + D C s 1 ) = ( C s + 1 − C s ) ( C s − C r ) ⩽ THE D C s D r + D C r + 1 + … + D C s 1 = C s + 1 − C s C s − C r ⩽ THE DeltaC_(s)(Deltar+DeltaC_(r+1)+dots+DeltaC_(s1))=(C_(s+1)-C_(s))(C_(s)-C_(r)) <= O\Delta \mathrm{C}_{\mathrm{s}}\left(\Delta \mathrm{r}+\Delta \mathrm{C}_{\mathrm{r}+1}+\ldots+\Delta \mathrm{C}_{\mathrm{s} 1}\right)=\left(\mathrm{C}_{\mathrm{s}+1}-\mathrm{C}_{\mathrm{s}}\right)\left(\mathrm{C}_{\mathrm{s}}-\mathrm{C}_{\mathrm{r}}\right) \leqslant \mathrm{O}DCs(Dr+DCr+1+…+DCs1)=(Cs+1−Cs)(Cs−Cr)⩽THE
care and and andandandin contradiction with (2).
The preceding completely proves theorem (2).
3. The question can now be asked whether any string (1) contains monotone partial strings of at least three terms.
We will prove the following Theorem 3 for this.
Any sequence (1) of (at least) five terms has at least one partially monotone sequence of three terms.
Indeed, at least one of the strings
C 1 , C 2 , C 3 ; C 2 , C 3 , C 4 ; C 3 , C 4 , C 5 ; C 2 , C 4 , C 5 ; C 1 , C 2 , C 4 C 1 , C 2 , C 3 ; C 2 , C 3 , C 4 ; C 3 , C 4 , C 5 ; C 2 , C 4 , C 5 ; C 1 , C 2 , C 4 C_(1),C_(2),C_(3);C_(2),C_(3),C_(4);C_(3),C_(4),C_(5);C_(2),C_(4),C_(5);C_(1),C_(2),C_(4)\mathrm{C}_{1}, \mathrm{C}_{2}, \mathrm{C}_{3} ; \mathrm{C}_{2}, \mathrm{C}_{3}, \mathrm{C}_{4} ; \mathrm{C}_{3}, \mathrm{C}_{4}, \mathrm{C}_{5} ; \mathrm{C}_{2}, \mathrm{C}_{4}, \mathrm{C}_{5} ; \mathrm{C}_{1}, \mathrm{C}_{2}, \mathrm{C}_{4}C1,C2,C3;C2,C3,C4;C3,C4,C5;C2,C4,C5;C1,C2,C4must be monotonous. Otherwise we should have
( c 2 − c 1 ) ( c 3 − c 2 ) < 0 , ( c 3 − c 2 ) ( c 4 − c 3 ) < 0 , ( c 4 − c 2 ) ( c 5 − c 4 ) < 0 ( c 4 − c 3 ) ( c 5 − c 4 ) < 0 , ( c 2 − c 1 ) ( c 4 − c 2 ) < 0 c 2 − c 1 c 3 − c 2 < 0 , c 3 − c 2 c 4 − c 3 < 0 , c 4 − c 2 c 5 − c 4 < 0 c 4 − c 3 c 5 − c 4 < 0 , c 2 − c 1 c 4 − c 2 < 0 {:[(c_(2)-c_(1))(c_(3)-c_(2)) < 0quad","quad(c_(3)-c_(2))(c_(4)-c_(3)) < 0","quad(c_(4)-c_(2))(c_(5)-c_(4)) < 0],[(c^(4)-c_(3))(c_(5)-c_(4)) < 0quad","quad(c_(2)-c_(1))(c_(4)-c_(2)) < 0]:}\begin{gathered} \left(c_{2}-c_{1}\right)\left(c_{3}-c_{2}\right)<0 \quad, \quad\left(c_{3}-c_{2}\right)\left(c_{4}-c_{3}\right)<0, \quad\left(c_{4}-c_{2}\right)\left(c_{5}-c_{4}\right)<0 \\ \left(c^{4}-c_{3}\right)\left(c_{5}-c_{4}\right)<0 \quad, \quad\left(c_{2}-c_{1}\right)\left(c_{4}-c_{2}\right)<0 \end{gathered}(c2−c1)(c3−c2)<0,(c3−c2)(c4−c3)<0,(c4−c2)(c5−c4)<0(c4−c3)(c5−c4)<0,(c2−c1)(c4−c2)<0
or
[ ( c 2 − c 1 ) ( c 3 − c 2 ) ( c 4 − c 3 ) ( c 5 − c 4 ) ( c 4 − c 2 ) ] 2 < 0 c 2 − c 1 c 3 − c 2 c 4 − c 3 c 5 − c 4 c 4 − c 2 2 < 0 [(c_(2)-c_(1))(c_(3)-c_(2))(c_(4)-c_(3))(c_(5)-c_(4))(c_(4)-c_(2))]^(2) < 0\left[\left(c_{2}-c_{1}\right)\left(c_{3}-c_{2}\right)\left(c_{4}-c_{3}\right)\left(c_{5}-c_{4}\right)\left(c_{4}-c_{2}\right)\right]^{2}<0[(c2−c1)(c3−c2)(c4−c3)(c5−c4)(c4−c2)]2<0
which is absurd.
From the previous theorem we can deduce the following
Theorem 4. Any string of (at least) 5 6 n ! 5 6 n ! (5)/(6)n!\frac{5}{6} n!56n!terms has at least one partially monotone sequence of n n nnnterms ( n ⩾ 3 n ⩾ 3 n >= 3n \geqslant 3n⩾3 ).
Let the string (1) with m = 5 6 n ! m = 5 6 n ! m=(5)/(6)n!m=\frac{5}{6} n!m=56n!We will prove the theorem by induction. The property is already proven for n = 3 n = 3 n=3n=3n=3. Suppose it is true for n − 1 n − 1 n-1n-1n−1and show that it will also be true for n n nnnIf we put k = 5 6 ( n − 1 ) ! k = 5 6 ( n − 1 ) ! k=(5)/(6)(n-1)!k=\frac{5}{6}(n-1)!k=56(n−1)!, each of the strings
(4) c i k + 1 , c i k + 2 , … , c ( i + 1 ) k , i = 0 , 1 , … n − 1 c i k + 1 , c i k + 2 , … , c ( i + 1 ) k , i = 0 , 1 , … n − 1 c_(ik+1),c_(ik+2),dots,c_((i+1)k),i=0,1,dots n-1c_{i k+1}, c_{i k+2}, \ldots, c_{(i+1) k}, i=0,1, \ldots n-1cik+1,cik+2,…,c(i+1)k,i=0,1,…n−1
contains by hypothesis, at least a partially monotone sequence of n − 1 n − 1 n-1n-1n−1terms. From the strings (4) let us therefore extract the partial monotone strings of n − 1 n − 1 n-1n-1n−1terms
(5) c 1 ( i + 1 ) , c 2 ( i + 1 ) , … , c n − 1 ( i + 1 ) , i = 0 , 1 , … n − 1 c 1 ( i + 1 ) , c 2 ( i + 1 ) , … , c n − 1 ( i + 1 ) , i = 0 , 1 , … n − 1 quadc_(1)^((i+1)),c_(2)^((i+1)),dots,c_(n-1)^((i+1)),i=0,1,dots n-1\quad c_{1}^{(i+1)}, c_{2}^{(i+1)}, \ldots, c_{n-1}^{(i+1)}, i=0,1, \ldots n-1c1(i+1),c2(i+1),…,cn−1(i+1),i=0,1,…n−1
The following two cases can then occur
: a) There are at least two among the strings (5) of opposite monotonicity.
For example, let it be
non-decreasing and
c 1 ( i ) , c 2 ( j ) , … c n − 1 ( j ) c 1 ( i ) , c 2 ( j ) , … c n − 1 ( j ) c_(1)^((i)),c_(2)^((j)),dotsc_(n-1)^((j))c_{1}^{(i)}, c_{2}^{(j)}, \ldots c_{n-1}^{(j)}c1(i),c2(j),…cn−1(j)
non-increasing. It can be assumed i < j i < j i < ji<ji<j
If c n − 1 ( 1 ) ⩽ c 1 ( j ) c n − 1 ( 1 ) ⩽ c 1 ( j ) c_(n-1)^((1)) <= c_(1)^((j))c_{n-1}^{(1)} \leqslant c_{1}^{(j)}cn−1(1)⩽c1(j)RANGE
c 1 ( i ) , c 2 ( i ) , … , c n − 1 ( i ) , c 1 ( i ) c 1 ( i ) , c 2 ( i ) , … , c n − 1 ( i ) , c 1 ( i ) c_(1)^((i)),c_(2)^((i)),dots,c_(n-1)^((i)),c_(1)^((i))c_{1}^{(i)}, c_{2}^{(i)}, \ldots, c_{n-1}^{(i)}, c_{1}^{(i)}c1(i),c2(i),…,cn−1(i),c1(i)
and of n n nnnterms, is a partial sequence of (1) and is monotone
If c n − 1 ( i ) > c 1 ( j ) c n − 1 ( i ) > c 1 ( j ) c_(n-1)^((i)) > c_(1)^((j))c_{n-1}^{(i)}>c_{1}^{(j)}cn−1(i)>c1(j)the string of n n nnnterms
c n − 1 ( i ) , c 1 ( i ) , c 1 ( i ) , … c n − 1 ( i ) c n − 1 ( i ) , c 1 ( i ) , c 1 ( i ) , … c n − 1 ( i ) c_(n-1)^((i)),c_(1)^((i)),c_(1)^((i)),dotsc_(n-1)^((i))c_{n-1}^{(i)}, c_{1}^{(i)}, c_{1}^{(i)}, \ldots c_{n-1}^{(i)}cn−1(i),c1(i),c1(i),…cn−1(i)
is monotone and is a sequence extracted from (1).
b) All sequences (5) are monotone of the same sense. We can assume that they are all nondecreasing. If now there is a i i iiiso that c n − 1 ( i ) ⩽ c n − 1 ( i + 1 ) c n − 1 ( i ) ⩽ c n − 1 ( i + 1 ) c_(n-1)^((i)) <= c_(n-1)^((i+1))\mathrm{c}_{\mathrm{n}-1}^{(\mathrm{i})} \leqslant \mathrm{c}_{\mathrm{n}-1}^{(\mathrm{i}+1)}cn−1(i)⩽cn−1(i+1)then the string of n n nnnterms
c 1 ( i ) , c 2 ( i ) , … , c n − 1 ( i ) , c n − 1 ( i + 1 ) c 1 ( i ) , c 2 ( i ) , … , c n − 1 ( i ) , c n − 1 ( i + 1 ) c_(1)^((i)),c_(2)^((i)),dots,c_(n-1)^((i)),c_(n-1)^((i+1))c_{1}^{(i)}, c_{2}^{(i)}, \ldots, c_{n-1}^{(i)}, c_{n-1}^{(i+1)}c1(i),c2(i),…,cn−1(i),cn−1(i+1)
is monotone and extracted from (1). Otherwise we must have c n − 1 ( i ) > c n − 1 ( i + 1 ) , i = 1 , 2 , … , n − 1 c n − 1 ( i ) > c n − 1 ( i + 1 ) , i = 1 , 2 , … , n − 1 c_(n-1)^((i)) > c_(n-1)^((i+1)),i=1,2,dots,n-1c_{n-1}^{(i)}>c_{n-1}^{(i+1)}, i=1,2, \ldots, n-1cn−1(i)>cn−1(i+1),i=1,2,…,n−1and the string of n n nnnterms
c n − 1 ( 1 ) , c n − 1 ( 2 ) , … , c n − 1 ( n ) c n − 1 ( 1 ) , c n − 1 ( 2 ) , … , c n − 1 ( n ) c_(n-1)^((1)),c_(n-1)^((2)),dots,c_(n-1)^((n))c_{n-1}^{(1)}, c_{n-1}^{(2)}, \ldots, c_{n-1}^{(\mathrm{n})}cn−1(1),cn−1(2),…,cn−1(n)
is monotone and extracted from (1).

Theorem 4 is completely proven.

  1. It follows from the foregoing that there is a number N n N n N_(n)\mathrm{N}_{\mathrm{n}}Nnsuch that any string having at least N n N n N_(n)\mathrm{N}_{\mathrm{n}}Nnterms contains at least one partially monotone string of n n nnnterms, but there is at least one string (1) with N n − 1 N n − 1 N_(n)-1\mathrm{N}_{\mathrm{n}}-1Nn−1terms that do not contain any partial monotone sequence of n n nnnterms.
Theorem 4 shows us that N ⩽ 5 6 n ! N ⩽ 5 6 n ! N <= (5)/(6)n!N \leqslant \frac{5}{6} n!N⩽56n!On the other hand, the string n − 1 , n − 2 , … . , 2 , 1 , 2 n − 2 , 2 n − 3 , … . , n , 3 n − 3 n − 1 , n − 2 , … . , 2 , 1 , 2 n − 2 , 2 n − 3 , … . , n , 3 n − 3 n-1,n-2,dots.,2,1,2n-2,2n-3,dots.,n,3n-3n-1, n-2, \ldots ., 2,1,2 n-2,2 n-3, \ldots ., n, 3 n-3n−1,n−2,….,2,1,2n−2,2n−3,….,n,3n−3, 3 n − 4 , … , 2 n − 1 , … , ( n − 1 ) 2 , ( n − 1 ) 2 − 1 , … , ( n − 2 ) n − ( n − 3 ) 3 n − 4 , … , 2 n − 1 , … , ( n − 1 ) 2 , ( n − 1 ) 2 − 1 , … , ( n − 2 ) n − ( n − 3 ) 3n-4,dots,2n-1,dots,(n-1)^(2),(n-1)^(2)-1,dots,(n-2)n-(n-3)3 n-4, \ldots, 2 n-1, \ldots,(n-1)^{2},(n-1)^{2}-1, \ldots,(n-2) n-(n-3)3n−4,…,2n−1,…,(n−1)2,(n−1)2−1,…,(n−2)n−(n−3)of ( n − 1 ) 2 ( n − 1 ) 2 (n-1)^(2)(n-1)^{2}(n−1)2terms does not contain any partially monotone sequence of n n nnnterms. It follows that N n > ( n − 1 ) 2 N n > ( n − 1 ) 2 N_(n) > (n-1)^(2)\mathrm{N}_{\mathrm{n}}>(n-1)^{2}Nn>(n−1)2.
number N n N n N_(n)\mathrm{N}_{\mathrm{n}}Nnis equal to 5 for n = 3 n = 3 n=3n=3n=3It would be interesting to determine its value for n n nnnsome. It is very likely that N n = ( n − 1 ) 2 + 1 N n = ( n − 1 ) 2 + 1 N_(n)=(n-1)^(2)+1\mathrm{N}_{n}=(n-1)^{2}+1Nn=(n−1)2+1, this remains to be demonstrated.
The problem of determining the minimum number of monotone partial sequences of n n nnnterms that can be extracted from a string having a given number m ⩾ N n m ⩾ N n m >= N_(n)m \geqslant \mathrm{~N}_{\mathrm{n}}m⩾ Nnof terms. It is easy to see that this number is at least equal to
[ m − N n n ] + 1 m − N n n + 1 [(m-N_(n))/(n)]+1\left[\frac{m-\mathrm{N}_{\mathrm{n}}}{n}\right]+1[m−Nnn]+1
where [ α ] [ α ] [alpha][\alpha][a]means as usual, the whole part of α α alpha\alphaaIt is likely that the number we are talking about is equal to the minimum of
( λ 1 n ) + ( λ 2 n ) + … + ( λ n − 1 n ) ( λ 1 n ) + ( λ 2 n ) + … + ( λ n − 1 n ) ((lambda_(1))/(n))+((lambda_(2))/(n))+dots+((lambda_(n-1))/(n))\binom{\lambda_{1}}{n}+\binom{\lambda_{2}}{n}+\ldots+\binom{\lambda_{n-1}}{n}(l1n)+(l2n)+…+(ln−1n)
when the whole λ i ⩾ 0 λ i ⩾ 0 lambda_(i) >= 0\lambda_{\mathbf{i}} \geqslant 0li⩾0check the relationship
λ 1 + λ 2 + … + λ n − 1 = m λ 1 + λ 2 + … + λ n − 1 = m lambda_(1)+lambda_(2)+dots+lambda_(n-1)=m\lambda_{1}+\lambda_{2}+\ldots+\lambda_{n-1}=ml1+l2+…+ln−1=m
This number is equal to
( n − 1 − r ) ( m − r n − 1 ) + ( m + n − r − 1 n − 1 ) ( n − 1 − r ) m − r n − 1 + m + n − r − 1 n − 1 (n-1-r)((m-r)/(n-1))+((m+n-r-1)/(n-1))(n-1-r)\left(\frac{m-r}{n-1}\right)+\left(\frac{m+n-r-1}{n-1}\right)(n−1−r)(m−rn−1)+(m+n−r−1n−1)
When r r rrris the remainder of the division of m m mmmrare n − 1 n − 1 n-1n-1n−1.
It can easily be seen that the problem posed here is equivalent to a combinatorial analysis problem. Given a permutation of the primes m m mmmnatural numbers, it's about how many groups of n n nnnterms exist in this permutation which terms, keeping their place, form an ascending or descending sequence?
Observation. The problem of extracting monotone partial sequences can also be posed for infinite sequences of numbers. It is easy to see that from any infinite sequence an infinite and monotone partial sequence can be extracted. However, the problem should not be considered as exhausted in this way. The problem should also be examined for sequences transfinite by an ordinal number (transfinite) given by the terms.
21 August, 940.
1940

Related Posts