9

I want to use the bars and stars method to list number of non-negative solutions of the equation x + y + z = 4. I tried with

\documentclass{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{fourier}
\begin{document}
\begin{tabular}{|c|c|}
\hline 
$(0, 0, 4)$ & $\big|\big|\star \star \star\star $ \\ 
\hline 
$(0, 1, 3)$ & $\big|\star\big| \star \star\star $ \\ 
\hline 
$(0, 2, 2)$ & $\big|\star\star \big|  \star\star $ \\ 
\hline 
$(0, 3, 1)$ & $\big|\star\star \star \big|  \star $ \\ 
\hline 
$(0, 4, 0)$ & $\big|\star\star \star  \star\big|  $ \\ 
\hline 
$(1, 0, 3)$ & $\star\big|\big|\star \star  \star  $ \\ 
\hline 
$(1, 1, 2)$ & $\star\big|\star \big|\star   \star  $ \\ 
\hline 
$(1, 2, 1)$ & $\star\big|\star \star\big|   \star  $ \\ 
\hline 
$(1, 3, 0)$ & $\star\big|\star \star   \star \big| $ \\ 
\hline 
$(2, 0, 2)$ & $\star \star\big|\big|\star   \star  $ \\ 
\hline 
$(2, 1, 1)$ & $\star \star\big|\star\big|   \star  $ \\ 
\hline 
$(2, 2, 0)$ & $\star \star\big|\star \star\big|     $ \\ 
\hline 
$(3, 0, 1)$ & $\star \star\star \big|\big| \star    $ \\ 
\hline 
$(3, 1, 0)$ & $\star \star\star \big| \star \big|   $ \\ 
\hline 
$(4, 0, 0)$ & $\star \star\star \star\big|  \big|   $ \\ 
\hline 
\end{tabular} 
\end{document}

enter image description here

I know that, number of non-negative solutions of the solution x + y + z = 4 is C_(4+3-1)^4=15. Is there any way to represent bars and stars faster?

  • 1
    What do you meen by "faster" ? Faster compilation or shorter code ? And do you want to do this in TikZ (this will probably be not so fast for compilation) ? – Kpym Jan 19 '15 at 8:57
7

The compulsory expl3 solution: two nested cycles for building the table body.

\documentclass{article}
\usepackage{xparse}

\ExplSyntaxOn
\NewDocumentCommand{\starsandbars}{m}
 {
  \minthao_starsandbars:n { #1 }
 }

\tl_new:N \l__minthao_table_body_tl

\cs_new_protected:Npn \minthao_starsandbars:n #1
 {
  \tl_clear:N \l__minthao_table_body_tl
  \int_step_inline:nnnn { 0 } { 1 } { #1 } % ##1 is x
   {
    \int_step_inline:nnnn { 0 } { 1 } { #1 - ##1 } % ####1 is y
     {
      \tl_put_right:Nx \l__minthao_table_body_tl
       {
        $(\int_to_arabic:n { ##1 },
          \int_to_arabic:n { ####1 },
          \int_to_arabic:n { #1 - ##1 - ####1 })$ &
       }
      \tl_put_right:Nx \l__minthao_table_body_tl
       {
        \prg_replicate:nn { ##1 } { $\star$ }
        \exp_not:n { \,\vline\, }
        \prg_replicate:nn { ####1 } { $\star$ }
        \exp_not:n { \,\vline\, }
        \prg_replicate:nn { #1 - ##1 - ####1 } { $\star$ }
       }
      \tl_put_right:Nn \l__minthao_table_body_tl { \\ \hline }
     }
   }
  \begin{tabular}{|c|c|}
    \hline
    \l__minthao_table_body_tl
  \end{tabular}
 }
\ExplSyntaxOff

\begin{document}

\starsandbars{4}

\end{document}

enter image description here

An expanded version featuring a key-value interface; the keys are

  • longtable (boolean); if expressed, a longtable is produced
  • preamble, for specifying the longtable preamble with \endhead and so on, or anyway something to be set at the start of the table (see the second example)

The picture shows only the first two pages.

\documentclass{article}
\usepackage{xparse,longtable}

\ExplSyntaxOn
\NewDocumentCommand{\starsandbars}{O{}m}
 {
  \group_begin:
  \keys_set:nn { minthao/starsandbars } { #1 }
  \minthao_starsandbars:n { #2 }
  \__minthao_starsandbars_print_table:
  \group_end:
 }

\keys_define:nn { minthao/starsandbars }
 {
  longtable .bool_set:N = \l__minthao_starsandbars_longtable_bool,
  longtable .default:n = { true },
  longtable .initial:n = { false },
  preamble  .tl_set:N  = \l__minthao_starsandbars_preamble_tl,
  preamble  .initial:n = \hline,
 }

\tl_new:N \l__minthao_table_body_tl

\cs_new_protected:Npn \minthao_starsandbars:n #1
 {
  \tl_clear:N \l__minthao_table_body_tl
  \int_step_inline:nnnn { 0 } { 1 } { #1 } % ##1 is x
   {
    \int_step_inline:nnnn { 0 } { 1 } { #1 - ##1 } % ####1 is y
     {
      \tl_put_right:Nx \l__minthao_table_body_tl
       {
        $(\int_to_arabic:n { ##1 },
          \int_to_arabic:n { ####1 },
          \int_to_arabic:n { #1 - ##1 - ####1 })$ &
       }
      \tl_put_right:Nx \l__minthao_table_body_tl
       {
        \prg_replicate:nn { ##1 } { $\star$ }
        \exp_not:n { \,\vline\, }
        \prg_replicate:nn { ####1 } { $\star$ }
        \exp_not:n { \,\vline\, }
        \prg_replicate:nn { #1 - ##1 - ####1 } { $\star$ }
       }
      \tl_put_right:Nn \l__minthao_table_body_tl { \\ \hline }
     }
   }
 }

\cs_new_protected:Npn \__minthao_starsandbars_print_table:
 {
  \bool_if:NTF \l__minthao_starsandbars_longtable_bool
   { \begin{longtable} }
   { \begin{tabular} }
   {|c|c|}
  \l__minthao_starsandbars_preamble_tl
  \l__minthao_table_body_tl
  \bool_if:NTF \l__minthao_starsandbars_longtable_bool
   { \end{longtable} }
   { \end{tabular} }
 }



\ExplSyntaxOff

\begin{document}

\starsandbars{3}

\bigskip

\starsandbars[
  preamble=\hline\multicolumn{2}{|c|}{$x+y+z=4$}\\\hline
]{4}

\starsandbars[
  longtable,
  preamble={
    \caption{$x+y+z=12$}\\
    \hline
    \endfirsthead
    \caption*{$x+y+z=12$ (continued)}\\
    \hline
    \endhead
  }
]{12}

\end{document}

enter image description here

  • Please help me with \starsandbars{n} n big. A longtable. – minthao_2011 Jan 19 '15 at 10:38
  • @minthao_2011 Easily done. ;-) – egreg Jan 19 '15 at 12:55
6

Not sure if the requirement is show the numbers in parenthesis and do the stars and bars. This \starsandbars macro just does the stars and bars:

\documentclass[varwidth,border=5]{standalone}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{fourier}
\usepackage{pgffor}

\def\starsandbars#1{{\ensuremath{%
  \edef\starlist{#1}%
  \foreach \i [count=\a] in \starlist{%
    \ifnum\a>1\big|\fi%
    \ifnum\i>0\foreach \j in {1,...,\i}{\star}\fi%
  }}}}%
\begin{document}
\foreach \i in {{0,1,2},{1,2,1},{0,0,5}, {1,3,0}, {4,3,2,6}}{\leavevmode
\hbox to .75in{(\i)\hfil} \starsandbars{\i} \par
}
\end{document}

enter image description here

5

The question was tagged tikz-pgf but if you want to do it with a tabular as in the original formulation this is an ideal job for \xintFor.

\documentclass{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{fourier}

\usepackage{xinttools}
% we need _ as private letter because we will employ \xint_dothis
% and \xint_orthat

\catcode`_ 11
\newcommand\barsandstars [1]{% solving x+y+z=#1 in non-negative integers
  \edef\tmp_N {\numexpr\the\numexpr #1\relax\relax}%
  \def\tmp_a {0}%
  \def\tmp_b {0}%
  \edef\tmp_c {\the\tmp_N }%
  \begin{tabular}{|c|c|}
   \hline
   \xintFor ##1 in {\xintegers [0+1]}\do 
   {%  ##1 = insertion location of first bar
       \xintFor ##2 in {\xintegers [{\numexpr##1+1\relax}+1]}\do 
       {%  ##2 = insertion location of second bar
        %     (first bar insertion has shifted by one all things to its right)
           $(\tmp_a,\tmp_b,\tmp_c)$
           &
           $\xintFor ##3 in {\xintegers [0+1]}\do 
            {%  
               \ifnum ##3<##1\xint_dothis{\star}\fi
               \ifnum ##3=##1\xint_dothis{\big|}\fi
               \ifnum ##3<##2\xint_dothis{\star}\fi
               \ifnum ##3=##2\xint_dothis{\big|}\fi
               \xint_orthat {\star}%
               \ifnum ##3>\tmp_N \expandafter\xintBreakFor\fi
            }$
% The trick is to always decide if we need to continue BEFORE inserting \\
% and we must do non-expandable things before the \\
           \xdef\tmp_b {\the\numexpr\tmp_b+1}%
           \xdef\tmp_c {\the\numexpr\tmp_c-1}%
           \ifnum ##2>\tmp_N \expandafter\xintBreakFor\fi
           \\\hline
       }%
       \xdef\tmp_a {\the\numexpr\tmp_a+1\relax }%
       \gdef\tmp_b {0}%
       \xdef\tmp_c {\the\numexpr \tmp_N-\tmp_a\relax}%
       \ifnum ##1=\tmp_N \expandafter\xintBreakFor\fi
       \\\hline
   }%
   \\\hline
  \end{tabular} 
}  
\catcode`_8


\begin{document}
  \barsandstars {7}
\end{document}

bar and stars

4

If "faster" meens shorter code working not only for 4, here is a TikZ solution:

\documentclass[tikz,border=7mm]{standalone}
\begin{document}
\begin{tikzpicture}[scale=.7]
  \def\total{4} % i+j+k = total
  \xdef\y{0}
  \foreach \i in {0,...,\total}{
    \pgfmathsetmacro{\maxj}{int(\total-\i)}
    \foreach \j in {0,...,\maxj}{
      \pgfmathparse{int(\y+1)}\xdef\y{\pgfmathresult}
      \pgfmathsetmacro{\k}{int(\total-\i-\j)}
      \foreach \i in {1,...,\total}
        \node at (\i,\y){$\star$};
      \node at (.45+\j+\i,\y) {$\big|$};
      \node at (.55+\i,\y) {$\big|$};
      \node[left] at (-1,\y){(\i,\j,\k)};
    }
  }
\end{tikzpicture}
\end{document}

enter image description here

if you set \def\total{2} you get:

enter image description here

And I'll not publish the result for 7 ;)

  • coincidentally I prepared my answer with 7 before reading yours... – user4686 Jan 19 '15 at 9:51
  • @jfbu I've seen this ... this is because I'm a mind reader ;) – Kpym Jan 19 '15 at 9:53
  • it is funny that as I don't dispose of the convenience of creating nodes at given locations in the context of pure TeX handling of tokens, my first concern was to generate efficiently the bars and stars and that the triplets (x,y,z) were thus a king a secondary thing, whereas in your approach it is the exact opposite. – user4686 Jan 19 '15 at 10:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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