21
$\begingroup$

Find the number of arrangements of $k \mbox{ }1'$s, $k \mbox{ }2'$s, $\cdots, k \mbox{ }n'$s - total $kn$ cards - so that no same numbers appear consecutively. For $k=2$ we can compute it by using the PIE, and it is $$\frac{1}{2^n} \sum_{i=0}^n (-1)^i \binom{n}{i} (2n-i)! 2^i$$

$\endgroup$
9
  • $\begingroup$ We have seen similar problems here before: math.stackexchange.com/questions/76213/… My impression is that there is no general formula for the solution, but I would love to be proven wrong! $\endgroup$
    – user940
    Apr 9, 2012 at 2:30
  • $\begingroup$ quite different problem! $\endgroup$
    – hkju
    Apr 9, 2012 at 3:57
  • $\begingroup$ Not so different. $\endgroup$
    – user940
    Apr 9, 2012 at 4:00
  • $\begingroup$ the problem you mentioned deals with the different number of cards, but here we consider the same number of cards. $\endgroup$
    – hkju
    Apr 9, 2012 at 6:41
  • $\begingroup$ The cases $k=2$ and $k=3$ are tabulated here: oeis.org/A114938 and oeis.org/A193638 . For $k=3$ there is no simple formula given. $\endgroup$
    – user940
    Apr 9, 2012 at 14:17

1 Answer 1

35
+500
$\begingroup$

I believe the answer is given by $$\int_0^\infty e^{-x} q_k(x)^n \, dx$$ where $q_k(x) = \sum_{i=1}^k \frac{(-1)^{i-k}}{i!} {k-1 \choose i-1}x^i$ for $k\geq 1$, and $q_0(x) = 1$. In general if we allow $k_i$ of the $i$th number the answer should be $$\int_0^\infty e^{-x} \prod_i q_{k_i}(x) \, dx$$

You can check that this agrees with the sequences oeis.org/A114938 and oeis.org/A193638 above. I do not (quite) have a proof of this, although I'm very close. The method is my own, and has not been published anywhere as far as I know. I'd be happy to give you more information in private, but I'm not sure I want to expose it publicly until it's proven. Please let me know if you think this is noteworthy and any potential applications.

Edit: Following some information given to me by Byron, I found that this formula is already known and that in fact $q_n(x) = (-1)^{n}L_n^{(-1)}(x)$ where $L_n^{(\alpha)} (x) $ denotes the generalized Laguerre polynomial. See Section 6 here for a labelled version. I should have mentioned this sooner; thanks Byron!

$\endgroup$
9
  • $\begingroup$ I must be missing something. When $k=2$ and $n=1$, the correct answer is zero, but that's not what your formula gives. $\endgroup$
    – user940
    Apr 9, 2012 at 22:36
  • $\begingroup$ Ahhh, sorry! I forgot a factor of $(-1)^{i-k}$ in the expression for $q_k$. I will fix it. $\endgroup$ Apr 10, 2012 at 1:46
  • $\begingroup$ You can check that $q_2(x) = -x + \frac{x^2}{2}$ and then $\int_0^\infty e^{-x} ( -x + \frac{x^2}{2}) \, dx = 0$ as desired. $\endgroup$ Apr 10, 2012 at 1:48
  • 1
    $\begingroup$ Well, I'm convinced! That is a wonderful formula. $\endgroup$
    – user940
    Apr 10, 2012 at 1:59
  • 1
    $\begingroup$ Yes - I don't know if this helps, but $q_k(x) = \int_0^x q_{k-1}(t)\, dt - q_{k-1}(x)$. Also, $q_k(x)$ is the inverse Laplace of $(1-x)^{k-1}/x^{k+1}$. Can I ask why this question came up? $\endgroup$ Apr 11, 2012 at 1:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.