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 is
It is equivalent to put m-1 bars between n stars which have n-1 gaps.
generating function
Consider generating function
Take , the coefficient of is
for non-negative integer solutions
Integer with infinite range
Use generating function to find the number of non-negative integer solutions of
Find the least common factor , the generating function can be expressed as
Example
Method 1
The number of solution is
Method 2
Alternatively, separate and take number of solutions of
This method reduces much effort on expanding polynomial.
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
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",
Including k consecutive "1",
Proof
Example
The number of positive integer solutions of is
It is equivalent to put m-1 bars between n stars which have n-1 gaps.
generating function
Consider generating function
Take , the coefficient of is
for non-negative integer solutions
The number of non-negative integer solutions of is
The responding generating function is
Take , the coefficient of is
The responding generating function is
Take , the coefficient of is
Integer with infinite range
Use generating function to find the number of non-negative integer solutions of
Find the least common factor , the generating function can be expressed as
Example
Method 1
The number of solution is
Method 2
Alternatively, separate and take number of solutions of
This method reduces much effort on expanding polynomial.
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
Example
Roll 2 normal dices with numbers 1 to 6
The number of solution is
The number of solution is
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",
Including k consecutive "1",
Proof
Consider the place of "0" items numbered from 1 to L.
Put the first "0" at , the second "0" at , the Nth "0" at
Once , the binary number includes k consecutive "1"
Also, if the last "0" placed before L-k+1, there will be k consecutive "1" after it
Therefore,
Alternatively,
The coefficient of is
Put the first "0" at , the second "0" at , the Nth "0" at
Once , the binary number includes k consecutive "1"
Also, if the last "0" placed before L-k+1, there will be k consecutive "1" after it
Therefore,
Alternatively,
The coefficient of is
Example
This post has been edited 9 times. Last edited by fungarwai, May 14, 2022, 10:44 AM