Number of integer solution of a linear equation

by fungarwai, Sep 15, 2018, 11:14 AM

Stars and bars
The number of positive integer solutions of $\sum_{k=1}^m x_k=n$ is $\binom{n-1}{m-1}$

It is equivalent to put m-1 bars between n stars which have n-1 gaps.

generating function

for non-negative integer solutions

Integer with infinite range

Use generating function $\prod_{k=1}^m \frac{1}{(1-x^{a_k})}$ to find the number of non-negative integer solutions of $\sum_{k=1}^m a_k x_k=n$

Find the least common factor $L=[a_1,a_2,\dots,a_m]$, the generating function can be expressed as

$\prod_{k=1}^m \frac{1}{(1-x^{a_k})}
=\frac{1}{(1-x^L)^m}\prod_{k=1}^m \sum_{l=0}^{L/a_k-1} x^{la_k}$

Example

Integer with finite range

Roll m normal dices with numbers 1 to 6, find the probability that the sum of these numbers equals to n

$\sum_{k=1}^m x_k=n$

$(x+x^2+x^3+x^4+x^5+x^6)^m=\frac{x^m (1-x^6)^m}{(1-x)^m}
=x^m\left(\sum_{j=0}^m (-1)^j\binom{m}{j} x^{6j}\right)\sum_{k=0}^\infty \binom{k+m-1}{m-1}x^k$

Example

Permutation of consecutive items
permutation of binary number with length L including/without k consecutive "1"
where the number of "1" and "0" are n and L-n respectively


Without k consecutive "1",
$\sum_{m=0}^{L-n+1}(-1)^m\binom{L-n+1}{m}\binom{L-km}{L-n}$
Including k consecutive "1",
$\sum_{m=1}^{L-n+1}(-1)^{m-1}\binom{L-n+1}{m}\binom{L-km}{L-n}$

Proof

Example
This post has been edited 9 times. Last edited by fungarwai, May 14, 2022, 10:44 AM

Comment

0 Comments

Notable algebra methods with proofs and examples

avatar

fungarwai
Shouts
Submit
  • Nice blog!

    by Inconsistent, Mar 18, 2024, 2:41 PM

  • hey, nice blog! really enjoyed the content here and thank you for this contribution to aops. Sure to subscribe! :)

    by thedodecagon, Jan 22, 2022, 1:33 AM

  • thanks for this

    by jasperE3, Dec 3, 2021, 10:01 PM

  • I am working as accountant and studying as ACCA student now.
    I graduated applied mathematics at bachelor degree in Jinan University but I still have no idea to find a specific job with this..

    by fungarwai, Aug 28, 2021, 4:54 AM

  • Awesome algebra blog :)

    by Euler1728, Mar 22, 2021, 5:37 AM

  • I wonder if accountants need that kind of math tho

    by Hamroldt, Jan 14, 2021, 10:55 AM

  • Nice!!!!

    by Delta0001, Dec 12, 2020, 10:20 AM

  • this is very interesting i really appericate it :)

    by vsamc, Oct 29, 2020, 4:42 PM

  • this is god level

    by Hamroldt, Sep 4, 2020, 7:48 AM

  • Super Blog! You are Pr0! :)

    by Functional_equation, Aug 23, 2020, 7:43 AM

  • Great blog!

    by freeman66, May 31, 2020, 5:40 AM

  • cool thx! :D

    by erincutin, May 18, 2020, 4:55 PM

  • How so op???

    by Williamgolly, Apr 30, 2020, 2:42 PM

  • Beautiful

    by Al3jandro0000, Apr 25, 2020, 3:11 AM

  • Nice method :)

    by Feridimo, Jan 23, 2020, 5:05 PM

  • This is nice!

    by mufree, May 26, 2019, 6:40 AM

  • Wow! So much Algebra.

    by AnArtist, Mar 15, 2019, 1:19 PM

  • :omighty: :omighty:

    by AlastorMoody, Feb 9, 2019, 5:17 PM

  • 31415926535897932384626433832795

    by lkarhat, Dec 25, 2018, 11:53 PM

  • rip 0 shouts and 0 comments until now

    by harry1234, Nov 17, 2018, 8:56 PM

20 shouts
Tags
About Owner
  • Posts: 859
  • Joined: Mar 11, 2017
Blog Stats
  • Blog created: Sep 15, 2018
  • Total entries: 18
  • Total visits: 5855
  • Total comments: 8
Search Blog
a