Number of permutations where first $k$ numbers decrease

Question

This comes from a question in Herbert Wilf's generatingfunctionology book:

Exercise 18 (chp. 1): Given $n, k$. For how many of the permutations of $n$ letters is it true that their first $k$ values decrease?

For example, if we let $g(n,k)$ be the number of $n$-permutations with at least $k$ decreasing values, we have $g(3,2) = 3$ since there are 3 permutations $(3 1 2)$, $(2 1 3)$, $(321)$ where the first 2 numbers are decreasing.

I have approached this by finding a recursion in the form (with $n \geq 1, k\geq 1$):

$g(n, k) = g(n-1, k-1) + (n-k)g(n-1,k)$

with $g(n, 0) = g(n,1) = n!$ and $g(n,k) = 0$ if $n < k$.

I could then find its generating function by defining $B_n(x) = \sum _{k \geq 1} g(n,k)x^k$ or sum for $n$. However, both end up with a derivative (a $B'_{n-1}(x)$ term) which I don't know how to solve yet.

I soon knew how to get the answer by using counting principles (with answer ${n \choose k} (n-k)! = \frac{n!}{k!}$), but in the answer section it writes:

The probability is evidently $1/k!$ that the first $k$ values will decrease, so $n!/k!$ of the permutations have this property.

I am not sure how he had 'evidently' got this probability, other than empirically observing probabilities at different $n$ values or by counting principles, and would like to ask hints/how to get the probability that he 'evidently' got.

Thank you!

Answer 1

Take any permutation. There is only one way for the first $k$ numbers to be in decreasing order, so that means that since there are $k!$ ways of arranging the first $k$ numbers, the chance of it working is $\frac{1}{k!}$.

To put it another way, for each way of arranging the $n$ numbers such that the first $k$ are in decreasing order, there are $k!$ ways of arranging the $n$ numbers without the restriction - these $k!$ ways are precisely the ones where we permute only the first $k$ numbers. For example, if $n=4,k=3$ then a way that works is $4 2 1 3$. But the $5$ ways that don't work are

$4 1 2 3$

$2143$

$2413$

$1423$

$1243$

obtained by permuting the first $k=3$ numbers. Therefore $\frac{1}{k!}$ arrangements work.

Answer 2

First you need to chhose the first $k$ numbers from the $n$ numbers, in $\binom{n}{k}$ ways. Now once the $k$ objects are chosen you can arrange them in descending order in just one way and one way only. The rest of the $n-k$ elements can be arranged among themselves in $(n-k)!$ ways. Thus total number of such arrangements of $n$ numbers such that the first $k$ numbers is in decreasing order is $$\binom{n}{k}(n-k)!=\frac{n!}{k!}$$

Answer 3

When he said "The probability is evidently $\frac{1}{k!}$ that the first $k$ values will decrease" I understand this to mean that given any $\sigma$ with $\sigma([k])$ to be fixed, then the chances $\sigma$ decreases the first $[k]$ values is $\frac{1}{k!}$ since there are $k!$ possible permutations of $\sigma([k])$ and only one which is decreasing.

When he said "so $\frac{n!}{k!}$ of the permutations have this property". I understand this to mean that there are $n!$ possible permutations and the probability that a permutation has the first $k$ decreasing is thus mass times density which is equal to $n!\times \frac{1}{k!}$.

Another way to see this is the image of $\sigma([k])$ has $\frac{n!}{k!(n-k)!}$ possibilities, and each image corresponds to exactly one decreasing permutation. The complement of the image of $\sigma([k])$ has (n-k)! possible permutations, so the total number of permutations on $n$ elements which permute the first $k$ is equal to $\frac{n!}{k!(n-k)!}\times (n-k)!=\frac{n!}{k!}$.