Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
We have seen similar problems here before:… 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: and . For $k=3$ there is no simple formula given. – Byron Schmuland Apr 9 '12 at 14:17
up vote 29 down vote accepted

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 and 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|cite|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 See – 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

Your Answer


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.