For 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)

0
votes
0answers
24 views

Probability of common element existence in random subsets

Consider a set $S$ of $N$ numbers. Fix a collection $T$ of $N^{\frac{4}{6}}$ numbers. Supposing we pick a pair of random subsets $T_1$, $T_2$ from $T$ with cardinality $N^{a}$ each, what is ...
4
votes
0answers
80 views

Has anyone seen this combinatorial identity involving the Bernoulli and Stirling numbers?

Does anyone know a nice (combinatorial?) proof and/or reference for the following identity? $$\left( \frac{\alpha}{1 - e^{-\alpha}} \right)^{n+1} \equiv \sum_{j=0}^n \frac{(n-j)!}{n!} |s(n+1, ...
0
votes
3answers
104 views

How many arrangements of letters in REPETITION are there with the first E occurring before the first T?

The question is: How many arrangements of letters in REPETITION are there with the first E occurring before the first T? According the book, the answer is $3 \cdot \frac{10!}{2!4!}$, but I'm having ...
0
votes
1answer
42 views

Combinatorics (coloring)

I know how to solve the two individual problems (lines alone and circles alone) but not combined.
-1
votes
1answer
39 views

In how many ways can 4 letters be chosen from the word TANGENT?

From a text book , the answer to this question is $5C4$. Why is this? Isn't the answer to be determined by examining all possible combinations of the groups TT and NN and AGE, which would give a ...
2
votes
3answers
74 views

Compact form of sum $\sum\limits_{k=0}^m (-1)^k \binom{n}{k} \binom{n}{m-k}$

How to find compact form of the sum $$\sum\limits_{k=0}^m (-1)^k \binom{n}{k} \binom{n}{m-k}$$ It looks like it's connected with Vandermonde's identity but I couldn't get to the solution.
0
votes
1answer
28 views

Ways of selecting at most n objects from a set containing k distinct elements where each element can occur any number of times.

I have a box with a maximum capacity of n elements. A state of the box is defined by the elements in it. There is an infinitely large heap which has k distinct elements; each element is available ...
0
votes
0answers
42 views

Measure all weights

Given a weight w(of W kg) in integer, and we need to find the minimum no. of weights we should have to measure all the weights from 1 kg to w kg(both included). Example : If w=5 then answer is 3 as ...
1
vote
1answer
58 views

What is a closed form for $\sum_{r=1}^k \binom nr$, where $k\leqslant n$.

What will be the closed form of the following equation $$\sum_{r=1}^k C(n,r), $$ where $n$ and $k$ are positive integers with $k\leqslant n$?
0
votes
2answers
59 views

In how many ways can you distribute $3$ chocolates among $2$ kids if you have to give all $3$ of the chocolates to the kids? [closed]

In how many ways can you distribute $3$ chocolates among $2$ kids? One kid can get none. But we need to give away all $3$ of the chocolates to the $2$ kids. Why is it wrong to use $3C2$(which gives ...
0
votes
1answer
33 views

Constructing a topological invariant in discrete space

Consider a $d$-dimensional discrete space with infinitely many cells. The Location of a cell is denoted by $x=(i_1,i_2,\dots,i_d)$ with $i_k \in \mathbb N$. Now I can define a function $\omega(x)$ ...
0
votes
1answer
33 views

Upper bound to multinomial coefficient sum

I'm currently stuck on what seems like a very trivial problem. I have the following calculation $$ \sum_{k_1+k_2=0}^{n} {n \choose n - k_1 - k_2, k_1, k_2}^2 \le \sum_{k_1+k_2=0}^{n} {n \choose ...
2
votes
2answers
195 views

$12$ Identical balls can be placed into $3$ identical boxes,

$12$ Identical balls can be placed into $3$ identical boxes, Then find probability that one of the boxes contain exactly $3$ balls. $\bf{My\; Try::}$ First we select $1$ bag out of $3$ and then ...
3
votes
0answers
33 views

Partial sum of squared binomial coefficients

Is there any formula for the partial sum of squared binomial coefficients $$S_n(k):= \sum_{i=0}^{k} \binom{n}{i}^2,$$ where $k<n$? Thank you in advance.
0
votes
2answers
29 views

Finding which of six numbers was used to make its sum

I have $6$ numbers: $C_1 = 1$, $C_2 = 2$, $C_3 = 4$, $C_4 = 8$, $C_5 = 16$, $C_6 = 32$ They could also be seen as $2^i$. If I am given a sum that is made up of some or all or none of these $6$ numbers ...
1
vote
2answers
23 views

How many people were at a party determined by the number of handshakes

At a party, everyone shook hands with everybody else. There were $66$ handshakes. How many people were at the party? I saw this question as pretty straightforward, but when I checked the solutions, ...
-3
votes
2answers
39 views

Summation Of Series of $\binom{x+k}{k+1}$ where $k$ is $0$ to $n$ [duplicate]

Want The formula or to find The Sum of Series where $$S=\sum_{k=0}^n \binom{x+k}{k+1}$$ where $x$ is any constant $\geq 1$ and $n$ is another constant.
2
votes
2answers
116 views

How to calculate $\sum_{m=1}^{N}\binom{m+k-1}{m}$. [closed]

What would be a simplified formula for $\displaystyle \sum_{m=1}^{N}\binom{m+k-1}{m}$ for a given number $k$ and any number $N$?
2
votes
0answers
30 views

Multivariable generating functions

Let's consider a 2-variable generating function for the Dyck triangle numbers. Reccurence, satisfying to the triangle conditions is $d_{n, k}=d_{n-1, k-1}+d_{n-1, k}+d_{n-1, k-1}$, $d_{0, 0}=1$, ...
1
vote
2answers
59 views

Walks on a n x n grid

Suppose a person is walking on an n x n grid, starting from the lower, left corner (0,0) walking up to the upper-right corner (n-1, n-1). How many different paths are possible for the person to reach ...
0
votes
2answers
86 views

Diagonalizing a power set

$S$ be any non-empty set, $2^S$ denote the power set of $S$. Let $f$ be a function from $S$ to $2^S$, where for each $x \in S$, $f(x) \subseteq S$. Also, $f$ is injective. Show that $f$ cannot ...
0
votes
1answer
74 views

Summation of binomial coefficients [duplicate]

Is there a closed formula for: $\sum_{i=1}^{N}{\binom{i+k}{i}}$ ( k is a constant whole number )
1
vote
3answers
66 views

combinatorics summation problem

My problem is following: $$\binom{n}{r} + \binom{n+1}{r+1} + \binom{n+2}{r+2} + \dots + \binom{n+M}{r+M}$$ how can we reduce it to a more short solution Here $\dbinom{n}{r} = \dfrac{n!}{r! (n-r)!}$ ...
0
votes
1answer
30 views

What is the number of words of length $h$ in a sequence of subsets of words?

Let $L=\{0,1\}^*$ (the set of binary words on $0$ and $1$), Given an integer $k$, and $S$ a finite subset of $L$ define recursively the following sequence of subsets of $L$: $$\begin{align} A_1 ...
-1
votes
1answer
38 views

Probability of getting an unknown question [closed]

There are 20 questions. 5 of them are chosen randomly. Lets say, I know the answer of 16 questions. What is the probability of getting at least one question of which I don't know the answer?
2
votes
0answers
60 views

Number of Points Inside a Rectangle

This question is from a Japanese contest: Let $S$ be a set of 2002 points in the coordinate plane, no two of which have the same $x$- or $y$- coordinate. For any two points $P,Q$ in $S$ consider ...
3
votes
2answers
66 views

Number of Ways of Partitioning a Rectangle

Given a rectangle of integer sidelengths $m\times n$, consider partitioning it into smaller rectangles also of integer sidelengths. How many such partitions are possible? I wonder if this is just an ...
0
votes
1answer
28 views

Probability and Counting

A friend of mine gave this for me to solve and I can't figure it out. I fail to see the correlation of houses and classes when we do not know how many people are in each house. The students at a ...
0
votes
0answers
14 views

Producing a binary string that has maximum distance to a set of binary strings

Suppose I have a set of $d$-length binary strings $S = \{0,1\}^{k\times d}$. How can construct a new string of $d$-length so that the minimum hamming distance w.r.t. the strings in $S$ is maximized?
2
votes
1answer
39 views

Coloring integers: there exist 2000 consecutive integers among which 1000 of each color

Every integer number is colored red or blue.We know that, for each finite set of consecutive integer numbers , the absolute value of the difference between the number of integers colouredof red and ...
3
votes
2answers
141 views

Sum of combinations with varying $n$ [duplicate]

What is the sum of number of ways of choosing $n$ elements from $(n+r)$ elements where $r$ is fixed and $n$ varies from $1$ to $m$ ? Can this be reduced to a formula ? $$ \sum ^m _{n=1} \binom{n + ...
0
votes
0answers
30 views

Arithmetic progressions in subset

Let $S$ be a subset of $\{1,\dots,n\}$. Does there exist a good algorithm to find a partition of $S$ into "reasonably long" arithmetic progressions? Many thanks!
1
vote
5answers
355 views

Count increasing sequences

Given three positive integers $N, L $ and $R$, we need to find the number of non-decreasing sequences of size at least $1$ and at most $N$, such that each element of the sequence lies between $L$ and ...
2
votes
1answer
31 views

What is the minimum longest repeated substring of a binary string of size n?

The longest repeated substring of 0111011 is 011 for example. My question is given the size of a binary string, what is the shortest this longest repeated substring can be. I have computed values for ...
1
vote
0answers
24 views

Getting stuck in a loop or the probability of hitting all points in a random walk around a circle.

Suppose you are walking around a circular path made up of $n$ tiles. Each tile $i$ is assigned a distinct value $r_i$ by a random variable uniformly distributed on the set of integers $\{1,...,k\}$ ...
1
vote
0answers
33 views

Picking $3n$ subset with repetitions allowed from $\{A,B,C\}$ with conditions - is my generating function correct?

I'm trying to solve the following cominatorics problem: How many ways are there to choose $3n$ subset with repetitions allowed from set $\{A,B,C\}$ where $A, B$ are present at most $2n$ times each ...
2
votes
1answer
38 views

How many 3-digit positive integers are there whose middle digit is equal to the sum of the first and last digits?

How many $3$-digit positive integers are there whose middle digit is equal to the sum of the first and last digits?
2
votes
1answer
35 views

Number of combinations in a string with n states

I have a problem in biology involving amino acids (think of them as a string of characters) that I want to formalise. Let assume we have a amino acid sequence of length 4, typical examples may be: ...
5
votes
2answers
85 views

If $\sum_{i=1}^n a_n=0$ then you can find a “good” ordering of $a_i$.

I'm trying to prove (or disprove, but I think it's true and I'll be surprised if someone would manage to disprove it) a small theorem. Given an array of real numbers $A=[a_1,a_2,...,a_n]$ such that ...
3
votes
1answer
47 views

Number of invertible matrices over finite rings

Is there an exact formula for the number of invertible matrices over the ring $\mathbb{Z}_n,$ $n=p_1^{k_1} p_2^{k_2} \ldots p_s^{k_s}$?
0
votes
2answers
64 views

Bonferroni Inequalities

Let $k$ and $m$ be positive integers with $k>m$. Then the partial sums of $$ 1-\binom{k}{1} + \binom{k}{2} - \cdots (-1)^m\binom{k}{m} $$ has alternating signs. (The partial sums of the ...
6
votes
0answers
41 views

Number of circuits that surround the square.

Consider a grid $G$ in the $\mathbb{R}^2$ plane formed by the points $(x,y)$ with integer coordinates i.e. $G=\{(x,y)\in\mathbb{R}^2: x\in\mathbb{Z},\;y\in\mathbb{Z} \}$. For $n>0$ let $B_n$ square ...
0
votes
2answers
67 views

Number of compositions of selection of four letters with limited repetition

In how many ways can 4 letters of the 8-letter word 'TANZANIA' be selected if (i) it has exactly 1 'N' and 1 'A' (ii)it has exactly 1 'N' in part (i) I can understand that we have to forget about ...
0
votes
1answer
47 views

Closed form for nth term - generating functions

I think I am mostly confused about what the question is asking. I read that "closed form" means that it should not be represented as as infinite sum, so I am not sure what they are asking for. Would ...
1
vote
0answers
31 views

Combinatorics : Minimization of the number of common objects between subsets

Let's consider the following setup. I have access to $N$ objects. Thanks to these objects, I can build up sub-packets containing $k$ such objects. I know that there exists a total of $\displaystyle ...
2
votes
4answers
40 views

$10$ Distinct Integers from a set and their sum equals to $954$

$10$ distinct integers from the set $ \left \{1;2;...;100 \right \} $ are chosen such that their sum is $954$. What is the smallest of the $10$ integers? How do I start this question? I have no idea ...
3
votes
1answer
55 views

Partition problem for consecutive $k$th powers with equal sums (another family)

This is the partition problem as applied to a special set, namely the first $n$ $k$th powers. Assume the notation, $$[a_1,a_2,\dots,a_n]^k = a_1^k+a_2^k+\dots+a_n^k$$ I. Family 1 The following ...
-1
votes
1answer
8 views

probability of n balls in n cells two remaining empty

I was interested to see how the problem found on this link (Probability of n balls in n cells, one remaining empty) would be solve if we wanted to know the probability of two cells being empty.
-1
votes
0answers
14 views

Calculating the modulo of a p / q ( i.e., ( (p / q) % M ) ) where q is divisible by p and q and p are very large numbers

How do we calculate the value of $$\frac{p}{q} \textrm{ mod } M$$ where $q$ divides $p$ . Also $q$ and $p$ are very large numbers ?
1
vote
1answer
36 views

How many cycles $A$ and $B$ can form this cycle

How many cycles $A$ and $B$ can form this cycle: $AB=(axyguimjrcwk)(bvqphsleofzt)(d)(n)$ I can see that $A$ and $B$ must share the cycle $(dn)$, and I believe due to ordering, both $A$ and $B$ must ...