# Another colored balls puzzle (part II)

The same colleague as in Another colored balls puzzle asked me the following variant which she called "part II".

Imagine you have $n$ balls in a bag that are colored from $1$ to $n$. At each turn you take one ball uniformly at random from the bag and then a second uniformly at random from the remaining balls which have a different color to the first. You then color one ball the color of the other and put them both back in the bag.

What is the expected number of turns before all the balls have the same color if:

1. You always paint the first ball the color of the second? Or...
2. You always paint the second ball the color of the first?

My intuition is that in the first case you are likely to be decreasing the number of balls with a commonly occurring color and in the second you are likely to be increasing the number of balls with a commonly occurring color. Hence the time to get all colors the same will be much less in the second case than the first.

Simulations.

For rule 1 I get the following approximate expected values for $n = 2 \dots 6$.

$1$, $4$, $10.33$, $22.48$, $45.23$.

For rule 2 I get the following approximate expected values for $n = 2 \dots 6$.

$1$, $2.500$, $4.416$, $6.698$. $9.310$.

To get some feeling for how the problem scales I also tried some other values up to $n=100$. For rule 1 and $n=100$ my simulation didn't get to all balls being equal even once in the time I gave it. However for $n=10$ I get about $618$ and for $n=20$ I get very roughly $520,000$. For rule 2 I get a mean of roughly $865$ for $n=100$. My blind guess is now that the mean for rule is 1 is at least exponential (in fact it looks a little like $2^{n-1}$) but that for rule two it is not quite $\frac{e}{4} n^{1.55}$ but it may be something similar.

-
You really need to choose your friends more carefully. –  Will Jagy May 13 '13 at 19:21
I don't have a solution yet, but I'd like to point out that there is a huge difference between these procedures. If you always paint the first ball the color of the second, then when there are two colors, there is a strong restoring force toward equal counts. If you are over $3/4$ for one color, the chance to increase it is under $1/4$. This means it will take at least exponentially long for every base, and I think it is something like $n!$. I think the second procedure takes at most a quadratic number of turns on average. –  Douglas Zare May 13 '13 at 19:57
To confuse matters again, I have now deleted my reply to the deleted comment. –  navid May 13 '13 at 21:17
Navid, have you run simulations? –  Greg Martin May 13 '13 at 21:52
My calculation earlier wasn't right. The first case may simply be exponential, not asymptotically greater than $c^n$ for every $c$. –  Douglas Zare May 14 '13 at 4:54

Ori Gurel-Gurevich pointed out that the transitions under Rule 1 are like the Hamming distances from $\vec{0}$ in a random walk on a hypercube $C$ (the Ehrenfest urn model). Further, the average number of steps for a random walk to return to a vertex in a regular connected graph is the number of vertices. We can use this idea on the quotient by the antipodal map to get that the average return time on $C/\sim$ is $2^{n-1}$, so on the hypercube, the average time before you either return to $00\ldots0$ or hit its antipode $11\ldots 1$ is $2^{n-1}$. The first step from $00\ldots0$ moves to a state with a single $1$ and $n-1$ $0$s, so the average time to reach either $(n,0)$ or $(0,n)$ from $(1,n-1)$ is $2^{n-1}-1$.

On the way to becoming a uniform color, the balls have to pass through a state with a single ball of one color, and $n-1$ of a second color. So, $2^{n-1}-1$ is an exponential lower bound for the expected number of steps from the original position with $n$ colors.

Here is a simple way to get an exponential upper bound for Rule 1. First, pick a color with $1$ element, and consider the probability that the next $n-1$ steps each increase the size of that color. This is at least $$p= \frac{n-1}{n}\frac{1}{n-1} \times \frac{n-2}{n}\frac{2}{n-1} \times ... \frac{1}{n}\frac{n-1}{n-1}= \frac{(n-1)!^2}{ n^{n-1}(n-1)^{n-1}}.$$

By Stirling's formula, $(n-1)! \sim \sqrt{2\pi (n-1)} ((n-1)/e)^{n-1}$ so

$$p \sim \frac{2\pi (n-1)^n}{n^{n-1} e^{2(n-1)}} \sim \frac{cn}{e^{2n}}.$$

The probability is even greater if you pick a color with more than one element, since you get the first few steps for free. Because the probability that the process will end in the next $n$ steps is at least $cn/(e^{2n})$, the expected number of steps until completion is at most $O(e^{2n})$.

Part of Johan Wästlund's answer to part 1 can be turned into bounds for Rule 2. Consider the number of pairs of balls which don't have the same color. This starts at $n \choose 2$. At each step, you choose an ordered pair of balls $(a,b)$. Conditioned on the choice of the unordered pair $\lbrace a, b \rbrace$, the expected number of pairs of balls of different colors decreases by at least $1$:

Suppose there are $c_a$ balls of the same color as $a$, and $c_b$ balls of the same color as $b$. The conditional probability that the ordering is $(a,b)$ is $(n-c_b)/(2n-c_a-c_b)$. The number of pairs of balls of different colors is decreased by $1 + c_a - c_b$. Conditioned on the event that the unordered pair was $\lbrace a, b\rbrace$, the number of pairs of balls of different colors is decreased on average by $1 + \frac{(c_a-c_b)^2}{2n-c_a-c_b} \ge 1.$

So, the expected number of steps under Rule 2 before all balls have the same color is at most $n \choose 2$.

This argument can be adjusted to give lower bounds which are better than linear. For $n \le x \le n^2/8$, if there are $x$ pairs of balls of the same color, then it takes an average of at least $k n$ steps for the number of pairs of balls of the same color to double to $2x$ for some constant $k$, since we can bound the numerator and denominator of $\frac{(c_a-c_b)^2}{2n-c_a-c_b}$ in terms of $x$. It takes about $\log_2 n - 2$ doublings to go from $n$ pairs the same color to $n^2/4$. This gives a lower bound of $\Omega(n \log n)$.

Here is an improved lower bound for rule 2. Suppose the number of ordered pairs of balls of the same color is $X \lt n^2/4$. $X = \sum_i c_i^2$ where $c_i$ is the number of balls of the $i$th color. We can estimate the expected change $E\bigg[2 + \frac{2(c_a-c_b)^2}{2n - c_a - c_b}\bigg] \le 2 + \frac{k}{n}E[c^2]$ where $k$ is some constant, and $c$ is the number of balls of the color of a random ball. $E[c^2] = \frac{1}{n} \sum_i c_i^3 \le \frac{1}{n} (\sum_i c_i^2)^{3/2} = \frac{1}{n}X^{3/2}$. (The inequality is that the $L^3$ norm is smaller than the $L^2$ norm.)

The number of ordered pairs of balls of the same color increases by at most $2 + \frac{k}{n^2}X^{3/2}$ per step on average. $X$ starts at $n$, and when $X \lt n^{4/3}$, the number of ordered pairs of balls of the same color increases by at most $2+k$ on average, so the expected number of steps for $X$ to reach $n^{4/3}$ (en route to $n^2$) is $\Omega (n^{4/3})$.

I believe that applying this up to $n^2$ would only give another factor of $\log n$, so this is still a bit off of the empirical result of about $n^{3/2}$.

-
I accepted this answer although it is not complete. I really like the way you are applying elementary methods to this problem. As a side note, I am not sure one can easily tell the difference between $n^{3/2}$ and $n^{4/3} \log{n}$ empirically so the latter could well turn out to be the right answer. –  navid May 21 '13 at 18:21
I think something like $n^{3/2}$ is more plausible. There is still some slack in the estimate which gives the $n^{4/3}$ lower bound. You get equality between the $L^2$ and $L^3$ norms when there is one giant color (say of size $n^{2/3}$) and everything else is negligible. However, I think that situation isn't stable. There may be a more complicated notion of progress than the count of pairs of balls of the same color, and that notion may not be maximized with one giant color. –  Douglas Zare May 21 '13 at 21:23

As Douglas Zare points out in a comment to Vincent Beffara's answer, in case 1 the expected time to completion of the process, starting from $(1,n-1)$ is $2^n-1$. To see this, consider a simple random walk on the $n$-th dimensional hypercube. When started at some vertex, say $00\ldots0$, the expected number of step to return to this vertex is exactly the number of vertices, $2^n$. On the other hand, if we only look at the hamming weight of the current vertex we see that the transition probabilities are exactly like in our case 1. Indeed, case 1 can be described as "choose a uniformly random ball and flip its color". Since we start at hamming weight 1 (corresponding to $(1,n-1)$) we get $2^n-1$ as the expected hitting time.

-
Nice! And just a comment for people like myself who don't see it immediately: If you walk around in the graph forever, then by symmetry you will spend $1/2^n$ of your time at each vertex, and therefore the expected time until you return is $2^n$. –  Johan Wästlund May 15 '13 at 8:51
Very nice indeed! –  Vincent Beffara May 15 '13 at 9:26
@ButchMalahide Do you know a reference for that remarkable fact? –  navid May 16 '13 at 20:50
@navid: Lovász, László. "Random walks on graphs: A survey." Combinatorics, Paul Erdos is Eighty 2.1 (1993): 1-46. See the end of section 1. –  Carl May 16 '13 at 22:13
Thank you for the proof and reference. –  navid May 17 '13 at 8:05

This feels a lot like Erdös-Renyi graphs ... How about a sub-problem with $n$ balls initially but only $2$ colors, red and blue. Let $X_t$ be the number of red balls. You always pick a red/blue pair, so everything maps to a random walk on the discrete interval $[0,n]$. Let $p_k$ be the jump probability to the right:

Case 1: $p_k = 1 - k/n$. The local drift is given by $2p_k-1$ so it point inward towards $n/2$. Let $\varepsilon_k = \log \frac {1-p_k} {p_k}$ and $V_k = \sum_{i=0}^{k} \varepsilon_k$. Then the random walk is exactly a walk in the potential $(V_k)$, which is very large towards the boundary. The time needed to exit the interval (and get to one color) behaves like the exponential of the height difference between the maximum of the potential and its minimum. Back-of-the-envelope computation: close to the left boundary $p_k=1$ so get $\varepsilon_k \simeq - \log k/n$. Summing to $n/2$ gives $- \log [(n/2)!/n^{n/2}]$ which is roughly linear in $n$, and the exit time is indeed exponential (update: the difference in potential can be estimated as a Riemann sum and it does scale like $n \log 2$ giving an expected exit time like $2^n$).

Case 2: $p_k = k/n$, now the drift is towards the boundary. The right asymptotic should be something diffusive while close to the middle, and then essentially deterministic (and ballistic) as soon as one catches positive enough drift. If the switch occurs at distance $n^\alpha$ from the boundary, where drift is of order $n^{\alpha-1}$, the first hitting time is like $n^{2\alpha}$ and the second one like $n/n^{\alpha-1} = n^{2-\alpha}$. $\alpha=2/3$ gives a bound of the form $n^{4/3}$.

All this up to computing errors, which are pretty likely. Going from $2$ colors to $n$ is left as an exercise to the reader ;-) but I am guessing similar behavior, exponential in case $1$ and polynomial in case $2$.

-
(Actually case 1 needs a proper estimate for the exponential rate, which I don't have time to do right now but should be straightforward enough ... sorry ...) –  Vincent Beffara May 14 '13 at 17:44
Exact calculations for $n \le 100$ give a value of $2^{n-1}-1$ for the expected time to completion from $(1,n-1)$. I haven't yet proved that this always holds. –  Douglas Zare May 14 '13 at 18:22
Good to know, at least my asymptotic analysis gives the right order of magnitude and even the right growth rate. Far from an exact result, but I believe that the approach is more robust than bijective methods like the one suggested by Ori. –  Vincent Beffara May 15 '13 at 10:04

For given $n$ it is possible to calculate the expected number of turns from an absorbing Markov chain on the integer partitions of $n$.

Each state of the Markov process corresponds to the ordered list of the number of equally colored balls. The matrix of transition probabilities between the states is easily calculated according to rules 1 or 2,

e.g. Removing from position 1, adding to position 2 : {3,1,1} -> {2,2,1}
with probability p = P(choosing position 1 out of all balls) * P(choosing position 2 out of remaining balls) =3/5 * 1/2

Given the transition matrix with the unique absorbing state {n} and the initial state {1,1,1,...,1} it is possible to calculate the expected number of turns before absorption.

This is done in the Mathematica program below. Here some results where the first number is n, the second the numerical result, and the third the exact fraction:

Rule 1

{{2, 1., 1},

{3, 4., 4},

{4, 10.3333, 31/3},

{5, 22.4852, 16729/744},

{6, 45.2173, 33913/750},

{7, 87.7733, 26707139046097/304274018880},

{8, 168.252, 129857255359868261/771803525388385},

{9, 322.292, 4555917617310039296830835441635/14135986803865219963776139264},

{10,620.346,822838635777324535445878391148603051494611/1326419190860455039655669536523314862820}}


Only the numerical values for n>10:

{{11, 1202.04}, {12, 2344.58}, {13, 4599.07}, {14, 9062.01},

{15, 17916.8}, {16, 35513.4},{17, 70522.1}, {18, 140231.},{19, 279122.}, {20, 555989.}}

Rule 2

{{2, 1., 1},

{3, 2.5, 5/2},

{4, 4.41667, 53/12},

{5, 6.6994, 2251/336},

{6, 9.31157, 866023/93005},

{7, 12.2249, 1009285097/82560060},

{8, 15.4166, 2246993235815929/145751872750176},

{9, 18.868, 2285085765293281062003190373/121108796080566797904702840},

{10, 22.5637, 618224636000595187350171250435705332105433100763641/27399140168645771065204844597274355963355735154297}}


Only the numerical values for n>10:

{{11, 26.4901}, {12, 30.6358}, {13, 34.9907}, {14, 39.546}, {15, 44.2936}, {16, 49.2266}, {17, 54.3383}, {18, 59.6231}, {19, 65.0754}, {20, 70.6904}}

Program:

(*
Defining Rule 1:
input : lst = Partition of n , e.g. {5,3,2,1} with n=11
k, m :  Positions to be changed ; remove ball from position k and add to position m
output : list containing changed partition and probability for this change

E.g. PartMove[{5, 3, 2, 1}, 1, 3] -> {{4, 3, 3, 1}, 5/33}
*)
PartMove[lst_, k_, m_] :=
Module[{ll = lst, len = Plus @@ lst, prob},
prob = (ll[[k]]/len*ll[[m]]/(len - ll[[k]]));
ll[[k]] -= 1; ll[[m]] += 1;
If[ll[[k]] == 0, ll = Drop[ll, {k}]]; {Reverse[Sort[ll]], prob}]

(*Alternatively
Defining Rule 2:
input : lst = Partition of n , e.g. {5,3,2,1} with n=11
k, m :  Positions to be changed ; add ball to position k and remove from  position m
output : list containing changed partition and probability for this change

E.g. PartMove[{5, 3, 2, 1}, 1, 3] ->   {{6, 3, 1, 1}, 5/33}
*)
PartMove[lst_, k_, m_] :=
Module[{ll = lst, len = Plus @@ lst, prob},
prob = (ll[[k]]/len*ll[[m]]/(len - ll[[k]]));
ll[[k]] += 1; ll[[m]] -= 1;
If[ll[[m]] == 0, ll = Drop[ll, {m}]]; {Reverse[Sort[ll]], prob}]

(*
Calculate all possible target partitions for a given partition with respective probabilities:
input : lst = Partition of n , e.g. {5,3,2,1} with n=11

output : list containing all possible changed partitions with their  probabilities
Note: Depends on the chosen rule via PartMove

E.g. for rule 1:
Targets[{2, 1, 1}] -> {{{2, 2}, 1/6}, {{3, 1}, 1/3}, {{2, 1, 1}, 1/2}}
*)
Targets[lst_] := Module[{len = Length[lst], pairs, res},
If[len <= 1, {{lst, 1}},
pairs = Select[Tuples[Range[len], 2], #[[1]] != #[[2]] &];
res = Sort[PartMove[lst, #[[1]], #[[2]]] & /@ pairs];
{#[[1, 1]], Plus @@ (#[[2]] & /@ #)} & /@ SplitBy[res, First]]]

(*  Define all possible states for chosen n (here n=4) *)

states = IntegerPartitions[4];

(* Define transition matrix PM for Markov chain *)
nn = Length[states];
Clear[PartIndex]; n = 1; (PartIndex[#] = n++) & /@ states;
PM = Table[0, {nn}, {nn}];
Do[(PM[[PartIndex[#[[1]]], k]] = #[[2]]) & /@
Targets[states[[k]]], {k, 1, nn}]

(* Define submatrix Q for transient state changes *)
Q = (Drop[#, 1] & /@ Drop[PM, 1]);
(* Calculate fundamental matrix NPM of absorbing Markov chain*)
NPM = Inverse[ IdentityMatrix[Length[Q]] - Q];
(*Calculate expected number t of turns when starting from {1,1,..,1} = states[[-1]] *)
t = Plus @@ (#[[-1]] & /@ NPM);
{N[t], t} (*numerical and exact value of t*)

-
I am impressed. Mostly as I tried and failed to do exactly the same thing. –  navid May 15 '13 at 11:53
So for Rule 1 one seems to be getting $(2^{n-1}-1)(1+\frac{1+o(n)}{n})$. –  Aaron Meyerowitz May 16 '13 at 11:56

LATER Concerning procedure 1: We know that the expected number of steps is greater than $2^{n-1}.$ However it appears that perhaps the expected number of steps is $2^{n-1}(1+\frac{1+o(n)}{n}).$ There will be a stage (after at least $n-2$ steps) at which there are $n-1$ balls of the same color and $1$ of another color. As has been elegantly proved, from this point the expected number of steps until all balls are the same color is exactly $2^{n-1}-1.$ This provides a lower bound and, in fact, a surprisingly good one. For each value of $n$ from $3$ to $6$ I did $50,000$ trials and for each value of $n$ from $7$ to $13$ I did $5000$ trials of the first procedure for $n$ balls initially with $n$ distinct colors. Here are the rounded averages

$[3, 4], [4, 10], [5, 22], [6, 45],[7, 88], [8, 172], [9, 322], [10, 610], [11, 1182], [12, 2388], [13, 4548]$

In all cases this is less than $2^{n-1}(1+\frac{3}{n})$ and for the last four cases less than $2^{n-1}(1+\frac{2}{n}).$

even later The exact expectations for $n$ up to $20$ found by Karl support this. If $a_n$ is the expected number of steps to get from $n$ balls with $n$ different colors to all the same color and $a_n=2^{n-1}(1+\frac{b_n}{n})$ then we have these values for $b_n:$

$[5, 2.495], [6, 2.752], [7, 2.752], [8, 2.516], [9, 2.364], [10, 2.140], [11, 1.925], [12, 1.741],$$[13, 1.600], [14, 1.488], [15, 1.404], [16, 1.341], [17, 1.294], [18, 1.258], [19, 1.231], [20, 1.210] EARLIER Consider the related problem of just two colors of balls, white and black (wlog at least as many black as white.) This will give lower bounds since the given problem will eventually have two colors of balls before it has just one. Also, we can split the many colors into two groups (light and dark) and follow the process. This simplification amounts to not counting the steps that involve two colors from the same group. The expected number of steps to get from 1 white and b black to all the same color has been shown to be 2^b-1=2^{n-1}-1 where n=w+b is the total number of balls. If the number of white balls is at least 2 of a total of n then the expected number of steps appears to be roughly 2^{n-1}(1+\frac{1}{n}+\frac{w^2-w}{2n^2}) Let f(w,b) be the expected number of steps to get from w white and b black balls to a situation with all balls of the same color. Also, let g(w) be f(w,b)=f(w,n-w) as a function of n=b+w. As Douglas observed for b \le 100 and Uri proved for all b, f(1,b)=2^b-1 (i.e. g(1)=2^{n-1}-1) It appears that f(b,b)=2^{2b-1}(1+o(b)) of course f(b,b) \gt f(1,2b-1)=2^{2b-1}-1 so almost all the time is taken up trying to get past the final step. Some numerical data is at the end. Clearly • f(0,b)=0 • for w \gt 0, f(w,b)=1+\frac{w}{w+b}f(w-1,b+1)+\frac{b}{w+b}f(w+1,b-1) so • f(b,b)=1+f(b-1,b+1) and f(b-1,b)=\frac{2b-1}{b-1}(1+f(b-2,b+1)). For fixed n=b+w this system of equations is sufficient to find all the values f(w,n-w) formulas The first two observations above are • g(0)=0 • For w \gt 0, g(w)=1+\frac{w}{n}g(w-1)+\frac{n-w}{n}g(w+1) This is sufficient to find the ratio of each of the g(w) for fixed w to g(1) which we now know to be g(1)=2^{n-1}-1. However (since I wrote this before I knew a proof of the value for g(1)) let us just define g(1)=Z=Z(n). Then the first few equations are g(0)=0 g(1)=Z (by fiat) but also g(1)=1+\frac{n-1}{n}g(2)+\frac{1}{n}g(0) so g(2)=\frac{n}{n-1}Z-\frac{n}{n-1} g(2)=1+\frac{n-2}{n}g(3)+\frac{2}{n}g(1) so with a little work: g(3)=\frac{n^2-2n-2}{(n-1)(n-2)}Z-\frac{n(2n-1)}{(n-1)(n-2)} g(4)=\frac{n(n^2-5n+8)}{(n-1)(n-2)(n-3)}Z-\frac{n(3n^2-7n+8)}{(n-1)(n-2)(n-3)} g(5)=\frac{n^4-9n^3+28n^2-32n+24}{(n-1)(n-2)(n-3)(n-4)}Z-\frac{n(4n^3-21n^2+47n-18)}{(n-1)(n-2)(n-3)(n-4)} This can be carried as far as desired. I satisfied myself that$$g(w)=\frac{n^{w-1}-(\binom{n}{2}-1)n^{w-2}+o(n^{w-2})}{n^{w-1}-(\binom{n}{2})n^{w-2}+o(n^{w-2})}Z+o(n) \approx (1+\frac{1}{n}+\frac{w^2}{2n^2})Z.$$This seems to agree well with the numerical calculations. Numerical Results The exact values of f(b,b) for 1 \le b \le 19 are 1,8,37,{\frac {448}{3}},{\frac {1753}{3}},{\frac {11416}{5}},{\frac { 134471}{15}},{\frac {3713536}{105}},{\frac {4900661}{35}},{\frac { 35008504}{63}},{\frac {695863087}{315}},{\frac {10155396928}{1155}},{ \frac {121367279443}{3465}},$${\frac {898500004936}{6435}},{\frac { 1672315989611}{3003}},{\frac {100087214575616}{45045}},{\frac { 399474183415387}{45045}},{\frac {430350607437304}{12155}},{\frac { 15466270252272383}{109395}}$

and the base $2$ logs of these numbers are $0., 3., 5.20946, 7.22239, 9.19065, 11.1568, 13.1300, 15.1101, 17.0952, 19.0840, 21.0750,$$23.0678,25.0619, 27.0570, 29.0529, 31.0491, 33.0461, 35.0432, 37.0408$

For $20$ balls the exact expected number of steps to get to all the same color is

$555690+\frac{29}{63}={\frac {35008504}{63}},{\frac {35008441}{63}},{\frac {11669408}{21}}, {\frac {3889749}{7}},{\frac {1666984}{3}},{\frac {5000563}{9}},{\frac {4999360}{9}},{\frac {4994503}{9}},551880,524287,0.$

So $f(1,19)=2^{19}-1=524,287$ steps expected for a $1/19$ white/black split. An additional $27,593$ expected steps for $f(2,18)$ an $18/2$. In more detail the increases are $1., 3.44444, 7.66667, 17.0952, 43.2222, 133.667, 539.667, 3064.78, 27593, 524287$ are the expected numbers of additional steps. So $f(10,10)$ is (of course) one more than $f(9,11)$ which is $3.44$ more than $f(8,12)$ etc.

-
If the exact value for $(n-1,1)$ is $2^{n-1}-1$, then the exact value for $(n-2,2)$ is $\frac{n}{n-1}(2^{n-1}-2)$. Similarly, one can work out more complicated expressions for the exact value for $(n-3,3)$, etc. however, I don't see the general form. Mathematica's RSolve spits out a page of things involving Hypergeometric2F1Regularized. If you can verify that starting with $a(0)=0, a(1) = 2^{n-1}-1$ and the recurrence $a(k) = 1 + \frac{k}{n} a(k-1) + \frac{n-k}{n} a(k+1)$ that $a(n-1) = 2^{n-1}-1$ then this solves the problem for $2$ colors, and provides a nice lower bound for everything. –  Douglas Zare May 15 '13 at 0:39
aha, you are quite right. It isn't that $a(n-1)=2^{n-1}-1$ exactly. But probably (likely not hard, but haven't checked it) for fixed $k \ge 1$ and arbitrary $n$ we have $a(k)=\frac{A(n)2^{n-1}+B(n)}{C(n)}$ where $A,B,C$ are all monic of degree $k$. –  Aaron Meyerowitz May 15 '13 at 1:53
The denominator is something like $(n-1)(n-2)...(n-k)$, but the polynomials in the numerator are more complicated, and the variations I tried on the coefficients didn't show up in the OEIS. –  Douglas Zare May 15 '13 at 5:55
An exact asymptotic answer for rule 1 of $2^{n-1}$ sounds perfect. I wonder if rule 2 has an attractive asymptotic answer too. –  navid May 16 '13 at 19:03