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$$

  • 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! – user940 Apr 9 '12 at 2:30
  • quite different problem! – hkju Apr 9 '12 at 3:57
  • Not so different. – user940 Apr 9 '12 at 4:00
  • the problem you mentioned deals with the different number of cards, but here we consider the same number of cards. – hkju Apr 9 '12 at 6:41
  • 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. – user940 Apr 9 '12 at 14:17
up vote 31 down vote accepted
+500

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!

  • I must be missing something. When $k=2$ and $n=1$, the correct answer is zero, but that's not what your formula gives. – user940 Apr 9 '12 at 22:36
  • Ahhh, sorry! I forgot a factor of $(-1)^{i-k}$ in the expression for $q_k$. I will fix it. – Jair Taylor Apr 10 '12 at 1:46
  • 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. – Jair Taylor Apr 10 '12 at 1:48
  • Here is some numerical evidence in the form of a Sage worksheet - it reproduces oeis.org/A114938. See sagenb.org/home/pub/4677 – Jair Taylor Apr 10 '12 at 1:56
  • 1
    Well, I'm convinced! That is a wonderful formula. – user940 Apr 10 '12 at 1:59

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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