18
$\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$
  • $\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 '12 at 2:30
  • $\begingroup$ quite different problem! $\endgroup$ – hkju Apr 9 '12 at 3:57
  • $\begingroup$ Not so different. $\endgroup$ – user940 Apr 9 '12 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 '12 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 '12 at 14:17
32
+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$
  • $\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 '12 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$ – Jair Taylor Apr 10 '12 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$ – Jair Taylor Apr 10 '12 at 1:48
  • 1
    $\begingroup$ Well, I'm convinced! That is a wonderful formula. $\endgroup$ – user940 Apr 10 '12 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$ – Jair Taylor Apr 11 '12 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.