3

I asked a combinatorics question on math stack exchange and received the following LaTeX-flavored answer. I have attempted to convert that equation into something that can be understood by wolfram alpha; however, it does not seem to work. Any ideas on how to edit the syntax of the equation? I have posted below the syntax used.

\[
n!+\sum_{i=1}^{n-1}(-1)^i\sum_{k=1}^i\binom{i-1}{i-k}\binom{n-i}{k}2^k(n-i)!
\]

closed as off-topic by egreg, user13907, Maarten Dhondt, Joseph Wright Nov 16 '16 at 6:54

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not fall within the scope of TeX, LaTeX or related typesetting systems as defined in the help center." – egreg, Community, Maarten Dhondt
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    This is better asked on the Mathematica.SE site. – Andrew Swann Nov 14 '16 at 8:14
  • Welcome to TeX.SX! It might be that there are some people here using regularly Wolfram alpha, but basically this is the wrong place for your question. It is about what Wolfram accepts as input, which is inspired by TeX syntax, but there is no TeX engine behind. The tag wolfram-mathematica refers to the TeX code generated by Mathematica and intended to be processed by TeX. – gernot says Reinstate Monica Nov 14 '16 at 8:15
  • I see. Can you please migrate this question there? @AndrewSwann – Christian Nov 14 '16 at 8:18
  • 2
    please keep it here too, I am working on an answer. – user4686 Nov 14 '16 at 8:44
  • 3
    Please leave this question on this site -- there are now two answers that show how the question may be solved using (Lua)LaTeX methods. – Mico Nov 14 '16 at 11:22
8

Table of contents:

  • initial answer using xintexpr and OP's formula. Implementation is expandable...

  • second answer using recurrence formula given at http://oeis.org/A002464. This second approach constructs once and for all an array of values of the given expression. It uses package bnumexpr for big integer calculations.


You can compute this using TeX or LaTeX.

Some a bit painful details are detailed in the code comments: the main one is that the binomial(x,y) function currently emits an error if y>x, rather than returning silently zero.

\documentclass{article}

\usepackage{xintexpr}[2016/03/12]% 1.2f or more recent needed for binomial

\begin{document}

% unfortunately the default binomial(x,y) function raises an error
% if y>x. Hence define wrapper to intercept the case.
\xintdefiifunc bbinomial(x,y):=if(y>x,0,binomial(x,y));

% unfortunately we can not use \xintdefiifunc F(n):=....; syntax because the
% function variable "n" appears in the summation range. This is current
% limitation, documented in §10.10.3 of xint.pdf.

% Hence we use a macro interface, which will need braces: \myF{10}.

% We employ parentheses around #1 in case
% it is itself some math expression.

% we choose \xintiiexpr rather than \xinttheiiexpr, for efficiency
% if used in other expressions.

\newcommand\myF [1]{% n = #1
   \xintiiexpr (#1)!+
   add((-1)^i % probably faster: ifodd(i, -1, +1)
       *add(binomial(i-1,i-k)*bbinomial((#1)-i,k)*2^k, 
       k=1..i)*((#1)-i)!, 
   i=1..(#1)-1)\relax }

% unfortunately in xintiiexpr, currently 1..0 does not evaluate
% to empty range, but proceeds by negative steps, hence evaluate to
% 1, 0 which we don't want.

% 1..[1]..0 would create such an empty range.
% but further problem is that add(<expression>, i = <range>) syntax
% currently does not work with range being empty.

% Consequently the above expression requires n > 1.

% test
% \xinttheiiexpr seq(\myF{n}, n=2..10)\relax

\medskip
\begin{tabular}{c|r}
  $n$&$F(n)$\\
\hline
\xintFor* #1 in {\xintSeq{2}{20}}
\do
{$#1$&$\xintthe\myF{#1}$\\}
\end{tabular}

\end{document}

enter image description here


More realistic approach which once and for all define macros expanding to the combinatorial values. Based on recurrence formula.

\documentclass{article}

\usepackage{bnumexpr}

% http://oeis.org/A002464

% If n = 0 or 1 then a(n) = 1; if n = 2 or 3 then a(n) = 0; otherwise a(n) =
% (n+1)*a(n-1) - (n-2)*a(n-2) - (n-5)*a(n-3) + (n-3)*a(n-4)

% 1, 1, 0, 0, 2, 14, 90, 646, 5242, 47622, 479306, 5296790, 63779034

\begin{document}

\begingroup
\makeatletter

\@namedef{F<0>}{1}
\@namedef{F<1>}{1}
\@namedef{F<2>}{0}
\@namedef{F<3>}{0}

\count@=4

\loop
% no \@nameedef in latex
  \expandafter\edef\csname F<\the\count@>\endcsname
       {\thebnumexpr (\count@+1)*\@nameuse{F<\the\numexpr\count@-1>}
                    -(\count@-2)*\@nameuse{F<\the\numexpr\count@-2>}
                    -(\count@-5)*\@nameuse{F<\the\numexpr\count@-3>}
                    +(\count@-3)*\@nameuse{F<\the\numexpr\count@-4>}\relax}%
\ifnum\count@<30
\advance\count@\@ne
\repeat

\count@=0

\ttfamily

http://oeis.org/A002464

\loop
\the\count@: \@nameuse{F<\the\count@>}\endgraf
\ifnum\count@<30
\advance\count@\@ne
\repeat

\endgroup

\end{document}

enter image description here

  • the oeis site contains the interesting info that the ratio a(n)/n! converges to exp(-2). There is precise asymptotics: a(n)/n! ~ (1 - 2/n^2 - 10/3/n^3 - 6/n^4 - 154/15/n^5 + ...)/e^2. It does fit well with data above for example for n=30 the exact formula holds a(30)/30! = (1 - 2/30^2 - 3.545.../30^3)*exp(-2). – user4686 Nov 14 '16 at 13:52
6

Here's a LuaLaTeX-based approach to computing F(n) as a function of n. Relative to the version you provided, the formula is rephrased a bit to (a) add braces and brackets to provide some visual grouping and (b) some explanatory text to highlight the outer ("i") and inner ("k") for loops.

The table starts with n=2 since F(1)=1 trivially. (F(1) is computed correctly, by the way.) For the table, I set n_{\max} to 15; in fact, the calculation method doesn't produce an overflow as long as n<20.

enter image description here

\documentclass{article}
\usepackage{amsmath} % for "\binom" macro
\usepackage{luacode} % for "luacode" env. and "\luaexec" macro
\begin{luacode}
-- First, define two helper functions: "factorial" and "mchoose"
function factorial ( n )
   local k
   if n==0 or n==1 then
      return 1
   else
      return n * factorial(n-1)
   end
end

-- 'mchoose' is patterned after the posting in http://stackoverflow.com/a/15302448. 
-- Thanks, @egreg, for pointing me to this posting!
function mchoose( n, k )
     if ( k == 0 or k == n ) then
        return 1
     else
        return ( n * mchoose(n - 1, k - 1)) / k 
     end
end

-- Second, set up the function "F"
function F ( n )
   local i, k, result, kterm
   result = factorial ( n ) 
   for i=1,n-1 do           -- outer loop is entered only if n>1
      kterm=0  -- (re)set "kterm" to 0
      for k=1,i do
         kterm = kterm + mchoose(i-1,i-k) * mchoose(n-i,k) * 2^k 
      end
      result = result + ((-1)^i) * factorial(n-i) * kterm
   end
   return result
end

\end{luacode}

\begin{document}
\[
F(n)=n!+\biggl\{\,
     \underbrace{ \sum_{i=1}^{n-1} (-1)^i (n-i)! \biggl[\,
         \underbrace{\sum_{k=1}^i \binom{i-1}{i-k} \binom{n-i}{k} 2^k}_%
         {\text{inner or $k$ loop}}\biggr]}_%
     {\text{outer or $i$ loop}}\biggr\}
\]

\bigskip
% print values of n and F(n) for n=2,...,15
\[
\begin{array}{@{}rr@{}}
\hline
n & F(n) \\
\hline
\luaexec{for n=2,15,1 do
           tex.sprint(n .. "&" .. math.floor(F(n)) .. "\\\\")
         end}
\hline
\end{array}
\]
\end{document}
  • +1 does lualatex like Python3 handle "big integers" out of the box ? – user4686 Nov 14 '16 at 12:00
  • @jfbu - Thanks! Per your suggestion, I've moved the multiplicative term factorial(n-i)out of the k for loop. On calculations with very large integers: Lua 5.3 provides the int numerical data type, which would be very beneficial for the calculations in this example. Unfortunately, LuaTeX -- even the recently-released version 1.0 -- is still based on Lua 5.2, which only provides the float numerical data type. There are external Lua libraries that allow (nearly) arbitrary-precision calculations with integers; I didn't pursue that possibility here as I don't know the OP's use case. – Mico Nov 14 '16 at 12:10

Not the answer you're looking for? Browse other questions tagged or ask your own question.