Falling factorial counts permutations, what does rising factorial count?

Question

Rising factorial example: Let $x = 7$ and $r = 4$. Then $7^{(4)} = 7(8)(9)(10) = 5040$. If we divide $7^{(4)}$ by $4!$ it counts multisubsets.

But what kind of combinatorial problem does rising factorial solve on its own?

Answer 1

Imagine constructing a permutation of $k$ elements with $n-1$ elements initially, but add a spot for each number placed in the sequence instead of taking one away. I'm going to call this a rising permutation for lack of a better name.

---

You can visualize the construction of an ordinary permutation on $n$ elements by imagining $n$ slots and replacing one slot with a number every turn. We'll number the turns $1,2, \dots, n$ . In this array below each $*$ is an as-yet-unfilled box and each row represents the state at the end of the $n$th turn, with the first row being the initial state.

$$ \begin{array}{ccc} * & * & * \\ * & 1 & * \\ 2 & 1 & * \\ 2 & 1 & 3 \\ \end{array} $$

There are several equivalent ways of thinking about constructing a permutation one element at a time. This way doesn't make it easy to visualize what happens if there are more numbers than slots (the falling factorial case). However, it does make the analogy with a "rising permutation" more obvious. The key difference is that, on the $i$th turn, we place the number $i$ between one of the items already in the sequence. Doing so creates a slot instead of consuming one.

Each row represents a turn. The gaps in the earlier rows are so that each column tracks the lifetime of a single item in the sequence.

$$ \begin{array}{cccccc} & * & * & & * & \\ & * & * & 1 & * & \\ 2 & * & * & 1 & * & \\ 2 & * & * & 1 & * & 3 \\ \end{array}$$

The above example is from $(4)^{\overline{3}}$ .

The rising factorial $(n)^{\overline{k}}$ asks how many distinct sequences can be made after $k$ turns if there are $(n-1)$ stars initially (equivalently $n$ stars at the end of turn $1$) . Note that a sequence contains the stars that are in it so * 1 * and 1 * * are not the same sequence.

Answer 2

A rising factorial counts the number of ways in which n objects can be inserted into a a list of x objects in a circular order while maintaining the order of x (the order of n need not be maintained). It is calculated as (x+n-1)!/(x-1)!

An example: The leaders of G20 nations are to be seated at a round table meeting in alphabetical order of country name. In addition, 3 others (the secretary of the UN, president of World Bank, and president of IMF) will also need to be seated at the round table. The rising factorial of 20 and 3 gives us the possible seating arrangements in this scenario (20 * 21 * 22 = 9240 ways).

Answer 3

This answer is just a rephrasing of Gregory Nisbet's earlier answer, but I hope that some people may find it clearer.

The rising factorial $(x)^k:= x(x+1)\dotsb (x+k-1)$ is the number of ways of placing $k$ flags (numbered $1,\dotsc,k$) on $x$ flagpoles.

for example

|3 |  |5 |1
|2 |  |  |4
|  |  |  |
|  |  |  |

is a configuration of five flags on four flagpoles. The order in which the flags appear on each flagpoles matters.

For the first flag there are $x$ positions (just choose any one of $x$ flagpoles). For the second flag, you have to choose which pole, and then if that pole already has a flag on it, then you have to choose whether to put the flag above or below that flag.

In general, if $r$ flags have already been placed, then there are $x+r$ choices for the $(r+1)$st flag--either at the top of one of $x$ poles, or just beneath one of the $r$ flags already placed (on the same pole).

It follows that $(x)^k$ is the number of ways of placing $k$ flags (numbered $1$ to $k$ on $x$ flagpoles).