TITLE: Sherman Morrison Formula for hermitian updates
QUESTION [1 upvotes]: I have a problem in which, in principle I can apply twice Sherman-Morrison formula but it seems to me that for this case, there should be a simpler solution so my question is "May the process described below simplified thanks to the fact that the matrix is Hermitian?". Moreover, invertibility of the matrices is known (for the particular matrices I use) never to be a problem (it is a consequence of some existence and uniqueness theorem).
Suppose I have an infinite hermitian matrix $A=(a_{i,j})_{i,j=0}^{\infty}$ and I want to find the inverses of the right-up corner diagonal matrices $A_n= (a_{i,j})_{i,j=0}^n$ for each value of $n$.
I could decompose $A_{n+1}$ as an $n \times n$ block containing $A_n$, $u:= ((a_{i,n+1})_{i=0}^n,0)$, $u^*$, the conjugate transpose of $u$, and the corner element $a_{n+1,n+1}$.
Call $B$ to the matrix containing the blocks $A_{n}$ and $a_{n+1,n+1}$ but zeros on the other positions. Then $B^{-1}$ is a matrix with blocks $A_n^{-1}$, a vector of zeros, and its transposed and $a_{n+1,n+1}^{-1}$.
Define $C$ the matrix equal to $B$ except that we update the last column by summing $u$ (so $C$ is also equal to $A_{n+1}$ substituting $u^*$ by zeros). From that, Sherman-Morrison formula, gives me the inverse of the matrix $C$, $C^{-1}$, depending on $B^{-1}$ and $u$ (the summing of a vector process can be considered as summing the matrix which is result of multiplying pointwise a vector $(0,...,0,1)$ with $((a_{i,n+1})_{i=1}^n,0)$).
Once I have the inverse of $C$, I can repeat the process to update with the transpose conjugate vector $u^*$ and form a matrix $D$ and apply Sherman-Morrison formula to obtain $D^{-1}$ from $C^{-1}$, and the elements of $u^*$.
It seems like the fact that everything is hermitian would be useful to reduce the number of steps here, right?
If I can work in abstract with this inversion process, this would have important applications in complex analysis.

REPLY [0 votes]: I'm not sure the fact that the matrix is Hermitian simplifies things much.  Rather than the Sherman-Morrison formula, use the more general Woodbury matrix identity, essentially reducing the problem to the solution of a 2x2 matrix.
A simplified version of it should work for you:
$$\left(B+CR\right)^{-1}=B^{-1}-B^{-1}C\left(I+RB^{-1}C\right)^{-1}RB^{-1}$$
Where:
$$B=\pmatrix{A_n&0\\0&a_{n+1,n+1}}$$
$$C=\pmatrix{u&e_{n+1}}$$
$$R=\pmatrix{e_{n+1}^*\\u^*}$$
And $e_{n+1}$ is the component unit vector (all $0s$ except the last coefficient which is $1$):
$$e_{n+1}=\pmatrix{0\\\vdots\\0\\1}$$
Let us define $v$ as $u$ with the last coefficient ($0$) dropped, so:
$$u=\pmatrix{v\\0}$$
$$C=\pmatrix{v&0\\0&1}$$
$$R=\pmatrix{0&1\\v^*&0}$$
$$I+RB^{-1}C=I+\pmatrix{0&1\\v^*&0}\pmatrix{A_n^{-1}&0\\0&a_{n+1,n+1}^{-1}}\pmatrix{v&0\\0&1}=\pmatrix{1&a_{n+1,n+1}^{-1}\\v^*A_n^{-1}v&1}$$
$$\left(I+RB^{-1}C\right)^{-1}=\frac{1}{1-a_{n+1,n+1}^{-1}v^*A_n^{-1}v}\pmatrix{1&-a_{n+1,n+1}^{-1}\\-v^*A_n^{-1}v&1}$$
$$C\left(I+RB^{-1}C\right)^{-1}R=\frac{1}{1-a_{n+1,n+1}^{-1}v^*A_n^{-1}v}\pmatrix{-a_{n+1,n+1}^{-1}vv^*&v\\v^*&-v^*A_n^{-1}v}$$
$$B^{-1}C\left(I+RB^{-1}C\right)^{-1}RB^{-1}=\frac{\pmatrix{-a_{n+1,n+1}^{-1}A_n^{-1}vv^*A_n^{-1}&a_{n+1,n+1}^{-1}A_n^{-1}v\\a_{n+1,n+1}^{-1}v^*A_n^{-1}&-a_{n+1,n+1}^{-2}v^*A_n^{-1}v}}{1-a_{n+1,n+1}^{-1}v^*A_n^{-1}v}$$
Or slightly cleaner:
$$B^{-1}C\left(I+RB^{-1}C\right)^{-1}RB^{-1}=\frac{\pmatrix{-A_n^{-1}vv^*A_n^{-1}&A_n^{-1}v\\v^*A_n^{-1}&-a_{n+1,n+1}^{-1}v^*A_n^{-1}v}}{a_{n+1,n+1}-v^*A_n^{-1}v}$$
And there you have your correction matrix which you subtract from $B^{-1}$ to get $A_{n+1}^{-1}$.
$$A_{n+1}^{-1}=\pmatrix{A_n^{-1}&0\\0&a_{n+1,n+1}^{-1}}-\frac{\pmatrix{-A_n^{-1}vv^*A_n^{-1}&A_n^{-1}v\\v^*A_n^{-1}&-a_{n+1,n+1}^{-1}v^*A_n^{-1}v}}{a_{n+1,n+1}-v^*A_n^{-1}v}$$
$$A_{n+1}^{-1}=\pmatrix{A_n^{-1}+\frac{A_n^{-1}vv^*A_n^{-1}}{a_{n+1,n+1}-v^*A_n^{-1}v}&\frac{-A_n^{-1}v}{a_{n+1,n+1}-v^*A_n^{-1}v}\\\frac{-v^*A_n^{-1}}{a_{n+1,n+1}-v^*A_n^{-1}v}&\frac{1}{a_{n+1,n+1}-v^*A_n^{-1}v}}$$
Computationally, the fact that $A$ is Hermitian simplifies things since $v^*A_n^{-1}$ is the Hermitian of $A_n^{-1}v$, but it may not simplify your theoretical work.


TITLE: Determinant of a $4\times4$ invertible matrix
QUESTION [1 upvotes]: Let $A$ be a $4$ by $4$ invertible matrix, such that $\det(3A)=3\det(A^4)$.
Then $\det(A)=3$.
Would somebody please give me some clues on this?
Thanks

REPLY [2 votes]: $3det(A^4) = 3(detA)^4$
$= det(3A) = 3^4det(A)$
$(detA)^4 - 27 det(A) = 0$
Since $A$ is invertible we can divide by $det(A)$
$(detA)^3 =27$
$detA = 3$


TITLE: Probability all Bernoulli random variables take value $1$ with limited independence
QUESTION [4 upvotes]: Let $S_1,\dots, S_n$ be Bernoulli random variables which are $4$-wise independent. We have that for each $i$, $P(S_i  = 1) = p$ for some fixed probability $0 < p < 1$.  What can we say about  $P(\forall i\; S_i= 1)$ in terms of upper  and lower  bounds?

Clearly $P(\forall i\; S_i= 1) \geq p^n$ but what is the largest it can be?

REPLY [7 votes]: This has been treated in the literature:
http://arxiv.org/pdf/0801.0059v3.pdf
also see
http://arxiv.org/pdf/1201.3261.pdf
In particular, the upper bound goes to 0, but only polynomialy in $n$.


TITLE: beads in a string with restrictions
QUESTION [1 upvotes]: Using the principle of inclusion and exclusion; let $p,q\in \mathbb{N}$, being $p$ odd, there are $pq$ beads of $q$ different colors, with $p$ beads in each color. If the beads of the same colour are identical, in how many ways can this beads be put in a string in such a way that beads of the same colour must be in two separate blocks?
the answer is $${1\over 2}\left[ {p\over 2}\right]^q\left(\sum_{i=0}^q(-1)^i{q\choose i}2^i(2q-i)!\right)$$ but I don't know why

REPLY [0 votes]: First we need to answer an auxiliary question, which is: given $i$ items with $i+1$ gaps surrounding them/between them, where each gap consists of a sequence of cells, what is the number of ways to distribute $m$ cells in total into these gaps? This is seen to have generating function $$ f(z) = \frac{1}{(1-z)^{i+1}}$$ and hence the count is given by
$$[z^m]  \frac{1}{(1-z)^{i+1}} = {m+i\choose m} = {m+i\choose i}.$$ (A similar calculation is at this MSE link.)
Second, solve the problem of having two items of each of $q$ colors and count all sequences where two items of the same color may not be adjacent. Here the base sets $A_j$ for inclusion-exclusion count the number of sequences where color $j$ is adjacent. This gives for the intersection terms $$|A_r\cap A_s\cap\cdots|$$ of $i$ colors the cardinality
$${q\choose i} \times i! \times {2q-2i+i\choose i} \times {2q-2i\choose 2,2,\ldots, 2}$$
because we must choose the $i$ adjacent colors from the $q$ colors total, consider all their permutations, distribute the $2q-2i$ remaining items into $i+1$ spaces and fill these with the $2q-2i$ items. (This will count the sequences where at least the $i$ chosen colors are adjacent.)
Simplifying we get
$${q\choose i} \times i! \times \frac{(2q-i)!}{(2q-2i)!\times i!}
\times \frac{(2q-2i)!}{2^{q-i}}
= {q\choose i} \frac{(2q-i)!}{2^{q-i}}.$$
Substituting this into the inclusion-exclusion formula yields
$$\sum_{i=0}^q {q\choose i} (-1)^i \frac{(2q-i)!}{2^{q-i}}
= \frac{1}{2^q} \sum_{i=0}^q {q\choose i} \times(-1)^i\times 2^i\times (2q-i)!$$
This sequence starts out like this:
$$0, 2, 30, 864, 39480, 2631600, 241133760, 29083420800, 4467125013120, 851371260364800,\ldots$$
and we find that we have A114938 from the OEIS.
Third, to conclude, note when there are $p$ instances of each color the two blocks may have the dimensions $(1,p-1),(2,p-2),(3,p-3),\cdots,(p-2,2),(p-1,1),$so there are $p-1$ pairs, giving the formula
$$\frac{(p-1)^q}{2^q}
 \sum_{i=0}^q {q\choose i} \times(-1)^i\times 2^i\times (2q-i)!$$
But since $p$ is odd we have
$$\Big\lfloor\frac{p-1}{2}\Big\rfloor = \Big\lfloor\frac{p}{2}\Big\rfloor$$ giving
$$\Big\lfloor\frac{p}{2}\Big\rfloor^q
 \sum_{i=0}^q {q\choose i} \times(-1)^i\times 2^i\times (2q-i)!,$$
which may be prepended with a multiplier of $1/2$ if reflective symmetry of the string is considered (with $p$ being odd two blocks of the same color cannot be mapped onto each other by a reflection).
The following Maple program may be used to verify the solution to part two for values up to $q=5.$

with(combinat,permute);

w :=
proc(n)
    local p, obj, r, adm, pos;
    option remember;

    r := 0;

    obj :=[seq(k,k=1..n),seq(k,k=1..n)];

    for p in permute(obj) do
        adm := true;

        for pos from 1 to 2*n-1 do
            if p[pos] = p[pos+1] then
                adm := false;
                break;
            fi;
        od;

        if adm then r := r+1 fi;
    od;

    r;
end;

w2 := q -> 1/2^q*sum(binomial(q,i)*(-1)^i*2^i*(2*q-i)!,i=0..q);


TITLE: Why to simplify $\sin x - 1 =\cos x$ you have to multiply both side by $(\frac{\sqrt 2}{2}) $?
QUESTION [1 upvotes]: Why do you have to multiply both side of $$\sin x - 1 = \cos x$$
by:
$$(\frac{\sqrt 2}{2}) $$ to simplify it?
I am doing Shaum's pre-calculus and the final answer to this question is: π but I have no clue where the idea of multiplying by $(\frac{\sqrt 2}{2})$ came from. Like what is the taught process behind it?

REPLY [2 votes]: Another solution you can consider is $$\sin x -\cos x = 1$$ then square both sides to get $$\sin^2x - 2\sin x \cos x + \cos^2x = 1$$ so $$-2\sin x \cos x  = 0$$
This is equivalent to $\sin(2x) = 0$, so $x$ is any $\frac{n\pi}{4}$ , $n \in \mathbb{Z}$
However, a danger with this approach is that you may introduce extra solutions; as when $$\sin^2x - 2\sin x \cos x + \cos^2x = 1$$ this also introduces $$\sin x -\cos x = -1$$ as possible roots.


TITLE: False proof of 0=1 using Laurent series
QUESTION [2 upvotes]: I found the following proof that 0 = 1:
\begin{align*}
\sum_{n=-\infty}^{\infty} 0\cdot z^n = 0 = \frac{1}{z-1} + \frac{1}{1-z} = \frac{1}{z}\frac{1}{1-\frac{1}{z}} + \frac{1}{1-z} \\
= \frac{1}{z} \sum_{n=0}^{\infty}\frac{1}{z^n} + \sum_{n=0}^{\infty}z^n = \sum_{n=-\infty}^{\infty} 1\cdot z^n
\end{align*}
from which it follows that 0 = 1. In every step, I can't find an error. If we take $f(z) = \frac{1}{z-1} + \frac{1}{1-z}$, then it is holomorfic on the disk around 0 with radius 1 (B(0,1)).The principal part $h(z)$ would be $\frac{1}{z-1}$, which is also holomorfic on $\mathbb{C}\backslash B[0,1]$ and also $h(z)$ tends to 0 if $|z|$ tends to $\infty$. So I can't see what is going wrong.

REPLY [1 votes]: The equality $\dfrac{1}{z}\dfrac{1}{1-\frac{1}{z}} + \dfrac{1}{1-z}
= \dfrac{1}{z} \sum \limits_{n=0}^{\infty}\dfrac{1}{z^n} + \sum \limits_{n=0}^{\infty}z^n$ only holds if $z\not \in \{0,1\}$, $\left|\frac 1 z\right|<1$ and $|z|<1$, i.e., never.


TITLE: How are units handled general relativity? How are units handled in curvilinear coordinate systems?
QUESTION [0 upvotes]: I'm having trouble understanding how the units of distance are handled when we think of (non-Cartesian) coordinates on a spacetime manifold. All sources I know of seem to brush this question under the rug.
My main thought-process/confusion comes down to the following:

Since coordinates determine positions, I would think that the values of the coordinates would come with units of length. So if we have a point $p\in M$ and a local coordinate system $(U, (x^{\mu}))$ about $p$, we would have $p = (cx^{0}, x^{1}, x^{2}, x^{3})$ with something like
$$ cx^{0} = 2\text{ m},\; x^{1} = -1.5\text{ m},\; x^{2} = 4\text{ m},\; x^{3} = 10\text{ m} $$
as an example.
However, we're thinking about coordinates in general, so they're arbitrary and I can imagine rescaling them any way I want. This line of reasoning ends up conflicting with the previous bullet point, because if I could rescale them, then there is no meaning to the units of meters that are invoked here. By this reasoning, coordinate values must be unitless.

The waters here become more muddied when we try to think about velocity vectors of curves. If we assume the values of coordinates are unitless, then I can take any curve $q:[0, 1]\rightarrow M$ with $q(t) = (q^{0}(t), \ldots, q^{3}(t))$, and then take the derivative to get
$$\dot{q}(t) = \dot{q}^{\mu}(t) \dfrac{\partial}{\partial x^{\mu}}$$
as a velocity vector of $q(t)$. Now if the components $q^{\mu}(t)$ are unitless, then $\dot{q}^{\mu}(t)$ must have units of inverse seconds $\text{1/s}$. This makes very little sense, because nowhere else in physics do we say that the units of velocity are inverse seconds instead of meters/seconds.
My worries come down to the following questions:

If I wanted to includes units in my calculations in GR, where do the units of position go? Is the first bullet point correct or the second (or neither)?

Is there a consistent system of units that resolves the dilemmas that I mentioned?

An answer to any one of the questions would be very helpful.

Edit: I thought I'd put an idea out there before I forget it. Perhaps we can consider the coordinates as unitless, but then assign length units to the components of the metric, so we'd have something like $g_{00} = 3\;\text{m}^2, \; g_{10} = 2\;\text{m}^2$, etc as an example. This would make sense because any calculation of a physically meaningful quantity involving distance would invoke the metric tensor.
Edit 2: This post gives some units of various objects in the case where the coordinates have a length unit to them.
Edit 3: Based off of J. Murray's reply, I gather that what's going on is that there are two conventions. One convention is that you leave the coordinates unitless, but then take the components of the metric with units of length squared (or radians squared, etc). The other convection is that you attach units to the coordinates and leave the components of the metric as unitless. As long as you are consistent and keep track of units, either convention works.
This is sort of similar to have some people choose $(+, -, -, -)$ for the Minkowski metric signature and some people choose $(-, +, +, +)$. Either one works as long as you're consistent and keep track of the signs.
Edit 4: I think my problem here is that we haven't defined what a meter would even mean in the context of curvilinear coordinates (especially if the coordinates gridlines aren't geodesics). I'm temped to say they are just mere labels or notational aid, but that can't be true. If this were just a matter of arbitrary labeling, then I could take coordinates with meter units, and then resize the coordinates so that 1 meter actually meant 1 yard. Clearly that's absurd, but I haven't seen anyone explain exactly what's wrong with doing that.

REPLY [3 votes]: You can use whatever units you'd like in your coordinates.  However, the infinitesimal spacetime interval
$$\mathrm ds^2 = g_{\mu\nu} \mathrm dx^\mu \mathrm dx^\nu$$
has dimensions of length squared.  As a result, whatever choice of units or dimensions you make in your coordinates are reflected in the components of the metric.  For example, if you choose Cartesian coordinates expressed in meters, then the metric components $g_{\mu\nu}= \mathrm{diag}(-1,1,1,1)$ are dimensionless.  If you choose polar coordinates $(r,\theta,\phi)$, then $g_{\mu\nu} = \mathrm{diag}\big(-1,1,r^2, r^2\sin(\theta)\big)$, and the latter two components have dimensions of length squared in accordance with $(\theta,\phi)$ being dimensionless.

I gather that what's going on is that there are two conventions. One convention is that you leave the coordinates unitless, but then take the components of the metric with units of length squared (or radians squared, etc). The other convection is that you attach units to the coordinates and leave the components of the metric as unitless.

It's not a binary choice of convention, it's just a choice of units.  In ordinary cartesian coordinates, all of the coordinates have dimensions of length and the corresponding metric components are dimensionless.  You could divide all of these coordinates by a characteristic length $L$ if you wanted, in which case all of your new coordinates would be dimensionless and your metric components would be scaled by $L^2$.  You could make your time component $t$ instead of $ct$, in which case it would have dimensions of time and the metric component $g_{00}$ would gain a factor of $c^2$.
There are plenty of coordinate choices which are mixed as well.  In spherical polar coordinates, some coordinates have dimensions of length ($ct$ and $r$) and some coordinates are dimensionless ($\theta$ and $\phi$).
At the end of the day, a choice of coordinates is simply a way to assign a collection of numerical labels to a spacetime event.  You can do this in just about any way you can imagine as long as choice of labels is continuous and unambiguous.

I'm temped to say they are just mere labels or notational aid, but that can't be true. If this were just a matter of arbitrary labeling, then I could take coordinates with meter units, and then resize the coordinates so that 1 meter actually meant 1 yard. Clearly that's absurd, but I haven't seen anyone explain exactly what's wrong with doing that.

There's nothing wrong with that at all.  However, if you do that then your metric tensor components are going to be rescaled accordingly, so physical distances (e.g. $\mathrm ds = \sqrt{g_{\mu\nu} dx^\mu dx^\nu}$ ) are unchanged.


text:
\begin{document}

\pagenumbering{arabic}
\pagestyle{headings}
\def\sof{\hfill\rule{2mm}{2mm}}
\def\llim{\lim_{n\rightarrow\infty}}

\title{Combinatorial Identities for Incomplete Tribonacci Polynomials}
\maketitle

\begin{center}
\author{Mark Shattuck\\
\small Department of Mathematics, University of Tennessee, Knoxville, TN 37996\\[-0.8ex]
\small\texttt{shattuck@math.utk.edu}\\[1.8ex]}
\end{center}

\section*{abstract}

The incomplete tribonacci polynomials, denoted by $T_n^{(s)}(x)$, generalize the usual tribonacci polynomials and were introduced in \cite{JR2}, where several algebraic identities were shown.  In this paper, we provide a combinatorial interpretation for $T_n^{(s)}(x)$ in terms of weighted linear tilings involving three types of tiles.  This allows one not only to supply combinatorial proofs of the identities for $T_n^{(s)}(x)$ appearing in \cite{JR2} but also to derive additional identities.  In the final section, we provide a formula for the ordinary generating function of the sequence $T_n^{(s)}(x)$ for a fixed $s$, which was requested in \cite{JR2}.  Our derivation is combinatorial in nature and makes use of an identity relating $T_n^{(s)}(x)$ to $T_n(x)$.\\

\noindent{Keywords}: tribonacci numbers, incomplete tribonacci polynomials, combinatorial proof

\noindent{2010 Mathematics Subject Classification}: 05A19, 05A15

\section{Introduction}

The \emph{tribonacci numbers} $t_n$ are defined by the recurrence relation $t_n=t_{n-1}+t_{n-2}+t_{n-3}$ if $n \geq 3$, with initial values $t_0=0$ and $t_1=t_2=1$.  See sequence A000073 in OEIS \cite{Sl}.  The tribonacci numbers are given equivalently by the explicit formula
\begin{equation}\label{ine1}
t_{n+1}=\sum_{i=0}^{\left\lfloor\frac{n}{2}\right\rfloor}B(n-i,i), \qquad n \geq 0,
\end{equation}
where $B(n,i)=\sum_{j=0}^i \binom{i}{j}\binom{n-j}{i}$, as shown in \cite{B}.  The number $B(n,i)$ is the $n$-th row, $i$-th column entry of the \emph{tribonacci triangle} (see \cite{AH}).

The \emph{tribonacci polynomials} $T_n(x)$ were introduced in \cite{HB} and are defined by the recurrence $T_n(x)=x^2T_{n-1}(x)+xT_{n-2}(x)+T_{n-3}(x)$ if $n \geq 3$, with initial values $T_0(x)=0$, $T_1(x)=1$, and $T_2(x)=x^2$.  In analogy to \eqref{ine1}, the tribonacci polynomials are given by the following explicit formula (see \cite{JR2}):
\begin{equation}\label{ine2}
T_{n+1}(x)=\sum_{i=0}^{\left\lfloor\frac{n}{2}\right\rfloor}\sum_{j=0}^i \binom{i}{j}\binom{n-i-j}{i}x^{2n-3(i+j)}.
\end{equation}

The \emph{incomplete tribonacci polynomials} $T_n^{(s)}(x)$ were considered in \cite{JR2} and are defined as
\begin{equation}\label{ine3}
T_{n+1}^{(s)}(x)=\sum_{i=0}^{s}\sum_{j=0}^i \binom{i}{j}\binom{n-i-j}{i}x^{2n-3(i+j)}, \qquad 0 \leq s \leq \left\lfloor\frac{n}{2}\right\rfloor.
\end{equation}
Note that the incomplete tribonacci polynomials generalize the ordinary ones and reduce to them when $s=\left\lfloor\frac{n}{2}\right\rfloor$. The \emph{incomplete tribonacci number}, denoted by $t_n^{(s)}$, is defined as the value of $T_n^{(s)}(x)$ at $x=1$.  Incomplete Fibonacci numbers and polynomials have also been considered and are defined in a comparable way; see, e.g., \cite{PF,JR1}.  Some combinatorial identities for the incomplete Fibonacci numbers were given in \cite{BB} and a bi-periodic generalization was studied in \cite{JR3}.

In \cite{JR2}, several identities were derived for the incomplete tribonacci
numbers and polynomials using various algebraic methods.  In this paper, we supply combinatorial proofs of these identities using a weighted tiling interpretation of $T_n^{(s)}(x)$ (described in Theorem \ref{t1} below). In some cases, a further generalization of an identity can be given.  In addition, using our interpretation, one also can find other relations not given in \cite{JR2} that are satisfied by $T_n^{(s)}(x)$.  In the final section, we provide  an explicit formula for the generating function of $T_n^{(s)}(x)$, as requested in \cite{JR2}.  Our derivation is combinatorial in nature and makes use of some identities involving $T_n(x)$.

\section{Combinatorial interpretation for $T_{n}^{(s)}(x)$}

We will use the following terminology.  By a \emph{square}, \emph{domino}, or \emph{tromino}, we will mean, respectively, a $1 \times 1$, $2 \times 1$, or $3 \times 1$ rectangular tile.  A (linear) \emph{tiling} of length $n$ is a covering of the numbers $1,2,\ldots,n$ written in a row by squares, dominos, and trominos, where tiles of the same kind are indistinguishable.  Let $\mathcal{T}_n$ denote the set of all tilings of length $n$.  It is well known that $\mathcal{T}_n$ has cardinality $t_{n+1}$ (see, e.g., \cite[p. 36]{BQ}).  We will often represent squares, dominos, and trominos by the letters $r$, $d$, and $t$, respectively.  Thus, a member of $\mathcal{T}_n$ may be regarded as a word in the alphabet $\{r,d,t\}$ in which there are $n-2i-3j$, $i$, and $j$ occurrences of the letters $r$, $d$, and $t$, respectively, for some $i$ and $j$.

By a \emph{longer piece} within a member of $\mathcal{T}_n$, we will mean one that is either a domino or a tromino.  Given $0 \leq s \leq \left\lfloor\frac{n}{2}\right\rfloor$, let $\mathcal{T}_{n}^{(s)}$ denote the subset of $\mathcal{T}_n$ whose members contain \emph{at most} $s$ longer pieces.  For example, if $n=5$ and $s=1$, then $\mathcal{T}_5^{(1)}=\{r^5,dr^3,rdr^2,r^2dr,r^3d,tr^2,rtr,r^2t\}$. Note that $\mathcal{T}_n^{(s)}$ is all of $\mathcal{T}_n$ when $s=\left\lfloor\frac{n}{2}\right\rfloor$.  By a \emph{square-and-domino} tiling, we will mean a member of $\mathcal{T}_n$ that contains no trominos.

Given $\pi \in \mathcal{T}_n^{(s)}$, let $\delta(\pi)$ and $\nu(\pi)$ record the number of squares and dominos, respectively, in $\pi$.  We now provide a combinatorial interpretation of $T_{n+1}^{(s)}(x)$ in terms of linear tilings.

\begin{theorem}\label{t1}
The polynomial $T_{n+1}^{(s)}(x)$ is the distribution for the statistic $2\delta+\mu$ on $\mathcal{T}_n^{(s)}$.
\end{theorem}
\begin{proof}
First note that $T_{n+1}^{(s)}(x)$ may be written as
\begin{equation}\label{e1}
T_{n+1}^{(s)}(x)=\sum_{i=0}^s B(n-i,i)(x),
\end{equation}
where $B(n,i)(x)=\sum_{j=0}^i \binom{i}{j}\binom{n-j}{i}x^{2n-i-3j}$.  We next observe that when $x=1$, the polynomial $B(n,i)(x)$ gives the cardinality of the set $\mathcal{B}_{n,i}$ consisting of square-and-domino tilings of length $n$ in which the squares come in two colors, black and white, and containing $i$ dominos and white squares combined.  To see this, note that members of $\mathcal{B}_{n,i}$ containing exactly $j$ dominos are in one-to-one correspondence with words in the alphabet $\{D,W,B\}$ containing $j$ $D$'s, $i-j$ $W$'s, and $n-i-j$ $B$'s and thus have cardinality
$$\binom{n-j}{j,i-j,n-i-j}=\frac{(n-j)!}{j!(i-j)!(n-i-j)!}=\binom{n-j}{i}\binom{i}{j}.$$
Summing over $j$ gives
$$|\mathcal{B}_{n,i}|=\sum_{j=0}^i \binom{i}{j}\binom{n-j}{i}.$$

Given $\pi \in \mathcal{B}_{n,i}$, let $\delta_1(\pi)$ and $\delta_2(\pi)$ record the number of black and white squares, respectively. Thus, if $\pi \in \mathcal{B}_{n,i}$ has $j$ dominos, then
$$2\delta_1(\pi)+\delta_2(\pi)=2(n-i-j)+i-j=2n-i-3j.$$
Considering all $j$, this implies $B(n,i)(x)$ is the distribution on $\mathcal{B}_{n,i}$ for the statistic $2\delta_1(\pi)+\delta_2(\pi)$.
Suppose now $\lambda \in \mathcal{B}_{n-i,i}$ is given and contains $j$ dominos for some $j$, where $0 \leq i \leq s$.  We replace each domino of $\lambda$ with a tromino and each white square with a domino.  The resulting tiling $\lambda'$ belongs to $\mathcal{T}_n^{(s)}$ and has $j$ trominos, $i-j$ dominos, and $n-2i-j$ squares.  Thus we have
$$2\delta(\lambda')+\nu(\lambda')=2\delta_1(\lambda)+\delta_2(\lambda)$$
for all $\lambda \in \mathcal{B}_{n-i,i}$.  By \eqref{e1}, it follows that $T_{n+1}^{(s)}(x)$ is the distribution on $\cup_{i=0}^s \mathcal{B}_{n-i,i}$ for $2\delta_1+\delta_2$, equivalently, for the distribution of $2\delta+\nu$ on $\mathcal{T}_n^{(s)}$.
\end{proof}

\emph{Remark:} Taking $x=1$ in the prior theorem shows that the cardinality of $\mathcal{T}_n^{(s)}$ is $t_{n+1}^{(s)}$.  Taking $s=\left\lfloor\frac{n}{2}\right\rfloor$ shows that $T_{n+1}(x)$ is the distribution for $2\delta+\mu$ on all of $\mathcal{T}_n$.

Using our interpretation for $T_{n}^{(s)}(x)$, one obtains the following recurrence formula from \cite{JR2} as a corollary.

\begin{corollary}\label{t1c1}
If $n \geq 2s+1$, then
\begin{equation}\label{c1e1}
T_{n+3}^{(s)}(x)=x^2T_{n+2}^{(s)}(x)+xT_{n+1}^{(s)}(x)+T_n^{(s)}(x)-(xB(n-s,s)(x)+B(n-1-s,s)(x)).
\end{equation}
\end{corollary}
\begin{proof}
We will show that the right-hand side of \eqref{c1e1} gives the weighted sum of all the members of $\mathcal{T}_{n+2}^{(s)}$ with respect to the statistic $2\delta+\nu$ by considering the final piece.  The first term clearly accounts for all tilings ending in a square.  On the other hand, if a member of $\mathcal{T}_{n+2}^{(s)}$ ends in a longer piece, then there can be at most $s-1$ additional longer pieces.  From the proof of Theorem \ref{t1} above, we have for each $m$ that $B(m-s,s)(x)$ gives the weight of all members of $\mathcal{T}_m^{(s)}$ containing exactly $s$ longer pieces. Note that addition of a longer piece to the end of a tiling already containing $s$ longer pieces is not allowed.  Thus, by subtraction, the total weight of all members of $\mathcal{T}_{n+2}^{(s)}$ ending in a domino is given by $x(T_{n+1}^{(s)}(x)-B(n-s,s)(x))$ and the weight of those ending in a tromino by $T_{n}^{(s)}(x)-B(n-1-s,s)(x)$, which completes the proof.
\end{proof}

\section{Some identities of $T_{n}^{(s)}(x)$}

In this section, we provide combinatorial proofs of some identities involving the incomplete tribonacci polynomials that generalize those shown in \cite{JR2} using algebraic methods.  We also consider some further identities that can be obtained from the combinatorial interpretation given in Theorem \ref{t1}.

In this section and the next, by the \emph{weight} of a subset $S$ of $\mathcal{T}_n$ or $\mathcal{T}_n^{(s)}$, we will mean the sum $\sum_{\lambda\in S} x^{2\delta(\lambda)+\nu(\lambda)}$.

The $x=1$ case of the following identity was shown in \cite{JR2} by an inductive argument.

\begin{identity}\label{i1}
If $h \geq 1$ and $n \geq 2s+2$, then
\begin{equation}\label{i1e1}
\sum_{i=0}^{h-1}x^{2(h-i-1)}T_{n+i}^{(s)}(x)=\frac{1}{1+x^3}\left(T_{n+h+2}^{(s+1)}(x)-x^{2h}T_{n+2}^{(s+1)}(x)+x^{2h+1}T_n^{(s)}(x)-xT_{n+h}^{(s)}(x)\right).
\end{equation}
\end{identity}
\begin{proof}
We show equivalently
$$T_{n+h+2}^{(s+1)}(x)=(1+x^3)\sum_{i=0}^{h-1}x^{2(h-i-1)}T_{n+i}^{(s)}(x)+x^{2h}T_{n+2}^{(s+1)}(x)+xT_{n+h}^{(s)}(x)-x^{2h+1}T_n^{(s)}(x).$$
For this, we'll argue that the right-hand side gives the total weight of all the members of $\mathcal{T}_{n+h+1}^{(s+1)}$.  First note that $x^{2h}T_{n+2}^{(s+1)}(x)$ gives the weight of the members of $\mathcal{T}_{n+h+1}^{(s+1)}$ in which positions $n+2$ through $n+h+1$ are covered by squares (i.e., the right-most longer piece ends at position $n+1$ or before).  On the other hand, the weight of all members of $\mathcal{T}_{n+h+1}^{(s+1)}$ whose right-most longer piece starts at position $n+i-1$ for some $0 \leq i \leq h-1$ is given by $\left(x^{2(h-i)+1}+x^{2(h-i-1)}\right)T_{n+i}^{(s)}(x)$ since such tilings $\lambda$ are of the form $\lambda=\lambda'dr^{h-i}$ or $\lambda=\lambda'tr^{h-i-1}$ for some tiling $\lambda'$ of length $n+i-1$ where $r^m$ denotes a sequence of $m$ squares. Note that $\lambda' \in \mathcal{T}_{n+i-1}^{(s)}$ since the number of longer pieces in $\lambda'$ is limited to $s$.  Summing over $0 \leq i \leq h-1$ gives the indexed sum on the right-hand side.  Next, the term $xT_{n+h}^{(s)}(x)$ accounts for all members of $\mathcal{T}_{n+h+1}^{(s+1)}$ whose final piece is a domino which were missed in the sum.  Finally, members of $\mathcal{T}_{n+h+1}^{(s+1)}$  of the form $\lambda'dr^h$, where $\lambda'$ has length $n-1$, were accounted for by both the $x^{2h}T_{n+2}^{(s+1)}(x)$ term and by the $i=0$ term of the indexed sum; hence, we must subtract their weight, $x^{2h+1}T_n^{(s)}(x)$, to correct for this double count.  Combining all of the cases above completes the proof.
\end{proof}

The following identity from \cite{JR2} gives a formula for the sum of all the incomplete tribonacci polynomials of a fixed order.

\begin{identity}\label{i2}
If $n \geq 1$, then
\begin{equation}\label{i2e1}
\sum_{s=0}^\ell T_{n+1}^{(s)}(x)=(\ell+1)T_{n+1}(x)-\sum_{i=0}^\ell \sum_{j=0}^i i\binom{i}{j}\binom{n-i-j}{i}x^{2n-3(i+j)},
\end{equation}
where $\ell=\left\lfloor\frac{n}{2}\right\rfloor$.
\end{identity}
\begin{proof}
Let $\lambda \in \mathcal{T}_n$ and suppose that it contains exactly $k$ longer pieces, where $0 \leq k \leq \ell$.  Then the weight of $\lambda$ is counted by each summand of $\sum_{s=0}^\ell T_{n+1}^{(s)}(x)$ such that $s \geq k$.  That is, the tiling $\lambda$ is counted $\ell+1-k$ times by this sum.  The proof of Theorem \ref{t1}
above shows that the total weight of all members of $\mathcal{T}_n$ containing exactly $k$ longer pieces is given by
$$\sum_{j=0}^k \binom{k}{j}\binom{n-k-j}{k}x^{2n-3(k+j)},$$
upon considering the number $j$ of dominos.  Thus, the only inner sum in the double sum on the right-hand side of \eqref{i2e1} in which $\lambda$ is counted occurs when $i=k$ and here it is counted $k$ times (due to the extra factor of $i=k$).  Since $\lambda$ is clearly counted $\ell+1$ times by the term $(\ell+1)T_{n+1}(x)$, we have by subtraction that $\lambda$ is counted $\ell+1-k$ times by the right-hand side of \eqref{i2e1} as well.  Since $\lambda$ was arbitrary, the identity follows.
\end{proof}

The $x=1$ case of the following identity was conjectured in \cite{JR2} and follows from the generating function proof given in \cite{KP}.

\begin{identity}\label{i3}
If $n \geq 1$, then
\begin{equation}\label{i3e1}
\sum_{s=0}^{\ell} T_{n+1}^{(s)}(x)=(\ell+1)T_{n+1}(x)-\sum_{j=1}^{n-1}(xT_j(x)+T_{j-1}(x))T_{n-j}(x),
\end{equation}
\end{identity}
where $\ell=\left\lfloor\frac{n}{2}\right\rfloor$.
\begin{proof}
Suppose $\lambda \in \mathcal{T}_n$ has exactly $k$ longer pieces.  By the proof of the preceding identity, we need only show that the weight of $\lambda$ is counted $k$ times by the sum on the right-hand side of \eqref{i3e1}.  Note that $xT_j(x)T_{n-j}(x)$ gives the weight of all members of $\mathcal{T}_n$ in which a domino covers positions $j$ and $j+1$, while $T_{j-1}(x)T_{n-j}(x)$ gives the weight of those in which a tromino covers positions $j-1$, $j$, and $j+1$.  Thus, for each longer piece of $\lambda$, there is a term in the sum that counts the weight of $\lambda$, which implies that $\lambda$ is counted $k$ times by the sum, as desired.
\end{proof}

\emph{Remark:}  Comparing the $x=1$ cases of the preceding two identities, it follows that
$$\sum_{n\geq 1}a_nz^n=\frac{z^2+z^3}{(1-z-z^2-z^3)^2},$$
where
$$a_n=\sum_{i=0}^{\left\lfloor\frac{n}{2}\right\rfloor} \sum_{j=0}^i i\binom{i}{j}\binom{n-i-j}{i},$$
which can also be shown directly using the methods of \cite[Section 4.3]{W} (see \cite{KP}).

The next three identities follow from the combinatorial interpretation of $T_n^{(s)}(x)$ given in Theorem \ref{t1} and do not occur in \cite{JR2}.

\begin{identity}\label{i4}
If $n \geq 2s+1$, then
\begin{equation}\label{i4e1}
T_{n+1}^{(s)}(x)=\sum_{i=0}^s(x^{i+2}T_{n-2i}^{(s-i)}(x)+x^iT_{n-2i-2}^{(s-i-1)}(x)).
\end{equation}
\end{identity}
\begin{proof}
Suppose a member of $\mathcal{T}_{n}^{(s)}$ ends in exactly $i$ dominos, where $0 \leq i \leq s$.  If the right-most piece that is not a domino is a square, then the tiles coming to the left of this square constitute a member of $\mathcal{T}_{n-2i-1}^{(s-i)}$ and thus the weight of the corresponding subset of $\mathcal{T}_{n}^{(s)}$ is $x^{i+2}T_{n-2i}^{(s-i)}(x)$.  On the other hand, if the right-most non-domino piece is a tromino, then the tiles to the left of this tromino form a member of $\mathcal{T}_{n-2i-3}^{(s-i-1)}$ and thus the weight of the corresponding subset is $x^iT_{n-2i-2}^{(s-i-1)}(x)$.  Considering all possible $i$ gives \eqref{i4e1}.
\end{proof}

Our next formula relates the incomplete tribonacci polynomials to the trinomial coefficients.

\begin{identity}\label{i5}
If $n \geq 3s+1$, then
\begin{equation}\label{i5e1}
T_n^{(s)}(x)=\sum_{i=0}^s \sum_{j=0}^{s-i} \binom{s}{i,j,s-i-j}x^{2s-i-2j}T_{n-s-i-2j}^{(s-i-j)}(x).
\end{equation}
\end{identity}
\begin{proof}
Suppose that there are $i$ dominos and $j$ trominos among the final $s$ tiles within a member of $\mathcal{T}_{n-1}^{(s)}$, where $n \geq 3s+1$.  Then there are $\binom{s}{i,j,s-i-j}$ ways to arrange these tiles, which contribute $x^{2(s-i-j)+i}$ towards the weight, with the remaining tiles forming a member of $\mathcal{T}_{n-s-i-2j-1}^{(s-i-j)}$.  Considering all possible $i$ and $j$ gives \eqref{i5e1}.
\end{proof}

The incomplete Fibonacci polynomials introduced in \cite{JR1} are given as
$$F_n^{(s)}(x)=\sum_{r=0}^s \binom{n-r-1}{r}x^{n-2r-1}, \qquad 0 \leq s \leq \left\lfloor\frac{n-1}{2}\right\rfloor.$$
Our next identity relates the incomplete Fibonacci and tribonacci polynomials.

\begin{identity}\label{i6}
If $n \geq 2s$, then
\begin{equation}\label{i6e1}
T_{n+1}^{(s)}(x)=x^{n/2}F_{n+1}^{(s)}(x^{3/2})+\sum_{i=1}^{n-2}x^{(i-1)/2}\sum_{j=0}^{s-1} (T_{n-i-1}^{(j)}(x)-T_{n-i-1}^{(j-1)}(x))F_i^{(s-j-1)}(x^{3/2}).
\end{equation}
\end{identity}
\begin{proof}
First note that the weight of all members of $\mathcal{T}_n^{(s)}$ that contain no trominos is given by
$$\sum_{r=0}^s\binom{n-r}{r}x^{2n-3r}=x^{n/2}F_{n+1}^{(s)}(x^{3/2}).$$
So assume a member of $\mathcal{T}_n^{(s)}$ contains at least one tromino and that the left-most tromino covers positions $i$ through $i+2$.  Suppose further that there are exactly $r$ dominos to the left of the left-most tromino.  Then the weight of all such members of $\mathcal{T}_n^{(s)}$ is given by $\binom{i-r-1}{r}x^{2i-3r-2}T_{n-i-1}^{(s-r-1)}(x)$. Summing over the possible $i$ and $r$ implies that the total weight of all the members of $\mathcal{T}_n^{(s)}$ containing at least one tromino is
$$\sum_{i=1}^{n-2}\sum_{r=0}^{s-1}\binom{i-r-1}{r}x^{2i-3r-2}T_{n-i-1}^{(s-r-1)}(x).$$

To obtain the expression in \eqref{i6e1}, we write $T_{n-i-1}^{(s-r-1)}$ as $\sum_{j=0}^{s-r-1}(T_{n-i-1}^{(j)}-T_{n-i-1}^{(j-1)})$, where $T_{n-i-1}^{(-1)}=0$.  We then obtain a total weight formula of
\begin{align*}
&\sum_{i=1}^{n-2}\sum_{r=0}^{s-1} \binom{i-r-1}{r}x^{2i-3r-2}\sum_{j=0}^{s-r-1}(T_{n-i-1}^{(j)}-T_{n-i-1}^{(j-1)})\\
&=\sum_{i=1}^{n-2}\sum_{j=0}^{s-1}(T_{n-i-1}^{(j)}-T_{n-i-1}^{(j-1)})\sum_{r=0}^{s-j-1}\binom{i-r-1}{r}x^{2i-3r-2}\\
&=\sum_{i=1}^{n-2}\sum_{j=0}^{s-1}(T_{n-i-1}^{(j)}-T_{n-i-1}^{(j-1)})x^{(i-1)/2}F_i^{(s-j-1)}(x^{3/2}),
\end{align*}
which gives \eqref{i6e1}.
\end{proof}

\section{Generating function formula for $T_n^{(s)}(x)$}

The generating function formula for the incomplete tribonacci numbers was found in \cite{JR2} and a formula was requested for the tribonacci polynomials.  The next result provides such a formula.  We remark that our method is more combinatorial than that used in \cite{JR2} in the case $x=1$ and thus supplies an alternate proof in that case.

\begin{theorem}\label{t2}
Let $Q_s(z)$ be the generating function for the incomplete tribonacci polynomials $T_n^{(s)}(x)$, where $n \geq 2s+1$.  Then
\begin{equation}\label{t2e1}
\frac{Q_s(z)}{z^{2s+1}}=\frac{T_{2s+1}(x)+(T_{2s-1}(x)+xT_{2s}(x))z+T_{2s}(x)z^2-z^2\left(\frac{x+z}{1-x^2z}\right)^{s+1}}{1-x^2z-xz^2-z^3}.
\end{equation}
\end{theorem}
\begin{proof}
Let $r_n=r_n(x)$ be given by
$$r_n=\sum_{j=0}^s \binom{s}{j}\binom{n+s-j-2}{s}x^{2n+s-3j-3}+\sum_{j=0}^s\binom{s}{j}\binom{n+s-j-3}{s}x^{2n+s-3j-6}, \qquad n \geq 3,$$
with $r_0=r_1=0$ and $r_2=x^{s+1}$.

We claim that $r_i(x)$ gives the total weight with respect to the statistic $2\delta+\nu$ of all the members of $\mathcal{T}_{i+2s}$ containing exactly $s+1$ longer pieces and ending in a longer piece, the subset of which we will denote by $\mathcal{A}$.  To show this, first note that $r_i(x)$ evaluated at $x=1$ is seen to give the number of square-and-domino tilings of length $i+s-2$ or $i+s-3$ in which squares are black or white and having exactly $s$ white squares and dominos combined.  We then increase the length of each white square and each domino by one and add a domino to the end if the original tiling had length $i+s-2$ and add a tromino to the end if it had length $i+s-3$.  This yields all members of $\mathcal{A}$ in a bijective manner and thus implies $r_i(x)$ at $x=1$ gives the cardinality of $\mathcal{A}$.  Note that members of $\mathcal{A}$ ending in a domino contain $i-j-2$ squares, $s-j+1$ dominos, and $j$ trominos for some $0 \leq j \leq s$, while members of $\mathcal{A}$ ending is a tromino contain $i-j-3$ squares, $s-j$ dominos, and $j+1$ trominos for some $j$.  Summing over $j$ then implies that $r_i(x)$ is the distribution for the statistic $2\delta+\nu$ on $\mathcal{A}$, as claimed.

By the interpretation for $r_i(x)$ just described, the product $r_i(x)T_{n-2s-i}(x)$ gives the total weight of all members of $\mathcal{T}_{n-1}$ containing at least $s+1$ longer pieces in which the $(s+1)$-st longer piece ends at position $i+2s$ since the final $n-2s-i-1$ positions of such a member of $\mathcal{T}_{n-1}$ may be covered by any tiling of the same length.  Summing over all possible $i$ then gives the total weight of all members of $\mathcal{T}_{n-1}$ containing \emph{strictly more} than $s$ longer pieces.  Subtracting from $T_n(x)$ thus gives the weight of all members of $\mathcal{T}_{n-1}$ containing \emph{at most} $s$ longer pieces and implies the following identity:
\begin{equation}\label{t2e2}
T_n^{(s)}(x)=T_n(x)-\sum_{i=0}^{n-2s-1}r_i(x)T_{n-2s-i}(x), \qquad n \geq 2s+1.
\end{equation}

In order to find a closed form expression for $Q_s(z)$ using \eqref{t2e2}, we express $T_n=T_n(x)$ as follows:
\begin{equation}\label{t2e3}
T_n=T_{n-2s}T_{2s+1}+T_{n-2s-1}(T_{2s-1}+xT_{2s})+T_{n-2s-2}T_{2s}, \qquad n \geq 2s+1.
\end{equation}
We provide a combinatorial proof of \eqref{t2e3} as follows.  Note that \eqref{t2e3} is clearly true if $s=0$ or if $n=2s+1$ since $T_0=T_{-1}=0$, so we may assume $s\geq 1$ and $n \geq 2s+2$.  Observe first that the $T_{n-2s}T_{2s+1}$ term gives the weight of all members of $\mathcal{T}_{n-1}$ in which there is no piece covering the boundary between positions $2s$ and $2s+1$.  On the other hand, the total weight of the members of $\mathcal{T}_{n-1}$ in which a domino covers this boundary is given by $xT_{n-2s-1}T_{2s}$.  Finally, if a tromino covers the boundary between positions $2s$ and $2s+1$, then that tromino covers either positions $2s-1$, $2s$, and $2s+1$ or positions $2s$, $2s+1$, and $2s+2$.  In the former case, the weight of the corresponding members of $\mathcal{T}_{n-1}$ is $T_{n-2s-1}T_{2s-1}$, while in the latter it would be $T_{n-2s-2}T_{2s}$.  Combining all of the cases above gives \eqref{t2e3}.

Multiplying both sides of the equation
$$T_n^{(s)}=T_{n-2s}T_{2s+1}+T_{n-2s-1}(T_{2s-1}+xT_{2s})+T_{n-2s-2}T_{2s}-\sum_{i=0}^{n-2s-1}r_iT_{n-2s-i}$$
by $z^n$ and summing over $n \geq 2s+1$ yields
$$\frac{Q_s(z)}{z^{2s}}=\left(T_{2s+1}+(T_{2s-1}+xT_{2s})z+T_{2s}z^2-\sum_{i\geq0}r_iz^i\right)
\cdot\sum_{n\geq1}T_nz^n.$$
The proof is completed by noting
$$\sum_{i\geq0}r_iz^i=z^2\left(\frac{x+z}{1-x^2z}\right)^{s+1}$$
and
$$\sum_{n\geq1}T_nz^n=\frac{z}{1-x^2z-xz^2-z^3},$$
the former being computed by the methods given in \cite[Section 4.3]{W}.
\end{proof}

Taking $x=1$ in the prior theorem yields the following result.

\begin{corollary}\label{t2c1}
Let $q_s(z)$ be the generating function for the incomplete tribonacci numbers $t_n^{(s)}$.  Then
\begin{equation}\label{t2e1}
\frac{q_s(z)}{z^{2s+1}}=\frac{t_{2s+1}+(t_{2s-1}+t_{2s})z+t_{2s}z^2-z^2\left(\frac{1+z}{1-z}\right)^{s+1}}{1-z-z^2-z^3}.
\end{equation}
\end{corollary}

\emph{Remark:} Equation \eqref{t2e1} appears as Theorem 8 of \cite{JR2}.  We note however that there was a slight misstatement of this theorem; in particular, there should be no $-2$ in the factor multiplying $z^2$ in the numerator on the right-hand side.

config: arxiv


TITLE: Broken Symmetry
QUESTION [3 upvotes]: I have a tangled web of ideas about natural transformations, vector spaces, equivalence classes, local coordinates, etc. in my head that I'm trying to unravel. So here are some of the questions I thought of:

Vector spaces: Why is it that in linear algebra we always calculate with basis but when we think of a definition we always try to make sure it is basis independent? What kinds of symmetries are we trying to preserve by this?
Categories: The obvious condition for natural transformations isn't so obvious to me and again I think the definition is the way it is because there is again some kind of symmetry that a natural transformation is preserving. What are the symmetries that a natural transformation is preserving?
Equivalence classes: Almost the same thing as in the vector space scenario. We do things with representatives but we make sure our definitions are true regardless of this choice. Ok, this one is kinda silly because we are trying to preserve $\cong$ so there isn't anything too complicated happening here.
Differential geometry: We again calculate with local coordinates but our definitions shouldn't depend on them. What symmetries are we trying to preserve in differential geometry?

So it seems to me we always break symmetry, whatever that means, when we want to work with something concrete but we try to make sure our calculations are preserved by these symmetries. Feel free to correct me and add your answers to some of my questions.
Edit: Dmitri gives a good answer for the definition of natural transformation in terms of the exponential and its adjoint.

REPLY [3 votes]: Your examples about vector spaces and differential geometry do not make any sense to me.
One does not need coordinates or bases to prove statements in linear algebra and differential geometry.
Personally, I always use coordinate- and basis-free proofs.
For me the reason to avoid coordinates and bases is that we lose geometric intuition whenever we use them.
See my manifesto on this matter here: When to pick a basis?
One way to make the definition of natural transformation more natural is to consider the category A
with exactly two objects and one non-trivial morphism between them.
Then the set of morphisms of an arbitrary category C is the set of functors Fun(A, C).
If we want the set of functors Fun(C, D) between two categories C and D to be a category,
then the set of morphisms of this category is Fun(A, Fun(C, D)).
But it is natural to assume that we have the standard adjunction Fun(A, Fun(C, D)) = Fun(A × C, D).
Unraveling the definition of functor from A × C to D yields precisely the usual axioms for natural transformations.


TITLE: Partial latin square with $\le n-1$ filled cells
QUESTION [1 upvotes]: How do we show that is $P$ if a $n\times n$ Latin square with $\le n-1$ filled cells, then $P$ can be completed to a proper Latin square?
Here is the definition of a Latin square.
(WHAT I HAVE DONE SO FAR: I have worked examples for $n=2,3,4$ but am unable to find a pattern that is rigorous, or any pattern for that pattern. A step-by step proof would be appreciated- or if you could tell me what facets here are of paramount importance when it comes to my observation.)
Could someone explain the inductive step in the link provided by Gerry Myerson in Theorem 5? I don't get it.

REPLY [2 votes]: You have a partial Latin square $P$ of order $m+1$ with exactly $m$ filled cells, and you’re assuming that the number of distinct symbols in $P$ is greater than $\frac{m+1}2$. If each of these symbols occurred in more than one cell, they would fill more than $m+1$ cells altogether, contradicting the assumption that $P$ has just $m$ filled cells. Thus, some symbol $s$ appears in exactly one cell of $P$. Here’s an example with $m=4$; I’ve marked the back diagonal in red.
$$\begin{array}{|c|c|c|c|c|}
\hline
&&&5&\color{red}\cdot\\ \hline
&&&\color{red}\cdot&\\ \hline
&&\color{red}\cdot&3&\\ \hline
&\color{red}\cdot&&&\\ \hline
\color{red}5&2&&&\\ \hline
\end{array}$$
At this point we use the second of the ‘key ideas’ identified at the top of p. 254 to conclude that the rows and columns of $P$ can be permuted to yield a new partial Latin square $Q$ of order $m+1$ with exactly $m$ filled cells in such a way that $s$ now lies on the back diagonal of $Q$, and the other filled cells of $Q$ lie above the back diagonal. Then we relabel the symbols so that $s$ becomes $m+1$. In my example I change the order of the rows from $12345$ to $13524$, bringing the lone $3$ to the back diagonal, relabel the $3$ as $5$, the $5$’s as $2$’s, and the $2$ as $3$ to get this:
$$\begin{array}{|c|c|c|c|c|}
\hline
&&&2&\color{red}\cdot\\ \hline
&&&\color{red}5&\\ \hline
2&3&\color{red}\cdot&&\\ \hline
&\color{red}\cdot&&&\\ \hline
\color{red}\cdot&&&&\\ \hline
\end{array}$$
The next step is to delete the $m+1$ on the back diagonal and the last row and last column. Note that the only cells in the last row and column that could possibly be filled at this point are the ones in the upper right and lower left corners, on the back diagonal, so the only symbol deleted in this step is the $m+1$ on the back diagonal. In the example above we’d be left with the following partial Latin square of order $4$:
$$\begin{array}{|c|c|c|c|c|}
\hline
&&&\color{blue}2\\ \hline
&&&\color{red}\cdot\\ \hline
\color{blue}2&\color{blue}3&\color{red}\cdot&\\ \hline
&\color{red}\cdot&&\\ \hline
\end{array}$$
The red dots mark the cells that were on the back diagonal of $Q$; the one just below the $2$ in the upper right corner is where the $\color{red}5$ was in $Q$. The blue cells are the entries retained from $Q$.
We now have a partial Latin square of order $m$ with $m-1$ filled cells; by the induction hypothesis, it can be completed to a Latin square $L$. In my example $L$ might be this Latin square:
$$\begin{array}{|c|c|c|c|c|}
\hline
1&4&3&\color{blue}2\\ \hline
3&2&4&1\\ \hline
\color{blue}2&\color{blue}3&1&4\\ \hline
4&1&2&3\\ \hline
\end{array}$$
Now construct the partial Latin square $P(L)$ of order $m+1$ as described at the bottom of p. 253 and top of p. 254: erase every symbol below the back diagonal of $L$ and add an empty last column and last row to get a partial Latin square of order $m+1$, and fill the back diagonal of this partial Latin square with the symbol $m+1$. In my example this produces the following partial Latin square $P(L)$, where the blue entries are those retained (or, in the case of the $5$, reintroduced) from $Q$:
$$\begin{array}{|c|c|c|c|c|}
\hline
1&4&3&\color{blue}2&5\\ \hline
3&2&4&\color{blue}5\\ \hline
\color{blue}2&\color{blue}3&5&\\ \hline
4&5&&\\ \hline
5\\
\hline
\end{array}$$
Next we apply the other of the two ‘key ideas’ mentioned at the top of the page to conclude that $P(L)$ can be completed.
One possible completion is this:
$$\begin{array}{|c|c|c|c|c|}
\hline
1&4&3&\color{blue}2&5\\ \hline
3&2&4&\color{blue}5&1\\ \hline
\color{blue}2&\color{blue}3&5&1&4\\ \hline
4&5&1&3&2\\ \hline
5&1&2&4&3\\
\hline
\end{array}$$
The blue cells, as before, show the cells retained from $Q$.
The final step is to reverse the relabelling and rearrangement of the rows and columns that took us from the original $P$ to $Q$. I changed $3$ to $5$, $5$ to $2$, and $2$ to $3$, so I must now change $3$ to $2$, $2$ to $5$, and $5$ to $3$:
$$\begin{array}{|c|c|c|c|c|}
\hline
1&4&2&\color{blue}5&3\\ \hline
2&5&4&\color{blue}3&1\\ \hline
\color{blue}5&\color{blue}2&3&1&4\\ \hline
4&3&1&2&5\\ \hline
3&1&5&4&2\\
\hline
\end{array}$$
I also have to reverse the permutation of the rows; this, finally, yields this Latin square:
$$\begin{array}{|c|c|c|c|c|}
\hline
1&4&2&\color{blue}5&3\\ \hline
4&3&1&2&5\\ \hline
2&5&4&\color{blue}3&1\\ \hline
3&1&5&4&2\\ \hline
\color{blue}5&\color{blue}2&3&1&4\\
\hline
\end{array}$$
This is clearly a completion of the original partial Latin square $P$.
Does this help, or were you more worried about the proofs of the two ‘key ideas’, for which the authors refer you to a paper by Lindner?