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
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
29 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
65 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
37 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
45 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
66 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 ...
1
vote
0answers
26 views

Finding the probability mass function in a balls and urns problem

I have $n$ balls and $m$ urns, and each ball is equiprobably distributed among the urns. Let $X$ be the random variable counting the number of empty baskets. What is the general probability mass ...
1
vote
2answers
145 views

Is applied mathematics dead? [closed]

I am an undergraduate currently enrolled in a applied math program. Recently, I have been having discussions with my professor who is teaching an introductory course to combinatorics and optimization. ...
0
votes
0answers
19 views

Show that $\Delta^{-1}\sin\alpha x = - \cos(\alpha x - \frac{α}{2})/(2\sin \frac{\alpha}{2}) + c(x)$ for fixed $\alpha\in \Bbb{R}$.

Show that $\Delta^{-1}\sin\alpha x = - \cos(\alpha x - \frac{α}{2})/\left(2\sin \frac{\alpha}{2}\right) + c(x)$ for fixed $\alpha \in \Bbb{R}$. I can find a few tables for anti-difference tables ...
2
votes
2answers
26 views

Question about an exercise from Feller

The following is an exercise from the classical textbook of Feller on probability theory. Four girls take turns at washing dishes. Out of the total of four breakages, three were caused by the ...
0
votes
2answers
28 views

By the binomial theorem, use this result to show with explanation that the number of subsets of a set $S$ is $2^{|S|}$

Given that $(1+1)^n = 2^n = \sum^n_{k=0} \binom{n}{k}$ by the binomial theorem use this result to show with explanation that the number of subsets of a set $S$ is $2^{|S|}$ I'm really confused. So ...
-1
votes
2answers
50 views

Number of ways for 7 people to be seated so that two particular ones are separated by 3

7 boys are to be seated in a row. Calculate the number of different ways in which this can be done if 2 particular boys, X and Y, have exactly 3 other boys between them. I have posted an image of ...
0
votes
1answer
30 views

how many ways you can take 4 integers from the N numbers such that their GCD is 1

how many ways you can take 4 integers from the N numbers such that their GCD is 1 Given N positive integers, not necessarily distinct, how many ways you can take 4 integers from the N numbers such ...
0
votes
2answers
70 views

There is a group made of 25 people made of 10 men and 15 women…

There is a group made of $25$ people made of $10$ men and $15$ women. How many committees of $2$ men and $3$ women ($5$ people total) can be chosen from this group? I know you are supposed to use ...
0
votes
1answer
19 views

How many 5-permutations of Q are there? (No repetition of character within a string and order matters)

How many 5-permutations of Q are there? (No repetition of character within a string and order matters) Q = {A, B, C, D, E}. So I think i'm supposed to be using the formula $(^n_k) = ...
3
votes
0answers
26 views

Problem on distributive lattices

I'm trying to prove the following: Show that a lattice is distributive if and only if it does not contain a sublattice isomorphic to either of the two lattices below. I was able to prove that ...
1
vote
2answers
64 views

How to represent a number in such a way that no more than 2 consecutive digits are the same?

The idea is to lower the probability of transcription errors when a person is reading the number on a paper and typing it on a computer, for instance. I'd be more interested in Base-58 notation, but ...
0
votes
0answers
23 views

Number of operation to transform $(0,0,0)$ to $(a,b,c)$ with $2^h\leq a,b,c \leq 2^h-1$

Given a positive integer $h$, define: $$A_h=[2^h,2^{h}-1]\big \{2^h-1+\sum_{i\in A}2^i \Big/ A\subset[0,h-1]\big \}$$ (this is in terms of binary expressions: the set of all numbers having exactly $h$ ...
0
votes
0answers
24 views

How many different sets of positive numbers have the sum of its elements equal to n?

The sets of number must satisfy the following conditions: The sum of numbers in it must equal to $N$. Each numbers can only appear once or less in the set. Sets must contain $2$ or more positive ...
3
votes
1answer
97 views

Complex Analysis proof of multinomial expression

I've recently come across the following identity $$ \displaystyle \sum_{k = 0}^n {n \choose k}^2= {2n \choose n} $$ A nice complex analysis proof (by Felix Marin, here) follows as: ...
0
votes
1answer
14 views

Stirling numbers of first kind induction proof

Prove by induction that $s(n, n-1) =$ $-$$n \choose 2$, where $s(n,k)$ is a Stirling number of the first kind. Workings: Proof: Base Case: $n = 2$ $s(2,1) = -1$ $-$ ${n} \choose {2}$ $= -1$ $-1 ...
0
votes
0answers
29 views
2
votes
4answers
157 views

Sequences that contain subsequence $1,2,3$

How many sequences can we construct using $a$ $1$'s, $b$ $2$'s and $c$ $3$'s under the condition that we can find $1$ before $2$ before $3$ (somewhere, in that order, but not necessarily consecutive)? ...
3
votes
1answer
57 views

$(a_1,\cdots a_n)\rightarrow (|a_1-a|,\cdots ,|a_n-a|)\rightarrow\cdots\rightarrow (0,\cdots ,0)$

NOTE: I only need verification of part (b) of this question. But feel free to comment on anything about this question. Given an initial sequence $a_1,\cdots a_n$ of real numbers, we perform a ...
2
votes
1answer
48 views

Trouble Understanding Counting Problem

Recall that in chess a queen attacks any square that is on a straight line (horizontally, vertically, or diagonally). Suppose a queen "attacks" the square it occupies. What is the smallest number of ...
2
votes
1answer
63 views

Contest problem - Solution is beyond my comprehension

Starting with the number 0, Casey performs an infinite sequence of moves as follows: he chooses a number from {1, 2} at random (each with probability $\frac{1}{2}$) and adds it to the current number. ...