A seemingly easy combinatorics brain teaser

Question

So I have a brain teaser that goes like this:

There's a school that awards students that, during a given period, are never late more than once and who don't ever happen to be absent for three or more consecutive days. How many possible permutations with repetitions of presence (or lack thereof) can we build for a given timeframe that grant the student an award? Assume that each day is just a state On-time, Late or Absent for the whole day, don't worry about specific classes. Example: for three day timeframes, we can create 19 such permutations with repetitions that grant an award.

So I thought about it like that: first, we narrow down our possible space of solutions. We know that there are $2^n$ possible permutations with repetitions with no being late at all (cause then each of the $n$ days is just On-time or Absent) and $n\cdot2^{n-1}$ permutations with repetitions with exactly one Late state.

And here comes the hard part - we now have to subtract all the permutations with repetitions which hold 3 consecutive Absent days, 4 consecutive Absent days and so on. At first, I thought about something like that: there are $n - (k-1)$ ways to fit the $k$-day consecutive absency in a $n$-day timeframe with no Late states. Then, I fiddled with finding a formula for $k$-day consecutive absency for timeframes with exactly one Late state and I even started to find some kind-of-working-ish formulas like $2\cdot 3^{(n-k-1)}$ for 3-day consecutive absencies in timeframes with exactly one Late state but it shortly followed that (a) my reasoning was flawed, (b) I couldn't come up with anything generalised for $k$-day absencies and (c) I realized that both for this and for my $n - (k-1)$, I have to also keep in mind all the possible combinations the remaining days may take (for example, all can be On-time but also every second can be Absent, there can be more than one 3-day absency and so on) and all of these things we have to subtract.

I guess I went way too deep with it and surely there has to be some less twisted solution. How should I go about it?

Answer 1

Try building a recurrence relation. There are six distinct states that we want to track: the student can either have 'used' their late date or not, and there can be 0, 1, or 2 consecutive absent days at the end of the interval we're looking at. So let's use the labels e.g. $f_{p0}(n)$ ($p$ for $p$erfect) for the number of strings of days of length $n$ that have no tardies and end with a non-absent day, $f_{p1}(n)$ the number of strings of days, that have no tardies and end with exactly one absence, $f_{t0}(n)$ the number of strings of days that have used the tardy date and end with no absences, etc. Then (for instance) $f_{p2}(n)=f_{p1}(n-1)$ because we uniquely know the end of the string (it's an absence) and we know uniquely the string before that (it's a string of $n-1$ days with no tardies that ends in one absence). Similarly, $f_{p0}(n)=f_{p0}(n-1)+f_{p1}(n-1)+f_{p2}(n-1)$ because we know the last day is a non-absence (and there are no tardies) but the string before that point could end in anything (as long as there are no tardies in that substring).

From here, you could go on to build a generating function and find an exact formula for the result; I would be surprised if there's a very clean explicit formula (although there's likely a binomial sum similar to the one for the Fibonacci numbers), but the generating function should give you an explicit formula at least.

Answer 2

Following Steven Stadnicki, $f_{p0}(n), f_{p1}(n+1), f_{p2}(n+2)$ are all the Tribonacci numbers at index $n+2$ and $f_{t0}(n), f_{t1}(n+1), f_{t2}(n+2)$ are all he same. The total number of series is the sum of these, which is the same series one index down, but not found in OEIS. I just made an Excel sheet and looked up the series in OEIS.

Answer 3

ETA2: OK, I think it's fine.

ETA3: As Brian Scott discovered, the actual series is in error. I think the generating function is OK, though, as it correctly produces $200$ for six days.

The explicit formula is $2^{n+2}-F_{n+4}$ (where $F_n$ is the $n$th Fibonacci number, with $F_0 = 0, F_1 = 1$). So, for instance, for three days, we have $2^5-13 = 32-13 = 19$.

As one other respondent did, I cheated a little by using OEIS. I first created a generating function, considering that there are zero, one, or two absences, followed by any number of sequences of one on-time followed by zero, one, or two absences. Denoting on-times by $y$ and absences by $z$, we can write

$$ F(y, z) = \frac{1+z+z^2}{1-y(1+z+z^2)} $$

We then account for the possibility of late arrivals. If there are $k$ on-times, one of those (or none of them) can be replaced by a single late arrival. Thus, we would like to replace $y^k$ by $(k+1)y^k$. This can be accomplished by defining

$$ G(y, z) = \frac{\partial}{\partial y} yF(y, z) $$

and then by evaluating the Taylor series to the necessary degree, and collecting all the terms of like degree, we end up with an expression such as

$$ \begin{align} G(y, z) & = 1+(2y+z)+(3y^2+4yz+z^2) \\ & + (4y^3+9y^2z+6yz^2) \\ & + (5y^4+16y^3z+18y^2z^2+4yz^3) \\ & + (6y^5+25y^4z+40y^3z^2+21y^2z^3+2yz^4)+\cdots \end{align} $$

which yields the terms $1, 3, 8, 19, 43, 94, \ldots$. Whence (a miracle occurs—i.e., OEIS yields) $2^{n+2}-F_{n+4}$. There's probably a good recurrence explanation for this, but it's dinnertime.

Answer 4

In essence you want to know the number of ternary strings (strings consisting of $0$s, $1$s, and $2$s) of length $n$ that have at most one $0$ and do not have three or more consecutive $1$s. (In other words, a $0$ is a late, and a $1$ is an absent.) Let $A_n$ be the set of such strings, and let $a_n=|A_n|$. Let $B_n$ be the set of strings in $A_n$ that do not contain $0$, and let $b_n=|B_n|$.

If $\sigma\in A_n\setminus B_n$, then $\sigma$ contains exactly one $0$. If there are $k$ digits before the $0$, then there are $n-1-k$ digits after the $0$, so there are $b_k$ possibilities for the digits before the $0$ and $b_{n-1-k}$ for those after the $0$. These can be combined arbitrarily, so

$$|A_n\setminus B_n|=\sum_{k=0}^{n-1}b_kb_{n-1-k}\;,$$

and

$$a_n=|A_n|=|B_n|+\sum_{k=0}^{n-1}b_kb_{n-1-k}=b_n+\sum_{k=0}^{n-1}b_kb_{n-1-k}\;.$$

Now $b_n$ is just the number of binary strings of length $n$ that don’t contain $00$, and it’s well-known that this satisfies the recurrence

$$b_n=b_{n-1}+b_{n-2}+b_{n-3}$$

with initial conditions $b_0=1$, $b_1=2$, and $b_2=4$. (These are the tribonacci numbers with an offset subscript.) Thus, the recurrence

$$b_n=b_{n-1}+b_{n-2}+b_{n-3}+[n=0]+[n=1]+[n-2]$$

is valid for all $n$ if we set $a_n=0$ for $n<0$, where the last three terms are Iverson brackets. Multiplying through by $x^n$, summing over $n\ge 0$, and letting $g_B(x)=\sum_{n\ge 0}b_nx^n$, we have

$$\begin{align*} g_B(x)&=\sum_{n\ge 0}b_{n-1}x^n+\sum_{n\ge 0}b_{n-2}x^n+\sum_{n\ge 0}b_{n-3}x^n+1+x+x^2\\\\ &=x\sum_{n\ge 0}b_{n-1}x^{n-1}+x^2\sum_{n\ge 0}b_{n-2}x^{n-2}+x^3\sum_{n\ge 0}b_{n-3}x^{n-3}+1+x+x^2\\\\ &=(x+x^2+x^3)g_B(x)+1+x+x^2\;, \end{align*}$$

and hence

$$g_B(x)=\frac{1+x+x^2}{1-x-x^2-x^3}\;.$$

Now $\sum_{k=0}^{n-1}b_kb_{n-1-k}$ is the coefficient of $x^{n-1}$ in $\big(g_B(x)\big)^2$, so if $g(x)=\sum_{n\ge 0}a_nx^n$, then

$$\begin{align*} g(x)&=g_B(x)+x\big(g_B(x)\big)^2\\\\ &=g_B(x)\big(1+xg_B(x)\big)\\\\ &=\frac{1+x+x^2}{\left(1-x-x^2-x^3\right)^2}\;. \end{align*}$$

The generating function is reasonably nice, but the roots of the cubic in the denominator aren’t, so you don’t get a very nice closed form for the $a_n$. Here’s a table of the first few values of $a_n$ and $b_n$.

$$\begin{array}{rcc} n:&0&1&2&3&4&5&6&7&8\\ b_n:&1&2&4&7&13&24&44&81&149\\ a_n:&1&3&8&19&43&94&200&418&861 \end{array}$$

Sadly, this is not the same as OEIS A008466 with an offset subscript, though this fact doesn’t show up until $a_6$; thus, it’s not $2^{n+2}-F_{n+4}$.

Answer 5

Here is how I would go about it :

• Draw the graph for the state machine representing the process. It has 7 states, and 3 transitions departing from each state (One for O, one for L, one for A)
• Reduce the problem to finding how many walks lead me from the initial state to the final state (where I am denied the award)
• Apply the solution of the "Good Will Hunting" problem. (http://www.math.harvard.edu/archive/21b_fall_03/goodwill/)
• Substract the result from $3^n$.