ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1017. Staircases

a math solution
Posted by Nonagod 11 Feb 2007 18:34
the answer is
the coefficient of y^n
of A(n)=(1+y+y^2+y^3+...)(1+y^2+y^4+y^6+...)
...(1+y^n+y^2n+y^3n...)
if y<1;
A(n)=1/((1-y)(1-y^2)(1-y^3)....)
Re: a math solution
Posted by Ahmed Ahmedov 17 Mar 2011 13:58
Can you please explain the formula? It is an infinite formula, right? So, How would I apply it? Please give an example
Re: a math solution
Posted by DEAL 29 Mar 2011 00:36
It's easy to apply this formula, first of all you should notice that only n brackets must be opened, then you simply count all coefficients, multiplying only terms with the power that is less than n (or equal). (there is also one way to multiply less terms) And of course, you eventually get an answer.

<

Edited by author 29.03.2011 00:37
Re: a math solution
Posted by Charles 6 Jun 2013 20:42
I think it's wrong. The correct answear is the coefficient of A(n) = (1+y)(1+y^2)(1+y^3)...(1+y^n)... less 1, because the staircase with one step must not be counted.