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)

-1
votes
1answer
55 views

Find the number of six-digit numbers that can be formed

find the number of six-digit numbers that can be formed using the digits from the number 112 233. If these numbers are arranged in ascending order,find a.) the largest number. b.) the 30th number. ...
-1
votes
2answers
37 views

ways to buy the six marbles [closed]

A boy wishes to buy exactly six marbles. There are four different colours of marbles available. In how many ways can he buy six marbles? hint:arrange 111 000000
19
votes
1answer
372 views

What function satisfies $F'(x) = F(2x)$?

The exponential generating function counting the number of graphs on $n$ labeled vertices satisfies (and is defined by) the equations $$ F'(x) = F(2x) \; \; ; \; \; F(0) = 1 $$ Is there some closed ...
3
votes
1answer
37 views

A problem on counting sub-graphs

How many distinct sub-graphs of a complete graph of $n$ labelled vertices are there, such that the sub-graph is a spanning tree connecting all the vertices and the degree of no vertex is more than ...
4
votes
2answers
111 views

Maths Puzzle: Partitioning a set into two disjoint sets

Le $X$ be the set of all non-empty subsets of $\{a,b,c,d,e,f\}$. So $X=\{a,b,c,d,e,f,ab,ac,ad,ae,af,bc,bd,be,bf,cd,ce,cf,de,df,ef,abc,\cdots,abcdef\}$; i.e., $|X|=63$. We want to partition $X$ into ...
0
votes
1answer
31 views

Given the size of $\mathscr{U}, A, B$, how many possible combinations of $A$ and $B$ such that $A\cap B \neq \varnothing$?

Given the $\mathscr{U} = n, |A| = c_1$, how many possible set $B$ with size $|B| = c_2$ are there, such that $A \cap B \neq \varnothing$.
5
votes
4answers
97 views

Verify that $\binom{n+1}{4} = \frac{\left(\substack{\binom{n}{2}\\{\displaystyle2}}\right)}{3}$ for $n \geq 4$

Verify that for $n \geq 4$ $$\dbinom{n+1}{4} = \frac{\left(\substack{\binom{n}{2}\\{\displaystyle2}}\right)}{3}$$ Now present a combinatoric argument for the above. First, by verify does ...
1
vote
1answer
61 views

Construction of Rauzy Fractals with substitutions without a fixed point

The formal definition of a Rauzy fractal can be found at the beginning of this paper Using Sage-math-cloud, I can generate Rauzy fractals of substitutions that I choose. Should I choose the ...
0
votes
1answer
70 views

Verifying coin flipping result

An interesting coin flipping game is described here: flip a fair coin, stopping whenever you like, with a maximum number of tosses. Try to maximize the ratio of heads to total flips. What is the ...
4
votes
1answer
94 views

What tactics could help with this probability questions

I'm not too sure if this question is solvable (I sort of just thought of it yesterday) but when I brute force numerical answers on my computer they seem to show a pattern, so I believe it to be ...
10
votes
1answer
1k views

Why isnt there only one way of painting these horses?

If you have $11$ identical horses in how many ways can you paint 5 of them red 3 of them blue and 3 brown. My intuition instantly tells me there is only one way of doing this. I mean if the ...
2
votes
1answer
39 views

Number of combinations of selecting $r$ numbers from first $n$ natural numbers of which exactly $m$ are consective.

Number of combinations of selecting $r$ numbers from first $n$ natural numbers of which exactly $m$ are consective. Say $g(n,r,m)$ is the number of such combinations. The two cases of $m=r$ and $m=1$ ...
11
votes
2answers
90 views

Let $x$ be an irrational number. Prove that there exist infinitely many rational numbers $\dfrac pq$ that satisfy the following

$$\bigg|\,x-\dfrac pq\,\bigg|<\dfrac 1{q^2+q}$$ My idea would be to solve the inequality for $\frac pq$ and then somehow use the pigeonhole principle. Is this heading in the right direction? Any ...
2
votes
2answers
78 views

Messaging probabilities

New to site! I'm a near-retirement cellist who likes to mess with math, but I have a probability problem beyond me. I'm part of a large family - we have twenty-four people who send texts back and ...
1
vote
2answers
26 views

Probability of getting same configuration in 2 throws with R dices

EDIT: There's same question already: Probability of throwing the same multiset twice in a row with six dice I'm trying to find general solution for a problem from Feller's book (p. 56): What ...
3
votes
2answers
79 views

Graph theory-related problem, unit distance graph, pairs of people with restraining orders

This problem is for my own exploration, not for class. The problem goes as follows: There are $n$ pairs of people with restraining orders against one another. However, all $2n$ people are friends ...
3
votes
5answers
88 views

How many $5$ element sets can be made?

Let $m$ be the number of five-element subsets that can be chosen from the set of the first $14$ natural numbers so that at least two of the five numbers are consecutive. Find the remainder when $m$ ...
0
votes
1answer
50 views

Mountain of coins

Let a mountain of coins be an arrangement coins in rows such that the coins in each row form a single block, and that in all rows (except the bottom row) each coin touches exactly two coins from the ...
1
vote
1answer
48 views

Special Palindromic String

A string of length $N$ can be made from $6$ characters $a$, $b$, $c$, $d$, $e$ and $f$. There are some rules to make such a string: 1) $b$ can not come directly after $a$. 2) $d$ can not come ...
2
votes
3answers
105 views

Fast way to get a position of combination (without repetitions)

This question has an inverse: (Fast way to) Get a combination given its position in (reverse-)lexicographic order What would be the most efficient way to ...
3
votes
3answers
1k views

Place maximum Rooks on a chessboard

I am given a chessboard of size $8*8$. In this chessboard there are two holes at positions $(X1,Y1)$ and $(X2,Y2)$. Now I need to find the maximum number of rooks that can be placed on this chessboard ...
2
votes
1answer
53 views

Easiest way to find the 'area of a Venn diagram,' given certain information.

We have a bunch of intersecting regions: $$X_1,\dots, X_n,$$ all with non-negative volume, and we know $V(X_i)$ and $V\left((\cup_{a\in A}X_a)\cap (\cup_{b\in B}X_b)\right)$ for any disjoint ...
2
votes
2answers
58 views

Generate all De Bruijn sequences

There are several methods to generate a De Bruijn sequence. Is there a general algorithm to create all unique (rotations are counted as the same) De Bruijn sequences for a binary alphabet of length ...
1
vote
1answer
22 views

Writing a Sum of Partition Items in Combinatorial Form

For each partition $\lambda$ we can define \begin{equation} n(\lambda) = \sum_{i \geq 1}(i-1)\lambda_i. \end{equation} According to my book this is equivalent to \begin{equation} n(\lambda)=\sum_{i ...
0
votes
0answers
45 views

Question on how to manipulate terms in this expression

sorry for the vague title, i dont know how else to express what i mean with this question. But what i need to do is find out which terms on the RHS of the expression are constants. It is clear that it ...
5
votes
2answers
53 views

Floor Function Equation

How many positive integers $ N$ less than $ 1000$ are there such that the equation $ x^{\lfloor x\rfloor} = N$ has a solution for $ x$? (The notation $ \lfloor x\rfloor$ denotes the greatest ...
21
votes
1answer
375 views

What is the intuition behind generating functions? What makes them valuable?

I'm sorry if this question makes no sense. I have been reading generatingfunctionology and I have been able to solve the problems in the first chapters and I understand the mechanism I have to follow ...
0
votes
1answer
21 views

Representing a combinatorial sum with an equation

I am trying to represent a situation with an equation that is fairly conceptually simple, but I am not sure what is the proper way to represent it as a formal mathematical equation. I have a set of n ...
1
vote
1answer
16 views

Maximal number of subsets with 3 elements and small intersection - special Constant Weight Codes

in the middle of some proof I encountered a combinatorial problem and tracked it back to the theory of Constant Weight Codes. Those problems seem hard to solve, but my question is rather specific, so ...
0
votes
0answers
30 views

Calculating the minimum number of players required for a system to operate

Players wish to find other players to play games against, games are 1 v 1. Games are played in discrete time periods of 1 hr on the hour for one week (i.e. starting Monday 00:00 and ending Sunday ...
3
votes
2answers
57 views

Maximum and minimum Expected values when taking colored balls

We have a sack with $60$ balls. From them $15$ balls are red, $15$ green, $15$ blue and $15$ yellow. We take $30$ balls from the sack. What's the expected number of balls of the color from which ...
0
votes
4answers
48 views

Choosing a ball randomly from each urn

I am stucked at this combinatorics/probability problem: There are 10 urns, each contains 8 balls numbered 1,2,...,8 If we randomly choose 1 ball from each urn, what is the probability that the ...
1
vote
1answer
43 views

Find the Sum using bijection

Find the sum of $S=\displaystyle\sum_{i,j,k \ge 0, i+j+k=17} ijk$. I am looking for a solution that uses some bijection. I couldn't find any bijection. I am able to do the problem by other method by ...
0
votes
1answer
105 views

number of ways to choose a convex subset that contains exactly 98 points (from MIT-Harvard Math Tournament) [closed]

A set of points is convex if the points are the vertices of a convex polygon (that is, a non-self intersecting polygon with all angles less than or equal to $180^\circ$ ). Let $S$ be the set of points ...
8
votes
3answers
153 views

Non combinatorial proof of formula for $n^n$?

I came across the below identity: $$ n^n=\sum_{k=1}^n\frac{n!}{(n-k)!}\cdot k\cdot n^{n-k-1} $$ A combinatorial proof of this fact is as follows. Consider the collection of lists of length $n$, where ...
1
vote
2answers
49 views

Number of finite-state machines with $n$ states, output alphabet size $a$, and binary input

How many FSMs are there where the machine has $n$ states, reads a binary symbol at each time-step, and may or may not output a symbol from an alphabet of size $a$ after each transition?
0
votes
2answers
69 views

Find the coefficient of $x^{17}$

Find the coefficient of $x^{17}$ in:$$ (1 + x^5 + x^7)^{20}$$ $x^{17} = x^{5} x^5 x^{7}$ I would say: $$\frac{17!}{5!5!7!} $$ But this isnt the correct answer. I know I need to use ...
2
votes
1answer
53 views

Homomorphism of Free Groups

I am reading the theorem of homomorphism of free group from Fraleigh's text in $\S$36 and could only get a fuzzy idea at best: Let $G$ be generated by $A = \{a_i \mid i \in I \}$ and let $G'$ be ...
1
vote
1answer
37 views

TCP Connection, 6 Packets, Probability of certain arrival orders

So I have a very hard time with statistics and probability. This comes from not being able to extract what I need to do from the given information. I don't get why I can't solve such easy stuff... :( ...
2
votes
2answers
47 views

Ways to make change

Given unlimited coins with values $1^2$, $2^2$, $3^2$, $4^2$,..., $17^2$ Now given an amount X, in how many ways can we exchange it using these coins? Example for $X=24$ answer is $16$. It means ...
3
votes
1answer
32 views

Equality of unions of subsets of finite set

For $n \in \mathbb{N}$, let $\alpha_n$ be the biggest number such that there exist $\alpha_n$ subsets $M_1, \dots, M_{\alpha_n} \subseteq \{1, \dots, n\}$ with the property \begin{equation*} M_{i_1} ...
10
votes
1answer
477 views

A polynomial sequence

I have a sequence of polynomials $Q_k(x, y)$, $k\geq 1$ defined recursively as follows: $Q_1=x$. There is a sequence of polynomials $p_j(y)$ of degree $j$ such that $Q_{2m}$ is of the form ...
-3
votes
0answers
35 views

12- In a standard deck of 52 cards, how many ways can you deal out 4 cards that are all black or all not face cards? [duplicate]

I did the sad mistake of taking math in summer school to boost my average. I am stuck on a few questions. In a standard deck of $52$ cards, how many ways can you deal out $4$ cards that are all ...
2
votes
2answers
54 views

Simplifying a Triple Summation

I have the summation: $$ \sum_{c=1}^{n-1} \sum_{k=c}^n \sum_j \frac{\rho(n,k)}{j!(k-c-j)!(c-j)!} $$ Where the sum $j$ goes from $0$ to $k-c$ if $k-c \leq c$, but if $k-c \geq c$ then the sum goes from ...
0
votes
0answers
11 views

Is this a Combinatorial Optimization problem with Multiple Constraint Satisfaction?

Given n-dimensional data consisting of over 20000 samples with 200 dimensions, using this as an example: ...
1
vote
1answer
61 views

“At least” type probability question.

Recently, I asked a question: Team A has more Points than team B Though I ultimately got the right answer, it took extreme casework, and long computations. My question is: suppose the question was ...
1
vote
1answer
53 views

Graph where every vertex has degree 3, perfect matching?

Suppose $G$ is a graph where every vertex has degree $3$. There is no single edge which separates the graph. My question is, must $G$ necessarily have a perfect matching? I tried drawing some graphs ...
13
votes
1answer
134 views

“Binomiable” numbers

Is there a nice criterion to determine whether a given natural $m$ can be written as a binomial number $\binom{n}{k}$ with $1 < k < n-1$? I've been thinking on this problem with a friend and ...
0
votes
0answers
70 views

Reference request for well known theorem in combinatorics

From where, I can find the proof of the following theorem. I have to to cite it, in my research article. Theorem: The combination $ {n} C {r}$ is the number of possibilities for ...
2
votes
1answer
34 views

Algorithm for generating restricted integer composition of N in k parts from interval [a,b] given the lexicographic number.

Consider the restricted compositions of $6$ in four parts from integers $\{1, 2, 3\}$. ...