EasyCounts.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We want to count ordered pairs of functions $(f,g)$ that satisfy certain identities.  This notebook collects identities where there is a straightforward combinatorial counting argument for such pairs.\n",
    "\n",
    "First, let us look at $gf=f$, ([A239750](https://oeis.org/A239750)) which has been completely solved previously, but nicely illustrates the basic combinatorial reasoning for these problems.  Here $g$ is the identity on the image of $f$, and arbitrary elsewhere.  There are two ways of looking at this, first if $k$ is the size of the image of $f$ then there are $k!\\left\\{n\\atop k\\right\\}$ such functions $f$ and $n^{n-k}$ functions $g$ that are the identity on the image of $f$, so we have\n",
    "$$\\#(f,g)=\\sum_{k=0}^n\\binom{n}{k}\\left\\{n\\atop k\\right\\}k!\\; n^{n-k}.$$\n",
    "\n",
    "On the other hand, if we start with functions $g$ that are the identity on $k$ points, then $f$ must map into the points where $g$ is the identity.  There are ${(n-1)}^{n-k}$ such functions $g$, and $k^n$ such functions $f$ so we also have\n",
    "$$\\#(f,g)=\\sum_{k=0}^n\\binom{n}{k}k^n{(n-1)}^{n-k}$$\n",
    "\n",
    "Note that this also counts $gf=f^r$ for any $r>0$ as $g$ is completely specified on the image of $f$ and arbitrary elsewhere, exactly the same conditions we had for $r=2$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "[1, 1, 6, 87, 2200, 84245, 4492656, 315937195, 28186856832, 3099006365769]\n"
     ]
    }
   ],
   "source": [
    "def a239750_1(n):\n",
    "    return sum(binomial(n,k) * stirling_number2(n,k) * factorial(k) * n^(n-k) for k in srange(n+1))\n",
    "\n",
    "def a239750_2(n):\n",
    "    return sum(binomial(n,k) * k^n * (n-1)^(n-k) for k in srange(n+1))\n",
    "\n",
    "print all(a239750_1(n) == a239750_2(n) for n in range(20))\n",
    "print [a239750_2(n) for n in range(10)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, let us look at $gff=f$ ([A235328](https://oeis.org/A235328)).  Here, $f=g^{-1}$ on the image of $f$, in particular both $f$ and $g$ are invertible on the image of $f$.  If there are $k$ points in the image of $f$ then there are $k!$ ways of assigning $f$ on the image of $f$, which then completely specifies $g$ on the image of $f$.  On the points outside the image of $f$ there are $k^{n-k}$ ways of assigning $f$ since it must map into its image.  Since $f$ permutes the elements of the image of $f$, we know that every point in the image of $f$  is mapped by $f$ from some point in the image of $f$, so we do not need to worry about only mapping to a subset.  Finally $g$ is completely arbitrary outside the image of $f$ so there are $n^{n-k}$ ways of assigning it.  So combining everything we have\n",
    "$$\\#(f,g)=\\sum_{k=0}^n\\binom{n}{k}k!\\;(nk)^{n-k}.$$\n",
    "\n",
    "The same reasoning holds for $gf^r=f$ where $r>1$, as both $f$ and $g$ are still invertible on the image of $f$, and $g$ is arbitrary off the image of $f$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 1, 6, 69, 1336, 39145]\n",
      "[1, 1, 6, 69, 1336, 39145, 1598256, 85996561, 5872177536, 494848403793]\n"
     ]
    }
   ],
   "source": [
    "def a235328(n):\n",
    "    return sum(falling_factorial(n,k) * (n*k)^(n-k) for k in srange(n+1))\n",
    "\n",
    "import itertools as it\n",
    "def count_coincidences(n, test):\n",
    "    count = 0\n",
    "    for f in it.product(range(n), repeat=n):\n",
    "        for g in it.product(range(n), repeat=n):\n",
    "            good = test(n,f,g)\n",
    "            if good:\n",
    "                count += 1\n",
    "    return count\n",
    "\n",
    "def check_cube(n, f, g):\n",
    "    for i in range(n):\n",
    "        if f[i] != g[f[f[f[i]]]]:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "\n",
    "print [count_coincidences(n, check_cube) for n in range(0,6)]\n",
    "print [a235328(n) for n in range(10)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us look at $ggf=f$ ([A239771](https://oeis.org/A239771)).  Here $g$ is an involution on the image of $f$.  \n",
    "\n",
    "We can divide the image of $f$ up into three parts, points $x$ where $g(x)=x$, pairs of points $(x,y)$ with both $x$ and $y$ in the image of $f$ where $g(x)=y$ and $g(y)=x$, and points $x$ where $g(x)$ is not in the image of $f$ and $g(g(x))=x$.\n",
    "\n",
    "This gives us\n",
    "\n",
    "$$\\#(f,g)=\\sum_{k=0}^n \\binom{n}{k}k!\\left\\{n \\atop k\\right\\} \\sum_{j=0}^{\\min(k,n-k)}\\binom{k}{j}\\frac{(n-k)!n^{n-k-j}}{(n-k-j)!} \\sum_{i=0}^{\\lfloor\\frac{k-j}{2}\\rfloor}\\frac{(k-j)!}{(k-j-2i)!i!2^i}\n",
    "$$\n",
    "\n",
    "The inner sum is [A000085](https://oeis.org/A000085) and satisfies the nice recurrence $a_n = a_{n-1}+(n-1)a_{n-2}$. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 1, 10, 213, 8056, 465945, 37823616, 4075467781, 560230714240, 95369455852497]\n",
      "[1, 1, 10, 213, 8056, 465945, 37823616, 4075467781, 560230714240, 95369455852497]\n"
     ]
    }
   ],
   "source": [
    "def a239771(n):\n",
    "    return sum(falling_factorial(n,k) * stirling_number2(n,k) *\n",
    "              sum(binomial(k,j) * falling_factorial(n-k,j) * n^(n-k-j) *\n",
    "                 sum(falling_factorial(k-j,2 * i)/(factorial(i)*2^i)\n",
    "                    for i in range(floor((k-j)/2)+1))\n",
    "                 for j in range(min(k,n-k)+1))\n",
    "              for k in range(n+1))\n",
    "\n",
    "@CachedFunction\n",
    "def involutions(n):\n",
    "    return 1 if n < 2 else involutions(n-1) + (n-1) * involutions(n-2)\n",
    "\n",
    "def a239771_b(n):\n",
    "    return sum(falling_factorial(n,k) * stirling_number2(n, k) *\n",
    "              sum(binomial(k,j)*falling_factorial(n-k,j)*n^(n-k-j)*\n",
    "                  involutions(k-j)\n",
    "                 for j in range(min(k,n-k)+1))\n",
    "              for k in range(n+1))\n",
    "print [a239771(n) for n in range(10)]\n",
    "print [a239771_b(n) for n in range(10)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This logic works (with increasing difficulty with $m$ for $g^r f=f$).  For $r=3$ we need to count the 3 cycles that have all points, two points, or one point in the image of $f$.\n",
    "\n",
    "If we let $k$ be the size of the image of $f$, $l$ be the number of three-cycles having one point in the image of $f$, $j$ being the number having two points in the image of $f$ and $i$ being the number of three cycles having three points in the image of $f$."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 7.3",
   "language": "",
   "name": "sagemath"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}