Let the number of ways to choose R objects from N objects be C(N,R) where the order does not matter, which has the famous closed form N!/(R! * (N-R)!).

Let the number of ways to choose R times from N objects with repetition be S(N,R) where the order of choosing does not matter.

for example if we were to choose from A,B and C four times A,B,C,C is the same as A,C,B,C so we should not count this twice in S(N,R)

S(N,R) turns also to be the number of solutions of

a1 + a2 + … + aN = R, where ai ≥ 0, and R is some non negative integer, simply imagine ai’s as objects the number of time an object is chosen is it’s value, and we choose from those objects R times so the sum would be equals R.

The question is how do we calculate S(N,R) using C(N,R) and this is the only reason for writing this post.

Lets try to solve an instance of the problem

lets assume N = 3 , R = 4

here are some possible solutions

a1 = 0, a2 = 2, a3 = 2

a1 = 1, a2 = 2, a3 = 1

a1 = 2, a2 = 2, a3 = 0

basically we are assigning a value to each variable such that their sum is 4 (youdon’tsay!)

but lets try to interpret this using binary numbers somehow, we can somehow write a solution using a binary number of length N + R – 1 bits as the following

a zero means move on to next variable

a one means increment current variable by 1

we can write a1 = 0, a2 = 2, a3 = 2 as 011011

at the beginning we have a1 = 0, we encounter a 0 so we move on to a2 increment it twice, then move on to a3 increment it twice.

similarly we can write a1 = 1, a2 = 2, a3 = 1 as 101101

since in any solution we need to move on to next variable N-1 times (N variables), and we have to increment all variables R times then from any binary number of N-1 zeroes, R ones we can construct a valid solution.

And if we have a solution we can construct a binary number.

Then there’s a one to one correspondence between the set of solutions and the set of binary numbers with N+R-1 bits where N-1 of them are zeroes and R of them are ones.

Counting those can be easily done using normal combinations so S(N,R) = C(N+R-1,R).

Update: it turns out that this post has a similar content to whats written here at topcoder tutorial :(, so you might want to check it out.

## Archive for the ‘**Combinatorics**’ Category

## Combinations with repetitions Leave a comment

## UVA – 11732 – “strcmp()” Anyone? Leave a comment

At first I thought this problem can be solved using trie, which would be an easy way however the simple trie would use a lot of memory 4000 * 1000 * 26 integers or so, Then I had to use another way which would be sorting, using any comparison based sorting algorithm as quick sort or merge sort would also cause Time limit exceeded so instead I used my not-so-efficient radix sort which runs in O(num_words*max_length), then using the sorted words you can easily calculate the result, see the solution for more information.

#include <stdio.h> #include <string.h> #include <stack> using namespace std; typedef long long ll; char words[4005][1005]; int len[4005]; int loc[4005]; int temp[4005]; int word_count; int freq[128]; int charAt(int i, int j) { return (j < len[loc[i]]) ? words[loc[i]][j] : 0; } void count_sort(int j) { memset(freq, 0, sizeof freq); for (int i = 0; i < word_count; i++) freq[charAt(i, j)]++; for (int i = 1; i < 128; i++) freq[i] += freq[i - 1]; for (int i = word_count - 1; i >= 0; i--) temp[--freq[charAt(i, j)]] = loc[i]; memcpy(loc, temp, word_count * 4); } void radix_sort() { int max_len = 0; for (int i = 0; i < word_count; i++) { loc[i] = i; if (len[i] > max_len) max_len = len[i]; } for (int i = max_len - 1; i >= 0; i--) count_sort(i); } int main(int argc, char *argv[]) { int cc = 1; while (scanf("%d", &word_count) && word_count) { getchar(); for (int i = 0; i < word_count; i++) { gets(words[i]); len[i] = strlen(words[i]); } radix_sort(); stack<int> s; s.push(0); s.push(word_count - 1); s.push(0); ll res = 0; memset(freq, 0, sizeof(freq)); while (s.size()) { int j = s.top(); s.pop(); int r = s.top(); s.pop(); int l = s.top(); s.pop(); int all = r - l + 1; for (int i = l; i <= r; i++) freq[charAt(i, j)]++; res += freq[0] * (freq[0] - 1); res += freq[0] * (all - freq[0]); freq[0] = 0; for (int i = l; i <= r; i++) { char c = charAt(i, j); if (!c) continue; if ((i > l && c == charAt(i - 1, j)) || !c) continue; res += freq[c] * (freq[c] - 1); res += freq[c] * (all - freq[c] - i + l); s.push(i); s.push(i + freq[c] - 1); s.push(j + 1); freq[c] = 0; } } printf("Case %d: %lld\n", cc++, res); } return 0; }

## UVA – 11282 – Mixing Invitations 1 comment

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class MixingInv { public static long[][] C(int MAX) { long C[][] = new long[MAX + 1][MAX + 1]; for (int i = 0; i < C.length; i++) C[i][0] = 1; for (int i = 1; i < C.length; i++) for (int j = 1; j < C[i].length; j++) C[i][j] = C[i - 1][j - 1] + C[i - 1][j]; return C; } public static void main(String[] args) throws Exception { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); long[] dp = new long[21]; long[][] C = C(21); dp[0] = 1; dp[1] = 0; for (int i = 2; i < dp.length; i++) dp[i] = (i - 1) * (dp[i - 2] + dp[i - 1]); while (true) { String s = in.readLine(); if (s == null) return; String[] arr = s.split(" "); int a = Integer.parseInt(arr[0]); int b = Integer.parseInt(arr[1]); long res = 0; for (int i = 0; i <= b; i++) res += C[a][i] * dp[a - i]; System.out.println(res); } } }

## UVA – 1224 – Tile Code Leave a comment

Using recurrence formula W1 it has repetitions as turning a tag upside down doesn’t make a different tag,so we use another recurrence relation W2 where W2[i] is the number of symmetric 2xi tags

and the final result for a 2xn tag is (W1[n]-W2[n])/2 + W2[n]

#include <stdio.h> #define MAXN 31 int main() { int W1[MAXN],W2[MAXN],i,tc; W1[0]=1; W1[1]=1; for(i=2;i<MAXN;i++) W1[i]=2*W1[i-2]+W1[i-1]; W2[0]=1; W2[1]=1; W2[2]=3; W2[3]=1; for(i=4;i<MAXN;i++) W2[i]=W2[i-2]+2*W2[i-4]; scanf("%d",&tc); while(tc-->0) { scanf("%d",&i); printf("%d\n",(W1[i]-W2[i])/2 + W2[i]); } return 0; }

## UVA – 10219 – Find the ways ! 1 comment

#include <stdio.h> #include <math.h> int main() { unsigned long long int a, b; long double res; unsigned long long int i; while(scanf("%llu %llu",&a,&b)==2) { res = 0; for(i=a;i>a-b;i--) res+=log10(i); for(i=b;i>0;i--) res-=log10(i); printf("%d\n",(int)floor(res)+1); } return 0; }

## UVA – 11554 – Hapless Hedonism Leave a comment

#include <stdio.h> #include <math.h> #include <stdlib.h> #define N 1000001 unsigned long long int dp[N]; unsigned long long int sum(int s,int t,int shift) { return (unsigned long long int)(abs(t-s)/shift+1)*(s+t)/2; } int main() { int i,n; for(i=0;i<N;i++) dp[i]=0; dp[4]=1; for(i=5;i<N;i++) { n = i / 2 + 1; dp[i]=dp[i-1]+sum(1,n-2,1)+sum(i-n-1,1,1); } scanf("%d",&i); while(i--) { scanf("%d",&n); printf("%llu\n",dp[n]); } return 0; }

## UVA – 11401 – Triangle Counting 7 comments

Problem:

suppose we have sticks 1,2,3….,n

find the number of possible triangles that can be formed any of those sticks such that each stick can only be used once per triangle

first if we have a triangle with sides a,b,c therfore this must be true a+b>c , a+c>b , b+c>a

if n = 3

we have 3 sticks

1 2 3

we can’t form any triangles with this

if n = 4

1 2 3 4

we can form 1 triangle

(2,3,4)

if n = 5

1 2 3 4 5

we can form 3 triangles

(2,3,4)

——-

(2,4,5)

(3,4,5)

we can form the same number of triangles using four sticks + the number of triangles

that can be formed using the new stick as one side of the triangle (stick with length 5)

let nTri(n) is the number of triangles that can be formed using n sticks 1,2,3,4..n

so nTri(n) = nTri(n-1) + X

where X is the number of triangles having the nth side

now we need to calculate X

to figure this quickly we’ll use n=6

1 2 3 4 5 6

we already have 6 as the largest side we’ll choose x the smallest side

let y be the third side

so choosing x=2 yields

(2,y,6) y=5

choosing x=3 yields

(3,y,6) y=4 or 5

choosing x=4 yields

(4,y,6) y=5

2,n can pair with y=n-1 for 2+y>n to be true

3,n can pair with y=n-1,n-2 for 3+y>n to be true

4,n can pair with y=n-1,n-2,n-3 for 4+y>n to be true

for n=6 the sequence is 1,2,1

for n=7 the sequence is 1,2,2,1

thus

for any even n>=4 the sequence will be

1,2,..,(n/2-1),..,2,1

for any odd n>4 the sequence will be

1,2,..,(n/2-1),(n/2-1),..,2,1

X is the sum of this sequence

X can be easily calculated using the arithmatic sequence sum rule

then nTri(n) = nTri(n-1) + X

#include <stdio.h> #include <math.h> #include <stdlib.h> #define N 1000001 unsigned long long int dp[N]; //Returns sum between integers 1 to n inclusive unsigned long long int sum(int n) { return (unsigned long long int)n*(n+1)/2; } int main() { int i,n; for(i=0;i<N;i++) dp[i]=0; dp[4]=1; for(i=5;i<N;i++) { n = i/2 -1; dp[i]=dp[i-1]+2*sum(n)-((!(i&1))*n); //((!(i&1))*n) if i is even this evaluates as n else it evaluates as 0 } scanf("%d",&n); while(n>=3) { printf("%llu\n",dp[n]); scanf("%d",&n); } return 0; }