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)

5
votes
2answers
189 views

Given any nine integers show that it is possible to choose, from among them, four integers a, b, c, d such that a + b − c − d is divisible by 20.

Given any nine integers show that it is possible to choose, from among them, four integers a, b, c, d such that a + b − c − d is divisible by 20. Further show that such a selection is not possible if ...
0
votes
2answers
48 views

Distinct pairs with equal sum mod p

Let $p$ be a prime and $\mathbb{F}$ be a field with $p$ elements. Define the sets $$A=\{ (m_1,m_2) : m_1, m_2 \in \mathbb{F}, m_1 \neq m_2 \}$$ and $$T =\{ (a_{1},a_{2}) : a_1, a_2 \in A, a_1 ...
2
votes
2answers
90 views

Calculate people needed to have all birthdays

for n people where n > 365, how can you calculate how many people you would need to expect that each of every distinct possible birthday would be had by at least one person at a given probability p? ...
2
votes
1answer
64 views

How to show $2\sum^{n/2}_{k=0}$ $(\frac{1}{2}-\frac{k}{n})\binom{n}{k} $ = $\frac{1}{2}$ $\binom{n}{n/2}$

How to show: $$2\sum^{n/2}_{k=0}\left(\frac{1}{2}-\frac{k}{n}\right)\binom{n}{k}=\frac{1}{2}\binom{n}{n/2}$$ n:even please could you help with this equality. on page 17: Rivlin, an intro to ...
5
votes
2answers
244 views

Shelving identical books

Suppose that we have $5$ red, $5$ black and $3$ white books that are indistinguishable to place onto a) $1$ shelf, b) $3$ shelves, so that no adjacent books have the same colour. How many different ...
2
votes
2answers
211 views

Inverse birthday estimation

We all know the birthday problem. Suppose an inversion* of the birthday problem: given a number of distinct birthdays (c) from a set of people, how can you estimate the number of people you had (n)? ...
0
votes
1answer
83 views

Find all divisors of an polynomial (simple combinatorics)

I want to implement the multivariate Kronecker factorization algorithm and at one stage I need to find out all divisors of a polynomial $u(y,\dots)$. I already know the irreducible factorization of ...
0
votes
1answer
195 views

how to calculate combinations of elements in groups?

How many combinations there are if I have 1 or 0 in a set of 6 elements with the possibility to group them in two (then three, four five and six elements)and in each group must be the same value? ...
1
vote
1answer
45 views

probability for socks pairs

Anna will give all her socks to her five poor aunts. She finds out that she has socks in k different colours. Moreover she has n pairs of each colour(n > 4). In how many ways can this be done if she ...
1
vote
1answer
66 views

Count recursive groupings of elements in pairs

For a given set of elements lets say $s=\{A,B,C,D\}$ I want to compute how many unique elements can be obtained converting the initial set in subsets of size two (pairs). Pairs can be made taking two ...
4
votes
2answers
144 views

Proof sought for a sum involving binomials that simplifies to 1/2

A proof of: $$\begin{align*}(1/2)^{2m+1} \sum_{k=0}^{m} \binom{m}{k} \sum_{j=0}^{k} \binom{m+1}{j} = \frac{1}{2} \end{align*} $$ Conjecture based on the following Maple code: ...
0
votes
1answer
34 views

how fast does the proportion of associative operations on $S$ decrease with |$S$|?

as doubtless many have done before me, i recently fell into wondering how many of the binary operations on a finite set are associative. the stackexchange software fortunately pointed me to this ...
0
votes
1answer
84 views

Proof for the probability that $A[i]<A[j]$ in a random permutation

I'm studying a proof on the expected number of inversions in a permutation of $n$ numbers. The numbers are distinct integers from $1$ to $n$. At some points it takes as given that chosen two indices ...
5
votes
2answers
1k views

number of strictly increasing sequences of length $K$ with elements from $\{1, 2,\cdots,N\}$?

What is the number of strictly incremental sequences of length $K$ with elements from $\{1, 2,\cdots,N\}$ ? Is there any exact value? How about approximations?
1
vote
1answer
1k views

How many compositions of n with k parts are there in which each part is a even number except that a 1 may occur as a part at most once?

I need to find how many compositions of n with k parts are there in which each part is a even number except that a 1 may occur as a part at most once. I have an example for the number of k-part ...
1
vote
2answers
45 views

Drawing with Replacement

Say I have a bag of n marbles, red and blue, and every time I pull out a red marble I colour it blue and replace it. What is P(# of trials until all blue marbles = k)? What kind of distribution ...
1
vote
1answer
76 views

Number of paths? [duplicate]

Hi need help with this question I don't know what to do? Let $m \geq 1$ and $n \geq 1$ be integers. Consider a rectangle whose horizontal side has length $m$ and whose vertical side has length $n$. ...
0
votes
1answer
820 views

How many four digit numbers between 1000 and 9000 can be made that are odd and number 1 and 5 cannot be used?

attempt: numbers you can use (0,2,3,4,6,7,8,9) = 8 numbers first position: (2,3,4,6,,8, 7) = 6 numbers last position: (3,7,9) = 3 numbers Rest of the two positions = 6 and 5 numbers left answer: ...
0
votes
3answers
262 views

Calculating probability with wordings “no more” and “at least”

75% of children have a systolic blood pressure lower than 136 mm of mercury. What is the probability that a sample of 12 children will include: A) exactly 4 who have a blood pressure greater than ...
2
votes
0answers
30 views

How to calculate when a specific semigroup is closed under conjugation by this group.

Let $\mathcal{T}_n$ be the set of $n \times n$ matrices such that $X\in \mathcal{T}_n$ can be written as: $$X = \bigl( \begin{array}{cc} 1 & \overline{0} \\ T & \underline{0} \end{array} ...
0
votes
2answers
69 views

How do you make a passwords which are 15 to 24 characters long and have at least one digit?

I know that you can use the complement to find this so one case could be that you have no digits which would be 10^24. I'm not sure where to go from here. I'm not sure what you need to subtract or ...
1
vote
1answer
125 views

Generalization of principle of inclusion and exclusion (PIE)

The PIE can be stated as $$|\cup_{i=1}^n Y_i| = \sum_{J\subset[n], J\neq \emptyset} (-1)^{|J|-1} |Y_J|$$ where $[n]=\{1,2,...,n\}$ and $Y_J=\cap_{i \in J} Y_i$. Problems using it are usually reduced ...
1
vote
3answers
94 views

How many solution of a equations?

I have the following question: Let $n$ and $k$ be integers with $n \geq k$. How many solutions are there to the equation $$ x_1 + x_2 + \cdots + x_k = n $$ where $x_1, x_2, x_k$ are integers $\geq ...
2
votes
2answers
65 views

Partition of integer with size constraint

A rather straightforward combinatorial question: Given numbers $X, q, n$ such that $0 \leq X \leq n(q-1)$, what are the total number of ways to express $X$ as sum of $n$ numbers, where each summand ...
0
votes
1answer
47 views

Counting Problem - Conditional Probability

Suppose you have 52 cards and know that you are in a state where the only cards you draw are 2,3,4,5,6,7,8,9,10. You draw 4 cards from the 52 cards (36 considering the state you know you are in). ...
0
votes
2answers
128 views

Combinatorics - Check my answer, sitting order, round table.

$n$ people are sitting at a round table with $n$ seats at a restaurant. The restaurant has only 2 dishes, steak and salad. How many ways are there for the diners to choose a dish, such that no 2 ...
5
votes
1answer
73 views

Combinatorics question - count how many ways to write $1,2,…,n$ with a certain order

A valid sequence is a sequence of length $n$ from the numbers $1,2,...,n$ such that: 1) every number appears once 2) apart from the first number in the sequence, every number $k$ has either a $k-1$ ...
2
votes
2answers
75 views

Separating points on a plane

BdMO 2011 There are $25$ points on a plane, no three of which lie on a line. Find the minimum number of lines needed to separate them from one another. Can we assume that the points lie on a ...
1
vote
0answers
52 views

Rectilinear polygons winding around a torus

A simple rectilinear polygon on the plane the difference between the number of interior convex angles ($ 90^{\circ}$) and that of interior concave angles ($ 270^{\circ}$) is always $4$. Consider a ...
-1
votes
2answers
402 views

Ice cream flavors

A survey was taken among $600$ middle school students for their preferred ice cream flavours. $250$ like strawberry $100$ liked both strawberry and vanilla $130$ like strawberry but not chocolate ...
1
vote
3answers
942 views

How many compositions of n are there in which each part is an even number?

I need to find out how many compositions of n there are in which each part is an even number. I think I have the correct generating function by doing the following: $$S = ∪_{k\geq0}N_{even}^k$$ ...
1
vote
2answers
73 views

Counting question?

Hi could anyone do this question for me or something similar cause I got a lot questions like this and I cant solve them thanks Let $n \geq 66$ be an integer and consider the set $S = ...
0
votes
4answers
327 views

Discrete Math- four digit odd integers with distinct digitst

a) Find the number of four-digit odd integers that have distinct digits. b) Find the number of four-digit even integers that have distinct digits. I've been working on this problem and I can't figure ...
2
votes
0answers
68 views

What is the number of simple connected graphs that are sparse (few edges compared to the number of nodes)?

The graphs that I consider are: labelled (so, I do not want to count them up to isomorphism). simple (no loops and at most one edge between two nodes). connected. In How to calculate the number ...
0
votes
2answers
106 views

how many ways are there to choose a Board of Directors consisting of seven distinct people?

If there are n>=7 people in a company that are vying to become a member of the Board of directors, how many ways are there to choose a Board of Directors consisting of seven distinct people? I'm ...
3
votes
2answers
790 views

What does $E[XY]$ mean?

Let's say I have two random variables, $X$ and $Y$. $X$ is the value of a fair die, $Y$ is the result of a coin flip, with heads being 1 and tails being 0. $E[X] = \sum_{k=1}^{6}{\frac{k}{6}} = ...
3
votes
4answers
74 views

Is there a way to assign a number to a combination without finding and numbering every combination?

Imagine I have 4 letters. Is there some algorithm that produces "abcd" -> 1 "bacd" -> 2 "bcad" -> 3 ... etc without finding and numbering every single combination? My goal is to get a number from 1 to ...
2
votes
3answers
251 views

An identity involving the Pochhammer symbol

I need help proving the following identity: $$\frac{(6n)!}{(3n)!} = 1728^n \left(\frac{1}{6}\right)_n \left(\frac{1}{2}\right)_n \left(\frac{5}{6}\right)_n.$$ Here, $$(a)_n = a(a + 1)(a + 2) \cdots (a ...
2
votes
1answer
61 views

Combinatorics of card game states

Suppose we have a card game with some $n$ cards and $m$ players, where $m \mid n$. Each player starts with $\frac{n}{m}$ cards. How many starting states does the game have? How many states can the ...
4
votes
2answers
120 views

How to prove $\frac{1}{q} \binom{p^k q}{p^k} \equiv 1 \mod p\;\;$?

An argument that I just came across asserts that if $p$ is prime, and $k, q\in \mathbb{Z}_{>0}$, then $$\frac{1}{q} \binom{p^k q}{p^k} \equiv 1 \mod p \;.$$ This assertion was made in a way (i.e. ...
1
vote
0answers
54 views

Designing a probability question with two unknowns but a unique solution

I'm trying to design a probability problem with two unknowns, one equality, and a unique solution. My first attempt: Trillian has $n$ mice, of which $w$ are white. She chooses four at random. The ...
0
votes
1answer
147 views

number of ways to fill a 2D grid

We have a 2D grid with n rows and m columns, we can fill it with numbers between 1 and k (both inclusive). Only condition is that for each r such that 1<=r<=k ,no two rows must have exactly the ...
1
vote
1answer
188 views

Arranging red and blue tiles in a line with at least 1 blue tile between any 2 red tiles

BdMO 2010 Nationals: Tom and Jerry have $8$ blue tiles and $6$ red tiles.They want to arrange them in a straight line so that between any $2$ red tiles there is always at least $1$ blue tile.In ...
1
vote
0answers
173 views

Baseball Statistic Problem

Problem If a batter has a batting average of 300 (he hits 30% of his times at bat), what is the probability that the batter has a streak of six hits? Attempt I see that there are 2^6 = 64 possible ...
0
votes
3answers
193 views

How many valid paths are there?(counting problem)

Consider a rectangle whose length is m and whose height is n. A path from bottom left corner to top right corner is called valid, if in each step, it either goes one unit to the right or one unit ...
1
vote
1answer
106 views

Counting number of subsets with restriction

Let $x\geq 66$ be an integer and consider set $S = \{1,2,3,4....,x\}$ (1) $k$ is an integer with $66\leq k\leq x$. How many $66$-element subsets of $S$ are there whose largest element is equal to ...
3
votes
1answer
99 views

combinations $\sum_{k=1}^m kn_k=m!$

If $n_k$'s are non-negative integers, how many ways can we solve $$ \sum_{k=1}^m kn_k=m!. $$ I don't even know if the answer can be written in a nice form (as a function of $m$). Any suggestions or ...
2
votes
2answers
92 views

Number of functions with some property

A function $f$ is defined on the set $\{0,1,2,3,…,n-1\}$ to itself. This is a function such that if you take any $k$ from the set $\{0,1,2,3,…,n-1\}$ then $f^m (k)=0$ for some natural number $m$. ...
1
vote
2answers
216 views

Basic combinatoric problem

I'm working on this problem and am not sure where to go next. The problem is: A student is given a true-false test with 10 questions. If she gets seven or more correct, she passes. If she is ...
0
votes
1answer
61 views

Constrained disjoint subsets

How to partition $n$ weighted elements into $m$ disjoint subsets such that the sum of weight of all elements in a subset is less than equals to the capacity of $j$th subset ($c_j$) . It is given that ...