Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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! –  Byron Schmuland Apr 9 '12 at 2:30
    
quite different problem! –  hkju Apr 9 '12 at 3:57
    
Not so different. –  Byron Schmuland 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. –  Byron Schmuland Apr 9 '12 at 14:17
show 4 more comments

1 Answer

up vote 18 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. the

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!

share|improve this answer
    
I must be missing something. When $k=2$ and $n=1$, the correct answer is zero, but that's not what your formula gives. –  Byron Schmuland 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
    
Well, I'm convinced! That is a wonderful formula. –  Byron Schmuland Apr 10 '12 at 1:59
show 4 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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