\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage{amsfonts,amsmath,amssymb,amsthm}

\PassOptionsToPackage{obeyspaces}{url}
\usepackage[colorlinks=true,citecolor=blue,urlcolor=blue,linkcolor=blue,bookmarksopen=true]{hyperref}
\usepackage{tikz}

\usepackage{enumitem}
\setlist{itemsep=0.5em}

%% header definitions
\def\course{MATH/CMSC H395}
\def\assign{HW \#1}
\def\doclink{\url{https://mathematicaster.org/teaching/discrete2026/hw/hw1.tex}}
\def\due{Sep 14}

%% environments
% theorem style
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{defn}[theorem]{Definition}

% definition style
\theoremstyle{definition}
\newtheorem{problem}{Problem}

% custom
\newenvironment{solution}{\noindent\textbf{Solution.}}{\qed}

%% custom commands
\newcommand*{\arXiv}[1]{\href{http://arxiv.org/pdf/#1}{arXiv:#1}}       % arXiv link
\newcommand*{\eqdef}{\stackrel{\mbox{\normalfont\tiny{def}}}{=}}        % definition by equality
\newcommand*{\abs}[1]{\lvert #1\rvert}     % absolute values, cardinality
\newcommand*{\eps}{\varepsilon}            % prettier epsilon
\newcommand*{\R}{\mathbb{R}}               % real numbers
\newcommand*{\C}{\mathbb{C}}               % complex numbers
\newcommand*{\Q}{\mathbb{Q}}               % rational numbers
\newcommand*{\Z}{\mathbb{Z}}               % integers
\newcommand*{\N}{\mathbb{N}}               % natural numbers
\newcommand*{\F}{\mathbb{F}}               % field
\newcommand*{\family}{\mathcal{F}}         % family
\newcommand*{\GL}{\mathbf{GL}}             % general linear group
\newcommand*{\what}[1]{\widehat{#1}}       % wider hat
\newcommand*{\wbar}[1]{\overline{#1}}      % wider bar
\newcommand*{\mcal}[1]{\mathcal{#1}}       % mathcal
\newcommand*{\mbf}[1]{\mathbf{#1}}         % mathbf
\newcommand*{\mbb}[1]{\mathbb{#1}}         % mathbb

% operators
\let\Pr\relax\DeclareMathOperator*{\Pr}{\mathbf{Pr}}       % probability
\DeclareMathOperator*{\E}{\mathbb{E}}          % expectation
\DeclareMathOperator*{\Var}{\mathbf{Var}}      % variance
\DeclareMathOperator*{\Span}{span}             % span
\DeclareMathOperator{\tr}{tr}                  % trace
\DeclareMathOperator{\rank}{rank}              % rank
\DeclareMathOperator{\supp}{supp}              % support
\DeclareMathOperator{\diam}{diam}



\begin{document}
\pagestyle{empty}

\noindent
\begin{minipage}{.33\textwidth}
	\flushleft {\bf \course}
\end{minipage}
\begin{minipage}{.33\textwidth}
	\centering {\bf \assign}
\end{minipage}
\begin{minipage}{.33\textwidth}
	\flushright {\bf \due}
\end{minipage}
\vskip3pt
\hrule\hrule\hrule
\vskip5pt

\noindent {\footnotesize This document is from \doclink}
\vskip10pt

\noindent {\small
    Solutions must be typeset in \LaTeX.
    Collaboration is allowed, but must be fully acknowledged.
    Any collaboration should involve only discussion; all writing \textbf{must} be done individually.
    Use of generative AI is \textbf{forbidden}.
    You are free to use the result from any problem on this (or previous) assignment as a part of your solution to a different problem even if you have not solved the former problem.
}

\vskip20pt

\begin{problem}
    Tell me a little bit about yourself!
    \begin{itemize}
        \item What's your year and major?
        \item What other classes are you taking this semester?
        \item What are you most excited to learn in this class?
        \item Is there anything specific that you'd like to cover in this class?
    \end{itemize}
\end{problem}


\begin{problem}
    A function $f\colon [m]\to[n]$ is \emph{weakly increasing} if $i\leq j\implies f(i)\leq f(j)$.
    How many weakly increasing functions are there from $[m]$ to $[n]$?
    Justify your answer with a bijective argument.
\end{problem}


\begin{problem}
    Give a combinatorial proof that
    \[
        {m_1+m_2\choose n}=\sum_{k=0}^n{m_1\choose k}{m_2\choose n-k}.
    \]
\end{problem}


\begin{problem}
    Let $f_i(n)$ denote the number of permutations $\pi\in S_n$ which have exactly $i$ fixed points (that is, $\pi(x)=x$ for exactly $i$ choices of $x$).
    Give combinatorial proofs of the following identities:
    \begin{enumerate}
        \item $\displaystyle n!=\sum_{i=0}^n f_i(n)$.
        \item $\displaystyle n!=\sum_{i=0}^n i\cdot f_i(n)$.
    \end{enumerate}
\end{problem}


\begin{problem}
    Use the binomial theorem and some calculus to find formulas for the following expressions:
    \begin{enumerate}
        \item $\displaystyle\sum_{k=0}^n{n\choose k}k$
        \item $\displaystyle\sum_{k=0}^n{n\choose k}{1\over k+1}$
    \end{enumerate}
\end{problem}



\end{document}
