If a game can result in a win, worth one point; a draw, worth half a point; or a loss, worth no points; how many ways are there of scoring k points in n games?

Applicable scenarios include NFL and chess.

  • Input is via stdin, and consists of n and k on separate lines.
  • n will be a non-negative integer. (n ≤ 16)
  • k will be either a non-negative integer or a non-negative integer plus a half. (k ≤ n)
  • Output is to stdout. It may, but does not have to, include a trailing newline.

Test cases

In each case, the first two lines are user-supplied input and the third line is the program output.




  • 4
    \$\begingroup\$ oeis.org/A027907 \$\endgroup\$ Jun 19, 2013 at 17:37
  • \$\begingroup\$ This is very insightful. I have a working solution in c# which compiles to the requirements outlined within the problem. I'm merely curious if someone can come up with a more compact solution than what I have. Cheers! \$\endgroup\$
    – glthomas
    Jun 19, 2013 at 20:07

6 Answers 6


Perl 59 bytes


Iteratively generates each row of the triangle of trinomial coefficients up to n, and then prints the correct term, 2k.

Ruby 73 bytes

p r[gets.to_f*2]

Largely equivalent to the Perl solution above.

Python 84 bytes

print r[int(input()*2)]

Same method as both solutions above.

PHP 91 bytes


Despite being the longest, this was actually the most fun to work on.


R - 81


A bit longer (106) but I also enjoyed writing it as a recursion:

Z=function(n,k)if(n<1|k<0)0 else if(n<2&k<3)1 else Z(n-1,k)+Z(n-1,k-1)+Z(n-1,k-2);Z(scan(n=1),2*scan(n=1))

C# (189 bytes)

Collaborative results from @glthomas, @recursive, @PeterTaylor and @primo

Best Solution (189 Bytes)
@glthomas and @recursive each found an additional 2 Bytes over the weekend. (We're convinced that this is the optimal solution using .Net 4.0 and compiling in VS 2010)!

using S=System.Console;class C{static void Main(){S.Write(G(G(),2*G()));}
static float G(float L=-1,float T=1){return L<0?float.Parse(S.ReadLine())

Improved Solution (193 Bytes)

using System;class C{static void Main(){Func<float,float,float>W=null;W=(n,k)=>n<0?

The additional Byte was saved by combining the input acquisition and static recursive method into a single multipurpose Func<>. Input acquisition is triggered when we pass in a negative value of n

Original Solution (195, 194)

using K=System.Console;class C{static void Main(){K.Write(T(int.Parse(K.ReadLine
()),2*float.Parse(K.ReadLine())));}static float T(int n,float k){return k==1?1:--
  • \$\begingroup\$ You can save one more byte by changing k<1?k+1 to k==0?1. It might be possible to save another if --n could somehow be moved to the front of the expression, i.e. return--n... \$\endgroup\$
    – primo
    Jun 21, 2013 at 6:24
  • \$\begingroup\$ @primo, unfortunately that alters the output, because k can sometimes be -1 because of the T(n,k-2) method call. Therefore we must check for k<1. \$\endgroup\$
    – glthomas
    Jun 21, 2013 at 18:50
  • \$\begingroup\$ I don't think it will. The k<0s will be allowed to propagate, true, but they will eventually be quenched when n reaches zero. Because a k that is less than zero cannot produce a k equal to zero in the successive calls, it cannot change the result. \$\endgroup\$
    – primo
    Jun 21, 2013 at 19:03
  • \$\begingroup\$ @primo I was incorporating both your second suggestion along with your first suggestion. The idea to return--n.. was interfering with my testing. I agree you can save a byte by converting k<1?k+1 to k==0?1. It appears the reason it doesn't work to move --n to the front of the expression is due to order of operation. The condition on k takes precedent over the condition on n. Wait until you see my post on 193 bytes :) \$\endgroup\$
    – glthomas
    Jun 21, 2013 at 19:50
  • \$\begingroup\$ Nice. Here's 7 bytes more: Func<float,float,float>W=null;W=(n,k) => Func<float,float,float>W=(n,k). \$\endgroup\$
    – primo
    Jun 21, 2013 at 21:04

C# (210 209 chars)

More efficient: iterative approach (209 chars):

using K=System.Console;class C{static void Main(){int
n=int.Parse(K.ReadLine()),k=(int)(2*float.Parse(K.ReadLine())),j;var t=new

Less efficient: recursive approach (210 chars);

using K=System.Console;class C{static void Main(){int
int T(int n,int k){return k<1?k+1:--n<0?0:T(n,k)+T(n,k-1)+T(n,k-2);}}

Note that if k is non-integral, it should be supplied in a format applicable to the locale. In my case that means that I have to format the input using , as the decimal separator.

  • \$\begingroup\$ 209 Bytes, you missed an easy 4 bytes :) using K=System.Console;class C{static void Main(){int n=int.Parse(K.ReadLine()),k=(int)(2*float.Parse(K.ReadLine())),j;var t=new int[k+3];for(t[2]=1;n-->0;)for(j=k+2;j>1;)t[j]+=t[--j]+t[j-1];K.Write(t[k+2]);}} \$\endgroup\$
    – glthomas
    Jun 19, 2013 at 21:55
  • \$\begingroup\$ @user1177611, it wasn't clear that that was permitted. I've edited the question and, among other changes, made that explicit. \$\endgroup\$ Jun 19, 2013 at 22:33
  • \$\begingroup\$ An anonymous user suggested saving a character in the iterative version by defining t=new int[99]. Technically with the current spec one could get away with t=new int[35], but I think that limiting the value of n to no more than 16 is a pointless restriction. \$\endgroup\$ Jun 20, 2013 at 13:39
  • \$\begingroup\$ Prior to being reworded, this problem started as an NFL win total combinatorics question. As such, 16 is currently the highest Win Total a team can achieve over one season. Though there has been a lot of debate regarding the expansion to an 18 game season. So, t=new int[99] is virtually future proof (at least as it pertains to the NFL) \$\endgroup\$
    – glthomas
    Jun 20, 2013 at 14:10

GolfScript (39 chars)


Online demo

Based on my answer to a previous question about binomial coefficients.


APL (22)


It's not exactly efficient though (set your workspace size to a couple of gigabytes if you want it to actually work up to N=16).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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