Probability of Choosing Increasing Sequence
by djmathman, Sep 25, 2020, 9:57 PM
Problem Stash 2.10 (Own), Restated. Find the probability that a random permutation of the numbers 
contains the increasing sequence 
.
Remark
Solution
contains the increasing sequence 
.Remark
As mentioned by the source, this problem was (part of) the last problem in Problem Stash 2, which took place back in May. The official solution was one I came up with after two days of work and some help from OEIS. However, this problem first seems to have originated in Issue 33 of the Congressus Numerantium way back in 1981. This is my writeup of the solution given in these proceedings, which is arguably more motivated and lends itself more nicely to a generalization mentioned later in the paper.
Solution
We claim the requested probability is
![\[
2^n\sum_{k=0}^n\frac{(-1)^k\binom nk}{(n+k)!}.
\]](//latex.artofproblemsolving.com/1/8/6/18665394975e10617823ed6898acadab9dd2369e.png)
To prove this, we will actually show the number of such sequences is 
; dividing by 
will give the desired probability.
Generalizing the problem slightly, let
denote the number of sequences of 
ones, 
twos, and so on, containing the increasing sequence 
; in our case, we seek the value of 
, where the 
is repeated 
times. We will call such sequences complete.
Let
. Before we proceed, we note the following properties of 
.
First, observe the recurrence relation
![\[
f(a_1,\ldots, a_k) = \binom{n-1}{a_1 - 1}f(a_2,\ldots, a_k) + \sum_{i=2}^kf(a_1,\ldots, a_i - 1,\ldots, a_k).\qquad(*)
\]](//latex.artofproblemsolving.com/6/2/a/62ae27221cd06a5ceedda205b8555953c7d532b5.png)
To prove this recursion, we case on the first term in the sequence:
.
This recursion seems very difficult to work with until we notice the following (very!) crucial claim.
Lemma. The function is symmetric in its arguments; that is, the value of depends only on the underlying multiset 
.
Proof. Proceed by induction on the sum
. The cases 
and 
are covered by the third and fourth points given above. Now remark that the inductive step and the recursion above show that is symmetric in the last 
arguments, while the fifth point above shows that is preserved under the reversal of these arguments. Combining both of these observations proves the claim.
Now define the function
, which equals when 
of the arguments equal and the remaining 
arguments equal 
; the lemma tells us that this function 
is well-defined. Then, under the assumption 
(which we can always force unless 
), the recursion rewrites as
![\[
g(k,\ell) = (k+\ell - 1)g(k-1,\ell - 1) + (\ell - 1)g(k,\ell - 1).\qquad(\dagger)
\]](//latex.artofproblemsolving.com/6/5/7/657c828f9936703af83d9de54d8976048f1f7be8.png)
To solve this recursion, we use generating functions. Define the multivariable generating function
![\[
A(x,y) = \sum_{k\geq 0}\sum_{\ell\geq 0}\frac{x^{k+\ell}y^\ell}{(k+\ell)!\ell!}g(k+\ell,\ell).
\]](//latex.artofproblemsolving.com/5/4/f/54f5db23df1c40c18ae9bdda4fb4e577db84dfd6.png)
Multiplying 
by 
, summing over all 
and , and formally integrating the resulting equality in 
yields
![\[
\frac{\partial^2 A(x,y)}{\partial x\partial y} + y\frac{\partial A(x,y)}{\partial y} = xA(x,y).
\]](//latex.artofproblemsolving.com/1/1/b/11beb03e0951d959faf832ccac1e52faeef2bb33.png)
Miraculously, this differential equation has the simple-looking solution
![\[
A(x,y) = e^{xy + x - y}.
\]](//latex.artofproblemsolving.com/2/d/2/2d2e2abec9ffd4d316093241438a096b61346365.png)
Expanding this and equating coefficients yields
![\[
g(k,\ell) = \sum_{i=0}^\ell\binom{k+\ell}{k+i}\binom\ell i (\ell - i)!(-1)^i.
\]](//latex.artofproblemsolving.com/d/a/d/dadd23e64c4f9edd70e90ac4a311854350b82f74.png)
In particular,
![\[
g(n,n) = \sum_{i=0}^n\binom{2n}{n+i}\binom ni (n-i)!(-1)^\ell = (2n)!\sum_{i=0}^n\frac{(-1)^i\binom ni}{(n+i)!}.
\]](//latex.artofproblemsolving.com/4/9/5/49510c5346562ef6b8d053d7176ae0f9e27000b9.png)
Whew.
![\[
2^n\sum_{k=0}^n\frac{(-1)^k\binom nk}{(n+k)!}.
\]](http://latex.artofproblemsolving.com/1/8/6/18665394975e10617823ed6898acadab9dd2369e.png)
To prove this, we will actually show the number of such sequences is 
; dividing by 
will give the desired probability.Generalizing the problem slightly, let
denote the number of sequences of 
ones, 
twos, and so on, containing the increasing sequence 
; in our case, we seek the value of 
, where the 
is repeated 
times. We will call such sequences complete.Let
. Before we proceed, we note the following properties of 
.
;
;
;
;
.
;
;
;
;
.First, observe the recurrence relation
![\[
f(a_1,\ldots, a_k) = \binom{n-1}{a_1 - 1}f(a_2,\ldots, a_k) + \sum_{i=2}^kf(a_1,\ldots, a_i - 1,\ldots, a_k).\qquad(*)
\]](http://latex.artofproblemsolving.com/6/2/a/62ae27221cd06a5ceedda205b8555953c7d532b5.png)
To prove this recursion, we case on the first term in the sequence:
- If the first term contains a , then there are
ways to arrange the remaining ones in the sequence; then there are 
ways to arrange the remaining terms. - If the first term contains some number
, then this number a priori must not belong to our increasing sequence; it follows that there are 
ways to arrange the remaining 
numbers.
ways to arrange the remaining ones in the sequence; then there are 
ways to arrange the remaining terms.
,
ways to arrange the remaining 
numbers.
.This recursion seems very difficult to work with until we notice the following (very!) crucial claim.
Lemma. The function
is symmetric in its arguments; that is, the value of depends only on the underlying multiset 
.Proof. Proceed by induction on the sum
. The cases 
and 
are covered by the third and fourth points given above. Now remark that the inductive step and the recursion above show that is symmetric in the last 
arguments, while the fifth point above shows that is preserved under the reversal of these arguments. Combining both of these observations proves the claim.Now define the function
, which equals when 
of the arguments equal and the remaining 
arguments equal 
; the lemma tells us that this function 
is well-defined. Then, under the assumption 
(which we can always force unless 
), the recursion rewrites as![\[
g(k,\ell) = (k+\ell - 1)g(k-1,\ell - 1) + (\ell - 1)g(k,\ell - 1).\qquad(\dagger)
\]](http://latex.artofproblemsolving.com/6/5/7/657c828f9936703af83d9de54d8976048f1f7be8.png)
To solve this recursion, we use generating functions. Define the multivariable generating function
![\[
A(x,y) = \sum_{k\geq 0}\sum_{\ell\geq 0}\frac{x^{k+\ell}y^\ell}{(k+\ell)!\ell!}g(k+\ell,\ell).
\]](http://latex.artofproblemsolving.com/5/4/f/54f5db23df1c40c18ae9bdda4fb4e577db84dfd6.png)
Multiplying 
by 
, summing over all 
and , and formally integrating the resulting equality in 
yields![\[
\frac{\partial^2 A(x,y)}{\partial x\partial y} + y\frac{\partial A(x,y)}{\partial y} = xA(x,y).
\]](http://latex.artofproblemsolving.com/1/1/b/11beb03e0951d959faf832ccac1e52faeef2bb33.png)
Miraculously, this differential equation has the simple-looking solution![\[
A(x,y) = e^{xy + x - y}.
\]](http://latex.artofproblemsolving.com/2/d/2/2d2e2abec9ffd4d316093241438a096b61346365.png)
Expanding this and equating coefficients yields![\[
g(k,\ell) = \sum_{i=0}^\ell\binom{k+\ell}{k+i}\binom\ell i (\ell - i)!(-1)^i.
\]](http://latex.artofproblemsolving.com/d/a/d/dadd23e64c4f9edd70e90ac4a311854350b82f74.png)
In particular,![\[
g(n,n) = \sum_{i=0}^n\binom{2n}{n+i}\binom ni (n-i)!(-1)^\ell = (2n)!\sum_{i=0}^n\frac{(-1)^i\binom ni}{(n+i)!}.
\]](http://latex.artofproblemsolving.com/4/9/5/49510c5346562ef6b8d053d7176ae0f9e27000b9.png)
Whew.This post has been edited 3 times. Last edited by djmathman, Sep 25, 2020, 10:00 PM
April 2025
November 2024