2
$\begingroup$

How many arrangements (permutations) of a set of $\frac{n(n+1)}{2}$ distinct cards, each having one of $n$ colors $c_1,\ldots,c_n$ where there are $i$ cards of color $c_i$ that are numbered $1,2,\ldots,i$, satisfy the following constraint: any two cards of the same color and with consecutive numbers cannot be adjacent in the arrangement. This seems to be similar to this problem, but in our case all the cards are distinct, whereas in that problem the cards of the same color are all identical.

  • 0
    How many cards are in an arrangement? Can you give an example of a forbidden arrangement?2012-04-09
  • 0
    Do you want permutations of the entire deck in which no two *adjacent* cards of consecutive numbers of the same color?2012-04-09
  • 0
    Yes, it is exactly what I mean. For example, case $n=3$, red 1, blue 1, 2 and green 1, 2, 3. Blue1 should not be adjacent to Blue2. Neither Green1 and Green2, nor Green2 and Green3.2012-04-09
  • 0
    Please, fix the question, so that it actually expresses what you mean. Then, please tell us where this question comes from and what kind of answer you expect.2012-04-09
  • 0
    I've edited the question to what seemed to be intended. Looks like a tough problem to me, considerably harder than the other problem linked to. Did you try do compute the numbers for small $n$, and used the [OEIS](http://oeis.org/)? Also, did you look at the [simpler problem](http://oeis.org/A002464) of permuting $n$ cards with consecutive numbers forbidden to be neigbours?2012-04-09
  • 1
    @Marc: I count $1,2,216,954432$ for the first four terms ([here's the code](https://gist.github.com/2349368)). That sequence isn't in OEIS.2012-04-10
  • 1
    $a(n)=\int_{z=0}^\infty \Biggl(e^{-z}\prod_{i=1}^{n}\biggl(\sum_{k=0}^{i-1}\Bigl(\sum_{j=0}^{i-1-k} \binom{k+1}{j}\binom{i-1-j}{k}\Bigr)(-1)^{i-1-k}z^{k+1}\biggr)\Biggr)dz.$ $a(1)=1, \;a(2)=2,\;a(3)=216,\;a(4)=954432,\;a(5)=313067602560,\;a(6)=11394325627300281600,\;a(7)=64336748997032761512891479040,\;a(8)=75093144953318072478960408305125194792960.$2017-07-29

0 Answers 0