5
$\begingroup$

Is anything known about the following?

I hold in my hand a shuffled pack of cards numbered $1$ to $n$. One by one, I place them all, face up, on a table in piles. For each card I deal from my hand, say card numbered $k$, I open a new pile only if the top card of an existing pile is not $k + 1$; otherwise I place that card on top of that pile. If at any stage (before dealing a new card) the bottom card of an existing pile is one less than the top card of another pile, I combine the two into a new pile in the obvious way.

  1. What is the most likely maximum number of piles that will be formed at some stage while so dealing the $n$ cards?

  2. What is the expected maximum number of piles that will be formed at some stage while so dealing the $n$ cards?

In both cases, count piles only if no two piles can be combined into one.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ I apologise for the TeXifying edit; I see now that you are an experienced user who seems to prefer not to post in TeX. Please feel free to revert the edit if it was unwelcome. $\endgroup$
    – LSpice
    Commented Feb 5, 2021 at 23:01
  • 1
    $\begingroup$ @LSpice Thanks for doing so. I am unfamiliar with TeX. I rely on colleagues like you! $\endgroup$
    – Bernardo Recamán Santos
    Commented Feb 5, 2021 at 23:03
  • 2
    $\begingroup$ So a slightly more formal reformulation. For a set $S\subset \mathbb{N}$ of natural numbers, let $\alpha(S)$ denote the minimum number of intervals $\{i,i+1,\ldots,j\}$ we need to write $S$ as a disjoint union of intervals. And for a permutation $\sigma \in \mathfrak{S}_n$, let $\alpha(\sigma) := \max_k \alpha(\{\sigma(1),\sigma(2),\ldots,\sigma(k)\})$. You're interested in the mode and the mean of $\alpha$ over $\mathfrak{S}_n$. $\endgroup$
    – Sam Hopkins
    Commented Feb 5, 2021 at 23:10
  • 1
    $\begingroup$ For $n=1, 2, 3, 4, 5, 6, 7, 8, 9, 10$ the sequence of modes is $1, 1, 1, 2, 2, 2, 3, 3, 3, 3$ and the sequence of means is $1, 1, 4/3, 5/3, 59/30, 203/90, 229/90, 3569/1260, 14143/4536, 385643/113400$. Obviously this small data doesn't tell you very much. $\endgroup$
    – Sam Hopkins
    Commented Feb 5, 2021 at 23:46
  • $\begingroup$ This seems similar to patience sorting but it's not exactly the same. $\endgroup$
    – Timothy Chow
    Commented Feb 6, 2021 at 1:03

1 Answer 1

Reset to default
3
$\begingroup$

At Timothy Chow's request, here is a table of $A(n,m)$, the number of permutations in $\mathfrak{S}_n$ with maximum number of piles equal to $m$. Note that clearly $A(n,m)=0$ if $m > \lceil n/2 \rceil$:

$ \begin{array}{c|c c c c} n/m & 1 & 2 & 3 & 4 & 5 \\ \hline 1 & 1 \\ 2 & 2 \\ 3 & 4 & 2 \\ 4 & 8 & 16 \\ 5 & 16 & 92 & 12 \\ 6 & 32 & 472 & 216 \\ 7 & 64 & 2312 & 2520 & 144 \\ 8 & 128 & 11104 & 24480 & 4608 \\ 9 & 256 & 52880 & 216432 & 90432 & 2880 \\ 10 & 512 & 250912 & 1815264 & 1418112 & 144000 \end{array}$

There are certainly some patterns visible, but the whole triangle does not appear to be in the OEIS.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I don't see an obvious argument why $A(n,1)=2^{n-1}$. Of course, you can construct a permutation counted by $A(n,1)$ by choosing, for each $i=2,\ldots,n$, $\sigma(i)$ to either be one more than the max or one less than the min of $\sigma(1),\ldots,\sigma(i-1)$, so $2^{n-1}$ makes sense as a rough guess; but this ignores two competing complications: the choice of $\sigma(1)$ and the fact that we might hit $n$ or $1$ in $\sigma(1),\ldots,\sigma(i-1)$ before $i=n$. $\endgroup$
    – Sam Hopkins
    Commented Feb 6, 2021 at 1:58
  • $\begingroup$ Nevermind, I see that for any sequence of length $n-1$ of max's or min's, there's a unique valid choice of $\sigma(1)$, so $A(n,1)=2^{n-1}$ is indeed clear. $\endgroup$
    – Sam Hopkins
    Commented Feb 6, 2021 at 2:16
  • $\begingroup$ Likewise, $A(2m-1,m)=m!(m-1)!$ is easily seen: choose any permutation of $1,3,5,\ldots,2m-1$ and concatenate it with any permutation of $2,4,\ldots,2m-2$. $\endgroup$
    – Sam Hopkins
    Commented Feb 6, 2021 at 2:20
  • $\begingroup$ Similarly, $A(2m,m)=2m(m!)^2$. $\endgroup$
    – Sam Hopkins
    Commented Feb 6, 2021 at 2:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .