This tag is for basic questions about the study of finite or countable discrete structures — specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions. ...

learn more… | top users | synonyms (4)

1
vote
0answers
58 views

Traverse resultant 2d array after integer partition

I have used the solution of integer partitioning using dynamic programming explained in this post and in this article. Following is the resultant matrix when N is equal to 6: $$\begin{bmatrix} 1 ...
1
vote
1answer
88 views

Looking for a bijection between this set and natural numbers

I am a computer programmer, and I am struggling with this mathematical problem without finding a consistent and efficient solution. Let $A_{k, M}$ be the set of all the possible assignments for $n_1, ...
-1
votes
0answers
44 views

Count suggestions to be send

A site currently has N registered users. As in any social network two users can be friends. We wants the world to be as connected as possible, so we want to suggest friendship to some pairs of users. ...
-2
votes
1answer
37 views

Counting overlapping figures

How many four-sided figures appear in the diagram below? I tired counting all the rectangles I could see, but that didn't work. How do I approach this?
0
votes
1answer
49 views

Sort of Binomial Expansion

I was trying to find a general formula for expanding the product: $$\prod_{i=1}^k (a+ib)$$ where $a, b \in \mathbb{R}$. The first few expansions are as follows: $$\prod_{i=1}^1 (a+ib) = a + b$$ ...
1
vote
0answers
57 views

Number of ways to make first move

Alice and Bob are playing a game. They have N containers each having one or more chocolates. Containers are numbered from 1 to N, where ith container has A[i] number of chocolates. The game goes like ...
3
votes
1answer
167 views

What is this myth/legend and origin of related ideas?

There is a story I recently heard but the story teller (who read about it someone on the Internet) have forgotten the majority of the story, so there is little I can work on: my search attempts went ...
1
vote
1answer
57 views

Maximise the smallest piece of grid

Given a big rectangular chocolate bar that consists of n × m unit squares. We wants to cut this bar exactly k times. Each cut must meet the following requirements: ...
0
votes
0answers
50 views

Sums with k dice

I have n dice, each with k sides, numbered from 1 to k inclusive. I want to find in how many ways I can get a sum of x using those dice. Doing some research, I found that what I am looking for is ...
1
vote
1answer
28 views

How many closed binary operations on A have x as the identity?

There is this one example in my book that explains how to do this, but it's very obsecure and I just can't follow it. It says if: A = {x,a,b,c,d} then there are 5^16 closed binary operations on A ...
2
votes
3answers
103 views

How many different choice of sets?

If $S_1$, $S_2$, $\dots$, $S_r$ are r sets, $S_i\subseteq \{1,2,\dots,n\}$. $|S_i|\geq 1$ for all $i$ and $S_i\cap S_{i+1}$=$\emptyset$ for all $1\leq i\leq r-1$. How many different chioce of ...
2
votes
1answer
47 views

Count no. of ways with exactly K turns

Given two distinct points A(P,Q) and B(R,S) with P,Q,R,S>=0. What is the number of ways to count paths with exactly K turns given that we can move in only two directions i.e. right and down? My ...
1
vote
1answer
24 views

Recurrence relation and combinatorics

I am reading p.4 of the article http://mercercountymathcircle.files.wordpress.com/2014/03/recurrence_relations.pdf which consider the following problem: Find the units digit of ...
2
votes
2answers
80 views

A simple question in combinatorics.

A university bus stops at some terminal where one professor,one student and one clerk has to ride on bus.There are six empty seats.How many possible combinations of seating? My problem:I know that if ...
0
votes
1answer
60 views

How many ways can we form an integer-sided scalene triangles with largest side <= N?

Since triangle is scalene, we can pick 3 numbers [a, b, c] from 1 to N, such that a + b > c, a + c > b and b + c > a. The result is A173196 but I can't get a way to obtain the result except by ...
3
votes
1answer
37 views

Combinatorial identity involving sum of products?

Let $(c_1, c_2, \cdots)$ be an $m$-periodic sequence of natural numbers and let $n$ and $k$ be integers with $0\leq k \leq n$. I am trying to simplify $$ \sum_{\substack{I \subseteq \{1, \cdots, n\}\\ ...
2
votes
1answer
52 views

Lattice Path Spaces.

It is well known that the number of paths from $(0,0)$ to $(n,k)$ in $\mathbb{N^2}$ with the set of steps $\{(1,0),(0,1)\}$ is ${n+k \choose k}$. This is the minimum number of steps needed to get to ...
1
vote
0answers
45 views

How can I find the smallest set of groups of $n$ elements such that every element is in the same group as every other at least once?

Background: I'm working on a King of the Hill challenge for Programming Puzzles & Code Golf, and I've run into a problem with how I'm creating the individual matchups (groups of 4 entries). ...
2
votes
0answers
29 views

Counting symmetric binary matrices with constant line-sum

I'm trying to count, as the title suggests, symmetric matrices with entries $0$ or $1$ and constant line-sum $k$. ($0 \leq k \leq n$). If you start listing the number of these on a table you'll get a ...
7
votes
1answer
123 views

Strange factorial identity

The following appears to be true. \begin{align*} n! &= \sum_{k=0}^n \sum_{j=0}^{\lfloor\frac{k}{3}\rfloor}\sum_{i=0}^{k-3j} (-1)^{i+j}\binom{k-2j}{i,j,k-i-3j}\frac{(n-i-2j)!}{(n-k)!}\\ &\qquad ...
18
votes
2answers
1k views

A riddle with a witch and some gnomes

My question concerns a variation and a generalization of the following riddle. The Original Riddle: A wicked witch kidnaps 2 gnomes. She paralyzes them, and places a hat on each of their heads. Each ...
4
votes
2answers
73 views

Theoretical computer science text for mathematician

I am a high school student, I know some basic programming in java,python and visual basic. I love combinatorics and I have encountered various cases in which I have found some problems are really ...
4
votes
3answers
76 views

Sum of $k$-combination with repetitions

I can see that there are $\binom{n+k-1}{k}$ cases of choosing k items of n types with repetition from http://en.wikipedia.org/wiki/Multiset_coefficient#Counting_multisets. I wonder whether there is ...
1
vote
3answers
61 views

How many ways to arrange $6$ children in $4$ bedrooms if at most $2$ kids per room

If I have $6$ children and $4$ bedrooms, how many ways can I arrange the children if I want a maximum of $2$ kids per room? The problem is that there are two empty slots, and these empty slots are ...
1
vote
2answers
72 views

Find $R$ such that $\sum\limits_{n=2k}^{3k}\binom{3k}{n}\cdot{(R)}^n\cdot{(1-R)}^{3k-n}$ is constant for all $k\in\mathbb{N}$

Given $A_k = \sum\limits_{n=2k}^{3k}\binom{3k}{n}\cdot{(R)}^n\cdot{(1-R)}^{3k-n}$ with $0<R<1$. The sequence $A_k$ seems to be decreasing for $R\leq0.6$ and increasing for $R\geq0.8$. How can ...
3
votes
2answers
83 views

Prove by induction that $A_k = \sum\limits_{n=2k}^{3k}\binom{3k}{n}\cdot{(\frac{60}{100})}^n\cdot{(\frac{40}{100})}^{3k-n}$ is decreasing

I want to prove that the following sequence is monotonously decreasing: $A_k = \sum\limits_{n=2k}^{3k}\binom{3k}{n}\cdot{(\frac{60}{100})}^n\cdot{(\frac{40}{100})}^{3k-n}$ I think it should be ...
2
votes
0answers
54 views

Number of faces of a polytopal subdivision

Let $\mathcal{P}$ be a (bounded) polytope in $\mathbb{R}^d$ and let $\mathcal{C}$ be a polytopal subdivision of $\mathcal{P}$ [1]. Is there a known tight upper bound in the number of polytopes in ...
6
votes
4answers
68 views

$k$-th number in $N \times M$ Table

Given an array $A$ , where $A[i][j] = i\times j$ and $1 \leq i \leq N, 1 \leq j \leq M$ , then what is the best way to find the $k$-th number in this array , if we order them into a single array in ...
1
vote
1answer
27 views

Writing $n$ as the sum of $m$ positive integers (without order)

Let $p(n,m)$ denote the number of ways of writing the integer $n$ as a sum of $m$ positive integers, regardless of any ordering. Prove that $p(n,m)=0$ if $m>n$ Prove that $p(n,1)=1$ ...
0
votes
1answer
31 views

Permutation problem - How many permutations are there such that no two numbers are immediately adjecent? [duplicate]

Consider the set of numbers 1,1,2,2,3,3,4,4. How many permutations are there such that no two identical numbers are immediately adjacent?
1
vote
0answers
26 views

Finding an array of numbers knowing the distribution and possible values

There is an array of 16 unknown numbers, which I need to find. I know that numbers are whole and can take values from 0 to 7. I also know what values the numbers can take in the array. I will give an ...
2
votes
0answers
46 views

hat matching problem (Ross, p.41)

I'm studying Ross's probability book, and kind of got stuck on the matching problem. Suppose that each of N men at a party throws his hat into the center of the room. The hats are first mixed up, and ...
1
vote
1answer
38 views

Number of subsets intersecting certain sets

I've puzzling this for a while, and I'm starting to doubt that there is a reasonable-looking closed form; and if you could give me some pointers towards which sorts of techniques I might want to look ...
0
votes
1answer
40 views

Expected Value Intermediate Counting Problem

A palindrome is chosen at random from the list of all 6-digit palindromes, with all entries equally likely to be chosen. (Recall that a palindrome is a number that reads the same forward and ...
2
votes
1answer
42 views

Partition of graph with maximal score

Let $G=(V,E)$ be an undirected graph. Suppose that we partition the nodes into groups $C_1,C_2,\ldots,C_k$. The score of group $C_i$ is $E(C_i)/n(C_i)$, where $E(C_i)$ is the number of edges within ...
5
votes
1answer
111 views

Combinations mod $n$ property

So after some "fooling around" I came across this property in Pascal's triangle (which seems to repeat, and makes a lot of sense): $\begin{pmatrix} n \\ k \end{pmatrix} \mod n = \begin{cases} n ...
1
vote
0answers
34 views

A Vandermonde like identity for binomial coefficients

The Vandermonde identity is given by $ \left(\begin{matrix} m + n \\ j \end{matrix}\right) = \displaystyle\sum_{j=0}^k \left(\begin{matrix} m \\ j \end{matrix}\right)\left(\begin{matrix} n \\ k-j ...
1
vote
2answers
48 views

4 pairs of identical pens.

Say I have 4 pairs of identical pens (say red, blue, green and black). How many ways can I arrange them such that no two identical pens are next to each other? Inclusion/Exclusion works (I get 864) ...
2
votes
1answer
28 views

Arrangements of the word ISOMORPHISM

Say I want to arrange the letters of the word ISOMORPHISM, such that no two vowels are next to each other but the vowels are in alphabetical order. What I'd do is firstly consider the consonants ...
1
vote
0answers
23 views

Weak compositions with bounded partial sums

Is there an easy way to count the number of weak m-compositions of n whose partial sums are lower bounded by some function? Example: Let K be a weak 3-composition of 4 K = (k1, k2, k3) Let s(t) be ...
0
votes
1answer
81 views

How many squares can be formed from n equidistant points in a circle?

I am trying to find a general formula for finding the number of squares that can be formed from n points that are equidistant from each other and placed on the circumference of a circle, I started ...
0
votes
2answers
59 views

How many positive integer solutions are there to the inequality $x_1+x_2+…+x_r\le n$?

The original problem is there are $r$ identical boxes and $n$ identical balls. Every box is nonempty. Then how many ways of putting balls in boxes? It is equivalent to the problem of finding ...
0
votes
1answer
48 views

How do 3 points define a plane?

I was solving a combinatorics problem which asked me to find the number of planes that can be constructed from a set of 25 points such that no 4 points in the set of 25 points are co-planar and then I ...
-1
votes
3answers
86 views

Trailing zeroes on factorial? [closed]

How many zeroes are at the end of the product (100!)(200!)(300!) when you multiply it all out? Thank you for your help in advance.
0
votes
0answers
20 views

Probability of x pocket pairs at a table of n people (NLHE)?

With n people at a table, what is the probability that x of them are dealt pocket pairs? There are several easy ways to approximate this but I was wondering there was an elegant solution. Any takers?
1
vote
0answers
67 views

Geometrical application of generation function for permutation

It is quite well known that the generation function for permutations is represented as $$(1+x)(1+x+x^2)\dots(1+x+x^2+x^3...+x^{n−1})$$ (See, e.g., question The generating function for permutations ...
0
votes
1answer
41 views

Intermediate to Advanced level Counting Problem [closed]

In how many ways can we fill a 3 by 3 grid with 0s and/or 1s, so that every row and every column has an odd total?
-1
votes
1answer
178 views

Number of ways to win chocolate game

Alice and Bob are playing a game. They have N containers each having one or more chocolates. Containers are numbered from 1 to N, where ith container has A[i] number of chocolates. The game goes like ...
0
votes
1answer
64 views

Is this solution correct? 4

There are $3$ black balls and $18$ white balls. In how many ways the balls can be arranged such that no two black balls are together? Solution: The number of ways of arranging all the balls ...
0
votes
0answers
47 views

generating function combinatorics solution

I am studying generating functions in combinatorics, and came across a problem that has already been posted here: Generating function and combinatorics =x^10(1-x^6)^10 * (1+x+x^2....)^10 I ...